Retour
Chemins 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. Le nom de la variable logique est composé de la lettre du sommet de départ suivi de la lettre du sommet d'arrivé. Exemple ad pour l'arc allant de A à D Solution locale à un sommet :

On montre que la solution locale à un sommet est :
(OU Exclusif des arcs allant vers le sommet) ET (OU Exclusif des arcs quittant le sommet) =1.

Si il n'y pas d'arc entrant ou pas d'arc sortant, on a respectivement :
(OU Exclusif des arcs quittant le sommet) =1.
(OU Exclusif des arcs allant vers le sommet) =1.


Le OU Exclusif de n variables v1 à vn est noté OUEXn(v1,v2,..,vn)

Fonction OU Exclusif

Solution globale :

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

Reprenons le dessin du graphe :


Solution locales :
En A : sla:=OUEX3(ab,ad,ae)
En B : slb:=OUEX3(ab,db,gb).OUEX2(bc,bg)
En C : slc:=OUEX1(bc).OUEX2(cd,cf)
En D : sld:=OUEX4(ad,cd,fd,gd).OUEX2(db,dg)
En E : sle:=OUEX2(ae,fe)
En F : slf:=OUEX1(cf).OUEX3(fd,fe,fg)
En G : slg:=OUEX3(bg,dg,fg).OUEX2(gb,gd)

Cependant, rien n'interdit dans ces équations d'arriver et de rapartir par le même chemin. Pour interdire cela, posons la condition pour tout arc à double sens :
arcsens1.arcsens2=0
soit
/arcsens1+/arcsens2=1
Il faut donc faire le ET de cette condition pour tous les arc1) Problème à résoudre.

Soit le graphe suivant :
s à double sens, soit ici :
Sens=(/bg+/gb).(/dg+/gd)

La solution globale est donnée par : sla.slb.slc.sld.sle.slf.slg.Sens=1
Le résultat du calcul est :
/ab./ad.ae./gb.db./bg.bc./cd.cf.gd./fd./dg./fe.fg+ /ab./ad.ae.gb./db./bg.bc./cd.cf./gd.fd.dg./fe./fg+ /ab.ad./ae.gb./db./bg.bc./cd.cf./gd./fd.dg.fe./fg=1
Ce qui correspond respectivement aux graphes suivants :



/ab./ad.ae./gb.db./bg.bc./cd.cf.gd./fd./dg./fe.fg : Il y a 6 arcs, le chemin passe par tous les sommets, mais il n'est pas continu.

/ab./ad.ae.gb./db./bg.bc./cd.cf./gd.fd.dg./fe./fg : Il y a 6 arcs, le chemin passe par tous les sommets, mais il n'est pas continu.

/ab.ad./ae.gb./db./bg.bc./cd.cf./gd./fd.dg.fe./fg : Solution correcte, le chemin a 6 arcs, est continu, et passe par tous les sommets.

Retour