Courses
  • IITGN
  • Online
  • Short Courses
  • Other

CS614. Advanced Algorithms. L02 Quiz.

CS614. Advanced Algorithms.

L02 Quiz

Back to the course page

Problem 1. Identify the Circuits

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?

Problem 2. Matchings

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.

Problem 3. Independent Sets

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.

Made with Quarto and 🩶

 

Content by Neeldhara Misra