One Stop GATE Forum: A problem on Graphs

Message

   Was bit confused about in which thread to post this question.

Following is the problem from book 

Data Structures Using C  

-- Yedidyah Langsam, Moshe. J. Augenstein, Aaron M. Tenenbaum 

Prove that every DAQ(Directed acyclic graph) can be represented by

an adjacency matrix such that the matrix is triangular.

Write a routine in C that will take as input a adjacency matrix adj of an DAQ,

and return a lower triangular matrix representing the same DAQ.

Also return an array P[] such that P represents node to which ith node

is mapped. 

Any takers.
_________________
Keep things Simple Stupid.

Author	Message
Ajay01 Newbie Joined: 03Feb2007 Online Status: Offline Posts: 12	Topic: A problem on Graphs Posted: 03Feb2007 at 10:56am
	Was bit confused about in which thread to post this question. Following is the problem from book Data Structures Using C -- Yedidyah Langsam, Moshe. J. Augenstein, Aaron M. Tenenbaum Prove that every DAQ(Directed acyclic graph) can be represented by an adjacency matrix such that the matrix is triangular. Write a routine in C that will take as input a adjacency matrix adj of an DAQ, and return a lower triangular matrix representing the same DAQ. Also return an array P[] such that P represents node to which ith node is mapped. Any takers. _________________ Keep things Simple Stupid. Post Resume: Click here to Upload your Resume & Apply for Jobs

	IP Logged

Adhiti Newbie Joined: 02Feb2007 Online Status: Offline Posts: 32	Posted: 03Feb2007 at 12:08pm
	Lemma 1 : Every DAG has atleast one node with indegree zero. Proof : Assume that there is node with indegree zero. Now consider one node, since its indegree is not zero, it has some parent. Now lets move onto one of its parents. Again its parent's indegree is not zero, it also must have some parents. We can move to one of its parents. We can continue like this indefinitely. But we have finite number of nodes, so at some point of our traversal, some node will get repeated. This means there is a cycle. This contradicts with our data that the graph is a DAG. Hence, our assumption is wrong and there is atleast one node with indegree zero. Lemma 2 : Every DAG can be topologically sorted. Proof : From lemma 1, every DAG has atleast one node of indegree zero. Remove that node and all its outgoing links. The resultant graph is also a DAG. This means that the resultant graph will also have atleast one node of indegree zero. This way we can continue till all the nodes have been removed. Thus, it is true that DAG can be topologically sorted. Theorem : Adjacency Matrix of every DAG with topologically ordered vertices is an upper triangular matrix. Proof : From Lemma 2, every DAG can be topologically sorted, hence its vertices can be topologically ordered. Assume that the adjacency matrix is not an upper triangular matrix. Then there is some entry A_ij = 1 , where j < i. But A_ij = 1 with j<i, means that there is an edge from vj to vi given that the topological order is vi , vj. A contradiction! Hence proved.
	IP Logged


One Stop GATE Forum : GATE AT A GLANCE : Other Discussions on GATE