|
  |
 stabile Menge, polynomieller Algorithmus |
drespan
Grünschnabel
Dabei seit: 15.05.2007
Beiträge: 4
 |
|
| stabile Menge, polynomieller Algorithmus |
     |
Hallo, ich hoffe ich bin hier im richtigen Forum gelandet.
Eine Aufgabe bereitet mir Kopfschmerzen:
Eine stabile Menge in einem Graphen G = (V, A) ist eine Knotenmenge S Teilmenge V mit der Eigenschaft, dass keine zwei Knoten in S durch eine Kante verbunden sind
d.h. für u, v aus S: (u, v) nicht in E.
Als Stabilitätszahl a(G) wird die maximale Kardinalität einer stabilen Menge in G bezeichnet.
Gegeben sei ein Algorithmus A, der das Entscheidungsproblem
STABLE-SET: “Entscheide für i aus N, ob es in G eine stabile Menge S mit Kardinalität |S| > i gibt.”
in polynomieller Zeit löst.
Zeigen Sie, dass sich unter diesen Umständen die Stabilitätszahl a(G) ebenfalls in polynomieller Zeit bestimmen lässt. Sie können davon ausgehen, dass für die Inputgröße des Problems, d.h. die
Kodierungslänge des Graphen G gilt:
<G> = theta(k), wobei k := <n> und n := |V| ist.
Könnt ihr mir helfen?
vielen dank drespan!
|
|
15.05.2007 10:36 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Das Problem "STABLE-SET" ist NP-schwer, d.h. diesen Algorithmus A gibt es nur unter der Hypothese P = NP. Aber mal abgesehen davon lässt sich mit diesem Algorithmus leicht a(G) bestimmen.
Du weißt, wie viele Ecken ein Graph G hat und ein STABLE-SET kann maximal so groß sein.
D.h. du kannst einfach A verwenden und von oben nach untern laufen:
Für i = |V| down to 0
Falls A ein STABLE-SET |S| > i findet: a(G) = i+1
|
|
|
15.05.2007 14:54 |
|
|
drespan
Grünschnabel
Dabei seit: 15.05.2007
Beiträge: 4
|
|
Hallo Tobias,
wenn ich den Begriff der Stabilen Menge richtig verstanden habe, dann heißt das doch, dass für einen Graphen G=(V,A) mit der Stabilitätszahl a(G) = |V| gilt, dass A = leere Menge.
In dem Fall hat ja kein Knoten ein Nachbar.
Was mein Algorithmus A jetzt entscheidet ist die Frage, ob für eine beliebige Zahl i aus N es eine stabile Menge S in G mit größerer Kardinalität |S| gibt.
Wenn ich das jetzt richtig verstehe, dann scheint die Aufgabe wiederum recht einfach.
Denn ich kann ja anhand dieses Algorithmus A jede mögliche Kardinalität der stabilen Menge S ausprobieren.
D.h. der Algorithmus muss maximal "|V| = Anzahl der Knoten" mal aufgerufen werden.
Aber wie kann ich jetzt begründen, dass das dann wiederum polynomiell ist? Ich hätte da so argumentiert, da die Laufzeit ja maximal mit |V| "multipliziert" wird --- wie kann man das besser formulieren?
Vielen dank für deine Hilfe - manchmal fallen mir die abstrakten Begriffe ein wenig schwer. Ich hoffe ich hab den begriff so richtig interpretiert.
Grüße und dank
Benjamin
|
|
|
16.05.2007 15:36 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Ja, das hast du richtig verstanden.
Meine Argumentation sollte ganz grob sein:
Ein Polynom p(n) (der Zeitaufwand von Algorithmus A) multipliziert mit einem anderen Polynom q(n) (der Mehraufwand durch |V|-maliges Ausführen von A) ist immernoch polynomiell.
Um es zu präzisieren müsste ich aber deine Notation
<G> = theta(k), wobei k := <n> und n := |V|
verstehen können. Hast du leider nicht definiert.
Du kannst den Algo von mir übrigens noch ein bisschen verbessern, indem du nicht einfach alles durchprobierst sondern bei |V|/2 anfängst und dann ggf. größer oder kleiner wirst. Ein bisschen wie logarithmische Suche.
|
|
|
16.05.2007 20:13 |
|
|
drespan
Grünschnabel
Dabei seit: 15.05.2007
Beiträge: 4
|
|
hallo tobias,
k := <n> ist die Kodierungslänge, wir haben eine Definition von Theta:
f in theta(g), wenn es positive Konstanten c1, c2 aus IR und
und n0 aus IN gibt, so dass für alle n > n0 gilt
c1|g(n)| <= |f (n)| <= c2|g(n)|
Das heißt ich habe mit den Konstanten c1 und c2 über die Funktion g eine obere und eine untere Schranke. wie verbinde ich das jetzt mit dem Algorithmus A?
grüße und dank
benjamin
|
|
|
16.05.2007 22:33 |
|
|
drespan
Grünschnabel
Dabei seit: 15.05.2007
Beiträge: 4
|
|
hallo tobias,
ich hab ein wenig weiter gedacht, was das formelle betrifft.
wenn der gedankengang so stimmt, dann wird durch die Schleife der Algorithmus A im schlechtesten Fall genau |V| mal aufgerufen wird.
Die "Kodierungslänge von G" ist nach oben und unten beschränkt:
c1|g(n)| <= |f (n)| <= c2|g(n)| mit n := |V|.
Da die Laufzeit des Algorithmuss A polynomiell ist, so ist auch das |V| malige Ausführen des Algorithmus wiederum polynomiell.
Was ich mit dem "theta(k)" nun soll ist mir ein wenig schleierhaft.
Was meinst du?
Grüße benjamin
|
|
|
19.05.2007 10:22 |
|
|
|
|
|
|
|
|
