# Types of Graphs #### Undirected Graphs In an undirected graph the edges have no orientation. The edge (u, v) is identical to the edge (v, u).  #### Directed Graphs Directed graphs (sometimes called digraphs) the edges are directed. The edge (u, v) is the edge from node u to node v. ] #### Weighted Graphs Edges on graphs can contain weights to represent cost, distance, quantities, etc. We can think about this as representing a type of "distance" between points in a sense. Consider that nodes are indeed a type of "point", but we do not know the distance between our points unless we somehow specify that. We can do so via weights. We can denote the edge of this type of a graph via a triplet (u, v, w). ] #### Trees A **[tree](Trees.md)** is an undirected graph with no cycles. Equivalently, it is a connected graph with N nodes and N - 1 edges. ] #### Rooted Trees A rooted tree is a tree with a designated root node, where every edge either points away from or towards the root node. When edges point away from the root the graph is called an **arborescence (out-tree)** and an anti-arborescence (in-tree) otherwise. ] #### Directed Acyclic Graphs (DAGs) DAGs are directed graphs with no cycles. Note: All out-trees are DAGs, but not all DAGs are out-trees (a BOP is a DAG, but not an out tree. ) ] #### Bipartite Graph A bipartite graph is one whose vertices can be split into two independent groups, U and V, such that every edge connects between U and V. ] #### Complete Graph A complete graph is one where there is a unique edge between every pair of nodes.