Le type et le nombre de points d'articulation varient-ils lorsque le point d'entrée (noeud racine) change pour un graphe non orienté?Articulation Point du graphe non orienté
Si cela change, pourquoi cela se produit-il?
Je comprends que les points peuvent varier, mais pourquoi le nombre de points varie-t-il?
Voici mon graphique: -
Comme indiqué dans le Wiki article, point d'articulation est un sommet tel que si elle est retirée que le nombre de composants augmente connectés. Il n'y a rien sur les points d'entrée et les DFS ici: la définition ne dépend que du graphe lui-même. Donc, la réponse à votre question est: non, les points d'articulation ne devraient pas changer si vous traversez le graphique à partir de différents nœuds.
Si vous utilisez un algorithme DFS standard pour trouver des points d'articulation, vous avez probablement un bogue.
Ce que je ne comprends pas au point d'articulation est que le nœud racine devrait avoir deux enfants indépendants. Dans mon graphique comme indiqué ci-dessus, pourquoi A (racine) n'est pas considéré comme un point d'articulation/point d'articulation coupé. – ddwivedy
@IvanSmirnov a répondu à cette question clairement. Supprimer A (avec ses bords incidents) n'affecte pas le nombre de composants connectés, ce n'est donc pas un point d'articulation. Les points d'articulation n'ont rien à voir avec les racines des graphes ou leur absence. – Gene
mettez '!' Mark avant '[Graph] [1]' comme ceci '! [Graph] [1]' – surajsn