Independent Set / Unabhängige Menge / Graphentheorie

Aufrufe: 627     Aktiv: 08.04.2020 um 22:46
0

Gibt es in einem ungerichteten Graphen G=(V,E) mit nur zwei Knoten eine unabhänige Menge? 

Also ich habe Knoten 1 und Knoten 2 bzw. V={1,2}, diese sind direkt über eine Kante miteinander verbunden. Gesucht ist hier die stabile/unabhängie Menge. 

Meine Vermutung ist, dass sich mit nur zwei direkt verbundenen Knoten keine stabile Menge bilden lässt. Benötige hier umbedingt Hilfe oder eine Bestätigung. 

Vielen Dank 

Diese Frage melden
gefragt

Student, Punkte: 28

 
Kommentar schreiben
1 Antwort
1

Jeder der Knoten alleine bildet eine stabile Menge. Eine Menge mit nur einem Knoten ist immer stabil. Siehst du, warum?

Diese Antwort melden
geantwortet

Student, Punkte: 5.33K

 
Heißt im Beispiel ist sowohl Knoten 1 eine stabile Menge als auch Knoten 2?
Gleichzeitig ist dann aber auch Knoten 1 oder Knoten 2 die maximale stabile Menge, weil ich keinen weiteren Knoten hinzufügen kann sodass die menge immer noch stabil ist?   ─   classic_92 08.04.2020 um 22:15
Alles korrekt. Die maximal stabile Menge ist in den wenigsten Fällen eindeutig bestimmt.   ─   sterecht 08.04.2020 um 22:46

Kommentar schreiben