Graph/optimierung Ecke bestim. < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Gegeben sei der Graph G = (V,E) mit V={1,2,3,4} und E = { {1,2} {1,3} {2,3} {2,3} }.
Man gebe die Darstellung des Polyeders an, die keine überflüssigen Gleichungen enthält. Gebe die Ecken des Polyeders an! |
huhu zusammen
Also das Polyeder ohne redundante Ungleichungen habe ich raus, es ist:
[mm] x_1 \le [/mm] 1
[mm] x_2 \le [/mm] 1
[mm] x_3 \le [/mm] 1
[mm] x_4 \le [/mm] 1
[mm] x_1 [/mm] + [mm] x_2 [/mm] + [mm] x_3 \le [/mm] 2
[mm] x_1 [/mm] + [mm] x_2 [/mm] + [mm] x_3 [/mm] + [mm] x_4 [/mm] =3
[mm] x_i \ge [/mm] 0 für all i = 1,2,3,4
ich könnte die Ecken nun aufwendig mit Simplexalgorithms bestimmen, aber da gibts zuuuu viele Möglichkeiten die ich durchgehen müsste und habe mich gefragt, ob es nicht mithilfer der Graphentheorie einfacher geht. (vlt als Stichwort Inzidenzvektor, das verstehe ich aber noch nicht so ganz)
Lg,
Eve
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 So 30.06.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
