- gestellte Fragen oder gegebene Antworten wurden upvotet (5 Punkte je Upvote)
- erhaltene Antwort akzeptiert (2 Punkte je Antwort)
- gegebene Antwort wurde akzeptiert (15 Punkte je Antwort)
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.
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.
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
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