CS614. Advanced Algorithms. L02 Quiz.
CS614. Advanced Algorithms.
L02 Solutions
Let \(G\) be a simple, undirected, and connected graph. Consider the graphic matroid discussed in class, i.e, where:
- the universe \(U\) is the set of edges of \(G\), i.e, \(E(G)\);
- the family \(\mathcal{F}\) of independent sets is the collection of all subsets of edges that are acyclic.
A maximal independent set in a matroid is called a basis, and for this example, the maximal independent sets correspond to spanning trees.
A minimal dependent set in a matroid is called a circuit. In this example, what are the circuits?
The circuits of the graphic matroid are the cycles of the graph \(G\).
Let \(G\) be a simple, undirected, and connected graph. Consider the following set system:
- the universe \(U\) is the set of edges of \(G\), i.e, \(E(G)\);
- the family \(\mathcal{F}\) of independent sets is the collection of all subsets of edges that are matchings.
Is this a matroid? Why or why not? Justify your answer.
Not a matroid: consider the graph on the vertex set \(\{a,b,c,d\}\) with the edges \(\{ab, cd, ad\}\).
There are two matchings in this instance:
- \(M_1 := \{ab,cd\}\)
- \(M_2: \{ad\}\)
However, although \(|M_1| > |M_2|\), neither of the edges from \(M_1\) can be added to \(M_2\).
Let \(G\) be a simple, undirected, and connected graph. Consider the following set system:
- the universe \(U\) is the set of vertices of \(G\), i.e, \(V(G)\);
- the family \(\mathcal{F}\) of independent sets is the collection of all subsets \(S\) of that are independent in \(G\), i.e, the subgraph \(G[S]\) has no edges.
Is this a matroid? Why or why not? Justify your answer.
Not a matroid: consider the graph on the vertex set \(\{a,b,c\}\) with the edges \(\{ab, ac\}\). There are two independent sets: \(S_1 := \{b,c\}\) and \(M_2: \{a\}\), but neither of the vertices from \(S_1\) can be added to \(S_2\).
If the independent sets formed a matroid the problem of finding a maximum independent set would not be NP-complete. {{< bi emoji-smile-upside-down >}}
— Comment in class