Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

Begründung bei a) ausreichend?

–1 Punkt
29 Aufrufe
wieso reicht bei Aufgabenteil a diese Begründung aus? nur weil ich bei eine geratenen Knotenmenge in polynomieller Zeit sagen kann ob alle Kanten einen Knoten in C haben? Damit ist doch die Frage ob es eine Knotenabdeckung einer bestimmten Größe gibt nicht gelöst? oder wo ist da mein Denkfehler?
Gefragt 22, Okt 2014 in BER-AC von utdbu utdbu Tutor(in) (106,580 Punkte)  

Eine Antwort

0 Punkte
Na doch, wenn man eine Knotenteilmenge C rät, in der sich k Knoten befinden, dann  muss man nur noch prüfen, ob jede Kante des Graphen mindestens einen ihrer Knoten in C hat. Wenn das der Fall ist, ist C eine Knotenüberdeckung der Größe k - so ist es ja definiert.

Das Raten geht in linearer Zeit, das Verifizieren in polynomieller Zeit, also haben wir insgesamt (nichtdeterministische) Polynomialzeit verbraucht und befinden uns in NP.

Viele Grüße

Lukas König und Friederike Pfeiffer-Bohnen
Beantwortet 22, Okt 2014 von utdbu utdbu Tutor(in) (106,580 Punkte)  
...