Kurs-Liste Einloggen

Information

Author(s) Nikita Tyunyayev
Deadline Keine Frist
Abgabenlimit No limitation

Einloggen

Einloggen

Graphes 3 - Graphes bipartis et couplages

Graphes bipartis

Un graphe \(G = (N, R)\) est biparti s'il existe une partition \((A, B)\) de \(N\) telle que toutes les arêtes sont incidentes à un nœud de \(A\) et à un nœud de \(B\). On dit que \((A, B)\) est une bipartition de \(G\).

Rappel : un coloriage d'un graphe associe à chaque nœud une couleur, de telle sorte que deux nœuds adjacents ont des couleurs différentes. Un graphe (avec au moins une arête) est biparti si et seulement si son nombre chromatique vaut \(\chi(G) = 2\) : on peut le colorier avec deux couleurs, \(A\) étant l'ensemble des nœuds d'une couleur et \(B\) celui des nœuds de l'autre. C'est aussi le cas si et seulement si le graphe ne contient aucun cycle de longueur impaire (par exemple, \(\chi(C_{2n}) = 2\) et \(\chi(C_{2n+1}) = 3\)).

/course/LINFO1114/graphes_bipartis/bipartis.svg

À gauche, un graphe biparti colorié avec deux couleurs : \(A = \{0, 2, 4\}\) en bleu, \(B = \{1, 3, 5\}\) en orange. À droite, un graphe qui n'est pas biparti : le cycle \((0, 1, 2, 3, 4, 0)\) est de longueur 5.

Couplages

Dans un graphe biparti \((N, R)\), un couplage \(C\) est un sous-ensemble de \(R\) tel que chaque nœud est incident à au plus une arête de \(C\). Un couplage couvrant un ensemble de nœuds \(S \subset N\) est un couplage incident à tous les nœuds de \(S\), et un couplage parfait est un couplage couvrant \(N\) : chaque nœud de \(A\) est relié par une arête de \(C\) à exactement un nœud de \(B\), et inversement. Un couplage parfait ne peut donc exister que si \(|A| = |B|\).

Exemple d'application, l'affectation de tâches : \(A\) est un ensemble d'étudiants, \(B\) un ensemble de projets, et une arête relie chaque étudiant aux projets qui lui conviennent. Un couplage parfait attribue un projet différent à chaque étudiant.

/course/LINFO1114/graphes_bipartis/couplage.svg

Un couplage parfait (en vert) entre 5 étudiants et 5 projets.

Pour un ensemble de nœuds \(S\), on note \(V(S)\) le voisinage de \(S\) : l'ensemble des nœuds adjacents à un nœud de \(S\).

Théorème de Hall. Un graphe biparti de bipartition \((A, B)\) admet un couplage couvrant \(A\) si et seulement si \(|V(S)| \ge |S|\) pour tout \(S \subset A\). Si de plus \(|A| = |B|\), ce couplage est parfait.

Question 1: Le graphe est-il biparti ?

Écrivez une fonction est_biparti(n, edges) qui renvoie True si le graphe est biparti et False sinon.

Le graphe a n nœuds numérotés de 0 à n - 1, et edges est une liste de couples (u, v) : une arête (non orientée) entre u et v. Le graphe n'est pas forcément simple : une arête peut apparaître plusieurs fois, et une arête (u, u) est une boucle. La définition ci-dessus s'applique telle quelle : une boucle n'est incidente qu'à un seul nœud, donc un graphe qui contient une boucle n'est pas biparti.

Par exemple, le graphe biparti dessiné à gauche plus haut (un cycle de 6 nœuds et l'arête 0 - 3) s'écrit :

n = 6
edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0), (0, 3)]
est_biparti(n, edges)   # True

Et voici un graphe de 3 nœuds où l'arête 0 - 1 apparaît deux fois (dans les deux sens) et où (2, 2) est une boucle sur le nœud 2 :

n = 3
edges = [(0, 1), (1, 0), (1, 2), (2, 2)]
est_biparti(n, edges)   # False, à cause de la boucle

Idée. Cherchez un coloriage avec deux couleurs. Coloriez un premier nœud en bleu, puis parcourez le graphe (en largeur ou en profondeur) : chaque nœud adjacent à un nœud bleu doit être orange, et inversement. Si une arête relie deux nœuds de même couleur, le graphe n'est pas biparti. Commencez par construire, pour chaque nœud, la liste des nœuds adjacents.

Attention
  • Le graphe n'est pas forcément connexe : un parcours à partir du nœud 0 ne visite pas forcément tous les nœuds. Le graphe est biparti si et seulement si chacune de ses composantes connexes l'est.
  • Un graphe qui contient une boucle (u, u) n'est pas biparti.

Évaluation. Votre fonction est testée sur des graphes bipartis et non bipartis, jusqu'à quelques centaines de nœuds (2 secondes par test). La note est le plus petit des deux taux de réussite (graphes bipartis reconnus, graphes non bipartis rejetés) : une fonction qui répond toujours la même chose obtient 0.

Question 2: Couplage parfait dans un graphe biparti

Écrivez une fonction couplage_parfait(A, B, edges) qui renvoie un couplage parfait du graphe biparti, ou None s'il n'en existe aucun.

(A, B) est la bipartition du graphe : A et B sont des listes de nœuds (des entiers ou des chaînes de caractères, sans élément commun) et edges est une liste de couples (a, b) avec a dans A et b dans B. Le couplage \(C\) est renvoyé sous la forme d'une liste de couples (a, b), qui doivent tous être des arêtes du graphe ; l'ordre de la liste n'a pas d'importance.

Algorithme des chemins augmentants. Associer chaque nœud de A au premier nœud adjacent encore libre ne suffit pas : un choix fait au début peut bloquer un nœud traité plus tard. On construit plutôt le couplage \(C\) nœud par nœud, en le corrigeant au besoin. Un nœud est libre s'il n'est incident à aucune arête de \(C\).

  1. Au départ, \(C\) est vide.

  2. Pour chaque nœud \(a \in A\), on cherche un chemin augmentant partant de \(a\) : un chemin \((a_0, b_1, a_1, b_2, \dots, a_{k-1}, b_k)\) avec \(a_0 = a\), dont les arêtes sont alternativement hors de \(C\) (entre \(a_{i-1}\) et \(b_i\)) et dans \(C\) (entre \(b_i\) et \(a_i\)), et qui se termine sur un nœud \(b_k\) libre.

    Concrètement, on essaie chaque nœud \(b\) adjacent à \(a\) et pas encore visité lors de cette recherche : si \(b\) est libre, c'est gagné ; sinon, l'arête de \(C\) incidente à \(b\) le relie à un nœud \(a'\), et on cherche récursivement un chemin augmentant partant de \(a'\), ce qui libérerait \(b\).

  3. Si un chemin augmentant est trouvé, on échange ses arêtes : celles qui étaient dans \(C\) en sortent, les autres y entrent. \(C\) reste un couplage et compte une arête de plus.

  4. S'il n'existe aucun chemin augmentant partant de \(a\), alors aucun couplage ne couvre \(A\) (on peut montrer qu'il existe alors un \(S \subset A\) avec \(|V(S)| < |S|\)) : il n'y a pas de couplage parfait.

Avec les listes de nœuds adjacents, chaque recherche coûte \(\mathcal{O}(|N| + |R|)\), donc l'algorithme coûte \(\mathcal{O}(|A| \cdot (|N| + |R|))\). Essayer toutes les associations possibles est beaucoup trop lent : les tests vont jusqu'à 200 + 200 nœuds (2 secondes par test).

Cas particuliers
  • Si \(|A| \neq |B|\), il n'y a pas de couplage parfait.
  • Si A et B sont vides, la liste vide [] est un couplage parfait.

Évaluation. La note est le plus petit des deux taux de réussite (couplages parfaits trouvés quand il en existe, None quand il n'en existe pas) : une fonction qui renvoie toujours None obtient 0. Pour les graphes sans couplage parfait, le feedback montre un ensemble \(S \subset A\) tel que \(|V(S)| < |S|\) (la condition du théorème de Hall n'est pas satisfaite).