top of page
Dhruv Badaya

How many topological orderings does the following graph have? Specify all of them.

Topological Ordering works on the concept of in-degree and out-degree.


In-degree means how many edges are coming into the vertex.

Out-degree means how many edges are going out of the vertex.


Also, note that only DIRECTED ACYCLIC GRAPHS (DAG) have topological orderings. Now, let us look at our graph.



We start by writing in-degree of all the vertices.

VERTEX

INDEGREE

a

0

b

1

c

1

d

1

e

2

We always add nodes with in-degree 0 to our graph. So, in our topological ordering, we place a first.

TOPOLOGICAL ORDERING: a


Next, we remove a completely from the graph.


Now, we will write the indegree of the remaining vertices.

VERTEX

INDEGREE

b

0

c

0

d

1

e

2

Now, we can add b as well as c to our graph. This results in two different topological orderings.

TOPOLOGICAL ORDERING 1: a→b

TOPOLOGICAL ORDERING 2: a→c


Now, we will consider two cases. In the first case, let us remove b.


Now, we get the following in degrees.

VERTEX

INDEGREE

c

0

d

1

e

1

So, topological ordering 1 is a→b→c→d→e


If we remove c, however, we get,

VERTEX

INDEGREE

b

0

d

0

e

2

Hence, we can say that topological ordering in case 2 can be one of the following:

  • a→c→b→d→e

  • a→c→d→b→e


Hence, three topological orderings are possible.

  • a→b→c→d→e

  • a→c→d→b→e

  • a→c→b→d→e

49 views0 comments

Comments


bottom of page