TU Wien:Diskrete Mathematik für Informatik VU (Rubey)/Beispiel17

Let $G = (V, E)$ be an undirected graph. Set $M_{k} (G) = (E, S)$ where $S = {F \cup M | F \subseteq E, (V, F) a c y c l i c, M \subseteq E, | M | ⩽ k}$ .

Show that $M_{k} (G)$ is the set of independent sets of a matroid! In particular, the set of spanning forests of an undirected graph $G = (V, E)$ is the set of independent sets of a matroid.

I think the OP means to say that $M_{k} (G) = (E, S)$ is a matroid on the ground set $E$ with $S$ being the family of independent sets. I assume here that $G$ is a finite graph (so $V$ and $E$ are finite sets). I don't know how to deal with infinite matroids. The second part of the task is simply showing that $M_{0} (G)$ is a matroid, which is implied by the first part.

From here, there are three checkpoints. For the first one, it is easy to see that $\emptyset \in S$ , since $F = \emptyset$ and $M = \emptyset$ gives $\emptyset = F \cup M \in S$ .

For the hereditary property, let $F \cup M \in S$ and $T \subseteq F \cup M$ . Write $T_{F} = T \cap F$ and $T_{M} = T \cap M$ . Then, the edge induced subgraph $G [T_{F}]$ of $G$ is a forest, and $| T_{M} | \leq | M | \leq k$ . So, $T = T_{F} \cup T_{M}$ is in $S$ .

For the augmentation property, let $F_{1} \cup M_{1}, F_{2} \cup M_{2} \in S$ be such that $| F_{1} \cup M_{1} | < | F_{2} \cup M_{2} |$ . WLOG, assume that $M_{1} \cap F_{1} = \emptyset$ and $M_{2} \cap F_{2} = \emptyset$ . In the case $| M_{2} | > | M_{1} |$ , things are pretty easy. Pick an element $m \in (F_{2} \cup M_{2}) ∖ (F_{1} \cup M_{1})$ . We have $| M_{1} \cup {m} | = | M_{1} | + 1 \leq | M_{2} | \leq k .$ So, $(F_{1} \cup M_{1}) \cup {m} = F_{1} \cup (M_{1} \cup {m})$ is in $S$ . If $| M_{2} | \leq | M_{1} |$ , then we must have $| F_{2} | - | F_{1} | \geq (| F_{2} | - | F_{1} |) + (| M_{2} | - | M_{1} |) = (| F_{2} | + | M_{2} |) - (| F_{1} | + | M_{1} |) .$ Because $F_{1} \cap M_{1} = F_{2} \cap M_{2} = \emptyset$ , $| F_{2} | - | F_{1} | \geq | F_{2} \cup M_{2} | - | F_{1} \cup M_{1} | > 0.$ Therefore, the forest $F_{1}$ has more connected components than $F_{2}$ (recalling that the number of connected components in a forest on $n$ vertices and $m$ edges is $n - m$ ). Therefore, there exists a connected component $C$ of $F_{2}$ with vertices from at least two connected components of $F_{1}$ . Therefore, there is an edge $e$ of $C$ that connects two distinct connected components of $F_{1}$ . Note that $F_{1} \cup {e}$ is still a forest. So, $(F_{1} \cup M_{1}) \cup {e} = (F_{1} \cup {e}) \cup M_{1} \in S$ .

Quelle: https://math.stackexchange.com/questions/2995272/show-that-m-kg-is-the-set-of-independent-sets-of-a-matroid

TU Wien:Diskrete Mathematik für Informatik VU (Rubey)/Beispiel17

Navigationsmenü

Suche