Unabhängig Menge an Knoten LP-Problem

Neue Frage »

FaithNoMore Auf diesen Beitrag antworten »
Unabhängig Menge an Knoten LP-Problem
Meine Frage:
Hallihallo Wink
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! Gott
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.
 
 
FaithNoMore Auf diesen Beitrag antworten »

Hallo smile
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. smile
Aber ich habe leider nicht verstanden, inwiefern du meinst, man sähe ja, dass wäre? Hammer
FaithNoMore Auf diesen Beitrag antworten »

Gibt es vielleicht eine Möglichkeit, dass jemand das Ganze bitte nochmal genauer erläutern kann? unglücklich Gott
Math1986 Auf diesen Beitrag antworten »

Zitat:
Original von FaithNoMore
Hallo smile
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. smile
Aber ich habe leider nicht verstanden, inwiefern du meinst, man sähe ja, dass wäre? Hammer

Wenn und , dann wären die Knoten und in der Menge - was hieße das für die Unabhängigkeit?
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »