Totale Unimodularität beweisen < Determinanten < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 16:35 So 19.01.2014 | | Autor: | custos |
| Aufgabe | | Schreiben Sie ein lineares Programm, welches für einen bipartiten Graphen [mm]G=(V,E)[/mm] das Problem des maximalen bipartiten Matchings löst. Zeigen Sie, dass die Lösung des linearen Programmes ganzzahlig ist. |
-- bitte verschieben, falls falsches Forum --
Mein Ansatz ist folgender: Sei [mm]V=\{y_1,…,y_k\}\cup\{z_1,…,z_{k'}\}[/mm]. Für jede Kante im bipartiteten Graphen wählen sei [mm]x_{ij}=(y_i,z_j)[/mm]. Dann können wir ein lineares Programm so definieren:
maximiere [mm]\sum_{i,j} x_{ij}[/mm] unter den Nebenbedingungen:
[mm]\sum_jx_{ij}\leq 1[/mm] (für [mm]i=1 … k[/mm])
[mm]\sum_ix_{ij}\leq 1[/mm] (für [mm]j=1 … k'[/mm])
[mm]x_{ij}\geq 0[/mm] (für alle [mm]x_{ij}\in E[/mm])
Soweit, so gut – ich habe also Nebenbedingungen der Form [mm]Ax=b[/mm], wobei [mm]b[/mm] ganzzahlig (nur Einsen) und [mm]A[/mm] eine [mm]|E|\times|V|[/mm]-Matrix mit Einsen und Nullen ist. Um zu zeigen, dass die Lösungen des LP ganzzahlig sind, bietet es sich an zu zeigen, dass die Matrix [mm]A[/mm] total unimodular ist. Wenn ich mir ein Beispiel nehme, trifft das auch zu, aber wie kann ich das allgemein für beliebige Graphen/LP beweisen? Da fehlt mir völlig der Ansatz.
Danke für eure Tipps!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:47 So 19.01.2014 | | Autor: | custos |
Hab eben eine Erkenntnis gewonnen: In der Matrix hat jede Spalte genau zwei Einsen und sonst ausschließlich Nullen! Ist das hinreichend für totale Unimodularität?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:20 Di 21.01.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
