Unabhängig Menge an Knoten LP-Problem |
15.11.2016, 19:11 | FaithNoMore | Auf diesen Beitrag antworten » | ||
Unabhängig Menge an Knoten LP-Problem Hallihallo Ich stecke gerade wirklich fest bei einer Aufgabe: Es sei ein ungerichteter Graph mit Knotenmenge und Kantenmenge . Eine Teilmenge U der Knotenmenge heißt unabhängig, falls keine zwei Knoten von U durch eine Kante verbunden sind. Ein bekanntes, in der Informatik häufig betrachtetes Optimierungsproblem: Finde in G eine unabhängige U, die möglichst viele Knoten enthält. Formulieren Sie das Problem für den unten abgebildeten Graphen G als ein binäres LP-Problem. Hinweis: Für jeden Knoten ist eine Variable zu betrachten. [attach]42995[/attach] Meine Ideen: Ich bin hier ziemlich am Rätseln. Ich habe schon zig Dinge ausprobiert, aber keine bringt mich Richtung Lösung. Ich bin der Meinung, dass ich vielleicht irgendwie zum Ziel komme, in dem ich die Anzahl der von einem Knoten ausgehenden Kanten durch den Koeffizient vor derjenigen Variable angeben muss und dann durch Addition von anderen Kantenanzahlen von anderen Variablen abschätzen muss, ob ein unabhängiger Knoten vorliegt oder sogar mehrere... Wenn mir hierbei jemand helfen könnte, wäre ich sehr, sehr dankbar! |
||||
15.11.2016, 20:22 | Math1986 | Auf diesen Beitrag antworten » | ||
RE: Unabhängig Menge an Knoten LP-Problem Naja, die binären Variablen sind doch für jeden Knoten und geben an, ob der Knoten in die Menge aufgenommen wird oder nicht. Die Summe hierrüber ist zu maximieren, also . Nun musst du noch eine Charakterisierung der Unabhängigkeit als Nebenbedingungen formulieren. Das kannst du aber in untenstehendem Problem leicht dadurch angeben, dass zum Beispiel oder ist. Formuliere das unten angegebene Problem. |
||||
16.11.2016, 22:43 | FaithNoMore | Auf diesen Beitrag antworten » | ||
Hallo Das verstehe ich leider nicht so ganz. Also dass ich irgendwie auf Abhängigkeit bzw. Unabhängigkeit prüfen muss, macht auf jeden Fall Sinn, denn nur so kann ich ja feststellen, ob die Knoten keine/ eine Kante zueinander haben. Aber ich habe leider nicht verstanden, inwiefern du meinst, man sähe ja, dass wäre? |
||||
17.11.2016, 21:47 | FaithNoMore | Auf diesen Beitrag antworten » | ||
Gibt es vielleicht eine Möglichkeit, dass jemand das Ganze bitte nochmal genauer erläutern kann? |
||||
18.11.2016, 19:37 | Math1986 | Auf diesen Beitrag antworten » | ||
Wenn und , dann wären die Knoten und in der Menge - was hieße das für die Unabhängigkeit? |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|