12 Aug, 2021

Courses βΈ± Algorithms

You can also access the quiz on Itempool here if you want to practice, or see the notes below for more context.

Lecture Recording

In-class Quiz Questions

πŸ“

We continue exploring examples and non-examples of matroids.

  1. Let be a undirected and connected graph. Let be the ground set. A subset is independent if the complementary subgraph of is connected. Consider the example shown in the figure below. Do the highlighted edges form an independent set?
    1. Yes
    2. No
    3. image
      Reveal answer
      βœ…

      Yes

      There are no cycles among the highlighted edges.

  2. Let be a undirected and connected graph. Let be the ground set. A subset is independent if the complementary subgraph of is connected. Consider the example where the graph G is a star, as shown below. What is the family of independent sets?
    1. Empty set.
    2. All singleton edges; i.e, the size of the family is 7 for the example above.
    3. All subsets of edges belong to the family; i.e, the size of the family is 128 for the example above
    4. None of the above
    5. image
      Reveal answer
      βœ…

      Empty set.

      There is no edge whose removal keeps connected.

  3. Suppose is subset of edges such that is connected. Further, let be a subset of What can you say about ? (Hint: think about in terms of . Is it a subgraph? A supergraph?)
    1. Also connected.
    2. May or may not be connected.
    3. Will not be connected.
    4. None of the above.
    5. Reveal answer
      βœ…

      Also connected

      is a supergraph of which was already connected.

  4. Suppose is a subset of edges such that is connected. Suppose is a subset of edges such that is connected. Further, suppose . What can we say about the number of edges in ? Pick the strongest claim you can make. Hint: since is connected, it must have at least how many edges? Now put two and two together given that .
    1. at least
    2. at least
    3. at least
    4. Reveal answer
      βœ…

      at least

      A connected graph with exactly one cycle will have at least edges.

  5. Let be an undirected and connected graph. Let be the ground set. A subset is independent if the complementary subgraph of is connected. Does this collection of independent sets form a matroid? Hint: for the exchange axiom, consider that a graph with at least n edges has a cycle.
    1. Yes
    2. No, it violates the first axiom (empty set membership)
    3. No, it violates the second axiom (heredity)
    4. No, it violates the third axiom (exchange axiom)
    5. Reveal answer
      βœ…

      Yes

  6. Let be an arbitrary undirected graph. Let be the ground set, and let be the family of all subsets of that form a matching. Does this family form a matroid? (Hint: Consider a path on four vertices and three edges. Can you find two matchings here that may give you some insights on one of the axioms?)
    1. Yes
    2. No, it violates the first axiom (empty set membership)
    3. No, it violates the second axiom (heredity)
    4. No, it violates the third axiom (exchange axiom)
    5. Reveal answer
      βœ…

      No, it violates the third axiom (exchange axiom)

      Follow the hint.