Déterminez si le graphique est connecté seul ou non

Question

Mon doute est faible. Si un graphique a des bords arrière, est-il connecté seul ou non? Par arêtes arrières, je veux dire les connexions du nœud enfant à l'un de ses ancêtres, sous la même racine. Si un nœud est connecté à un nœud supérieur à celui-ci, mais pas à son ancêtre, alors c'est un nœud croisé. http://en.wikipedia.org/wiki/Polytree

update: Ce lien clarifie la notion de graphe connecté individuellement.

Answer 1

Bonne question. Si un graphique a des arêtes arrière, cela ne l'empêche pas d'être seul connecté. Mais il pourrait ne pas être isolé pour d'autres raisons. Par exemple, si le graphique n'est pas dirigé.

Answer 2

Il semble que vous essayez de faire une analogie avec les listes chaînées (où des liaisons simples connectés et doublement connectés sont des termes communs avec un sens habituel).

Cependant, ce n'est pas un gros problème pour les graphiques, et la connectivité à long terme est le plus souvent associé à joignabilité (ie .: est-il un chemin d'un noeud à un autre?)

Answer 3

Si je comprends vous vous interrogez correctement, vous voulez savoir si un Polytree peut contenir des arêtes arrières (arêtes d'un noeud à l'un de ses ancêtres). A partir de l'article wikipedia auquel vous avez lié, un Polytree est un DAG qui reste un arbre même si les bords sont rendus non dirigés. Si un graphe orienté contenait des arêtes arrière, cela signifierait qu'il y aurait un cycle dans le graphe (vous pouvez atteindre le noeud à partir de son ancêtre puis revenir à l'ancêtre en utilisant le bord arrière). Ainsi, ce ne serait plus un DAG, encore moins un arbre. Si ce n'est pas un DAG, il ne peut pas être un Polytree. Donc, aucun Polytree ne peut avoir un avantage.