A problem on Graphs
Printed From: One Stop GATE
Category: GATE AT A GLANCE
Forum Name: Other Discussions on GATE
Forum Discription: If you want to discuss some aspects of GATE which are not covered by any of the threads above, you are free to use this forum for those discussions.
URL: http://forum.onestopgate.com/forum_posts.asp?TID=205
Printed Date: 23Feb2025 at 7:17pm
Topic: A problem on Graphs
Posted By: Ajay01
Subject: A problem on Graphs
Date 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.
|
Replies:
Posted By: Adhiti
Date 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.
|
|