Heiratssatz , stochastische Op < stoch. Prozesse < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Heiratssatz (1.Fassung): Ein Matching, das alle Knoten aus S trifft, existiert immer dann, wenn die Nachbarmenge für jede beliebige Knotenmenge aus S mindestens so viele Elemente enthält wie die Menge selbst.
oder
Heiratssatz (2.Fassung): Sei ein bipartiter Graph G = ( V1+V2,E) gegeben.
Dann ist m(G) = |V1| genau dann, wenn
|A| ≤ |N(A)| für alle A ⊂V1. |
Zum Heiratssatz habe ich die Frage: Sind A und N(A) gematcht oder nicht?
Ich versuche, den Satz zu beweisen, aber scheitere daran.
Mein Beweisversuch:
Die hinreichende Bedingung lautet: Wenn für jede Teilmenge A ⊂ S gilt: ∣A∣ ≤ ∣N(A)∣, dann existiert ein Matching, das alle Knoten in S trifft.
Wir wollen den Beweis als indirekten Beweis führen:
Aus: Aus A folgt B machen wir : aus „nicht B“ folgt „nicht A“.
Dies ergibt für unsere hinreichende Bedingung:
Existiert kein Matching, das alle Knoten aus S trifft, z.B. nicht S1 trifft, dann ist |A| kleiner gleich |NA| nicht erfüllt.
Lösungsweg:
Wie groß ist die Nachbarschaftsmenge von S1? Wir schauen uns den Graphen an und sehen, dass S1 einen Nachbarn hat, aber dieser ist nicht mit S1 gematcht. Das heißt seine gematchte Nachbarschaftsmenge ist die leere Menge.
Dies wiederspricht der Bedingung /A/ < = /NA/, damit ist auch diese Richtung des Beweises bewiesen.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:22 Mo 02.06.2025 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
