Ändert sich die Art und Anzahl der Artikulationspunkte, wenn sich der Eintrittspunkt (Wurzelknoten) für eine ungerichtete Graphik ändert?Artikulationspunkt des ungerichteten Graphen
Wenn es sich ändert, warum passiert das?
Ich verstehe, dass Punkte variieren können, aber warum variiert die Anzahl der Punkte?
Hier ist mein Diagramm: -
Wie in den Wiki article angegeben, Gelenkpunkt ist eine Ecke, so dass, wenn sie als die Anzahl der angeschlossenen Komponenten erhöhen entfernt wird. Es gibt hier nichts über Einstiegspunkte und DFS: Die Definition hängt nur vom Graphen selbst ab.
Die Antwort auf Ihre Frage lautet also: Nein, die Artikulationspunkte sollten sich nicht ändern, wenn Sie den Graphen von verschiedenen Knoten aus durchlaufen.
Wenn Sie einen Standard-DFS-basierten Algorithmus verwenden, um Artikulationspunkte zu finden, haben Sie höchstwahrscheinlich einen Fehler.
Was ich am Artikulationspunkt nicht verstehe ist der Wurzelknoten sollte zwei unabhängige Kind haben. Warum wird A (Wurzel) in meinem obigen Diagramm nicht als Schnittpunkt/Artikulationspunkt betrachtet? – ddwivedy
@IvanSmirnov hat das ziemlich deutlich beantwortet. Das Entfernen von A (zusammen mit seinen Kanten) wirkt sich nicht auf die Anzahl der verbundenen Komponenten aus, also ist es kein Gelenkpunkt. Artikulationspunkte haben nichts mit Graphenwurzeln oder deren Fehlen zu tun. – Gene
put '!' Markiere vor '[Graph] [1]' like this '! [Graph] [1]' – surajsn