Neeldhara
  • About
  • Research
    • Overview
    • People
    • Publications
    • Surveys
  • Teaching
    • Courses
    • Materials
  • Lists
    • Puzzles
    • Bookmarks
  • Exposition
    • Talks
    • Videos
  • Events
  • Blog

CS614. Advanced Algorithms. L02 Quiz.

CS614. Advanced Algorithms.

L02 Quiz

Back to the course page

Problem 1. Identify the Circuits

Let GGG be a simple, undirected, and connected graph. Consider the graphic matroid discussed in class, i.e, where:

  • the universe UUU is the set of edges of GGG, i.e, E(G)E(G)E(G);
  • the family F\mathcal{F}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 GGG be a simple, undirected, and connected graph. Consider the following set system:

  • the universe UUU is the set of edges of GGG, i.e, E(G)E(G)E(G);
  • the family F\mathcal{F}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 GGG be a simple, undirected, and connected graph. Consider the following set system:

  • the universe UUU is the set of vertices of GGG, i.e, V(G)V(G)V(G);
  • the family F\mathcal{F}F of independent sets is the collection of all subsets SSS of that are independent in GGG, i.e, the subgraph G[S]G[S]G[S] has no edges.

Is this a matroid? Why or why not? Justify your answer.


© 2022 • Neeldhara Misra • Credits •

 

Corrections? Please leave a comment here or a PR in this repository, thanks!

I’d rather be a failure at something I love than a success at something I hate.

George Burns

You live and you learn — at any rate, you live.

Douglas Adams

A problem worthy of attack proves its worth by fighting back.

Paul Erdos

×