Question

Make sure to answer part a and b. Consider the graph below. a. (5 points) Create an adjacency matrix. b. (5 points) Can this graph be topologically sorted? If so, what are the vertice topological order if you use the decrease-by-one (source) method to topologica sort and resolve ties in ascending order alphabetically? (В E С F D A

Answer 1

• Below is the detailed solution of the above problem.

1. Adjacency matrix is shown below (a matrix of size 6*6):

2.For topological sort : Yes this graph can be topologically sorted as a Directed Acyclic graph can be topologically sorted. Clearly we can see that the graph has no cycle and it is directed also.

Topological sorted order:  A F B C D E\

Indegree of a node is number of incoming edges to it.

Using the decrease by one method to topological sort we can get the above order, below is the algorithm for that.

1. Calculate the in-degree of all the nodes in the graph and initialize a count variable to 0 i.e, it represents number of visited nodes.

2. Now take all the nodes with indegree as 0 and put it in a queue.

3. Now remove a vertex from the queue( and add it to our answer vector which will contain the topological sort of graph) and then increase the count variable by 1 as we visit this node and decrease indegree of all the node's neighboring nodes by 1, if some node's indegree become 0 then add it into queue.

4. Repeat all the above step(3) until queue becomes empty.

5. Now if our count variable is not euqal to total nodes in the graph that means some node is unvisited so topological sort is not possible otherwise we have our topological sort in our vector.

indegree={A:0, B:1, C:2, D:1, E:4, F:1}

So first A has indegree 0 so it is added into queue, then A is popped out and added to our answer then decreasing indegree of neighbors of A by 1 we get indegree={A:0, B:1, C:1, D:1, E:3, F:0},

so indegree of F becomes 0 so it is added to queue.

Now again an element is popped from queue i.e, F and added to our answer then updated indegree becomes, indegree={A:0, B:0, C:0, D:1, E:3, F:0}

So indegree of B and C becomes 0 so it is added to queue then now again we pop an element from queue i.e, B(and added to our answer) and update our indegree so it becomes, indegree={A:0, B:0, C:0, D:1, E:2, F:0}

Now pop C(and added to our answer) from the queue, and update the indegree {A:0, B:0, C:0, D:0, E:1, F:0}, so indegree of D becomes 0 so add it in queue,

Now pop D(and added to our answer) from queue and update our indegree as {A:0, B:0, C:0, D:0, E:0, F:0}, so indegree of E becomes 0 so add it in queue.

At last pop E(and added to our answer) from queue and now the queue will be empty.

Now we have our answer vector as {A F B C D E}.

Answer 2

• Below is the detailed solution of the above problem.

1. Adjacency matrix is shown below (a matrix of size 6*6):

. B. Ot F D А 0 Adjacency list: А А A B O MUA BICIDEE 0 |||0||1 O Io 1 10 O ♡ololololo OOOO E o lolo 1 lo lolo M[i][j 2 l if there is an adge from i› Otherwise

2.For topological sort : Yes this graph can be topologically sorted as a Directed Acyclic graph can be topologically sorted. Clearly we can see that the graph has no cycle and it is directed also.

Topological sorted order:  A F B C D E\

Indegree of a node is number of incoming edges to it.

Using the decrease by one method to topological sort we can get the above order, below is the algorithm for that.

1. Calculate the in-degree of all the nodes in the graph and initialize a count variable to 0 i.e, it represents number of visited nodes.
2. Now take all the nodes with indegree as 0 and put it in a queue.
3. Now remove a vertex from the queue( and add it to our answer vector which will contain the topological sort of graph) and then increase the count variable by 1 as we visit this node and decrease indegree of all the node's neighboring nodes by 1, if some node's indegree become 0 then add it into queue.
4. Repeat all the above step(3) until queue becomes empty.
5. Now if our count variable is not euqal to total nodes in the graph that means some node is unvisited so topological sort is not possible otherwise we have our topological sort in our vector.

indegree={A:0, B:1, C:2, D:1, E:4, F:1}

So first A has indegree 0 so it is added into queue, then A is popped out and added to our answer then decreasing indegree of neighbors of A by 1 we get indegree={A:0, B:1, C:1, D:1, E:3, F:0},

so indegree of F becomes 0 so it is added to queue.

Now again an element is popped from queue i.e, F and added to our answer then updated indegree becomes, indegree={A:0, B:0, C:0, D:1, E:3, F:0}

So indegree of B and C becomes 0 so it is added to queue then now again we pop an element from queue i.e, B(and added to our answer) and update our indegree so it becomes, indegree={A:0, B:0, C:0, D:1, E:2, F:0}

Now pop C(and added to our answer) from the queue, and update the indegree {A:0, B:0, C:0, D:0, E:1, F:0}, so indegree of D becomes 0 so add it in queue,

Now pop D(and added to our answer) from queue and update our indegree as {A:0, B:0, C:0, D:0, E:0, F:0}, so indegree of E becomes 0 so add it in queue.

At last pop E(and added to our answer) from queue and now the queue will be empty.

Now we have our answer vector as {A F B C D E}.

So if you have any doubt regarding this solution then please feel free to ask in the comment section below and if it is helpful then please upvote this solution, THANK YOU.