a. The incidence matrix for an undirected graph G D (V, E) is a |V| |E|

Question:

a. The incidence matrix for an undirected graph G D (V, E) is a |V| × |E| matrix M such that Mνe = 1 if edge e is incident on vertex ν, and Mνe = 0 otherwise. Argue that a set of columns of M is linearly independent over the field of integers modulo 2 if and only if the corresponding set of edges is acyclic.

Then, use the result of Exercise 16.4-2 to provide an alternate proof that (E, I) of part (a) is a matroid.

b. Suppose that we associate a nonnegative weight w(e) with each edge in an undirected graph G = (V, E). Give an efficient algorithm to find an acyclic subset of E of maximum total weight.

c. Let G(V,E) be an arbitrary directed graph, and let (E, I) be defined so that A ∈ I if and only if A does not contain any directed cycles. Give an example of a directed graph G such that the associated system (E, I) is not a matroid. Specify which defining condition for a matroid fails to hold.

d. The incidence matrix for a directed graph G = (V, E) with no self-loops is a |V| × |E| matrix M such that Mνe = −1 if edge e leaves vertex ν, Mνe = 1 if edge e enters vertex ν, and Mνe = 0 otherwise. Argue that if a set of columns of M is linearly independent, then the corresponding set of edges does not contain a directed cycle.

e. Exercise 16.4-2 tells us that the set of linearly independent sets of columns of any matrix M forms a matroid. Explain carefully why the results of parts (d) and (e) are not contradictory. How can there fail to be a perfect correspondence between the notion of a set of edges being acyclic and the notion of the associated set of columns of the incidence matrix being linearly independent?

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question

Introduction to Algorithms

ISBN: 978-0262033848

3rd edition

Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest

Question Posted: