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?