2. Graphs (11 points) (1) (3 points) How many strongly connected components are

Question

2. Graphs (11 points) (1) (3 points) How many strongly connected components are in the three graphs below? List the vertices associated with each one. Reminder: for undirected graphs strongly connected and connected are equivalent state- ments. 36 1 so of do do (2) (4 points) For the graph G5: (a) (0.5 points) Specify the set of vertices V. (b) (0.5 points) Specify the set of edges E. (c) (1 point) Give the degree for each vertex. (d) (1 point) Give the adjacency matrix representation for this graph. (Assume vertices are sorted lexicographically.) (e) (1 point) Give the adjacency list representation for this graph. (3) (4 points) For the graph G6: (a) (0.5 points) Specify the set of vertices V. (b) (0.5 points) Specify the set of edges E. (c) (1 point) Give the in-degree and the out-degree for each vertex. (d) (1 point) Give the adjacency matrix representation for this graph. (Assume vertices are sorted lexicographically.) (e) (1 point) Give the adjacency list representation for this graph. Pf G6

Explanation / Answer

(1)
Strongly connected component for G1
{a,e,c} and {d,b,f}

Strongly connected component for G2
{a,b,c,d,e,f} whole graph

Strongly connected component for G3
{a},{b},{c},{d},{e}and {f} all nodes are connected components.

Strongly connected component for G4
{a},{b,d,e} and {c,f} are connected components.

(2) FOR G5
(a) V = {a,b,c,d,e,f}
(b) E = { ( a,b), (a,d), (b,d), (b,e), (d,e), (e,f), (b,f), (c,f) }
(c) Degree
Node degree
a 2
b 4
c 1
d 3
e 3
f 3
(d)

(e) adjacency list

(3)

(a) V = {a,b,c,d,e,f}
(b) E = { (a,d), (b,a) ,(b,e) ,(b,c) ,(c,c) ,(d,a), (d,e), (e,f),(f,e) }

(c)

(d)

a b c d e f a 0 1 0 1 0 0 b 1 0 0 1 1 1 c 0 0 0 0 0 1 d 1 1 0 0 1 0 e 0 1 0 d 0 0 f 0 1 1 0 0 0

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

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