12 Aug, 2021

Courses ⸱ Algorithms

Lecture Recording

In-class Quiz Questions

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
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



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.
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
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)
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)
Reveal answer
✅
No, it violates the third axiom (exchange axiom)
Follow the hint.