0 Daumen
229 Aufrufe

Aufgabe:

Sei G ein zusammenhängender Graph und k ∈ N so gewählt, dass für alle Blöcke B ⊆ G gilt |V (B)| ≤ k.

(i)Geben Sie ohne Begründung einen Algorithmus an, der eine größte, bezüglich Kardinalität,unabhängige Menge in G findet und dessen Laufzeit in O(f(k) p(|V (G)|)) liegt. Dabei soll f : N → N eine beliebige Funktion sein, die ausschließlich von k abhängt,während p: N → N ein Polynom ist,das ausschließlich von |V (G)| abhängt.
(ii) Beweisen Sie die Korrektheit des Algorithmus aus (i).



Problem/Ansatz:

kann jemand helfen diese Afgabe zu lösen bitte?

von

Bitte logge dich ein oder registriere dich, um die Frage zu beantworten.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...