Problèmes d'affectation et flots : rappels
Nous nous intéressons ici aux problèmes de flot appliqués aux graphes bipartis et nous commençons par rappeler les notions de base sur les graphes bi-partis déjà présentées dans le module de base sur la théorie des graphes.
Fondamental : Théorème
Un graphe G=(X,E) est un graphe biparti 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.
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 :
Un couplage est maximal s'il contient un maximum d'arcs.
RAPPEL
Dans le module de base, on utilisait déjà des chaînes améliorantes pour obtenir un couplage maximal.
En fait, on utilisait déjà l'algorithme de Ford et Fulkerson en l'appliquant au cas particulier des graphes bipartis et nous allons montrer comment on peut transformer le graphe biparti en un graphe muni d'une seule source, d'un seule puits et de capacité de telle sorte que le flot maximal sur ce graphe fournisse en fait un couplage maximal sur le graphe biparti.
Ajouts d'un source, d'un puits et de capacités supérieures à un graphe bi-parti
Comme dans un graphe biparti, il y a autant de sources que de points dans le premier ensemble de points et autant de puits que de points dans le deuxième ensemble de points, on commence par ajouter une seule source que l'on relie aux points du premier ensemble avec des arcs de capacité supérieure égale à 1 et un seul puits et on relie tous les points du deuxième ensemble de points au puits avec des arcs de capacité 1.
Les arcs du graphe biparti obtiennent une capacité illimitée.
Liens entre un couplage dans le graphe bi-parti et un flot à valeurs entières dans le graphe étendu
Avec l'hypothèse que les valeurs du flot sont des entiers, tous les flots sont égaux à 0 ou à 1 sur le graphe biparti étendu. En effet, les arcs qui sont adjacents à la source et au puits ont une capacité unitaire et comme il y a exactement un arc qui arrive en chaque point du premier ensemble, les arcs qui sortent de ces points ne peuvent pas avoir de flot strictement supérieur à 1.
Si on dispose d'un couplage, on peut construire un flot conservatif de capacité au plus égale à 1 en mettant un flot de 1 sur les arcs du couplage, un flot de 1 sur les arcs qui vont de la source aux origines des arcs du couplage et un flot de 1 sur les arcs qui vont des extrémités des arcs du couplage au puits.
Réciproquement, si on dispose d'un flot maximal, on obtient un couplage en sélectionnant les arcs qui ont un flot non nul entre les points du premier sous-ensemble et ceux du deuxième sous-ensemble, c'est bien un couplage car les flots sont entiers et que le flot qui arrive éventuellement dans un point du premier ensemble ne peut s'écouler que dans un seul des arcs du graphe biparti, de même il ne peut y avoir un flot que dans au plus un des arcs qui arrivent à un point du deuxième ensemble de points ; ceci assure que les arcs du couplage sont bien indépendants entre eux, leurs origines sont disjointes et leurs extrémités sont disjointes.
Fondamental :
Un couplage d'un graphe bi-parti est maximal si et seulement si le flot conservatif entier est maximal sur le graphe biparti étendu.
Remarque :
En conséquence, le couplage et le flot sont maximaux si et seulement si il n'existe pas de chaîne améliorante. Une chaîne améliorante du graphe biparti étendu est obtenu en ajoutant un arc de la source au premier point de la chaîne améliorante et un arc du dernier point de la chaîne améliorante au puits.
