Question

Run the DFS-based topological ordering algorithm on the following graph. Whenever you have a choice of vertices to explore, always pick the one that is alphabetically first.

(a) Indicate the pre and post numbers of the nodes.

(b) What are the sources and sinks of the graph?

(c) What topological ordering is found by the algorithm?

(d) How many topological orderings does this graph have?

Short answer

(a). The pre and post numbers of the nodes is:$\mathrm{A}(1,14),\mathrm{B}(15,16),\mathrm{C}(2,13),\mathrm{D}(3,10),\mathrm{E}(5,6),\mathrm{F}(4,9),\mathrm{G}(5,6),\mathrm{H}(7,8)$

(b) Sources of the graph:$\mathrm{A}\hspace{0.33em}\mathrm{and}\hspace{0.33em}\mathrm{B}$

Sink of the graph:$\mathrm{G}\hspace{0.33em}\mathrm{and}\hspace{0.33em}\mathrm{H}$

(c) The topological ordering is$\left\{\mathrm{B},\mathrm{A},\mathrm{C},\mathrm{E},\mathrm{D},\mathrm{F},\mathrm{H},\mathrm{G}\right\}$

(d) The number of topological orderings of the graph is 8.

Step-by-step solution

 Explain Depth First Search based topological ordering algorithm.

Depth First Search (DFS) is an application of graph traversal. It traverses downwards and uses the stack as a data structure, through this it traverses all vertices in downward direction one by one. And the topological orderings is basically a linear ordering of graph if and are the vertices of graph there u must be comes before. And the graph must be directed acyclic graph.

The edge obtained by traversing while using depth first search is called its tree edge. The edge$(\mathrm{u},\mathrm{v})$ where u is descendant and it is not part of depth first search is called forward edge. The edge$(\mathrm{u},\mathrm{v})$where u is ancestor and it is not part of depth first search is called forward edge.

Find pre and post number.

(a)

The pre and post numbers of each vertex A while traversing is $A\left(1,14\right)$where 1 is pre vertex and 14 is post vertex. All the pre order number is obtained before obtaining post order number. The pre and post number of each vertex of the graph is ,$\mathrm{A}(1,14),\mathrm{B}(15,16),\mathrm{C}(2,13),\mathrm{D}(3,10),\mathrm{E}(5,6),\mathrm{F}(4,9),\mathrm{G}(5,6),\mathrm{H}(7,8)$

Hence, $\mathrm{A}(1,14),\mathrm{B}(15,16),\mathrm{C}(2,13),\mathrm{D}(3,10),\mathrm{E}(5,6),\mathrm{F}(4,9),\mathrm{G}(5,6),\mathrm{H}(7,8)$is the pre and post order of all vertices in the given graph.

Find the source and sink of the graph.

(b)

The source of the graph is a starting vertex and the source contain in degree of at least 1 .The sink of the graph is also called terminal. Sink is a vertex from which no other node or edge is attached or it is a ending point.Sink contains out-degree of 0.Sometimes if in a graph only one vertex is present so, it act as both source and sink.

The source vertices are$\mathrm{A}\hspace{0.33em}\mathrm{and}\hspace{0.33em}\mathrm{B}$and

The sinks are $\mathrm{G}\hspace{0.33em}\mathrm{and}\hspace{0.33em}\mathrm{H}$.

The final solution is:

Source =$\left\{\mathrm{A},\mathrm{B}\right\}$

Sink =$\left\{\mathrm{G},\mathrm{H}\right\}$

Find the topological order in the graph.

(c)

The topological ordering is found by the algorithm is the output in decreasing order of post number that is $\left\{\mathrm{B},\mathrm{A},\mathrm{C},\mathrm{E},\mathrm{D},\mathrm{F},\mathrm{H},\mathrm{G}\right\}$. Here while traversing the directed acyclic graph in order to get a topological order in a way that the output is the decreasing order of post number and preference is given to alphabetical order.

Select source vertex as B with in order degree zero. Then select A and then take C as the next node while traversing in depth first search. From C another option with in-degree zero are D and E . Consider E as the next vertex because it follows depth first search and decreasing order of post number. Then after E, select F as our next node again search for degree here now the degree of G and H is 1 . Select H and then select G.

Thus, the final sequence is$\left\{\mathrm{B},\mathrm{A},\mathrm{C},\mathrm{E},\mathrm{D},\mathrm{F},\mathrm{H},\mathrm{G}\right\}$ .

Find the number of topological ordering in the given graph

(d)

1) The topological ordering is basically a linear ordering of graph if u and v are the vertices of graph there u must be comes before v .

2) It must be (directed acyclic graph)

3) The given graph should be DAG (directed acyclic graph)

4) The graph must not contain any cycle.

5) Every DAG (directed acyclic graph) have at least (directed acyclic graph) onetopological ordering.

The given graph is:

In this graph topological orders are possible.

In first step check whether the graph has cycle or not. If not then proceed for topological ordering and find out the node with indegree zero and consider it as source vertex. Starting with the source there are two nodes with in degreethat are A and B .

Select A then B after that it seems that C has degree zero D and 1 has degree up to here the sequence of graph is ABC .Then eliminate C . Now the degree of D and E are zero. Select any one from them. Select D and after that select E . Now the degree of F is zero and the degree of G and H is 1. After selecting F eliminate F and again look for degree and the degree of both G and H is zero because no other edge is coming on these nodes let select G and after that select H .

Now the sequence is,$\mathrm{ABCDEFGH}$

Similarly, by selectingas A,B first edge again three case is possible through this they are as follows,

$$\begin{gathered} \mathrm{ABCDEFGH} \\ \mathrm{ABCEDFGH} \\ \mathrm{ABCEDFHG} \\ \mathrm{ABCDEFHG} \end{gathered}$$

Now the next possibility is when the source node asB and after that selectAas the next vertex now again find the degree of the each and every node in the graph after eliminating both vertex A and B then it is clear the new degree of b C is zero. So, select C Again D and E are the two options select each of them one by one for showing various possibility.

Then select in one case $\mathrm{EFGH}$.

The other four cases are as follows:

$$\begin{gathered} \mathrm{BACEDFHG} \\ \mathrm{BACDEFHG} \\ \mathrm{BACDEFGH} \\ \mathrm{BACEDFGH} \end{gathered}$$

So, 8 topological orders are possible in the graph.