Wie finde ich eine unabhängige Knotenmenge?
Guten Morgen,
ich habe die folgende Aufgabe
Mein Problem ist, dass ich gerade nicht die Idee dazu habe wie ich eine unabhängige Menge in solche einen Graphen finden kann.
Erst einmal wie schaut denn so ein Graph aus? So hier oder
?
Die Frage ist nun was genau meint man mit größter (bzw wenn es mehrere gibt, eine größte) unabhängige Menge? Meine Idee war es den größten Block zu finden und dessen Schnittknoten zu entfernen, dann müsste er doch unabhängig sein oder?
Obwohl ich das anzweifle.
Kann mir Jemand eine Strategie verraten, bzw mit mir diskutieren?
2 Antworten
Ist G ein Graph, so bezeichnet V(G) seine Knotenmenge und E(G) seine Kantenmenge
Eine Knotenmenge H ( als Teilmenge von V(G) ) heißt unabhängig, wenn deren Knoten nicht adjazent sind, d.h. wenn es keine direkte Verbindung gibt.
Solche Knotenmengen gibt es in einem Graphen viele, es reicht ja jeweils ein passendes Paar zu finden.
Eine maximal unabhängige Knotenmenge ist eine unabhängige Knotenmenge maximaler Kardinalität. Das ist also die Menge, die alle unabhängigen Knoten enhält.
Beispiel:
Die grünen Knoten bilden eine maximal unabhängige Menge. Sie sind paarweise nicht direkt durch Kanten verbunden.
Aber jede Untermenge aus mindestens zwei grünen Knoten bildet eine unabhängige Knotenmenge.
Unabhängig heißt hier, dass es keine direkte Kante zwischen irgendwelchen zwei Knoten der Menge gibt. Es gibt prinzipiell viele solcher Knotenmengen - und von denen sollst du diejenige, mit der größten Knotenzahl finden.
https://de.wikipedia.org/wiki/Stabile_Menge#Maximale_stabile_Menge
Hier werden Algorithmen aufgeführt:
https://en.wikipedia.org/wiki/Maximal_independent_set
Kurz: Es ist nicht trivial. ;-))