Algorithmen und Datenstrukturen hilfe?
Es geht um die aufgabe 2, ich versteh die aufgabenstellung nicht und weiß halt nicht was man da machen soll. help pls
Was soll hier d(w) sein?
wurde nichts dazu angegeben
1 Antwort
Nehmen wir mal an, d(w) wäre der Grad des Knoten w. Wenn w eien Artikulatio9n ist, dann zerfäöllt der Graph ohne we in mindestens 2 Zusammenhangskomponenten.
Ist w keine Artikulation, dann bildet V\w immenroch eine einzelne Zusammenhangskomponente. Es gilt oBda, daß ich über einen beliebigen Nachbarn alle Knoten des Graph besuchen kann. Ich muß w also nur mit mindestens eine rKante mit dem restlichen Graphen verbinden.
Im Gegensatz dazu, sollte w eine Artikulation sein, und der Grad von w lediglich 1, dann kann ich mit der Tiefensuche lediglich über die eine Kante die daran hängende Zusammenhangskomponente besuchen. Ich brauche also zwingend von w eine Kante zu jeder Zusammenhangskomponente in die V\w zerfallen würde, um einen vollständigen Spannbaum zu erhalten, respektive einen vollständigen Tiefensuchbaum.