Let G be a directed acyclic graph with n vertices and eedges, such that the undi
ID: 3610162 • Letter: L
Question
Let G be a directed acyclic graph with n vertices and eedges, such that the undirected version of
G is connected. The out-degree (resp., in-degree) of a vertex isthe number of directed edges leaving (resp., entering) that vertex;in other words the out-degree of v is the length of the adjacencylist of v,
and the in-degree of v is the number of times v appears in theadjacency lists of other vertices.
Because it is acyclic, G must obviously have vertices of in-degreezero: Let V+ be the set of s
such vertices of in-degree zero. Similarly, G must have vertices ofout-degree zero: Let V be
the set of vertices of out-degree zero, and assume that s < t.Suppose that, when the vertices of V+ and Vare given in a particular order, V+ = v1, . .. , vs and V = w1, . . .,wt, G is such that the following propertyholds: For all 1 i s, a depth-first searchstarted at vi visits wi.
Design a linear time algorithm that makes G strongly connected byadding to it as few edges as possible. Prove that your algorithm iscorrect by arguing that it is not possible to make G stronglyconnected by adding fewer edges to it.
Let G be a directed acyclic graph with n vertices and eedges, such that the undirected version of
G is connected. The out-degree (resp., in-degree) of a vertex isthe number of directed edges leaving (resp., entering) that vertex;in other words the out-degree of v is the length of the adjacencylist of v,
and the in-degree of v is the number of times v appears in theadjacency lists of other vertices.
Because it is acyclic, G must obviously have vertices of in-degreezero: Let V+ be the set of s
such vertices of in-degree zero. Similarly, G must have vertices ofout-degree zero: Let V be
the set of vertices of out-degree zero, and assume that s < t.Suppose that, when the vertices of V+ and Vare given in a particular order, V+ = v1, . .. , vs and V = w1, . . .,wt, G is such that the following propertyholds: For all 1 i s, a depth-first searchstarted at vi visits wi.
Design a linear time algorithm that makes G strongly connected byadding to it as few edges as possible. Prove that your algorithm iscorrect by arguing that it is not possible to make G stronglyconnected by adding fewer edges to it. and Vare given in a particular order, V+ = v1, . .. , vs and V = w1, . . .,wt, G is such that the following propertyholds: For all 1 i s, a depth-first searchstarted at vi visits wi.
Design a linear time algorithm that makes G strongly connected byadding to it as few edges as possible. Prove that your algorithm iscorrect by arguing that it is not possible to make G stronglyconnected by adding fewer edges to it.
Explanation / Answer
Linear Time Sorting: The ?(nlogn) Lower boundimplies that if we hope to sort numbers faster than in O (nlogn)time, we cannot do it by making comparisons alone. In some specialcases, it is possible to sort without the use of comparisons. Thisleads to the possibility of sorting in linear(that is,O(n)) time.Here Three such algorithms.
An undirected graph (or graph ) G =(V,E )consists of a ?niteset V of vertices, and a set E of unorderedpairs of distinct vertices, called the edges.(Note that self-loopsare not allowed). Vertex v is adjacent to vertex u if there is anedge (u,v). In undirected graphs u and v are the end points of theedge. The edge e is incident (meaning that it touches) both u andv. In a digraph, the number of edges coming out of a vertex iscalled the out-degree Of that vertex, and the number of edgescoming in is called the in-degree. In an undirected graph we justtalk about the degree of a vertex a the number of incident edges.By the degree of a graph, we usually mean the maximum degree of itsvertices.
In a digraph: Number of edges:
0 E n2.
Sum of degrees:
v V in-deg(v)=vVout-deg(v)=E.
Let G =( V,E ) be a digraph with n = |V | and let e = | E | .Wewill assume that the vertices of G are indexed{1,2,...,n}, an arrayAdj [1 ...n] of pointers where for 1 v n, Adj [ v ]points to a linkedlist containing the vertices which are adjacentto v (i.e. the vertices that can be reached from V by a singleedge). If the edges have weights then these weights may also bestored in the linkedlist elements. We can represent undirectedgraphs using exactly the same representation, but we will storeeach edge twice. In particular, were presenting the undirected edge{v,w}by the two oppositely directed edges(v,w) and (w,v).
Depth first search for un directed graphs: Weuse four auxiliary arrays. As before we maintain a color for eachvertex:
white means undiscovered, gray means discovered but not ?nishedprocessing, and black means ?nished.
As before we also store predecessor pointers, pointing back tothe vertex that discovered a given vertex. We will also associatetwo numbers with each vertex. These are timestamps. When we ?rstdiscover a vertex u store a counter in d[u] and when we are ?nishedprocessing a vertex we store a counter in f [u].
DFS(G)
{ //main program for each u in V
{ //initialization
color[u] =white;
pred[u]=null;
}
time=0;
for each u in V
if(color[u]==white) //found an undiscovered vertex
DFSVisit(u); //start a new search here
}
DFSVisit(u)
{ //start a search at u
color[u]=gray; //mark u visited
d[u]=++time;
for each v inAdj(u) do
if(color[v]==white)
{ //if neighborv undiscovered
pred[v]=u; //...set predecessorpointer
DFSVisit(v); //...visitv
}
color[u]=black; //we’redonewith u
f[u]=++time;
}
The running time of DFS is ( V + E):
Treestructure: DFS naturally imposes a tree structure(actually a collection of trees, or a forest) on the structure ofthe graph. This is just the recursion tree, where the edge
( u,v ) arises when processing vertex u we call DFSVisit(v) forsome neighbor v.
For directed graphs the other edges of the graph can beclassi?ed as follows:
Backedges: ( u,v )where v is a(not necessarily proper) ancestorof u In the tree. (Thus, a self-loop is considered to be a backedge).
Forwardedges: (u,v) where v is a proper descendent of u in thetree.
Crossedges: (u,v)where u and v are no tancestors or descendentsof one another
With undirected graphs, there are some important differences inthe structure of the DFS tree. First,there is really no distinct ion between forward and backedges.
Given a digraph
G = (V,E) ,and any DFS tree for G and any two vertices u,v V .
• u is a descendent of v if and only if [ d [ u ] ,f[ u ]] [ d [ v ] , f [ v ]] .
• u is an ancestor of v if and only if [ d [ u ] ,f[ u ]] [ d [ v ] , f [ v ]] .
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.