Polytop der maximalen Matching < Optimierung < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 09:54 Di 19.07.2011 | | Autor: | Stoecki |
Hallo zusammen,
ich suche eine Beschreibung (am besten durch Facetten) für das Polytop der maximalen Matchings (maximal in dem Sinne, dass wenn M ein Matching im Graphen G=(V,E) ist, dann ist M [mm] \cup [/mm] e für alle e [mm] \in [/mm] E kein Matching)
Grundidee:
N(v)=Menge aller Nachbarn von v
[mm] \summe_{w \in N(v)} x_{(v,w)} \le [/mm] 1 (normale Matchingbedingung)
[mm] (\summe_{u \in N(v), u \not= w} x_{(u,v)}) [/mm] + [mm] (\summe_{u \in N(w), u \not= v} x_{(u,w)}) [/mm] + [mm] x_{(v,w)} [/mm] = 1 für alle Kanten (v,w)
[mm] x_{(v,w)} \in [/mm] {0,1}
(Zusätzlich die Blütenungleichungen, die separiert werden müssen, siehe Eintrag von vor 5 Tagen von mir)
Bemerkung zur zweiten Bedingung: Diese sagt aus, dass es keine zwei benachbarten Knoten geben darf, die ungematcht sind.
Gibts da evtl was besseres? Bin mit Quellenverweisen zufrieden. Habe aber selber noch nicht all zu viel gefunden.
Ich habe diese Frage in keinem weiteren Forum gestellt.
Gruß Bernhard
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:20 Do 28.07.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
