Les graphes bipartis expliqués

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Ce qui rend un graphe biparti

Un graphe est biparti lorsque ses sommets peuvent être répartis en deux groupes de sorte que chaque arête aille d'un groupe à l'autre. Aucune arête ne peut rester à l'intérieur d'un groupe. Les deux groupes s'appellent les côtés ou les parties du graphe, et la répartition elle-même est une bipartition.

En symboles, un graphe G = (V, E) est biparti s'il existe des ensembles disjoints U et W avec U ∪ W = V tels que chaque arête a une extrémité dans U et l'autre dans W. Beaucoup de manuels écrivent le graphe sous la forme G = (U, W, E) pour garder la répartition sous les yeux. Rien n'exige que toutes les arêtes possibles entre les côtés soient présentes, et rien n'exige que les côtés aient la même taille. La seule règle est une interdiction : il n'y a aucune arête à l'intérieur de U ni aucune arête à l'intérieur de W. Dans le vocabulaire du guide sur les sommets et arêtes, les deux côtés sont des ensembles indépendants.

La propriété est facile à énoncer et étonnamment facile à manquer. Le graphe de gauche dans la figure ci-dessous est l'exemple fil rouge de tout cet article : huit sommets, neuf arêtes. Dessiné comme un anneau avec une corde, il ne ressemble à rien de particulier. Rangez les mêmes sommets en deux colonnes, et la structure devient évidente.

La liste des arêtes est assez courte pour être retenue :

V = {A, B, C, D, E, F, G, H}
E = {AB, AD, AF, BC, CF, DE, EH, FG, GH}          9 arêtes

U = {A, C, E, G}      W = {B, D, F, H}             chaque arête relie U à W

Deux cas limites méritent d'être réglés d'emblée. Une boucle relie un sommet à lui-même, donc ses deux extrémités sont du même côté, et un graphe avec une boucle n'est jamais biparti. Les arêtes parallèles ne changent rien : une seconde arête entre u et v passe d'un côté à l'autre exactement comme la première, et c'est l'une des propriétés que le guide sur les graphes simples et multigraphes range parmi celles que la multiplicité n'affecte pas. Pour un graphe orienté, la question porte sur le graphe non orienté sous-jacent, puisque la définition ne regarde jamais dans quel sens pointe une arête.

2. Deux couleurs, une bipartition

Peignez en bleu les sommets de U et en orange ceux de W. La définition dit alors que les deux extrémités de chaque arête ont des couleurs différentes, ce qui est exactement une coloration propre à deux couleurs. Les deux descriptions sont interchangeables :

Un graphe est biparti si et seulement s'il admet une coloration propre à deux couleurs. Son nombre chromatique vaut alors au plus 2 : exactement 2 s'il a au moins une arête, et 1 s'il n'en a aucune.

Le point de vue de la coloration explique un fait que le point de vue ensembliste cache. Dans un graphe biparti connexe, la bipartition est unique, à l'échange près des noms des deux côtés. Coloriez n'importe quel sommet en bleu et tous les autres sont imposés : un voisin doit être orange, un voisin de voisin bleu, et en général un sommet est bleu exactement quand sa distance au sommet de départ est paire. Il ne reste aucun choix nulle part. Dans l'exemple fil rouge, {A, C, E, G} face à {B, D, F, H} est la seule répartition possible.

Un graphe à plusieurs composantes se comporte autrement, car chaque composante peut être inversée indépendamment. Avec k composantes, il existe 2k colorations propres à deux couleurs et 2k−1 bipartitions distinctes, en comptant chaque sommet isolé comme une composante. La question « de quel côté se trouve le sommet v ? » a donc un sens à l'intérieur d'une composante et devient arbitraire d'une composante à l'autre. Un code qui stocke un seul côté global par sommet puis compare les côtés entre des morceaux non reliés compare des étiquettes choisies indépendamment.

3. Des graphes bipartis que vous connaissez déjà

Les graphes bipartis ne sont pas un sujet spécial relégué dans un chapitre tardif. Plusieurs des familles les plus familières sont bipartites, certaines pour des raisons qui demandent un instant de réflexion.

• Arbres et forêts. Un arbre n'a aucun cycle, donc rien ne peut mal tourner : enracinez-le n'importe où et coloriez chaque sommet selon que sa profondeur est paire ou impaire. Tout arbre est biparti, une conséquence de plus de la structure développée dans les arbres en théorie des graphes.
• Chemins et cycles pairs. Un chemin alterne les couleurs sur toute sa longueur. Un cycle avec un nombre pair de sommets aussi, et il se referme correctement. Un cycle avec un nombre impair ne le fait pas, comme le prouve la section suivante.
• Grilles et échiquiers. Coloriez la case de la ligne r et de la colonne c selon la parité de r + c et vous obtenez le motif de l'échiquier. Un pas vers une case voisine change la parité, donc le graphe de grille est biparti. Un saut de cavalier change une coordonnée de 1 et l'autre de 2, soit un total impair, donc le cavalier atterrit toujours sur la couleur opposée et le graphe du cavalier est lui aussi biparti.
• Hypercubes. Le graphe du cube Qn a pour sommets les chaînes de n bits, avec une arête entre deux chaînes qui diffèrent d'exactement un bit. Inverser un bit modifie de un le nombre de 1, donc colorier selon la parité de ce nombre fonctionne.
• Tout ce qui est construit à partir de deux sortes de choses. Candidats et postes, utilisateurs et produits, auteurs et articles, étudiants et cours. Quand chaque arête relie une sorte à l'autre, le graphe est biparti par construction.

L'exemple de l'échiquier a un dénouement classique. Retirez deux coins diagonalement opposés d'un échiquier de 8 sur 8. Peut-on paver les 62 cases restantes avec 31 dominos ? Chaque domino couvre deux cases voisines, une de chaque couleur. Les deux coins retirés ont la même couleur, donc l'échiquier compte maintenant 30 cases d'une couleur et 32 de l'autre, et aucun pavage ne peut exister. En termes de graphes, un pavage par dominos est un couplage parfait dans le graphe de grille, un couplage parfait dans un graphe biparti exige des côtés égaux, et ces côtés sont inégaux. Le casse-tête a été discuté par le philosophe Max Black en 1946 puis rendu célèbre par Martin Gardner ; il reste l'un des arguments les plus élégants pour montrer qu'il vaut la peine de repérer la bipartition.

Tout aussi utiles sont les graphes qui ne sont pas bipartis. Tout graphe contenant un triangle échoue, car trois sommets deux à deux adjacents exigent trois couleurs. Cela exclut tout graphe complet Kn avec n ≥ 3, et cela exclut aussi les sept ponts de Königsberg : la rive nord, l'île et l'île de l'est forment un triangle. Le graphe de Petersen échoue sans contenir le moindre triangle, parce qu'il est rempli de cycles de longueur 5.

4. Le théorème de Kőnig : aucun cycle impair

Les triangles sont un obstacle, mais pas le véritable. Le véritable obstacle, c'est tout cycle de longueur impaire, et c'est le seul qui existe.

Théorème. Un graphe est biparti si et seulement s'il ne contient aucun cycle de longueur impaire.

Le résultat est dû à Dénes Kőnig. Asratian, Denley et Häggkvist le font remonter à son article de 1916 dans les Mathematische Annalen, et il apparaît avec sa preuve dans son livre de 1936, Theorie der endlichen und unendlichen Graphen, le premier manuel de théorie des graphes (le même livre que celui évoqué dans l'article sur les graphes finis et infinis). Les deux sens de la preuve sont courts, et le second est un algorithme déguisé.

Biparti implique aucun cycle impair. Parcourez un cycle v0, v1, …, vk−1 et revenez à v0. Chaque pas change la couleur, donc vi a la même couleur que v0 exactement quand i est pair. L'arête qui ferme le cycle, de vk−1 à v0, ne relie deux couleurs différentes que si k − 1 est impair, c'est-à-dire seulement si la longueur du cycle k est paire.

Aucun cycle impair implique biparti. Travaillez composante par composante et choisissez une racine quelconque r. Coloriez chaque sommet selon la parité de sa distance à r. Supposons qu'une arête uv relie deux sommets de même couleur, de sorte que d(u) et d(v) ont la même parité. Suivez un plus court chemin de r à u, franchissez l'arête jusqu'à v, puis suivez un plus court chemin de v pour revenir à r. Cette marche fermée a pour longueur d(u) + d(v) + 1, qui est impair.

Une marche fermée n'est pas encore un cycle, car elle peut repasser par des sommets, et c'est l'étape que les preuves négligentes sautent. Un petit lemme la répare : toute marche fermée de longueur impaire contient un cycle de longueur impaire. Si la marche repasse par un sommet, coupez-la à cet endroit en deux marches fermées plus courtes ; leurs longueurs ont une somme impaire, donc l'une d'elles est impaire, et une récurrence sur la longueur termine le travail. Le cycle impair contredit l'hypothèse, donc une telle arête n'existe pas et la coloration par distances est propre.

Le panneau central de la figure contient le piège à retenir. Le cycle à 5 sommets est sans triangle et pourtant non biparti. « Pas de triangle » est une condition nécessaire, et très loin d'être suffisante. Toute longueur impaire compte.

L'exemple fil rouge passe le test. Ses cycles ont pour longueurs 4 (A, B, C, F), 6 (A, D, E, H, G, F) et 8 (l'anneau extérieur), toutes paires. Deux corollaires simples sont bons à avoir en tête. Supprimer des arêtes ou des sommets ne peut jamais créer de cycle impair, donc tout sous-graphe d'un graphe biparti est biparti. Ajouter une seule arête peut en revanche détruire la propriété, comme le montre la section suivante.

5. Tester un graphe en temps linéaire

La seconde moitié de la preuve est une procédure. Lancez un parcours en largeur depuis n'importe quel sommet, donnez à chaque sommet nouvellement découvert la couleur opposée à celle de son parent, et surveillez chaque arête examinée. Si une arête a un jour la même couleur à ses deux extrémités, le graphe n'est pas biparti. Si le parcours se termine sans que cela arrive, les couleurs forment une bipartition valide. Recommencez depuis un sommet non colorié jusqu'à ce que toutes les composantes aient été parcourues.

Un bon test fait plus que répondre oui ou non. Il renvoie un certificat vérifiable de façon indépendante : la 2-coloration quand la réponse est oui, et un véritable cycle impair quand la réponse est non. La fonction ci-dessous fait les deux.

from collections import deque

def bipartite_or_odd_cycle(graph):
    """Renvoie (True, colour) ou (False, odd_cycle) pour un graphe non orienté."""
    colour, parent, depth = {}, {}, {}
    for start in graph:                      # toutes les composantes, pas une seule
        if start in colour:
            continue
        colour[start], parent[start], depth[start] = 0, None, 0
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if v not in colour:          # arête d'arbre : v reçoit l'autre couleur
                    colour[v], parent[v], depth[v] = 1 - colour[u], u, depth[u] + 1
                    queue.append(v)
                elif colour[v] == colour[u]: # même couleur aux deux bouts : cycle impair
                    return False, odd_cycle(u, v, parent, depth)
    return True, colour

def odd_cycle(u, v, parent, depth):
    # u et v sont à la même profondeur BFS ; remonter jusqu'à la rencontre des chemins.
    left, right = [u], [v]
    while u != v:
        u, v = parent[u], parent[v]
        left.append(u)
        right.append(v)
    return left + right[-2::-1]              # u ... rencontre ... v, fermé par l'arête v-u

graph = {
    'A': ['B', 'D', 'F'], 'B': ['A', 'C'], 'C': ['B', 'F'], 'D': ['A', 'E'],
    'E': ['D', 'H'], 'F': ['A', 'C', 'G'], 'G': ['F', 'H'], 'H': ['E', 'G'],
}
ok, colour = bipartite_or_odd_cycle(graph)
print(ok, sorted(v for v in colour if colour[v] == 0))
# True ['A', 'C', 'E', 'G']

graph['C'].append('E'); graph['E'].append('C')   # une arête supplémentaire
print(bipartite_or_odd_cycle(graph))
# (False, ['C', 'B', 'A', 'D', 'E'])

L'extraction du cycle repose sur une propriété du parcours en largeur : chaque arête relie deux sommets dont les profondeurs diffèrent d'au plus un. Deux sommets de même couleur ont des profondeurs de même parité, donc une arête en conflit relie toujours deux sommets à la même profondeur. En remontant leurs pointeurs vers les parents au même rythme, on atteint donc le sommet de rencontre au même moment des deux côtés. Si les deux remontées font chacune t pas, le cycle a 2t + 1 arêtes, un nombre impair par construction.

Voici ce qui se passe sur l'exemple fil rouge, puis après l'ajout d'une arête de C à E :

BFS depuis A      niveau 0 : A    niveau 1 : B, D, F    niveau 2 : C, E, G    niveau 3 : H
                  chaque arête relie des niveaux voisins   → biparti, couleur 0 = {A, C, E, G}

ajout de C-E      C et E sont tous deux au niveau 2, donc de même couleur
                  remontée depuis C : C, B, A    depuis E : E, D, A    rencontre en A
                  cycle impair C, B, A, D, E    5 arêtes

Chaque sommet entre une fois dans la file et chaque arête est examinée deux fois, une fois depuis chaque extrémité, donc le test s'exécute en temps O(V + E). C'est aussi rapide que la lecture du graphe. Un parcours en profondeur fonctionne aussi bien en principe, mais un DFS récursif en Python bute sur la limite de récursion par défaut de 1 000 sur un long chemin, et c'est l'une des raisons pour lesquelles la version itérative en largeur est le choix par défaut le plus sûr.

Une variante mérite d'être connue. Si les arêtes arrivent une par une et que vous devez savoir après chaque insertion si le graphe est encore biparti, relancer le parcours est du gaspillage. Une structure union-find qui enregistre en plus la parité de chaque sommet par rapport à sa racine répond à la question en temps amorti presque constant par arête : relier deux sommets qui partagent déjà une racine n'est permis que si leurs parités diffèrent.

6. Graphes bipartis complets et le plafond n²/4

Le graphe biparti complet Km,n a m sommets d'un côté, n de l'autre, et chacune des m × n arêtes possibles entre les côtés. Il est aux graphes bipartis ce que Kn est aux graphes en général : le membre le plus dense de la famille pour des tailles de côtés données.

Deux membres ont un nom propre. K1,n est l'étoile, un centre relié à n feuilles, et c'est aussi un arbre. K3,3 est le graphe des trois maisons de la vieille énigme qui demande de relier trois maisons à trois services publics sans qu'aucune ligne ne se croise. L'énigme n'a pas de solution : le théorème de Kuratowski de 1930 dit qu'un graphe est planaire exactement quand il ne contient aucune subdivision de K5 ou de K3,3, et K3,3 est l'une des deux formes interdites.

La bipartition donne une preuve en une ligne que K3,3 n'est pas planaire. Dans un dessin sans croisement, chaque face est entourée par une marche fermée d'arêtes. Un graphe biparti n'a pas de triangle, donc dans un graphe biparti planaire simple et connexe ayant au moins trois sommets, le bord de chaque face compte au moins 4 arêtes. Chaque arête est comptée deux fois au total sur l'ensemble des bords de faces, ce qui donne 4f ≤ 2m. En reportant dans la formule d'Euler v − m + f = 2 on obtient

m ≤ 2v − 4        pour un graphe biparti planaire simple et connexe avec v ≥ 3

K3,3 :  v = 6,  m = 9,  mais 2v − 4 = 8        donc aucun dessin planaire n'existe

Une deuxième borne classique concerne la densité. Si un côté a k sommets et l'autre n − k, il y a au plus k(n − k) arêtes, et ce produit est maximal quand les côtés sont aussi égaux que possible. Un graphe biparti à n sommets a donc au plus ⌊n²/4⌋ arêtes, valeur atteinte par K⌊n/2⌋,⌈n/2⌉. Mantel a prouvé en 1907 que le même plafond vaut pour tout graphe sans triangle, le graphe biparti complet équilibré étant le seul graphe qui l'atteint. C'est un écho frappant au piège de la section 4 : les graphes sans triangle ne sont pas forcément bipartis, et pourtant le graphe sans triangle le plus dense l'est toujours. L'exemple fil rouge a 9 arêtes pour un plafond de 16, le nombre d'arêtes de K4,4.

Les degrés obéissent à une version plus fine du lemme des poignées de main. Chaque arête a exactement une extrémité de chaque côté, donc

∑ deg(u) pour u dans U  =  |E|  =  ∑ deg(w) pour w dans W

exemple :  3 + 2 + 2 + 2  =  9  =  2 + 2 + 3 + 2

Une conséquence rapide : si tous les sommets ont le même degré k ≥ 1, alors k|U| = k|W|, donc un graphe biparti régulier a toujours deux côtés de même taille. Ce fait est le premier pas vers les résultats sur les couplages de la section suivante.

7. Couplages : pourquoi les graphes bipartis comptent

Un couplage est un ensemble d'arêtes dont deux quelconques ne partagent aucun sommet. Dans un graphe biparti, c'est une affectation : chaque candidat obtient au plus un poste et chaque poste au plus un candidat. Un couplage est parfait lorsqu'il couvre tous les sommets. Si les graphes bipartis remplissent les manuels, c'est surtout parce que les problèmes de couplage y sont à la fois importants et résolubles efficacement, et que la théorie fournit des certificats exacts.

Le premier certificat dit quand tout le monde d'un côté peut être servi.

Théorème de Hall (1935). Un graphe biparti G = (U, W, E) possède un couplage qui couvre tous les sommets de U si et seulement si toute partie S ⊆ U a au moins |S| voisins dans W.

Lisez l'hypothèse attentivement, car elle est souvent mal citée. La condition de Hall porte sur la couverture d'un seul côté, pas sur un couplage parfait. Les deux ne coïncident que lorsque |U| = |W|. La nécessité est évidente : si deux candidats ne sont qualifiés chacun que pour un seul poste, et que c'est le même poste, ils ne peuvent pas être placés tous les deux. L'apport de Hall est que ce genre de pénurie locale est la seule chose qui puisse mal tourner. Un corollaire que Kőnig a prouvé en 1916 : tout graphe biparti k-régulier avec k ≥ 1 possède un couplage parfait.

Le second certificat prouve qu'un couplage ne peut pas être amélioré. Une couverture par sommets est un ensemble de sommets qui touche toutes les arêtes. Chaque arête d'un couplage a besoin de son propre sommet de couverture, donc aucun couplage n'est plus grand qu'une couverture quelconque. Dans les graphes bipartis, les deux se rejoignent :

Théorème de Kőnig et Egerváry (1931). Dans un graphe biparti, la taille d'un couplage maximum est égale à la taille d'une couverture par sommets minimum.

Hors des graphes bipartis, cela échoue à la première occasion : un triangle a un couplage maximum de taille 1 et une couverture par sommets minimum de taille 2. Dans l'exemple fil rouge, il existe un couplage de taille 4, et {A, C, E, G} est une couverture par sommets de taille 4, donc chacun certifie que l'autre est optimal, sans aucune recherche.

Pour trouver un couplage maximum, on utilise des chemins augmentants : un chemin qui part d'un sommet libre, alterne entre arêtes hors du couplage et arêtes du couplage, et se termine sur un autre sommet libre. Échanger les deux types d'arêtes le long de ce chemin agrandit le couplage de un. Berge a prouvé en 1957 qu'un couplage est maximum exactement quand aucun chemin augmentant n'existe. Dans un graphe biparti, chercher un tel chemin revient à un simple parcours en profondeur, ce qui donne la méthode courte souvent appelée algorithme de Kuhn :

def max_matching(left, adj):
    """Algorithme des chemins augmentants de Kuhn. adj associe à chaque sommet gauche ses voisins droits."""
    match_of = {}                            # sommet droit -> sommet gauche

    def augment(u, seen):
        for v in adj[u]:
            if v in seen:
                continue
            seen.add(v)
            # v est libre, ou son partenaire peut passer à un autre sommet droit
            if v not in match_of or augment(match_of[v], seen):
                match_of[v] = u
                return True
        return False

    size = sum(augment(u, set()) for u in left)
    return size, {u: v for v, u in match_of.items()}

adj = {'A': ['B', 'D', 'F'], 'C': ['B', 'F'], 'E': ['D', 'H'], 'G': ['F', 'H']}
size, pairs = max_matching(['A', 'C', 'E', 'G'], adj)
print(size, dict(sorted(pairs.items())))
# 4 {'A': 'D', 'C': 'B', 'E': 'H', 'G': 'F'}

Le résultat est un couplage parfait, A–D, C–B, E–H, G–F. Ce n'est pas le seul : ce graphe a exactement trois couplages parfaits. La méthode s'exécute en temps O(V · E), et comme toute recherche récursive en Python, elle doit être réécrite de façon itérative pour des graphes très profonds. Pour de grandes instances, le choix standard est l'algorithme de Hopcroft-Karp de 1973, qui trouve plusieurs plus courts chemins augmentants par phase et s'exécute en O(E √V).

Trois problèmes voisins méritent d'être connus par leur nom :

• Affectation pondérée. Quand chaque arête a un coût et que vous cherchez le couplage parfait le moins cher, la méthode hongroise de Kuhn (1955) le résout efficacement. Le guide sur l'affectation du travail l'applique à de vraies décisions de planification du personnel.
• Le couplage comme flot. Ajoutez une source reliée à chaque sommet de U, un puits relié depuis chaque sommet de W, donnez à chaque arête une capacité de 1, et un flot maximum est un couplage maximum. Le théorème de Kőnig et Egerváry devient alors un cas particulier de flot maximum égal coupe minimum.
• Couplage stable. Quand les deux côtés se classent mutuellement, Gale et Shapley (1962) ont montré qu'il existe toujours un couplage sans aucune paire qui préférerait être ensemble, et ont donné l'algorithme qui le trouve.

8. Coloration des arêtes et emplois du temps

Colorier les arêtes d'un graphe de sorte que deux arêtes ayant une extrémité commune reçoivent des couleurs différentes demande au moins Δ couleurs, où Δ est le degré maximum, parce que les arêtes d'un sommet de degré maximum entrent toutes en conflit entre elles. Pour un graphe quelconque, cela ne suffit pas toujours : un triangle a Δ = 2 et demande 3 couleurs, et Vizing a prouvé en 1964 que Δ + 1 suffit toujours pour les graphes simples. Les graphes bipartis n'ont jamais besoin de la couleur supplémentaire.

Théorème de coloration des arêtes de Kőnig (1916). Les arêtes de tout graphe biparti, multigraphes compris, peuvent être coloriées avec exactement Δ couleurs.

Une façon de le voir utilise le théorème de Hall : on peut compléter un graphe biparti avec des sommets et des arêtes supplémentaires jusqu'à obtenir un multigraphe biparti Δ-régulier, qui se décompose alors en Δ couplages parfaits, un par couleur. L'exemple fil rouge a Δ = 3, aux sommets A et F, et trois couleurs suffisent.

C'est le théorème qui se cache derrière les emplois du temps scolaires. Placez les enseignants d'un côté et les classes de l'autre, et tracez une arête pour chaque cours qu'un enseignant donne à une classe dans la semaine, avec des arêtes parallèles quand le même enseignant voit la même classe plusieurs fois. Une couleur est un créneau, et une coloration propre des arêtes est un emploi du temps dans lequel aucun enseignant et aucune classe ne se trouve à deux endroits à la fois. Le théorème de Kőnig dit que le nombre de créneaux nécessaires est égal à la plus lourde charge hebdomadaire d'un enseignant ou d'une classe, jamais plus. Les vrais emplois du temps ajoutent des salles et des préférences qui brisent la structure bipartite bien nette, et c'est là que le problème devient difficile, mais le cœur de l'affectation est une coloration bipartite des arêtes.

9. Le point de vue matriciel

Listez d'abord les sommets de U puis ceux de W, et la matrice d'adjacence d'un graphe biparti se découpe en blocs. Les deux blocs diagonaux sont nuls, puisqu'il n'y a pas d'arête à l'intérieur d'un côté :

A  =  [ 0    B ]            B est la matrice de biadjacence |U| × |W|
      [ Bᵀ   0 ]

B pour l'exemple       B  D  F  H
                   A [ 1  1  1  0 ]
                   C [ 1  0  1  0 ]
                   E [ 0  1  0  1 ]
                   G [ 0  0  1  1 ]

Le bloc hors diagonale B, la matrice de biadjacence, contient toute l'information, et les programmes ne stockent donc que lui. Une table de notes utilisateurs et articles est exactement une matrice de biadjacence pondérée, ce qui explique pourquoi les systèmes de recommandation sont naturellement des problèmes de graphes ; les compromis entre formats de stockage sont traités dans la représentation des graphes.

La structure en blocs laisse une empreinte sur les valeurs propres. Si un vecteur (x, y), découpé selon les côtés, vérifie A(x, y) = λ(x, y), alors (x, −y) vérifie la même équation avec −λ. Le spectre d'un graphe biparti est donc symétrique par rapport à zéro, et la réciproque est vraie aussi : un graphe dont le spectre d'adjacence est symétrique par rapport à zéro est biparti. Les valeurs propres de l'exemple fil rouge sont ±2,356, ±1,477, ±1,095 et ±0,262, en paires parfaites. Ajoutez l'arête de C à E et l'appariement se rompt, avec la plus grande valeur propre à 2,592 et la plus petite à −2,281. Pour un graphe connexe, un seul nombre tranche : le graphe est biparti exactement quand l'opposé de sa plus grande valeur propre est aussi une valeur propre. Le cycle à 5 sommets, par exemple, a la valeur propre 2 mais pas −2.

Les chimistes l'ont découvert avant que les théoriciens des graphes ne le nomment. En 1940, Coulson et Rushbrooke ont montré que pour les hydrocarbures alternants, dont les atomes de carbone se répartissent en deux ensembles avec des liaisons uniquement entre les ensembles, les niveaux d'énergie des électrons π vont par paires placées symétriquement autour du milieu. Ce théorème d'appariement est la symétrie spectrale des graphes bipartis, énoncée pour des molécules. Le lien plus général entre valeurs propres et structure est le sujet de la théorie spectrale des graphes.

10. Où l'on rencontre des graphes bipartis

Les graphes bipartis sont le modèle honnête chaque fois qu'un système relie deux sortes d'objets différentes et ne relie jamais directement deux objets de la même sorte.

Deux lignes méritent qu'on s'y attarde. En théorie des codes, Tanner a introduit en 1981 le graphe qui porte aujourd'hui son nom, avec les bits du code d'un côté et les contrôles de parité de l'autre. Les codes LDPC modernes (à matrice de parité creuse), utilisés dans le Wi-Fi et la 5G, sont décodés en faisant circuler des messages dans les deux sens le long des arêtes de ce graphe biparti précisément. Et tout hypergraphe, où une arête peut relier plus de deux sommets, peut être stocké sans perte sous la forme d'un graphe d'incidence biparti, ce qui permet d'y appliquer les algorithmes de graphes ordinaires.

La ligne des collaborations cache une erreur de modélisation courante. Les analystes projettent souvent un graphe biparti sur un seul côté, en reliant deux auteurs dès qu'ils partagent un article. La projection perd de l'information. Trois auteurs qui ont écrit un article ensemble et trois auteurs qui ont écrit trois articles distincts deux à deux produisent le même triangle dans la projection, alors que les collaborations sous-jacentes sont complètement différentes. Gardez le graphe biparti comme source de vérité et ne projetez que pour une question précise.

11. Facile à tester, difficile à réparer

La bipartition se trouve juste à la frontière entre problèmes faciles et difficiles, et il vaut la peine de voir exactement où passe la ligne.

• Deux couleurs : temps linéaire. La section 5 règle la question en O(V + E).
• Trois couleurs : NP-complet. Décider si un graphe admet une coloration propre à trois couleurs est l'un des problèmes NP-complets classiques recensés par Garey et Johnson. Une couleur de plus transforme un parcours en largeur en un problème sans algorithme polynomial connu, comme l'explique le guide sur la coloration de graphes.
• Réparer un graphe non biparti : NP-difficile. Supprimer le moins d'arêtes possible pour rendre un graphe biparti revient à garder le plus d'arêtes possible qui traversent une certaine répartition des sommets, c'est-à-dire le problème de la coupe maximum, l'un des 21 problèmes NP-complets de Karp de 1972. Supprimer le moins de sommets possible, le problème du transversal des cycles impairs, est lui aussi NP-difficile.

Le cycle impair renvoyé par le test est donc peu coûteux à trouver, mais il ne dit rien sur la façon la moins coûteuse de les éliminer tous. Dans l'exemple fil rouge avec l'arête supplémentaire, supprimer C–E rétablit la bipartition, mais sur un grand graphe avec de nombreux cycles impairs imbriqués, la réparation minimale est véritablement difficile à calculer.

12. Erreurs courantes

13. Glossaire

15. Références

Les définitions, théorèmes et attributions ci-dessus proviennent de ces sources, classées par ordre chronologique.

1. Mantel, W. (1907). "Problem 28." Wiskundige Opgaven 10, 60 à 61. La borne ⌊n²/4⌋ pour les graphes sans triangle.
2. Kőnig, D. (1916). "Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre." Mathematische Annalen 77(4), 453 à 465. Le théorème de coloration des arêtes des graphes bipartis et les couplages parfaits des graphes bipartis réguliers.
3. Kuratowski, K. (1930). "Sur le problème des courbes gauches en topologie." Fundamenta Mathematicae 15, 271 à 283. La planarité et les graphes interdits K5 et K3,3.
4. Egerváry, J. (1931). "Matrixok kombinatorius tulajdonságairól." Matematikai és Fizikai Lapok 38, 16 à 28.
5. Kőnig, D. (1931). "Gráfok és mátrixok." Matematikai és Fizikai Lapok 38, 116 à 119. Avec Egerváry, l'égalité entre couplages maximums et couvertures par sommets minimums.
6. Hall, P. (1935). "On Representatives of Subsets." Journal of the London Mathematical Society 10(1), 26 à 30.
7. Kőnig, D. (1936). Theorie der endlichen und unendlichen Graphen. Leipzig : Akademische Verlagsgesellschaft. Le premier manuel de théorie des graphes, avec la caractérisation par les cycles impairs.
8. Coulson, C. A. et Rushbrooke, G. S. (1940). "Note on the Method of Molecular Orbitals." Proceedings of the Cambridge Philosophical Society 36(2), 193 à 200. Le théorème d'appariement pour les hydrocarbures alternants.
9. Kuhn, H. W. (1955). "The Hungarian Method for the Assignment Problem." Naval Research Logistics Quarterly 2, 83 à 97.
10. Berge, C. (1957). "Two Theorems in Graph Theory." Proceedings of the National Academy of Sciences 43(9), 842 à 844. Les chemins augmentants caractérisent les couplages maximums.
11. Gale, D. et Shapley, L. S. (1962). "College Admissions and the Stability of Marriage." American Mathematical Monthly 69(1), 9 à 15.
12. Vizing, V. G. (1964). "On an Estimate of the Chromatic Class of a p-Graph." Diskretnyi Analiz 3, 25 à 30.
13. Karp, R. M. (1972). "Reducibility Among Combinatorial Problems." In Complexity of Computer Computations, 85 à 103. New York : Plenum. La coupe maximum parmi les 21 problèmes NP-complets.
14. Hopcroft, J. E. et Karp, R. M. (1973). "An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs." SIAM Journal on Computing 2(4), 225 à 231.
15. Garey, M. R. et Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco : W. H. Freeman. La 3-colorabilité des graphes comme problème NP-complet.
16. Cvetković, D. M., Doob, M. et Sachs, H. (1980). Spectra of Graphs: Theory and Application. New York : Academic Press. Les spectres symétriques caractérisent les graphes bipartis.
17. Tanner, R. M. (1981). "A Recursive Approach to Low Complexity Codes." IEEE Transactions on Information Theory 27(5), 533 à 547.
18. Asratian, A. S., Denley, T. M. J. et Häggkvist, R. (1998). Bipartite Graphs and Their Applications. Cambridge Tracts in Mathematics 131. Cambridge : Cambridge University Press. Source de l'attribution à 1916 du théorème des cycles impairs.
19. Diestel, R. (2017). Graph Theory, 5e édition. Graduate Texts in Mathematics 173. Berlin : Springer.