CS614. Advanced Algorithms. L03 Quiz.

CS614. Advanced Algorithms.

L03 Quiz

Back to the course page

Problem 1. Partition Matroid

Show that the exchange axiom holds for the Partition Matroid defined in class.

Problem 2. Representing the Graphic Matroid

The graphic matroid of a graph G can be represented by the following matrix: we have one row for each vertex, and one column for each edge. The column for edge e has +1 in the row for one endpoint, -1 in the row for the other endpoint, and 0 elsewhere; the choice of which endpoint to give which sign is arbitrary.

Argue that this is a valid representation (i.e, that the forests correspond to linearly independent columns and the subsets of edges that have cycles in them correspond to dependent columns).