3. Using the graphs in Figure 1, answer the following questions (a) Is the graph

Question

3. Using the graphs in Figure 1, answer the following questions (a) Is the graph in Figure 1c a directed acyclic graph (DAG)? Why or why not? Be very precise. [6 points Is the digraph in Figure 1c strongly connected? Why or why not? (6 points it becomes disconnected. Give all such edges. [6 points] (b) A digraph is strongly connected when there is a path between every pair of vertices. (c) What are the fewest edges that must be removed from the graph in Figure 1a so that (a) An Undirected Graph (b) A Weighted Grapt (d) Give the indegree and outdegree of each vertex in Figure 1c. [6 points (e) Suppose vertices A, B, C, D and E in Figure 1d represent cities and the weights on the edges represent distances in miles. Give the shortest distance from city B to E. Give the complete route sequence of cities along the path beginning from city B and ending at city E. [6 points] 7 (c) A Digraph (d) A Weighted Digraph Figure 1: Ilustration of various Graphs

Explanation / Answer

Answer:

3. a) A Directed Acyclic Graph (DAG) is a Directed Graph that Contains no Cycles.

But in the Figure 1.(c) there is a cycle from B-->C-->D-->E-->B

So, the given graph is not a Directed Acyclic Graph.

b) Figure 1.(c) is strongly connected. Because, there is a path between every pair of vertices.

A-->B (path: A-->E-->B), A-->C (path:A-->E-->B-->C), A-->D (path:A-->E-->B-->D), A-->E (path: A-->E)

B-->A (path: B-->A), B-->C (path: B-->C), B-->D (path: B-->D), B-->E (path:B-->A-->E)

C-->A (path: C-->D-->E-->B-->A), C-->B (path: C-->D-->E-->B), C-->D (path: C-->D), C-->E (path: C-->D-->E)

D-->A (path: D-->E-->B-->A), D-->B (path: D-->E-->B), D-->C (path: D-->E-->B-->C), D-->E (path: D-->E)

E-->A (path: E-->B-->A), E-->B (path: E-->B), E-->C (path: E-->B-->C), E-->D (path: E-->B-->D)

c) If we remove the edge BE, the graph will become disconnected.

d) Indegree: The number of head ends adjacent to a vertex.

Outdegree: The number of tail ends adjacent to a vertex.

In figure 1.(c)  

Indegree(A)=1, Indegree(B)=1, Indegree(C)=1, Indegree(D)=2, Indegree(E)=2

Outdegree(A)=1, Outdegree(B)=3, Outdegree(C)=1, Outdegree(D)=1, Outdegree(E)=1

e) We have three different paths from B to E

path 1: B-->C-->D-->E (5+5+7=17)

path 2: B-->D-->E (8+7=15)

path 3: B-->A-->E (6+4=10)

Out of which the best path is the minimum cost path. that is B-->A-->E, cost is 10

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.