Zeigen minimal spannenden Baum

Question

Sei \( G=(V, E) \) ein ungerichteter, zusammenhängender Graph mit paarweise unterschiedlichen Kantengewichten.

Wir nennen eine Kante \( (u, v) \in \) E lokal minimal wenn alle anderen zu \( u \) inzidenten Kanten größeres Gewicht haben oder wenn alle anderen zu \( v \) inzidenten Kanten größeres Gewicht haben.
Zeigen Sie:
(a) Jede lokal minimale Kante gehört zum minimal spannenden Baum von \( G \).
(b) Die Menge aller lokal minimaler Kanten eines Graphen ist kreisfrei.

Comments

Nimm den minimal spannenden Baum H. Wenn e:={u,v} nicht enthalten ist, wähle eine Nachbarkante in H mit größerem Gewicht. Ersetze Sie durch e.

Bleiben 2 Fragen: Wieso gibt es in H eine passende Kante? Wiese ist der Ersatzbaum ein Spannbaum?

---

Ist mir leider nicht klar geworden . Kannst du bitte die Aufgabe mal beantworten

Answer 1

Sei \(H=(V,F)\) der minimale Spannbaum, \(e=\{u,v\}\) eine lokal minimale Kante. Annahme: Sie gehört nicht zu F.

In H existiert ein Weg \((u,x_1,x_2, \ldots,x_n,v)\). Weil e minimal ist, hat \(\{u,x_1\}\) ein größeres Gewicht (2. Fall: \(\{x_n,v\}\) hat größeres Geweicht ....). Wir bilden F', indem wir aus F \(\{u,x_1\}\) entfernen und durch e ersetzen. Dann ist \(H':=(V,F')\) ein Spannbaum (s.u.) mit kleinerem Gewicht als H, also ein Widerspruch.

Noch zu zeigen: H' ist zusammenhängend: Seien a,b zwei Knoten, dann existiert in H ein Weg von a nach b. Falls dieser Weg die Kante \(\{u,x_1\}\) enthält, also

$$(a,y_1,y_2, \ldots, y_k,u,x_1,y_{k+1}, \ldots,b)$$

dann wäre

$$(a,y_1,y_2, \ldots, y_k,u,v,x_n, \ldots, x_1,y_{k+1}, \ldots,b)$$

ein Weg in H' von a nach b.

Zu zeigen: H' enthält keinen Kreis: Jetzt Du