 |
 |
 |
 |
 |
 |
Startseite » Forum » Unabhängige Mengen
Unabhängige Mengen
Universität / Fachhochschule
Graphentheorie
Tags: Graphentheorie
 
|
  |
|---|
|
Guten Tag, ich habe ein großes Problem und hoffe ihr könnt mir weiterhelfen. Ich schreibe bald eine Klausur und dort müssen wir auch einen Algorithmus entwickeln, der auf dieses Problem aufbauen wird. Ich soll einen Algorithmus zum finden einer größte, bezüglich Kardinalität, unabhängige Menge in findet. Dabei sei ein zusammenhängender Graph und ∈ so gewählt, dass für alle Blöcke ⊆ gilt ∣V (B)∣ ≤ . Meine Idee: Wir bilden einen Blockgraph. Dann gehen wir über alle Blöcke mit diesem Schema: In jeden Block werden die Teilmengen herausgesucht, danach werden die Gelenkpunkte aus den Teilmengen entfernt. Daraus erhält einzelne Zusammenhangskomponenten und diese Prüft man auf Unabhängigkeit. Liegen solche unabhängigen Mengen vor, speichern wir sie in einem Array /List wie auch immer. Aus dieser Liste löscht man nun die nicht maximalen unabhängigen Mengen, man möchte eine größte haben. Bedeutet dass in dem Array auch mehrere der gleichen Größe liegen können. Nun wählt man davon eins aus und hat die Menge. Das Problem ist, das dieser "Algorithmus" so nicht funktioniert. Könnte mir jemand auf die Sprünge helfen wie ich vorgehen soll? Der Algorithmus soll in Laufzeit p(∣V (G)∣)) laufen. Über eine schnelle Antwort wäre ich dankbar, die Klausur ist schon Dienstag. Liebe Grüße Lisa Marie Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
1475247
1475247