chemin de longueur L dans un graphe ?

Salut ..

je dois ecrire en language c un programme pour representer un graphe numériquement par sa martice d'adjacence

parmis les fontions demandés une fonction permettant d’afficher l’existence d’un chemin de longueurs L mais je ne trouve pas d'algorithme pour ça ..

j'ai juste besoin du pricipe d'un algorithme ou une condition d'exictence d'un chemin de langueur donnée (pas besoins de trouver le chemin)

Bonsoir,

Si je me souviens bien de mes cours, il suffit de multiplier la matrice par elle-même, éventuellement plusieurs fois.

En prenant M^n, on peut déduire à partir d'un nœud de départ s'il existe un chemin allant vers un autre nœud en au plus n étapes, et le coût total du voyage si les arêtes ont des poids.

Bien sûr on suppose que la matrice est construite comme suit: la case i;j est >0 s'il y a une arête entre i et j; 0 s'il n'y a pas d'arête.

@QuentinC : Si $M$ est la matrice d'adjacence du graphe, $M^n$ donne les nombres de chemins en exactement $n$ étapes. Si on veut uniquement savoir s'il existe ou non un chemin de longueur au plus $n$ d'un nœud vers un autre, il ne faut plus travailler dans $\mathbb{N}$ mais dans le demi-anneau à deux éléments ⊥ et ⊤, avec comme addition le "ou" et comme multiplication le "et".

(edit : Il faut aussi prendre I+M à la place de M (sinon on ne pourrait même pas aller d'un nœud à lui-même en au plus une étape). Ça revient à prendre $(I+M)^n$ dans $\mathbb{N}$, mais en confondant tous les nombres supérieurs ou égaux à 1 (ou se fiche de savoir combien de chemins, on veut juste savoir s'il y en a un).)

Mais je pense que ce qu'on demande à Timm est juste un parcours du graphe.

@ Timm : Tu ne précises pas assez ce que tu veux faire, je pense. Un chemin entre quoi et quoi ? Entre tout couple de nœuds ou juste d'un nœud à un autre ? Il y a des contraintes de complexité ? Ça veut dire quoi « un programme pour representer un graphe numériquement par sa martice d'adjacence » ? Le graphe t'es donné par sa matrice d'adjacence ou bien tu dois calculer la matrice d'adjacence d'un graphe qui t'es donné sous un autre format ? C'est pas assez clair pour que je puisse t'aider.

le probleme c'est qu'on a pas les sommets de depart et d'arrivé

je ne comprend pas si je multiplie la matrice par elle meme n fois qu'est ce que j'obtiendrai ?

@blo yhg: au fait je dois ecrire d'une fonction avec comme parametres d'entré la matrice l'adjacence le nombre de sommets du graphe et l la logueur donnée .. qui retourne si il existe ou pas un chemin de cette longuer dans le graphe ..

Déjà, est-ce que dans votre définition de "chemin", on demande à ne pas passer qu'une seule fois par un noeud ? (ou par une arête ?)

Parce que bon, si c'est pas le cas, on va pas chercher à se compliquer la vie.

nn un chemin peut passer par le meme neud ou la mem arrete plusieus fois ( et le graphe peut contenir des cyles aussi)

Je comprends pas trop pourquoi tu veux rajouter $I$. Avec ca on aurait un chemin entre $u$ et $u$ de n'importe quelle longueur $L$.

Ok, je viens de voir le "au plus n etapes" plus haut.

Ca me parait suspect, parce qu'avec cette definition, il suffit de verifier qu'il existe une arete dans le graphe. Si on a une arete entre u et v, il suffit de faire u - v - u - v … $L$ fois pour obtenir un chemin de longueur $L$…

mais non le graphe est pondéré chaque arete a une valeur

je ne comprend pas c'est quoi I ?? et comment je peut déduire l'existence du chemin apartir de la matrice $(I+M)^n$

mais non le graphe est pondéré chaque arete a une valeur

Je ne vois pas ce que ça change à l'existence ou non d'un chemin. (Et puis on ne pouvait pas le deviner.)

$I$ est la matrice identité. L'exponentiation de matrices sert lorsqu'on veut compter les chemins entre chaque paire de nœuds, mais ce n'est apparemment pas le cas ici. À mon avis, Lucas-84 a raison et il est question de dire s'il existe un chemin de longueur L qui ne passe pas deux fois par la même arête (ce serait cohérent avec la question qui suit). À toi de confirmer…

la question qui suit n'a aucune relation avec celle ci ( je l'ai faite avec l'algorithme de fleury )

le fait que le graphe soit pondéré implique que la longueur du chemin n'est egale au nombre d'aretes parcourues (etapes) mais à la somme des valeurs des aretes

"l’existante d’un chemin de longueur L fait référence à la notion de fermeture transitive d’un graphe,notion non abordée au cours." c'est tout ce que j'ai pu obtenir comme éclaircissement

le fait que le graphe soit pondéré implique que la longueur du chemin n'est egale au nombre d'aretes parcourues (etapes) mais à la somme des valeurs des aretes

D'accord, haut taon pour moi ! Je suppose que les poids sont tous des entiers positifs et qu'il y a toujours au plus une arête d'un nœud vers un autre. Je ne sais pas s'il existe un algorithme standard.

As-tu déjà écrit une solution, sans te préoccuper de son efficacité ?

"l’existante d’un chemin de longueur L fait référence à la notion de fermeture transitive d’un graphe,notion non abordée au cours." c'est tout ce que j'ai pu obtenir comme éclaircissement

Je n'ai jamais entendu parler de la clôture transitive d'un graphe pondéré (sauf éventuellement pour l'algorithme de Floyd). On peut imaginer que c'est le graphe dont les arêtes de A vers B sont les chemins de A à B dans le graphe initial, pondérés par leurs longueurs.

D'accord, haut taon pour moi ! Je suppose que les poids sont tous des entiers positifs et qu'il y a toujours au plus une arête d'un nœud vers un autre. Je ne sais pas s'il existe un algorithme standard. blo yhg

si c'est aussi compliqué que ça .. c'est surement moi qui ai mal compris .. peut etre que les poids des arretes ne sont pas pris en compte .. dans ce cas c'est comment ??

Je ne sous-entendais pas que c'était compliqué (en tout cas pour une complexité en temps de O(E×V×L) avec E le nombre d'arêtes et V le nombre de nœuds).

Tu n'as pas répondu à ma question. Je te conseille de commencer par écrire une solution sans prendre en compte son efficacité, et d'ensuite essayer de l'améliorer.

je ne sais pas d'oü commencé

Dans ce cas, reviens aux définitions des termes de la question. La question est de savoir s'il existe un chemin tel que sa longueur est L.

Un « il existe », c'est comme un gros « ou ». Si je te dis « il existe élément de {1,2,3} dont le carré est plus grand que 2 », ça veut dire « 1² ≥ 2 ou 2² ≥ 2 ou 3^2 ≥ 2 ». Essaie de faire pareil avec tes chemins : tu les prends tous, et tu regardes s'il y en a un qui satisfait la propriété demandée. Alors, bien sûr, il y en a une infinité, donc tu ne peux pas les prendre tous.

merci @blo yhg

je pense que je vais juste utiliser " M^L !=0 alors il existe un chemin de longueur L " meme si ce n'est pas trés convaicant comme réponse .. puisque cette fonction ne sera pas utilisée dans les parties suivantes

C'est faux, surtout. Je pense que tu peux dans un premier temps laisser de côté cette exponentiation de matrices, ce n'est pas primordial.

Pour commencer, peux-tu écrire un algorithme qui dit si oui ou non il existe un chemin de longueur L partant d'un certain nœud donné ? Si tu n'y arrives toujours pas, prends le cas particulier où tous les arcs ont une longueur de 1.