Chemin le plus long

TBD à réordonner. Mettre avec Hamilton 2 ?

Ca où on sait faire :

• arbres
• acyclique pour chemin le plus long : et conséquence inattendue sr le BTP (pb d'ordonnancements. Aussi DFS !)

Cas particulier métrique et complet

1. pas simple : exhaustif avec backtrack + branch and bound

Ordonnancement

TBD DFS et Problème d’ordonnancements

TBD tri topologique dans un DAG avec un DFS + à la visite ajoute en fin de liste. Ensuite on regarde la liste à l'envers

Un problème d'ordonnancement peut se modéliser par un DAG nommé graphe de dépendances où si $xy$ est une arête alors il faut faire $x$ avant de pouvoir faire $y$.

Vous résolvez des problèmes d'ordonnancement tous les jours comme par exemple comment s'habiller le matin (voir graphe ci-après)

C'est encore un exemple où les contraintes sont locales et ou l'on cherche une solution globale.

NP-complétude

TBD Chemin le plus long ≥ chemin hamiltonien

Formalisons les problèmes du cycle hamiltonien dans ses versions orienté et non orienté :

Et faisons de même pour les chemins hamiltonien dans ses versions orienté et non orienté :

Les quatre problèmes ci-dessus sont clairement des problèmes de décisions de NP. Nous allons montrer qu'ils sont NP-complet par des réduction depuis le problème 3-SAT.

Chemin orienté hamiltonien

Pour transformer une instance de 3-SAT en une instance de recherche d'un chemin hamiltonien dans un graphe, il faut :

• encoder les différentes variables dans leur état 1 ou 0
• gérer les clause pour que tout ne soit pas possible
• s'assurer qu'il n'existe de chemin hamiltonien que si et seulement si le système est satisfiable.

Nous allons appliquer la réduction à l'exemple du problème 3-SAT.

Encodage des variables

Chaque variable est encodé par le sous-graphe suivant :

Il possède uniquement deux chemins passant par tous les sommets :

• $y_{i-1}x_iv_iv^1_iu^1_if^1_i\dots v^j_iu^j_if^j_i\dots v^m_iu^m_if^m_if_iy_i$ : le chemin vrai
• $y_{i-1}x_if_if^1_iu^1_iv^1_i\dots f^j_iu^j_iv^j_i\dots f^m_iu^m_iv^m_iv_iy_i$ : le chemin faux

Le graphe de toutes les variables est composé de l'union de tous ces graphes. Pour l'exemple cela donne :

Il possède $2^5$ chemin hamiltoniens selon que l'on passe par le chemin vrai ou le chemin faux pour chaque variable.

Encodage des clauses

On encode chaque clause $c_i = l_i^1 \lor l_i^2 \lor l_i^3$ par un sommet $c_i$ que l'on ajoute au graphe des variables et tels que ses voisins sont, pour $1\leq k \leq 3$ :

• $v^i_jc_i$ et $c_iu^i_j$ si $l_i^k = x_j$,
• $f^i_jc_i$ et $c_iu^i_j$ si $l_i^k = \overline{x_j}$,

Le graphe complet de l'exemple est :

Satisfiabilité

Si la conjonction de clause est satisfiable, il existe un chemin hamiltonien passant pas les chemins vrais des variables vraies, les chemins faux des variables fausses et passant par chaque clause pour un des littéral vrai de la clause. Pour l'exemple :

Réciproquement s'il existe un chemin hamiltonien :

• il passe par les chemins vrais ou les chemins faut de chaque variable
• il passe par une clause en passant par le vrai ou le faux

Notez que pour un chemin hamiltonien, si $v^j_ic_i$ est un arc (resp. $f^j_ic_i$), alors $c_iu^j_i$ en est un aussi, sinon $f^j_i$ (resp. $v^j_i$) ne peut être atteint. Cette construction justifie le fait que la clause est satisfaite pour un de ses littéraux (ceci montre qu'il faut 3 sommets v, f et u pour cette construction et qu'on ne peut s'en sortir qu'avec des sommets v et f).

On en conclut :

Circuit orienté hamiltonien

La précédente preuve s'applique de manière identique pour la recherche d'un circuit hamiltonien en ajoutant un arc de $y_n$ à $y_0$. On en conclut :

Cycle et chemins hamiltonien

On va montrer ici que la recherche d'un chemin (resp. circuit) hamiltonien dans un graphe orienté est équivalent à chercher un chemin (resp. cycle) hamiltonien dans un graphe. Pour cela on va associer à tout graphe dirigé un graphe.

On effectue la transformation suivante, pour chaque sommet du graphe orienté :

On en associe 3 dans le graphe non orienté associé, permettant de séparer les arcs entrant des arcs sortants :

Il est alors évident que si le graphe non orienté a un chemin (resp. cycle) hamiltonien, alors le graphe orienté possède également un chemin (resp. circuit) hamiltonien. La réciproque est aussi trivialement vrai ce qui montre que les problèmes orientés ou non orientés sont équivalent.

Chemin le plus long

La NP-complétude des chemins et cycles hamiltoniens nous permet de conclure qu'il est illusoire de tenter de trouver un algorithme efficace pour résoudre le problème du chemin le plus long :

Résoudre ce problème revient en effet clairement à résoudre le problème du chemin hamiltonien.

Notez comment une petite différence — remplacer sommet (hamiltonien) par arête (eulérien) — rend un problème soit très simple soit très compliqué à résoudre.

Il existe un cas où trouver un chemin le plu long est facile : dans les graphes orientés qui ne contiennent pas de circuit (souvent appelé DAG, direct acyclic graph).

On appelle tri topologique d'un graphe orienté $G = (V, E)$ un ordre total $<$ sur les sommets du graphe tel que $xy \in E$ implique $x < y$ dans l'ordre.

Entrée :
    - un graphe orienté G = (V, E)
    - un tri topologique V0 < ... < Vn des éléments de V
Initialisation :
    longueur(x) = 0 pour tout sommet x
    predecesseur(x) = x pour tout sommet x
    V' = {}, E' = {}
Algorithme :
    pour v allant de V0 à Vn:
        pour chaque voisin sortant w de v:
            si longueur(w) < longueur(v) + 1:
                longueur(w) = longueur(v) + 1
                predecesseur(w) = v
    soit a l'élément de V ayant la plus grande longueur
    chemin = [a]
    x = a
    tant que x est différent de predecesseur(x):
        x = predecesseur(x)
        ajoute x au début de chemin
Retour :
    chemin

Applications

Voyageur de commerce

Problème vu sous l'angle algorithmique dans le cours d'algorithmie :

TBD formaliser ça en graphe.