Matching und Kreise < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:55 So 20.02.2011 | | Autor: | hilado |
| Aufgabe | | Die symmetrische Differenz [mm] M_{1} \Delta M_{2} [/mm] = [mm] (M_{1} [/mm] \ [mm] M_{2}) \cup (M_{2} [/mm] \ [mm] M_{1}) [/mm] zweier verschiedener perfekter Matchings eines Graphen enthält mindestens einen Kreis. |
Ich weiß leider nicht, wie man darauf kommt, dass man durch die symmetrische Differenz zweier verschiedener perfekter Matchings zu einem Kreis kommt. Kann man das irgendwie genauer erläutern ?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:26 So 20.02.2011 | | Autor: | felixf |
Moin!
> Die symmetrische Differenz [mm]M_{1} \Delta M_{2}[/mm] = [mm](M_{1}[/mm] \
> [mm]M_{2}) \cup (M_{2}[/mm] \ [mm]M_{1})[/mm] zweier verschiedener perfekter
> Matchings eines Graphen enthält mindestens einen Kreis.
>
> Ich weiß leider nicht, wie man darauf kommt, dass man
> durch die symmetrische Differenz zweier verschiedener
> perfekter Matchings zu einem Kreis kommt. Kann man das
> irgendwie genauer erläutern ?
Da die Matchings verschieden sind gibt es mind. eine Kante [mm] $K_0$ [/mm] in der symmetrischen Differenz. Sei [mm] $P_0$ [/mm] ein Eckpunkt dieser Kante. Angenommen, die Kante [mm] $K_0$ [/mm] liegt in [mm] $M_1$. [/mm] Sei [mm] $P_1$ [/mm] jetzt der zweite Punkt von [mm] $M_1$. [/mm] Nun gibt es genau eine Kante [mm] $K_1$ [/mm] in [mm] $M_2$, [/mm] welche mit [mm] $P_1$ [/mm] inzidiert, und [mm] $K_1$ [/mm] liegt nicht in [mm] $M_1$ [/mm] (warum?). Damit liegt [mm] $K_1$ [/mm] in [mm] $M_1 \Delta M_2$. [/mm] Sei nun [mm] $P_2$ [/mm] der zweite Punkt von [mm] $K_1$, [/mm] und es gibt genau eine Kante [mm] $K_2$ [/mm] in [mm] $M_1$, [/mm] die mit [mm] $P_2$ [/mm] inzidiert. Kann diese Kante in [mm] $M_2$ [/mm] liegen? Faellt dir was auf?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:26 So 20.02.2011 | | Autor: | hilado |
Danke. Das hab ich jetzt verstanden :)
|
|
|
| |
|
> Die symmetrische Differenz [mm]M_{1} \Delta M_{2}[/mm] = [mm](M_{1}[/mm] \
> [mm]M_{2}) \cup (M_{2}[/mm] \ [mm]M_{1})[/mm] zweier verschiedener perfekter
> Matchings eines Graphen enthält mindestens einen Kreis.
> Ich weiß leider nicht, wie man darauf kommt, dass man
> durch die symmetrische Differenz zweier verschiedener
> perfekter Matchings zu einem Kreis kommt. Kann man das
> irgendwie genauer erläutern ?
Guten Tag allerseits !
Graphentheorie hat mich früher einmal sehr beschäftigt -
als Gymnasiast meinte ich einmal, einen Beweis für den
Vierfarbensatz zu haben (damals das noch ungelöste
"Vierfarbenproblem") ...
Den Ausdruck "Matching" bzw. "perfektes Matching" habe
ich allerdings bisher nie gehört. Für alle denen es ebenso
ergeht, hier die entsprechenden Wiki-Links auf
![[]](/images/popup.gif) englisch: Matching oder deutsch: Paarung .
LG Al
|
|
|
|
