Retour
Chemin passant une fois par chaque sommet


1) Problème à résoudre.

Soit le graphe suivant :

Le problème : aller de A en E en passant une fois par chaque sommet.

Les raisons logiques du sytème de description ci-dessous ne seront pas démontrées ici.

Arc et algèbre de Boole :

Associons à chaque arc une variable logique. Chaque arc a un ou deux sens. Chemin et algèbre de Boole : Donc pour ajouter une arc à un chemin, il suffit de faire le ET du chemin et de l'arc

Solution locale à un sommet :

On montre que la solution locale à un sommet est : (OU des arcs allant vers le sommet)ET(OU des arcs quittant le sommet)
Si il n'y pas d'arc entrant ou pas d'arc sortant, on a respectivement le (OU des arcs quittant le sommet) ou le (OU des arcs allant vers le sommet)

Solution globale :

C'est le ET des solutions locales de chaque sommet.

Reprenons le dessin du graphe :


Solution locales :
En A : sla:=a+b+c
En B : slb:=(a+/d+h).(d+e)
En C : slc:=(e).(f+g)
En D : sld:=(g+b+/i+j).(h+i)
En E : sle:=(c+k)
En F : slf:=(f).(j+k+l)
En G : slg:=(l+i+d).(/i+/d)

La solution globale est donnée par : sla.slb.slc.sld.sle.slf.slg
Le résultat du calcul est :
a./d.e.h.f.g.k.l + a./d.e.f.g.i.k + a./d.e.h.f.j.k.l + a./d.e.f.i.j.k + a.d.e.h.f./i.k + a.e.h.f./i.k.l + b.c./d.e.f.i.l + b./d.e.f.i.k + b.c./d.e.h.f.l + b./d.e.h.f.k.l + b.d.e.h.f./i.k + b.e.h.f./i.k.l + c./d.e.h.f.g.l + c./d.e.f.g.i.l + c./d.e.f.g.i.k + c./d.e.h.f.j.l + c./d.e.f.i.j + c.d.e.h.f./i.j + c.d.e.h.f./i.k + c.e.h.f./i.l
On sait que le chemin que l'on cherche ne comporte que 6 arcs. Donc en gardant les termes à 6 variables logiques, il reste :
b./d.e.f.i.k + c./d.e.f.i.j + c.e.h.f./i.l
Ce qui correspond respectivement aux graphes suivants :


b./d.e.f.i.k : Solution correcte, le chemin a 6 arcs, est continu, et passe par tous les sommets.


c./d.e.f.i.j : Il y a 6 arcs, le chemin passe par tous les sommets, mais il n'est pas continu.


c.e.h.f./i.l : Il y a 6 arcs, le chemin passe par tous les sommets, mais il n'est pas continu.

Retour