Recherche d'au moins deux chemins de même longueur dans un graphe orienté

Supposons que nous ayons un graphe orienté et deux noeuds et . Je voudrais savoir s'il existe déjà des algorithmes pour calculer le problème de décision suivant: $G=(V,E)$ $A$ $B$

Y a-t-il au moins deux trajets entre et de même longueur? $A$ $B$

Et la complexité? Puis-je le résoudre en temps polynomial?

Je voudrais ajouter une nouvelle contrainte sur le graphique, peut-être que le problème est plus résoluble. Sur la matrice d'adjacence, chaque colonne n'est pas vide. Ainsi, chaque nœud a au moins une flèche en entrée et il y a également au moins un nœud connecté à lui-même. Donc, si le nœud est le ème nœud, alors est une arête dans le graphique. $i$ $(i,i)$

complexity-theory graph-theory time-complexity graphs Paolo Parisen T.
la source

Voulez-vous dire des chemins simples? (visitant chaque nœud au plus une fois), sont-ils également autorisés à avoir un nœud interne commun?

non, il n'y a aucune restriction sur les chemins. vous pouvez faire une boucle, si vous le souhaitez.

Paolo Parisen T.

L'observation facile est la suivante: s'il n'y a qu'un seul chemin simple entre et que ce chemin simple est connecté à au plus une boucle, vous pouvez simplement dire , s'il y a au moins deux boucles de longueur différente connectées à ce chemin simple , vous pourriez dire oui, .... (Je pense que des choses similaires sont utiles et vous pouvez le prouver), mais dans le cas de chemins simples disjoints (si pendant la preuve de cela vous avez rencontré des chemins simples disjoints), c'est NPC.

A, B

$A,B$

N o

$No$

@mrm: Je ne vois pas cela comme un doublon. Demander toutes les promenades est une opération qui prend énormément de temps (en général, il y a un nombre infini de promenades), alors que l'OP demande deux chemins (simples), pas toutes les promenades.

Dave Clarke

Réponses:

Considérons un graphe , nous voulons savoir s'il existe deux chemins différents de à de même longueur. Que faire? Simple: codez deux chemins en un. Définissez le graphe avec les sommets . Vous faites un pas dans en faisant deux étapes indépendantes dans . Le bit supplémentaire vous indique si les deux chemins se sont déjà séparés l'un de l'autre. $G$ $A$ $B$ $G'$ $V \times V \times \{0,1\}$ $G'$ $G$

Formellement, il y a une arête dans ssi , dans et . $(i,j,e) \to (i',j',e')$ $G'$ $i \to i'$ $j \to j'$ $G$ $e'=e ∨ (i,i')≠(j,j')$

L'algorithme vérifie s'il existe un chemin vers dans , qui est , ou quelque chose comme . $(A,A,0)$ $(B,B,1)$ $G'$ $O(V^4)$ $O((V+E)^2)$

Si vous convenez que cet algorithme est correct, par conséquent, le chemin dans est de longueur au plus , donc les "collisions de chemin" potentielles doivent se produire au plus tard à cette longueur. Vous pouvez obtenir un algorithme partir de cette observation, où est la complexité de multiplication de la matrice (demandez si vous avez besoin d'un spoiler ...). $G'$ $2n^2$ $O(V^{\omega} \log V)$ $\omega$

Je pense fortement qu'il existe un algorithme , qui utilise davantage la structure du problème. $O(V+E)$

sdcvvc
la source

C'est élégant.

Raphael

J'ai probablement une réponse à ce problème, mais je ne suis pas sûr que cela fonctionne.

Il n'est pas important de «trouver» les deux voies, la seule chose importante est de «savoir» si elles existent ou non. Je ne pense pas que ce soit un problème NP complet.

Alors, prenez la matrice contiguïté . On peut facilement supposer qu'il est rempli avec 0,1 valeur. (0 = pas de bord; 1 = il y a un bord) Utilisons l'algèbre suivante avec 3 valeurs (0,1,2), où tout fonctionne comme d'habitude sauf: ; $\textbf A$ $2+\text{<something>} = 2$ $2*\text{<whatever greater than 0>} = 2$

Donc, s'il y a deux chemins de même longueur à partir de je m'attends à ce qu'il y ait une valeur telle que . $i,j$ $p$ $(\textbf A^p)_{i,j} = 2$

Soit le nombre de sommets du graphe (ou, disons, que a la dimension ). Je ne connais pas la valeur de , mais si j'itère en multipliant avec lui-même pendant au plus je devrais trouver la réponse. (donc, ) (le sens est que je vérifie , puis je vérifie , puis je vérifie et ainsi de suite ...) $n$ $\textbf A$ $n\times n$ $p$ $\textbf A$ $n^2$ $p<n^2$ $\text A$ $\text A^2$ $\text A^3$

voici mon argumentation:

si les deux chemins sont des chemins simples, eh bien, ça marche; s'il y en a, au plus je dois répéter fois. $n$
S'il y a au moins un cycle neasted ou s'il y a un chemin avec deux cycles, eh bien, je dois trouver le plus petit commun multiple (LCM). est une valeur plus grande à coup sûr et en moins de fois s'il y en a, je devrais avoir à les trouver. $n^2$ $n^2$
Si les deux chemins sont deux chemins distincts, tous les deux avec un cycle, alors c'est plus ou moins similaire à trouver une solution pour ces deux équations: , où et sont la longueur de ces deux cycles distincts. Multiplication matricielle , tel que défini ci-dessus, dit "y a-t-il un chemin de à dont la longueur est ?" Donc, si est plus grand que cela signifie qu'il y a plus de chemins menant de à . En itérant la matrice fois, nous passons par toutes les combinaisons possibles de $\alpha + \beta m = \gamma + \delta k$ $m$ $k$ $\text A^q$ $i$ $j$ $q$ $\textbf A^q$ $1$ $i$ $j$ $n^2$ $\delta$ et . En effet, est défini comme et aucun cycle ne peut être supérieur à . $\beta$ $LCM(a,b)$ $(a*b)/GCD(a,b)$ $n$

Je m'arrête pour répéter une fois que j'ai trouvé . $(\textbf A^p)_{i,j} = 2$

ai-je tort?

Paolo Parisen T.
la source

J'ai essayé la même chose et j'ai rencontré des problèmes / incertitudes: 1) Et si les chemins sont connectés à plus d'un cycle? Devez-vous "vérifier" toutes les combinaisons (dans le pire des cas, chaque nœud repose sur de nombreux cycles exponentiels!), Faisant exploser la limite supérieure, ou est-ce suffisant de n'en considérer qu'une pour chaque? 2) En raison des décalages constants et , le LCM est-il vraiment une borne supérieure?

α

$\alpha$

γ

$\gamma$

Raphael

Au fait, il n'y a pas besoin d'une algèbre funky: arrêtez-vous juste au moment où vous calculez un comme entrée de matrice.

2

$2$

Raphael

@Raphae 1) s'il y a un chemin à deux cycles, alors il y a bien sûr deux chemins de même longueur. celui qui boucle sur le premier cycle et celui qui boucle sur le second. combien ont-ils à boucler? exactement le LCM de la durée des deux cycles. ceci est délimité par , où est le nombre de sommets dans le graphique. 2) LCM est la limite supérieure (dans le cas 1)) parce que LCM (a, b) est délimité par un * b plus décalages et ; donc, au total, nous avons . nous savons que , donc est inférieur à .

n^{2}

$n^2$

n

$n$

α

$\alpha$

γ

$\gamma$

L C M (a, b) + α + γ < a * b + α + γ

$LCM(a,b) + \alpha+\gamma < a*b+\alpha + \gamma$

α + γ + a + b < n

$\alpha+\gamma+a+b < n$

a * b + α + γ

$a*b+\alpha+\gamma$

n^{2}

$n^2$

Paolo Parisen T.