Théorie des graphes et algorithmes

On vient de voir que dans le cas d'un graphe biparti, on peut utiliser le graphe biparti étendu et l'algorithme de Ford et Fulkerson pour trouver un couplage maximal.

Dans le module de base sur la théorie des graphes, on avait également vu une autre équivalence de problèmes : la recherche d'un couplage maximal dans un graphe biparti et également équivalent à la recherche d'un nombre maximal de cases deux à deux indépendantes dans la matrice booléenne correspondant au graphe biparti.

Et pour ceux qui ont travaillé la dualité dans les modules d'enseignement de la programmation linéaire, la recherche d'une coupe minimale sur le graphe bi-parti étendu est équivalent à la recherche d'un support minimal en nombre de lignes et de colonnes sur la matrice booléenne correspondant au graphe biparti.

Nous pouvons maintenant expliquer comment on obtient l'algorithme de recherche des cases indépendantes dans un tableau en utilisant tout simplement l'algorithme de Ford et Fulkerson au graphe bi-parti étendu correspondant au tableau de cases autorisées et interdites.

On commence avec un flot nul, soit aucune case affectée dans le tableau.

Méthode du Nord Ouest :

-----------------------------

Elle consiste à construire un premier flot de manière systématique en n'utilisant que des chemins.

Un chemin qui passe par le premier point et le premier de ses successeurs (une case affectée sur la première ligne).

Un chemin qui passe par le deuxième point et le premier de ses successeurs non encore utilisés s'il en reste (une case affectée au plus sur la deuxième ligne ne correspondant pas à une colonne utilisée par la première ligne).

...

Un chemin qui passe par le k^ième point et le premier de ses successeurs non encore utilisés s'il en reste (une case affectée au plus sur la k^ième ligne ne correspondant pas à une colonne utilisée pour une ligne précédente).

----------------------------

Quand la méthode du Nord Ouest s'arrête, il n'existe plus aucun chemin allant de la source au puits et permettant d'améliorer le flot. Il faut donc maintenant rechercher des chaînes améliorantes par une technique de marquage.

Depuis la source, on peut marquer les points du premier ensemble lorsque l'arc est non saturé entre la source et le point, comme la capacité est unitaire et le flot entier, cela signifie que le flot est nul sur cet arc, ce qui implique qu'il n'y a pas de flot sur les arcs qui sortent de ce point et donc aucun arc dans le couplage ni aucun un sur la ligne associée de la matrice.

Sur le tableau, on peut marquer les lignes qui ne contiennent pas de 1.

Dans l'algorithme du flot utilisant une file, après cette opération, la file contient toutes les lignes que l'on vient de marquer depuis la source.

Si on ne peut marquer aucune ligne, le flot, le couplage et l'affectation sont tous les trois maximaux, la coupe minimale est entre la source et le premier ensemble de points et le support minimal contient toutes les lignes.

Comme les capacités sont infinies entre les points du premier ensemble et les points du deuxième ensemble, on peut marquer un point y du deuxième ensemble s'il existe un arc dans le graphe biparti entre un point marqué et le point y.

Sur la matrice, cela signifie qu'à partir le la ligne Li marquée, on peut marquer la colonne Cj s'il existe un arc qui va du point i du premier ensemble au point j du deuxième ensemble, c'est-à-dire que la case (i,j) est une case autorisée.

On marque donc toutes les colonnes non encore marquées (la première fois, il n'y en a aucune) qui contiennent une case autorisée sur une ligne marquée et on marque la colonne avec la première ligne examinée qui permet de la marquer.

Si on n'a pu marquer aucune nouvelle colonne à partir des lignes marquées, cela signifie que le marquage ne peut plus progresser et que le flot, le couplage et l'affectation sont tous les trois maximaux.

La coupe minimale sépare les points marqués des points non marqués.

Le support minimal comporte les lignes non marquées et les colonnes marquées.

Dès l'instant où on marque un point du deuxième ensemble qui est origine d'un arc non saturé qui mène au puits, cela signifie que l'on peut propager l'amélioration du flot jusqu'au puits et donc que l'on a trouvé une chaîne améliorante.

Dans la matrice, ce cas se produit lorsque l'on arrive à marquer une colonne qui ne contient aucun 1.

Si toutes les nouvelles colonnes marquées contiennent un 1, alors on passe au marquage des lignes.

Pour toute colonne j nouvellement marquées lors du marquage des lignes et qui contient exactement un 1 sur la ligne i, on marque la ligne i avec Cj (où le numéro de la colonne j) si la ligne i n'est pas déjà marquée.

Si lors du marquage des lignes à partir des colonnes, on n'arrive à marquer aucune nouvelle ligne, alors le flot, le couplage et l'affectation sont maximaux et comme dans le cas de l'arrêt lors du marquage des colonnes, on obtient la coupe minimale et le support minimal à partir des marques.

Si à partir d'une ligne Li, on arrive à marquer une colonne Cj qui ne contient aucun 1 dans toute la colonne,

alors on ajoute un 1 dans la case (i,j).

Puis on cherche la colonne qui a permis de marquer la ligne i : Cj = marque_ligne(i),

on ôte le 1 qui se trouvait dans la case (i,j).

Puis on cherche la ligne qui a permis de marquer la colonne j : Li= marque_colonne(j).

on ajoute un 1 dans la case (i,j).

Puis on cherche qui a permis de marquer la ligne i : si c'est la source, on a terminé l'examen de la chaîne améliorante, si ce n'est pas la source,

alors on cherche la colonne qui a permis de marquer ligne i, etc.

Après l'utilisation de la chaîne améliorante, les anciennes marques n'ont plus aucune signification, il ne faut donc pas oublier de les effacer.

Vous pouvez dérouler l'algorithme de Ford et Fulkerson ainsi obtenu dans le cas particulier du graphe biparti sur les tableaux de cases indépendantes liées à des problèmes d'affectation.