Stabile Menge in einem ungerichteten Graphen.

Aufrufe: 969     Aktiv: 02.03.2020 um 12:22
0

Gegeben ist der im anhang beigefügte Graph. Ich suche nun die stabile Menge für jeden Knoten. Das Problem stammt aus dem Bereich Graph Coloring bzw. List Coloring.

Kann mir da jemand helfen?

 

VG

 

 

Diese Frage melden
gefragt

Student, Punkte: 28

 
Kommentar schreiben
1 Antwort
0
Du suchst also eine Teilmenge der Knotenmenge für die gilt, dass 2 Knoten aus dieser Menge nicht benachbart (also durch einen Bogen verbunden) sind. So wie ich das in deinem Beispiel sehe, heißt das also, dass \( U = \{1;3\} \) die maximale stabile Menge deines Graphens ist.
Diese Antwort melden
geantwortet

M.Sc., Punkte: 6.68K

 
Vielen Dank.
Soweit habe ich das jetzt auch verstanden.
Das ganzen soll nun mit dem oben gezeigten ILP Modell gelöst werden.
In der Zielfunktion wird aber nun unter der zweiten Summ dieser Ausdruck verwendet S∈S(Gj). Gj ist dabei ein Subgraph von G = (V, E) und S(Gj) ist das maximale stabile Set des Subgraphen. j steht dabei für den die Farben, welche in meiner Zeichnung über den Knoten zu finden sind. Ich suche quasi das maximale stabile Set des jeweiligen Subgraphen Gj. Allerdings weiß ich nicht wie ich das Stabile Set des Subgraphen hier finde.   ─   classic_92 02.03.2020 um 12:22

Kommentar schreiben