Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
[EffAlg] Frage zur Übungsaufgabe 1.1 - Artikulationspunkte
Gestern haben wir ja in der Übung in EffAlg besprochen, dass die Wurzel r des Tiefensuchbaums dann ein Artikulationspunkt (=: AP) eines Graphen G = (V, E) ist, wenn der Ausgangsgrad von r im Tiefensuchbaum >= 2 ist. Danach kam von einem Studenten eine Frage auf, ob man auch für Knoten v != r sagen kann, dass v ein AP ist, wenn der Ausgangsgrad von v >= 2 ist.
Ich denke, ein Gegenbeispiel dazu gefunden zu haben. Starten wir nun die Tiefensuche in v1 unter Verwendung alphabetischer Reihenfolge in den Inzidenzlisten, so entsteht der folgende Tiefensuchbaum (bis auf die dfnr). Hier hat v2 im Tiefensuchbaum den Ausgangsgrad 2, ist aber kein AP.
Kann bitte jemand kontrollieren, ob das Gegenbeispiel - insbesondere der Tiefensuchbaum - so stimmt?
Hat sich geklärt, das Beispiel scheint zu stimmen. 