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?
