perfektes Matching Polytop < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich möchte folgendes zeigen:
gegeben ist ein bipartiter Graph G=(V,E). Das perfekte Matching-Polytop ist gegeben als
[mm] P=conv\{x_M \in\IR^{|E|} : M \text{ist perfektes Matching von} G \}
[/mm]
dabei ist [mm] x_M [/mm] der Vektor, der an der i-ten Stelle eine 1 stehen hat, wenn [mm] e_i\in [/mm] E eine Kante des perfekten Matchings M ist und sonst nur Nullen ( [mm] x_M [/mm] hat also so viele Einser, wie das perfekte Matching groß ist )
Ich soll nun zeigen, dass dieses Polytop das selbe ist wie das folgende:
[mm] P=\{x\in\IR^{|E|}: x_e\geq0 \forall e\in E, \sum_{e \text{ mit } v\in e} x_e=1 \forall v\in V\}
[/mm]
dabei ist [mm] x_e [/mm] die e-te Komponente des Vektors x.
An Beispielen konnte ich das verifizieren. Und mein erster Gedanke war, dass das irgendwas mit der Eigenschaft zu tun haben muss, dass in einem bipartiten Graph die Kardinalität des maximalen Matchings genau so groß ist wie die Kardinatlität der minimalen Knotenüberdeckung. Immerhin ist im ersten Fall die Summe der Einträge von [mm] x_M [/mm] genau die Kardinalität des perfekten Matchings. Das hat aber irgendwie zu nichts geführt. Und auch der Versuch, die Ecken des zweiten Polytops zu berechnen, hat nicht geklappt... kann mir deswegen bitte irgendjemand helfen...
Danke 
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:27 Fr 15.06.2012 | | Autor: | Stoecki |
> Hallo,
>
> ich möchte folgendes zeigen:
>
> gegeben ist ein bipartiter Graph G=(V,E). Das perfekte
> Matching-Polytop ist gegeben als
> [mm]P=conv\{x_M \in\IR^{|E|} : M \text{ist perfektes Matching von} G \}[/mm]
>
> dabei ist [mm]x_M[/mm] der Vektor, der an der i-ten Stelle eine 1
> stehen hat, wenn [mm]e_i\in[/mm] E eine Kante des perfekten
> Matchings M ist und sonst nur Nullen ( [mm]x_M[/mm] hat also so
> viele Einser, wie das perfekte Matching groß ist )
>
> Ich soll nun zeigen, dass dieses Polytop das selbe ist wie
> das folgende:
>
> [mm]P=\{x\in\IR^{|E|}: x_e\geq0 \forall e\in E, \sum_{e \text{ mit } v\in e} x_e=1 \forall v\in V\}[/mm]
>
> dabei ist [mm]x_e[/mm] die e-te Komponente des Vektors x.
>
>
> An Beispielen konnte ich das verifizieren. Und mein erster
> Gedanke war, dass das irgendwas mit der Eigenschaft zu tun
> haben muss, dass in einem bipartiten Graph die
> Kardinalität des maximalen Matchings genau so groß ist
> wie die Kardinatlität der minimalen Knotenüberdeckung.
> Immerhin ist im ersten Fall die Summe der Einträge von [mm]x_M[/mm]
> genau die Kardinalität des perfekten Matchings. Das hat
> aber irgendwie zu nichts geführt. Und auch der Versuch,
> die Ecken des zweiten Polytops zu berechnen, hat nicht
> geklappt... kann mir deswegen bitte irgendjemand helfen...
> Danke
Zunächst einmal stimmt die aussage nur, wenn man auch ganzzahligkeit fordert. auf den ersten blick glaube ich nicht, dass die matrix, die hier entsteht tootal unimodular ist, daher wirds wahrscheinlich sogar ganzzahlige ecken geben.
ansonsten überlege dir mal folgendes:
die summe aller kanten, die an einem knoten liegen (bzw deren bewertung) ist 1. diese 1 entspricht genau einer gematchten kante. hilft dir das weiter?
Gruß Bernhard
|
|
|
|
