stabile Menge & sein Polyeder < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei [mm]P = \left \{ x \in \IR^n | x_i + x_j \leq 1, x_i \geq 0 , x_i \leq 1; \forall i=1,...,n \right \}[/mm] das zugehöriger Polyeder zum Problem der stabilen Menge. P' sei das zugehörige ganzzahlige Polyeder. ([mm]P' = conv (P \cap \IZ^n )[/mm] ).
Zeigen oder widerlegen Sie , ob die folgenden Ungleichungen für P oder P' gültig sind:
a.) [mm]x_i + x_j + x_k \leq 1[/mm]
b.) [mm]x_i + x_j + x_k \geq 1[/mm]
c.) [mm]x_i + x_j - x_k \leq 1[/mm] |
Hallo,
habe mir gerad mal Gedanken gemacht zum Thema Graphentheorie und ILP's und LP's.
Wenn man das Problem der stabilen Menge aus der Graphentheorie betrachtet, und in ein LP formuliert, sehe ich dass dann richtig, dass das POlyeder aussieht wie das des Standardsimplex???
aber nun zur wichtigeren Frage wegen den Ungelichungen a.) b.) und C.)
Meine Schätzung:
a.) Nein, die Ungleichung ist weder gültig für P, noch für P'.
b.) ja, die Ungleichung ist gültig für P und P'.
c.) Nein, für kein Polyeder gültig.
Sind die Aussagen so korrekt?
Wie kann man das beweisen, also bei Nein, klar durch gegenbeispiel aber b.) ??
Wäre dankbar für Hinweise.
Grüße
student
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:37 Mo 26.09.2011 | | Autor: | Stoecki |
also mir sind deine indices nicht klar. das polytop der stabilen mengen hängt auch von den kanten ab. ich würde da also sowas wie [mm] x_i [/mm] + [mm] x_j \le [/mm] 1 für i [mm] \in [/mm] N(j) schreiben (N(i):= Nachbarschaftsmenge von i. geht man davon aus, dass diese nachbarschaftsrelationen gefordert sind, bzw. die ungleichungen nur dafür definiert sind, dann dürfen zwei benachbarte knoten nicht in der menge sein. wie sieht das dann für andere soummen wie denen da unten aus? zulässigkeit zeigst du, indem du eine ungleichung dann einfach für einen allgemeinen graphen durchspielst (stichwort fallunterscheidung)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:44 Mo 26.09.2011 | | Autor: | Stoecki |
noch eine anmerkung. nein, das polyeder sieht nicht aus wie das standardsimplex. die leere menge ist eine stabile menge, aber der nullvektor ist kein element des polytops der stabilen mengen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:20 Do 29.09.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
