0 Daumen
436 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

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community