9780023606922, Chapter 2, Problem 22E

Prévia do material em texto

Chapter 2, Problem 22E Step-by-step solution Step 1 of 4 A directed graph is a graph in which all the nodes are connected with edges having fixed directions. As compared to directed graph, undirected graph is a graph with no directed edges. A graph contains a cycle which is called as Euler cycle, if we are traversing the complete graph when our starting and ending node is same, each edge will be traversed only once. Suppose we have an undirected graph which we got by removing edges of G (where G is a directed graph containing directed Euler cycle). If we connect all the edges by the rule indegree of is equal to outdegree of we are going we will get our original graph. To prove that, we will consider a case which will be inverse of our condition, that is, indegree of is not equal to outdegree of (for every vertex V in G). Step 2 of 4 Case I: Now let us consider a node n having 2 incoming edges and 1 outgoing edge. That means 2 nodes are connected to n. And because it has 2 incoming nodes n will be traversed 2 times. Step 3 of 4 Case II: Another possibility will be a node m having 1 incoming edge and 2 outgoing edges. In this case we know at least 3 nodes are connected to node m. Now to traverse 2 nodes connected to m with outgoing edges m will be traversed twice which will only be possible if the incoming edge is traversed twice. Step 4 of 4 So, to get our original directed graph having Euler cycle the condition will be indegree of should be equal to outdegree of