 |
 |
 |
 |
 |
 |
Startseite » Forum » k-Knotenüberdeckung
k-Knotenüberdeckung
Universität / Fachhochschule
Graphentheorie
Tags: Graphentheorie
 
|
  |
|---|
|
Sei ein ungerichteter Graph. Eine Knotenmenge heißt k-Knotenüberdeckung genau dann, wenn gilt für jede Kante im Graphen enthält mindestens einen der beiden Knoten und . Wir definieren die folgende Sprache Knotenüberdeckung besitzt eine k-Knotenuberdeckung. . Sei A ein deterministischer Algorithmus, der die Sprache Knotenuberdeckung in Polynomialzeit entscheidet. Geben Sie einen deterministischen Algorithmus an, der mithilfe von A bei Eingabe eines Graphen und einer natürlichen Zahl in polynomieller Zeit eine k-Knotenüberdeckung für konstruiert, bzw. ein Fehlersymbol ⊥ ausgibt, sollte nicht zu der Sprache gehören Mein Ansatz: Bei Eingabe Konstruiere für die Menge alle Untermengen mit Elementen. Dann teste für jede dieser Untermengen, ob sie eine gültige Knotenüberdeckung ist, . überprüfe für jede Kante in ob einer der beiden Knoten oder in der Untermenge enthalten ist. Wenn ja akzeptiere, wenn für alle Untermenge nein, dann lehne ab Alle Untermengen zu generieren geht in und das Testen aller Kanten also insgesamt Laufzeit . Weil eine natürliche Zahl ist, ist ja ein Polynom und somit die Sprache in polynomieller zeit entscheidbar Habe ich einen Denkfehler? 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.
|
1534939
1534939