Graphes bipartis et couplage
Fondamental : Théorème
Un graphe G=(X,E) est un graphe bi-parti si et seulement si pour tout point x de X, on a di(x).de(x)=0.
X1={x/x∈X et di(x)=0} et X2=X-X1, est un des partitionnement possible de X, il est unique s'il n'y a pas de points isolés tels que di(x) = de(x)=0.
Exemple :
Les points de X1 sont représentés par des numéros placés dans des carrés roses.
Les points de X2 sont représentés par des lettres placées dans des ronds bleus.
Remarque :
Dans un graphe bi-parti :
Tout chemin est vide ou réduit à un seul arc.
Toute chaîne est alternée d'arcs appartenant au graphe et d'arcs appartenant au graphe inverse.
Il y a autant de composantes fortement connexes que de points.
Le graphe réduit est isomorphe et même identique au graphe initial.
Il n'y a ni circuit, ni boucle, mais il peut y avoir des cycles.
Définition : Arcs adjacents
Dans un graphe, deux arcs sont dits adjacents s'ils ont une de leurs extrémités communes.
Définition : Couplage
On appelle couplage un sous-ensemble d'arcs deux à deux non adjacents.
Exemple de couplage dans un graphe bi-parti
A gauche, un graphe bi-parti, à droite, les arcs rouges constituent un couplage sur ce graphe.
On n'a pas fait figurer le sens des arcs sur la représentations graphiques car on sait que tous les arcs vont des Ai vers les Bj.
Définition : Sommets saturés par un couplage
Les sommets saturés par un couplage sont les sommets qui sont extrémités des arcs du couplage. Les autres sommets sont insaturés.
Définition :
Dans un graphe bi-parti B=(X1, X2, E), on dit que l'on peut coupler X1 sur X2, s'il existe un couplage où tous les points de X1 sont saturés.
Fondamental : Théorème de König-Hall
Dans un graphe bi-parti B=(X1, X2, E), on peut coupler X1 sur X2, si quelque soit A, sous-ensemble contenu dans X1, Le nombre d'éléments dans A est inférieur ou égal au nombre d'éléments de l'ensemble de tous les successeurs des points de A.
Définition : Chaîne alternée améliorante d'un couplage
On appelle chaîne alternée améliorante d'un couplage une chaîne telle que le premier arc n'appartient pas au couplage, l'arc suivant appartient couplage, l'arc suivant n'appartient pas au couplage, ... , le dernier arc n'appartient pas au couplage.
Cette chaîne contient au minimum un arc.
Ces deux extrémités sont des sommets insaturés.
Fondamental : Théorème d'optimalité
Un couplage d'un graphe bi-parti est maximum si et seulement s'il n'existe pas de chaînes alternées améliorantes pour ce couplage.
Remarque : Représentation matricielle d'un graphe bi-parti
Comme il n'y a, en prenant les notations du dernier exemple graphique, que des arcs allant des Ai vers les Bi et que le reste de la matrice en variable 0-1 est rempli de 0, on peut ne représenter que la partie intéressante de cette matrice.
Exemple de représentation matricielle d'un graphe-biparti
Les lignes correspondent aux Ai et les colonnes correspondent aux Bj.
Définition : Maximum de cases indépendantes dans un tableau
On considère une matrice en variables 0-1 où 1 signifie que la case est autorisée et 0 que la case est interdite.
Le problème de recherche d'un maximum de cases indépendantes dans un tableau consiste à retenir le plus possible de cases autorisées de telle sorte qu'il y a au plus une case retenue par ligne et par colonne.
Fondamental :
Recherche un maximum de cases indépendantes dans un tableau à cases autorisées et à cases interdites est équivalent à rechercher un couplage maximum sur un graphe bi-parti dont la représentation matricielle est le tableau des cases autorisées.
Remarque :
Une chaîne améliorante sur le tableau de cases indépendantes consiste à partir d'une ligne qui ne contient pas de 1, à chercher une colonne autorisée où on peut donc ajouter un 1, à rechercher s'il y a déjà un 1 sur cette colonne, si oui à retirer ce 1 et à chercher à le mettre ailleurs sur la ligne etc. jusqu'à trouver une colonne où il n'y avait pas encore de 1.
Cette procédure est utilisée dans l'animation qui vous est proposée ci-dessous.
Définition :
On appelle ensemble de sommets disjonctifs ou support d'un graphe bi-parti tout sous-ensemble de sommets tel que tout arc du graphe ait au moins une de ses extrémités dans le sous-ensemble de sommets. Tout arc est adjacent au support.
Définition :
On appelle support d'un tableau de cases autorisées tout sous ensemble de lignes et de colonnes tel que toute case autorisée correspond à une ligne ou à une colonne du support. On dit que la case autorisée est couverte par le support.
Remarque :
Un support d'un tableau de cases autorisées est également un support du graphe bi-parti défini par le tableau de cases autorisées.
Fondamental :
A tout couplage maximum on peut faire correspondre un support minimum.
ou
A tout sous ensemble maximum de cases indépendantes, on peut faire correspondre un support minimum en nombre de rangées (lignes + colonnes).
Remarque :
On peut utiliser une technique de marquage pour construire un algorithme qui recherche les chaînes améliorantes dans un graphe bi-parti jusqu'à ce qu'il ne soit plus possible de trouver des chaînes améliorantes.
Chaque fois que l'on trouve une chaîne améliorante, on échange les arcs du couplage et hors couplage le long de la chaîne alternée, ce qui permet d'augmenter le couplage d'un arc.
Le même algorithme peut être exécuté sur la matrice en variables 0-1 du graphe bi-parti, en considérant le problème comme la recherche d'un maximum de case indépendante dans un tableau.
Cet algorithme est présenté dans l'animation qui suit.
Le marquage permet de mettre en évidence le support minimal.
Animation de recherche d'un maximum de cases indépendantes dans un tableau
Cliquez sur Anim, choisissez un tableau en utilisant les triangles derrière précédent ou devant suivant, puis laissez vous guider par les explications fournies dans l'animation. Il est à noter que l'onglet Déf est particulièrement intéressant pour cette animation.
