Graph Traversals and Topological Sorting

Graph Traversal

BFS = A B D E C
DFS = A B C D E

Topological Sorting

Theorem 17: A graph can be topologically sorted iff it is acyclic. There are two cycles in $E$ : BCD and BDE. Therefore, to get a graph that can be sorted topologically, we need to remove $(C, D)$ and $(E, D)$ .

E^{'} = E ∖ {(C, D), (E, D)}

topological sorting = A D B C E

Explanation: ord of nodes:

A -> 0 incoming edges
B -> 2, from A & D
C -> 2, from A & B
D -> 0
E -> 2, from C & E

n | number of edges
--------------------------
1 | 0
2 | 1
3 | 2+1 = 3
4 | 3+2+1 = 6

Conjuncture: The maximum number of edges in a directed graph with $n$ vertices that can be topologically sorted is:

\sum_{i = 1}^{n - 1} i = \frac{n (n - 1)}{2}

The bound is an upper bound: since there are no more edges one could add without creating a cycle. From node with $ord 1$ there are $n - 1$ possible edges to to nodes without creating a cycle. From node with $ord 2$ there are $n - 2$ possible edges to nodes without creating a cycle (all except node $1$ ), ...
The bound is tight: because such a graph can be constructed by adding all edges $v_{i} \to v_{j}$ with $ord i < ord j$ .