Quel est le moyen le plus efficace de déterminer si un graphe dirigé est singulièrement connecté ?

Question

Je travaille sur un projet dont l'un des problèmes est de dériver un algorithme pour vérifier si un graphe dirigé G=(V,E) est singulièrement connecté (il y a au plus un chemin simple de u à v pour tous les sommets distincts u, v de V.).

Bien sûr, vous pouvez le vérifier par force brute, ce que je fais en ce moment, mais je veux savoir s'il existe une méthode plus efficace. Quelqu'un pourrait-il m'indiquer la bonne direction ?

Answer 1

J'ai pensé à ceci : 1) Exécuter une DFS à partir de n'importe quel sommet, si tous les sommets sont couverts par la DFS sans arêtes avant (il ne peut pas y avoir de croisement, sinon tous les sommets ne seront pas couverts), alors ce sommet peut être un candidat potentiel.

2) Si un sommet (niveau j) trouvé dans la DFS a un bord arrière vers le niveau i, alors aucun autre sommet trouvé après lui ne devrait avoir un bord arrière vers un sommet de niveau inférieur à j et chaque sommet devrait être accessible à la racine (vérifié avec la deuxième DFS).

Cela le fait en temps linéaire si c'est correct.

Answer 2

Regardez la définition d'un chemin simple. Un graphe cyclique peut être singulièrement connecté. DFS ne fonctionnera pas pour A->B, B->A qui est singulièrement connectée.

L'article suivant utilise des composants fortement connectés pour résoudre ce problème.

https://www.cs.umd.edu/~samir/grant/khuller99.ps

Answer 3

Exécutez DFS une fois à partir de chaque sommet. Le graphe est singulièrement connecté si et seulement si seulement s'il n'y a pas d'arêtes vers l'avant et s'il n'y a pas d'arêtes croisées dans une composante. composant.

Complexité : O(V.E)