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
![- (Mathematik, Informatik, Graphen)](https://images.gutefrage.net/media/fragen/bilder/algorithmen-und-datenstrukturen-hilfe/0_big.jpg?v=1701283091000)
![](https://images.gutefrage.net/media/default/user/5_nmmslarge.png?v=1438863662000)
Was soll hier d(w) sein?
![](https://images.gutefrage.net/media/default/user/8_nmmslarge.png?v=1551279448000)
wurde nichts dazu angegeben
1 Antwort
![](https://images.gutefrage.net/media/default/user/5_nmmslarge.png?v=1438863662000)
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.