Graphes Simples et Multigraphes Expliqués

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Trois définitions, deux permissions

Il y a deux choses qu'un ensemble de paires non ordonnées ne peut pas exprimer : une arête qui relie un sommet à lui-même, et deux arêtes distinctes qui relient la même paire. Les autoriser ou non donne trois objets différents, et il vaut la peine de bien les nommer, car les théorèmes portent sur des objets précis.

Le graphe simple est le choix par défaut de la plupart des ouvrages, et sa définition est celle du guide sur les sommets et arêtes :

G = (V, E)      avec   E ⊆ [V]²      chaque arête est une partie à 2 éléments de V

Comme E est un ensemble de parties à 2 éléments, {v, v} n'est pas admissible (il n'a qu'un élément) et la même paire ne peut pas apparaître deux fois (un ensemble contient chaque élément une seule fois). Ces deux restrictions découlent de la notation, et non d'une décision prise par quelqu'un.

Pour les lever, il faut un autre formalisme. L'ouvrage Graph Theory de Bondy et Murty donne aux arêtes une identité propre et ajoute une fonction qui indique quelle paire relie chacune :

G = (V, E, ψ)      avec   ψ: E → paires non ordonnées de sommets (pas nécessairement distincts)

Désormais, e1 et e2 peuvent être des éléments distincts de E avec ψ(e1) = ψ(e2) = {u, v}, ce qui forme une paire d'arêtes parallèles, et ψ(e) = {v, v} est une boucle. Diestel arrive au même point avec deux applications qui envoient chaque arête sur ses extrémités, et West avec une relation qui associe chaque arête à ses extrémités. Le formalisme diffère, le contenu non.

Deux mises en garde sur le vocabulaire lui-même, car il crée une vraie confusion à la lecture des articles :

• « Multigraphe » n'est pas employé de façon cohérente. Certains auteurs autorisent les boucles dans un multigraphe, d'autres réservent cela au « pseudographe », et quelques-uns emploient « multigraphe » pour n'importe quel graphe. Vérifiez la définition de la source avant de citer l'un de ses théorèmes.
• « Graphe » signifie généralement « graphe simple ». La plupart des ouvrages le disent une fois au premier chapitre et ne le répètent jamais. Un résultat énoncé pour des « graphes » comporte souvent une hypothèse implicite de simplicité, et la section 5 montre à quel point certains échouent sans elle.

2. La théorie des graphes est née d'un multigraphe

Ce n'est pas un cas marginal ajouté après coup. Le problème qui a lancé la discipline est un multigraphe, et il cesse d'être le même problème si on le simplifie.

L'article d'Euler de 1736 sur les ponts de Königsberg modélise quatre terres reliées par sept ponts. Deux ponts relient la rive nord à l'île, et deux autres relient la rive sud à l'île. Ce sont des arêtes parallèles, et aucun graphe simple ne peut les contenir.

Le critère d'Euler porte sur la parité des degrés, et ce sont les ponts parallèles qui placent les degrés là où ils sont :

Multigraphe de Königsberg    7 arêtes    degrés 3, 5, 3, 3    quatre impairs  → pas de chaîne eulérienne
Graphe simple sous-jacent    5 arêtes    degrés 2, 3, 2, 3    deux impairs    → une chaîne existe

Supprimez les doublons et la réponse s'inverse. La multiplicité n'est pas un ornement du modèle, elle est le modèle, et le détail historique relaté dans l'histoire de la théorie des graphes est inséparable du formalisme. Quiconque charge les sept ponts dans une structure de données qui déduplique silencieusement les arêtes conclura qu'Euler s'est trompé.

3. Ce qu'une boucle fait au degré

Le degré compte les extrémités d'arêtes qui touchent un sommet, pas les arêtes. Une boucle a deux extrémités, et toutes deux arrivent sur le même sommet, donc :

Une boucle en v contribue pour 2 à deg(v). Les arêtes parallèles contribuent chacune pour 1, exactement comme des arêtes séparées.

Cette convention est imposée, pas choisie. Le lemme des poignées de main compte de deux façons les couples (sommet, extrémité d'arête en ce sommet), et toute arête, boucle comprise, a exactement deux extrémités, donc ∑ deg(v) = 2m reste vraie pour les pseudographes. Donnez à une boucle le degré 1 et le plus ancien théorème de la discipline tombe immédiatement.

Quelques conséquences à garder en tête :

• Un sommet portant une boucle et aucune autre arête a le degré 2, pas 0, et n'est pas isolé.
• Le nombre de sommets de degré impair reste pair, puisque la démonstration n'utilise que ∑ deg(v) = 2m.
• Dans un graphe simple , on a deg(v) = |N(v)|, la taille du voisinage. Dans un multigraphe, cette identité tombe : trois arêtes parallèles vers un même voisin donnent un degré 3 pour un seul voisin. Le code qui calcule le degré comme la taille d'un ensemble de voisins dédupliqué calcule le mauvais nombre.

4. Ce que change la multiplicité, et ce qu'elle ne peut pas changer

La question utile n'est pas « mon graphe est-il simple ? » mais « la propriété que je calcule dépend-elle de la multiplicité ? ». Les réponses se répartissent nettement, et la répartition n'a rien d'évident.

Trois de ces lignes méritent que leur raisonnement soit détaillé.

La coloration ignore les arêtes parallèles mais meurt avec les boucles. Une coloration propre exige que les extrémités de chaque arête reçoivent des couleurs différentes. Une seconde copie de {u, v} répète une contrainte déjà présente, donc l'ensemble des colorations propres, et par conséquent le nombre chromatique et le polynôme chromatique, sont exactement ceux du graphe simple sous-jacent. Une boucle exige c(v) ≠ c(v), ce que rien ne satisfait, donc un pseudographe comportant une boucle n'a aucune coloration propre et son polynôme chromatique est identiquement nul. C'est pourquoi la coloration de graphes est presque toujours énoncée pour des graphes sans boucle.

Le nombre d'arbres couvrants dépend de la multiplicité. Deux sommets reliés par une seule arête ont un arbre couvrant ; reliés par deux arêtes parallèles, ils en ont deux, car choisir l'une ou l'autre arête donne un arbre différent. Le théorème matrice-arbre de Kirchhoff, de 1847, les compte à partir du laplacien, et il est énoncé pour les multigraphes précisément parce que les multiplicités entrent dans la matrice comme des nombres hors diagonale. Les réseaux électriques, là où Kirchhoff a rencontré le problème, comportent couramment des composants en parallèle.

Les coupes et les flots dépendent de la multiplicité. Le nombre minimum d'arêtes dont la suppression sépare u de v vaut 1 quand une seule arête les relie et 2 quand il y en a deux. Comme le flot maximum égale la coupe minimum, il en va de même pour le flot : k arêtes parallèles de capacité unitaire transportent k unités. C'est exactement pourquoi un multigraphe à capacités unitaires est le modèle non pondéré naturel d'un réseau de flot.

5. Toutes les bornes des graphes simples tombent

Une grande partie des résultats classiques porte une hypothèse implicite de simplicité, et sans elle ils ne se dégradent pas progressivement. Ils échouent complètement.

Les deux lignes qui résistent méritent autant d'attention que celles qui échouent. Le lemme des poignées de main et la formule polyédrique d'Euler se démontrent tous deux en comptant des incidences, et un argument de comptage se moque de savoir si deux arêtes relient la même paire. Les bornes qui tombent sont celles qu'on démontre en choisissant des paires distinctes de sommets, ce qui est précisément l'étape qu'un multigraphe invalide.

La version pratique de cette section : quand vous consultez une borne, regardez si sa démonstration compte des incidences ou des paires. La première sorte se transpose aux multigraphes, la seconde non.

6. Stockage : là où la matrice d'adjacence ne suffit plus

Les trois représentations classiques se dégradent très différemment, et ces différences décident de celle à utiliser.

La matrice d'adjacence cesse d'être une matrice 0/1. L'extension naturelle stocke le nombre d'arêtes reliant chaque paire, donc le coefficient (u, v) devient un nombre, et une boucle place par convention 2 sur la diagonale pour que les sommes des lignes donnent toujours les degrés. Cela fonctionne, mais avec une limite fatale pour les données réelles : un nombre ne peut pas porter d'information par arête. Si vos trois vols parallèles ont chacun un prix différent, une matrice de nombres n'a nulle part où les ranger.

simple        A[u][v] ∈ {0, 1}
multigraphe   A[u][v] = nombre d'arêtes reliant u et v
pseudographe  A[v][v] = 2 × (nombre de boucles en v)      pour que les sommes des lignes soient les degrés

La liste d'adjacence conserve les doublons. La liste de u contient simplement v autant de fois qu'il y a d'arêtes entre eux. Le code de parcours ne change pas, et un BFS ou un DFS examinera le même voisin plusieurs fois, ce qui est sans conséquence quand le marquage des visites porte sur les sommets.

La liste d'arêtes devient le format naturel. C'est la représentation qui colle vraiment aux mathématiques : chaque arête est un enregistrement doté de sa propre identité, donc les arêtes parallèles sont simplement des enregistrements distincts, et les attributs par arête ont une place. C'est la définition par fonction d'incidence de la section 1 , exprimée sous forme de structure de données.

Il en découle un principe de conception, et c'est la chose la plus utile à retenir de cette section :

Dans un multigraphe, les arêtes ont besoin d'identités. Une paire d'extrémités n'identifie plus une arête, donc tout ce qui fait référence à une arête, qu'il s'agisse d'un couplage, d'un arbre couvrant, d'un flot ou d'une suppression, doit faire référence à un identifiant d'arête et non à (u, v).

Presque tous les bugs de multigraphes remontent à cette seule phrase. Stocker un arbre couvrant comme un ensemble de paires de sommets, ou un ensemble d'arêtes visitées indexé par (u, v), confond silencieusement les arêtes parallèles et produit des réponses fausses d'une manière qu'aucun vérificateur de types ne détectera.

7. Quels algorithmes sont concernés

La plupart des algorithmes de type parcours sont indifférents à la multiplicité, car ils marquent les sommets. Ceux qui marquent ou sélectionnent des arêtes demandent de l'attention.

La ligne de Karger est celle qui surprend, et elle mérite d'être détaillée car elle renverse l'instinct habituel. L'algorithme randomisé de coupe minimum de Karger contracte à répétition une arête choisie uniformément au hasard, en fusionnant ses deux extrémités en un seul sommet. La contraction transforme deux arêtes qui pointaient vers les deux sommets fusionnés en deux arêtes parallèles pointant vers le nouveau, et l'analyse probabiliste de l'algorithme repose sur la conservation de chaque copie, car la probabilité de contracter une arête est proportionnelle à son nombre de copies. Simplifiez le graphe intermédiaire et l'algorithme cesse d'être correct. Il en va de même pour l'étape de contraction de l'algorithme d'arbre couvrant de Borůvka.

8. Quand un multigraphe n'est pas optionnel

Les multigraphes ne sont pas une curiosité à normaliser. Ils sont le modèle honnête dès que deux entités peuvent être liées plus d'une fois et que chaque lien compte individuellement :

• Réseaux de transport. Deux villes reliées par trois vols différents, ou une route et une voie ferrée entre la même paire. Chacun a sa propre durée, son prix et sa capacité.
• Circuits électriques. Des composants en parallèle entre les deux mêmes nœuds, exactement le cadre dans lequel Kirchhoff a développé le théorème matrice-arbre en 1847.
• Graphes de transactions et de paiements. Deux comptes peuvent effectuer de nombreuses transactions entre eux ; les réduire à une arête perd les montants, les horodatages et le nombre lui-même, qui est généralement le signal recherché.
• Graphes de réactions chimiques et graphes moléculaires. Les liaisons doubles et triples sont des arêtes parallèles dans le modèle classique d'une molécule par un graphe.
• Graphes de connaissances et RDF. Deux entités liées par plusieurs prédicats distincts. C'est pourquoi ces données sont généralement stockées sous forme de triplets, c'est-à-dire une liste d'arêtes avec une étiquette par arête.
• Tout ce qui est construit par contraction. L'algorithme de Karger, celui de Borůvka et les étapes de condensation de nombreux algorithmes d'approximation créent des arêtes parallèles au fil de leur exécution, quelle que soit l'entrée.
• Problèmes de tournées eulériennes. Le balayage des rues et les tournées postales exigent de parcourir chaque rue physique, et deux rues entre les mêmes carrefours sont deux obligations.

9. Simplifier, et ce que cela coûte

Transformer un multigraphe en graphe simple est souvent le bon choix, et ce n'est sans risque que si vous savez lesquelles des propriétés de la section 4 vous allez modifier. Il existe trois méthodes classiques, et elles répondent à des questions différentes :

Notez que la deuxième et la troisième règle sont incompatibles : additionner est juste pour les capacités et faux pour les distances, garder le minimum est juste pour les distances et faux pour les capacités. Laquelle s'applique dépend de la façon dont les poids se combinent le long d'un chemin, sujet du guide sur les graphes pondérés et non pondérés. Choisir la mauvaise fusion répond silencieusement à une autre question, et le graphe paraîtra ensuite parfaitement raisonnable.

Une quatrième option vaut souvent mieux que toutes les autres : gardez le multigraphe et laissez l'algorithme s'en charger. BFS, DFS, Dijkstra, Kruskal et Prim fonctionnent tous correctement sur des multigraphes tels quels, donc simplifier n'apporte souvent rien et coûte de l'information.

10. Multigraphes orientés

Tout ce qui précède se transpose aux graphes orientés, avec une distinction supplémentaire à nommer. Dans un graphe orienté, les arcs (u, v) et (v, u) sont déjà des objets différents, ce qui relève non de la multiplicité mais de l'orientation : cette paire est un digone, et un graphe orienté ordinaire peut déjà en contenir un sans aucune extension de sa définition. Beaucoup de graphes orientés n'en contiennent aucun : un DAG jamais. La multiplicité dans le cas orienté désigne deux arcs ou plus ayant la même origine et la même extrémité, ce qui exige de nouveau une définition du type fonction d'incidence, comme dans l'ouvrage Digraphs de Bang-Jensen et Gutin.

Les conséquences pratiques se transposent directement : degré entrant et degré sortant comptent des arcs et non des voisins distincts, une boucle orientée ajoute 1 à chacun, et les conditions eulériennes sur un multigraphe orienté comparent toujours degré entrant et degré sortant en chaque sommet.

11. Erreurs courantes

• Charger un multigraphe dans une structure qui déduplique. Un Set de paires, une matrice d'adjacence booléenne ou une contrainte d'unicité en base de données sur (u, v) éliminent tous silencieusement les arêtes parallèles. Le graphe a alors l'air correct et tous les comptes sont faux.
• Identifier les arêtes par leurs extrémités. Dans un multigraphe, (u, v) désigne un ensemble d'arêtes, pas une seule. Couplages, arbres couvrants, flots et ensembles d'arêtes visitées doivent être indexés par identifiants d'arête.
• Calculer le degré comme le nombre de voisins. Correct dans un graphe simple, faux dès qu'une arête est dupliquée ou qu'une boucle apparaît.
• Donner à une boucle le degré 1. Elle contribue pour 2, et le lemme des poignées de main en dépend.
• Appliquer m ≤ n(n-1)/2. Cette borne, et tout ce qui en découle, y compris le raisonnement creux ou dense, exige la simplicité.
• Simplifier avant un calcul eulérien, de coupe ou de flot. Les trois dépendent de la multiplicité, comme le montre Königsberg sur l'exemple fondateur de la discipline.
• Dédupliquer à l'intérieur d'un algorithme de contraction. Les algorithmes de Karger et de Borůvka créent délibérément des arêtes parallèles et ont besoin de les conserver.
• Supposer qu'une bibliothèque fait ce que l'on attend. Les bibliothèques de graphes diffèrent : ajouter une arête existante crée un doublon, est ignoré ou lève une erreur. Vérifiez-le une fois, dans un test.

12. Glossaire

14. Références

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

1. Euler, L. (1736). "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Petropolitanae 8 (publié en 1741), 128 à 140. Les ponts de Königsberg, modélisés par un multigraphe.
2. Kirchhoff, G. (1847). "Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird." Annalen der Physik 148(12), 497 à 508. Le théorème matrice-arbre, développé sur des réseaux électriques à composants en parallèle.
3. Harary, F. (1969). Graph Theory. Reading, Massachusetts : Addison-Wesley. Distingue graphes, multigraphes et pseudographes.
4. Karger, D. R. (1993). "Global Min-cuts in RNC, and Other Ramifications of a Simple Min-cut Algorithm." Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, 21 à 30. L'algorithme de contraction qui crée des arêtes parallèles au fil de son exécution.
5. Karger, D. R. et Stein, C. (1996). "A New Approach to the Minimum Cut Problem." Journal of the ACM 43(4), 601 à 640.
6. Bollobás, B. (1998). Modern Graph Theory. Graduate Texts in Mathematics 184. New York : Springer.
7. West, D. B. (2001). Introduction to Graph Theory, 2e édition. Upper Saddle River : Prentice Hall. Définit un graphe par un ensemble de sommets, un ensemble d'arêtes et une relation d'extrémités, ce qui admet boucles et arêtes parallèles.
8. Bondy, J. A. et Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. Londres : Springer. Source de la définition par fonction d'incidence de la section 1.
9. Bang-Jensen, J. et Gutin, G. (2009). Digraphs: Theory, Algorithms and Applications, 2e édition. Londres : Springer. Multigraphes orientés.
10. Cormen, T. H., Leiserson, C. E., Rivest, R. L. et Stein, C. (2009). Introduction to Algorithms, 3e édition. Cambridge, Massachusetts : MIT Press.
11. Wilson, R. J. (2010). Introduction to Graph Theory, 5e édition. Harlow : Prentice Hall. Développe les multigraphes aux côtés des graphes simples dès le premier chapitre.
12. Chartrand, G., Lesniak, L. et Zhang, P. (2015). Graphs & Digraphs, 6e édition. Boca Raton : CRC Press.
13. Diestel, R. (2017). Graph Theory, 5e édition. Graduate Texts in Mathematics 173. Berlin : Springer. Source de la définition du graphe simple et de la formulation des multigraphes par deux applications d'extrémités.