Draw the adjacency list and adjacency matrix descriptions of the following graph. b N 7. (30pts)...

Transcribed Image Text:

Draw the adjacency list and adjacency matrix descriptions of the following graph. b N 7. (30pts) Let G = (V, E) be a directed graph. A set of cycles C₁,..., Ck of G are disjoint if they do not share any edges. A set of disjoint cycles C=C₁,...,Ck is maximal if there does not exist a cycle c in G which is disjoint from C₁,...,Ck. (a) (15pts) Give (the pseudo-code of) an algorithm that returns a maximal set of disjoint cycles in a given graph G. (b) (10pts) Prove that your algorithm is correct (always returns a maximal set of disjoint cycles). (c) (5pts) Prove that your algorithm runs in time O(|E|(V| + |E|)). Draw the adjacency list and adjacency matrix descriptions of the following graph. b N 7. (30pts) Let G = (V, E) be a directed graph. A set of cycles C₁,..., Ck of G are disjoint if they do not share any edges. A set of disjoint cycles C=C₁,...,Ck is maximal if there does not exist a cycle c in G which is disjoint from C₁,...,Ck. (a) (15pts) Give (the pseudo-code of) an algorithm that returns a maximal set of disjoint cycles in a given graph G. (b) (10pts) Prove that your algorithm is correct (always returns a maximal set of disjoint cycles). (c) (5pts) Prove that your algorithm runs in time O(|E|(V| + |E|)).