200
Recherche opérationnelle
Quant aux cycles, on les a déjà définis et utilisés pour des graphes non orientés. Mais on
peut aussi définir des cycles sur un graphe orienté : il suffit de désorienter les arcs. Un
cycle sur un graphe orienté est donc constitué d'une suite d'arcs qui ne sont pas
forcément orientés dans le même sens.
Démontrons le lemme suivant :
b) Lemme de MINTY
Ce lemme, qui a priori n'a rien à voir avec les flots, mais nous sera très utile par la suite,
s'énonce de la façon suivante :
Soit un graphe
, dont on colorie arbitrairement certains arcs soit en noir, soit en
rouge, soit en vert (les autres restant incolores). On suppose qu'il existe un arc noir que
nous appellerons . Alors une seule des propositions suivantes est vérifiée :
a) il passe par
un cycle ne contenant pas d'arcs incolores, avec tous les arcs noirs
orientés dans le même sens, tous les arcs verts orientés dans le sens contraire et les arcs
rouges orientés dans un sens quelconque.
b)
appartient à un cocycle ne contenant pas d'arcs rouge avec tous les arcs noirs
orientés dans le même sens et tous les arcs verts orientés dans le sens contraire.
Démontrons ce lemme :
Appelons respectivement et l'extrémité initiale et l'extrémité terminale de .
1. on marque
2. si le sommet est marqué, et si l'arc est noir, alors on marque
3. si le sommet est marqué, et si l'arc est vert, alors on marque
4. si ou est marqué, et si l'arc est rouge, alors on marque ou .
On réitère cette procédure jusqu'à ce qu'on ne puisse plus marquer de sommet. Deux cas
alors se produisent :
a) Par cette procédure de marquage, on arrive à marquer . Ceci veut dire qu'il existe au
moins une chaîne de sommets marqués entre et (donc un cycle partant de si on
ajoute l'arc ), telle que tout sommet sur cette chaîne est marqué grâce au sommet
précédent. Il n'y a donc pas d'arc incolore sur ce cycle. Par ailleurs, les arcs noirs sont
tous dans le même sens (sens
) et les arcs verts dans le sens contraire. Les arcs
rouges sont dans un sens quelconque.
b) On ne parvient pas à marquer
par cette procédure de marquage appliquée
systématiquement. Appelons alors
l'ensemble des sommets du graphe marqués et
l'ensemble des sommets non marqués.
Recherche opérationnelle
Quant aux cycles, on les a déjà définis et utilisés pour des graphes non orientés. Mais on
peut aussi définir des cycles sur un graphe orienté : il suffit de désorienter les arcs. Un
cycle sur un graphe orienté est donc constitué d'une suite d'arcs qui ne sont pas
forcément orientés dans le même sens.
Démontrons le lemme suivant :
b) Lemme de MINTY
Ce lemme, qui a priori n'a rien à voir avec les flots, mais nous sera très utile par la suite,
s'énonce de la façon suivante :
Soit un graphe
, dont on colorie arbitrairement certains arcs soit en noir, soit en
rouge, soit en vert (les autres restant incolores). On suppose qu'il existe un arc noir que
nous appellerons . Alors une seule des propositions suivantes est vérifiée :
a) il passe par
un cycle ne contenant pas d'arcs incolores, avec tous les arcs noirs
orientés dans le même sens, tous les arcs verts orientés dans le sens contraire et les arcs
rouges orientés dans un sens quelconque.
b)
appartient à un cocycle ne contenant pas d'arcs rouge avec tous les arcs noirs
orientés dans le même sens et tous les arcs verts orientés dans le sens contraire.
Démontrons ce lemme :
Appelons respectivement et l'extrémité initiale et l'extrémité terminale de .
1. on marque
2. si le sommet est marqué, et si l'arc est noir, alors on marque
3. si le sommet est marqué, et si l'arc est vert, alors on marque
4. si ou est marqué, et si l'arc est rouge, alors on marque ou .
On réitère cette procédure jusqu'à ce qu'on ne puisse plus marquer de sommet. Deux cas
alors se produisent :
a) Par cette procédure de marquage, on arrive à marquer . Ceci veut dire qu'il existe au
moins une chaîne de sommets marqués entre et (donc un cycle partant de si on
ajoute l'arc ), telle que tout sommet sur cette chaîne est marqué grâce au sommet
précédent. Il n'y a donc pas d'arc incolore sur ce cycle. Par ailleurs, les arcs noirs sont
tous dans le même sens (sens
) et les arcs verts dans le sens contraire. Les arcs
rouges sont dans un sens quelconque.
b) On ne parvient pas à marquer
par cette procédure de marquage appliquée
systématiquement. Appelons alors
l'ensemble des sommets du graphe marqués et
l'ensemble des sommets non marqués.