Graphs

Graphs

1. A Digraph is a set of nodes (vertices) together with a set of ordered pairs of nodes (arcs / edges)

2. If (u, v) ∈ E, v is adjacent to u, v is an out-neighbor of u and u is an in-neighbor of v

3. WALKS, PATHS & CYCLES

   • A walk in a digraph is a sequence of nodes such that an edge exist between the nodes
   • A path is a walk in which no node is repeated
   • A cycle is a walk in which v0 = vn and no other nodes are repeated

4. DISTANCE & DIAMETER

   • Distance is the minimum length of a path from a node to another
   • The diameter of a digraph is the max distance between any two vertices

5. Underlying Graph

   • The underlying graph of a digraph is the graph G = (V, E) is the graph G' = (V, E') where E' = {{u, v} | (u, v) ∈ E}.

6. Sub-Digraphs

   • A Subdigraph is a digraph with some/all of the vertices and edges in the original graph
   • A spanning subdigraph contains all nodes from original graph

7. Traversal Arc Classifications

   • If an arc belongs to one of the trees of F it is called a TREE ARC
     • OTHERWISE:
       • A forward arc if u is an ancestor of v in F
       • A back arc if u is a descendant of v in F
       • A cross arc if neither u nor v is an ancestor of the other in F

8. Graph Connectivity

   • A graph is connected if there is a path between each pair of vertices
   • Strongly Connected Components
     • Parts of a graph where you can get from any node to any other node
     • A Digraph is strongly connected if it has only one strong component
     • To find them using an algorithm must pick the right root node
       • First run depth-first --> gives you a forest
         • Reverse the diagram (Turn the arrows the other way)
           • Run Depth-first search on reverse. Everytime you have a choice of a node, you choose the one who ran the latest on the first depthfirst search