Sommets et Arêtes Expliqués

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. La définition formelle d'un graphe

Presque toutes les introductions disent qu'un graphe, ce sont « des points reliés par des lignes ». Cette image est utile et c'est aussi la raison pour laquelle tant de gens se retrouvent bloqués plus tard : les points et les lignes ne sont pas l'objet mathématique. L'objet est un couple d'ensembles.

L'ouvrage de Diestel, Graph Theory, la référence standard de niveau master, s'ouvre sur la définition dans sa forme la plus épurée :

Un graphe est un couple G = (V, E) d'ensembles tel que E ⊆ [V]², où [V]² désigne l'ensemble de toutes les parties à 2 éléments de V.

Dépliez cela et tout le reste de cet article en découle :

• V est un ensemble d'objets appelés sommets. On ne suppose rien à leur sujet. Ce peuvent être des villes, des personnes, des pages web, des atomes ou des entiers. La théorie ne regarde jamais à l'intérieur ; elle se soucie seulement de savoir lesquels sont distinguables.
• E est un ensemble de parties à 2 éléments de V. Une arête est littéralement l'ensemble {u, v}, ni une flèche ni une courbe. Elle n'enregistre rien d'autre que la paire qu'elle relie.
• Comme E est un ensemble, une arête est présente ou absente. Elle ne peut pas apparaître deux fois.
• Comme chaque élément de E a exactement deux membres distincts, une arête ne peut pas relier un sommet à lui-même.

Ces deux dernières conséquences ne sont pas des restrictions ajoutées après coup. Elles découlent directement de la théorie des ensembles, et un graphe qui les respecte est dit simple. Autoriser des arêtes répétées ou des boucles revient à modifier la définition elle-même, ce qui fait l'objet de la section 4.

Deux autres notations standard que vous rencontrerez partout. Lorsque plusieurs graphes sont en jeu, on écrit V(G) et E(G) pour préciser de quel graphe il s'agit. Et les deux mesures de taille ont un nom : on appelle ordre du graphe son nombre de sommets, et tailleson nombre d'arêtes. La plupart des textes d'algorithmique les abrègent en n = |V| et m = |E|, et c'est la convention utilisée sur tout ce site.

Ce graphe est l'exemple récurrent pour la suite de l'article. Son ensemble de sommets est V = {A, B, C, D, E, F}, son ordre vaut donc n = 6, et son ensemble d'arêtes est

E = { {A,B}, {A,C}, {B,C}, {B,D}, {C,D}, {D,E}, {E,F} }        donc  m = 7

2. Les sommets : ce qu'ils sont et ce qu'ils ne sont pas

Un sommet ne porte aucune structure propre. Dans l'objet formel, c'est un élément anonyme d'un ensemble, et tout ce que l'on peut en dire vient des arêtes qui le touchent. Il vaut la peine d'insister là-dessus, car c'est précisément ce qui rend la théorie des graphes transférable : un théorème démontré sur des sommets est en même temps un théorème sur des aéroports, des transistors, des protéines et des commits Git.

Trois conséquences qui font trébucher en pratique :

• Les sommets sont distinguables, mais interchangeables par ailleurs. Deux graphes qui ne diffèrent que par le nom de leurs sommets sont isomorphes, et la théorie des graphes les traite comme le même graphe. Quand vous étiquetez des sommets dans du code, vous ajoutez de la comptabilité, pas des mathématiques.
• Un sommet isolé reste un sommet. Un sommet sans aucune arête est parfaitement licite et est dit isolé. Les débutants construisent souvent un graphe à partir d'une liste d'arêtes et perdent silencieusement tous les sommets isolés, ce qui change l'ordre du graphe et casse discrètement tout ce qui divise par n.
• Le graphe vide existe, et les graphes infinis aussi. Rien dans la définition n'interdit V = ∅, et rien n'y interdit non plus que V soit infini, ce qui fait l'objet du guide sur les graphes finis et infinis. La plupart des textes l'autorisent et quelques-uns l'excluent par décret ; l'important est de savoir quelle convention votre source utilise avant de faire confiance à un cas limite.

La note historique mérite une ligne, car le vocabulaire n'est pas stable sur un siècle de littérature. Le texte classique de Harary de 1969 les appelle des points et des lignes. Les physiciens et de nombreux articles appliqués disent nœuds et liens. Les chimistes, à la suite de la note de Sylvester parue en 1878 dans Nature qui a donné au domaine le mot « graphe », parlaient d'atomes et de liaisons. Ces quatre vocabulaires décrivent le même couple d'ensembles.

3. Arêtes, adjacence et incidence

Une arête relie exactement deux sommets, et ces deux-là sont ses extrémités ou ses bouts. De cette seule relation, les deux mots que les débutants intervertissent le plus souvent tirent leur sens précis :

• L'adjacence est une relation entre deux sommets. Les sommets u et v sont adjacents, ce que l'on note u ~ v, lorsque {u, v} ∈ E. Des sommets adjacents sont aussi appelés voisins, et l'ensemble de tous les voisins de v est son voisinage, noté N(v).
• L'incidence est une relation entre un sommet et une arête. L'arête {u, v} est incidente à u et incidente à v, et à aucun autre sommet.

La distinction paraît pédante jusqu'à ce que vous tombiez sur une phrase comme « deux arêtes adjacentes ». Elle est correcte et désigne deux arêtes qui partagent une extrémité. Les sommets sont adjacents par une arête ; les arêtes sont adjacentes par un sommet. Garder les deux relations séparées est ce qui permet de lire sans ambiguïté une définition telle que celle d'une coloration propre (« des sommets adjacents reçoivent des couleurs différentes »).

Dans l'exemple récurrent, N(B) = {A, C, D}, donc B a trois voisins. L'arête {B, D} est incidente à B et à D. Les arêtes {B, D} et {C, D} sont adjacentes entre elles, puisque toutes deux sont incidentes à D.

4. Boucles et arêtes parallèles : là où la définition doit changer

Les systèmes réels produisent deux choses que la définition ensembliste ne sait pas exprimer. Une route qui quitte un rond-point et y revient est une arête d'un sommet vers lui-même. Deux vols distincts entre les deux mêmes aéroports sont deux arêtes distinctes reliant la même paire. Sous E ⊆ [V]2 aucune des deux n'existe : {A, A} est un ensemble à un seul élément, et un ensemble ne peut pas contenir deux fois le même élément.

Le correctif n'est pas une note de bas de page, c'est une autre définition. L'ouvrage de Bondy et Murty, Graph Theory , ajoute aux deux ensembles une fonction d'incidence explicite :

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

Désormais une arête est un objet à part entière doté d'une identité, et ψ indique quelle paire elle relie. Deux arêtes différentes peuvent être envoyées sur la même paire, ce qui donne des arêtes parallèles, aussi appelées arêtes multiples. Une arête peut être envoyée sur une paire dont les deux entrées coïncident, ce qui donne une boucle. L'ouvrage de West, Introduction to Graph Theory , suit la même voie et définit un graphe comme un ensemble de sommets, un ensemble d'arêtes et une relation associant à chaque arête ses extrémités.

Le vocabulaire qui en résulte :

Deux mises en garde pratiques. D'abord, « multigraphe » n'est pas employé de façon uniforme : certains auteurs y incluent les boucles, d'autres non, vérifiez donc la source avant de citer un théorème. Ensuite, une boucle ajoute 2 au degré de son sommet, et non 1, car ses deux extrémités y aboutissent. Cette convention n'est pas arbitraire, et la section suivante explique exactement pourquoi il doit en être ainsi.

Sauf mention contraire, « graphe » signifie « graphe simple ». Tous les résultats de la suite de cet article le supposent, et le guide complémentaire sur les graphes simples et multigraphes détaille précisément ce que ces deux autorisations changent et quelles bornes standard cessent d'être valables sans elles.

5. Le degré et le premier théorème de la théorie des graphes

Le degré d'un sommet v, noté deg(v) ou d(v), est le nombre d'arêtes qui lui sont incidentes. De façon équivalente, et plus utile, c'est le nombre des extrémités d'arêtes qui se rejoignent en v. Dans un graphe simple, il est égal à la taille du voisinage, deg(v) = |N(v)|.

Deux quantités voisines reviennent sans cesse dans les bornes et les démonstrations : le degré minimum δ(G) et le degré maximum Δ(G). Un graphe dont tous les sommets ont le même degré k est dit k-régulier.

Voici maintenant le plus ancien théorème du domaine, issu du mémoire d'Euler de 1736 sur les ponts de Königsberg, celui qui a fondé la théorie des graphes :

Lemme des poignées de main. Pour tout graphe fini, la somme des degrés de tous les sommets est égale au double du nombre d'arêtes : ∑v∈V deg(v) = 2m.

La démonstration tient en une ligne de double dénombrement. Comptez les couples (sommet, extrémité d'arête qui s'y rejoint). En sommant sur les sommets, on obtient ∑ deg(v). En sommant sur les arêtes, on obtient 2m, puisque chaque arête a exactement deux extrémités. Les deux comptent le même ensemble fini, elles sont donc égales. Remarquez que cet argument est aussi ce qui oblige une boucle à compter double : une boucle a bien deux extrémités, et toutes deux aboutissent au même sommet.

Vérifiez-le sur l'exemple récurrent : les degrés sont 2, 3, 3, 3, 2, 1, leur somme vaut 14, et le graphe a 7 arêtes. Le lemme a un corollaire immédiat et très utile.

Corollaire. Dans tout graphe, le nombre de sommets de degré impair est pair.

Séparez la somme entre sommets de degré impair et de degré pair. Le total est pair et la part des degrés pairs est paire, donc la part des degrés impairs doit l'être aussi, ce qui force le nombre de termes impairs à être pair. C'est pourquoi une fête ne peut jamais compter exactement trois personnes ayant chacune serré un nombre impair de mains, et c'est le même argument de parité qui décide de l'existence d'une chaîne eulérienne .

6. Suites de degrés : quelles listes de nombres sont des graphes

Écrivez les degrés par ordre décroissant et vous obtenez la suite des degrés. Pour l'exemple récurrent, c'est (3, 3, 3, 2, 2, 1). La question naturelle va dans l'autre sens : étant donné une liste de nombres, existe-t-il un graphe ayant exactement ces degrés ? Une liste pour laquelle il en existe un est dite graphique.

Le lemme des poignées de main élimine déjà la moitié des candidates : toute suite de somme impaire n'est pas graphique. Mais ce test est loin de suffire. Prenez (3, 3, 1, 1). La somme vaut 8, donc elle est paire, et aucun sommet ne réclame plus que les 3 voisins disponibles. Pourtant aucun graphe simple ne la réalise : les deux sommets de degré 3 doivent chacun être reliés aux trois autres sommets, ce qui force les deux sommets de degré 1 à avoir un degré 2.

Deux résultats classiques règlent complètement la question :

• Le théorème d'Erdős–Gallai (1960) donne un critère exact : une suite décroissante de somme paire est graphique si et seulement si, pour chaque k, la somme des k premiers termes vaut au plus k(k-1) plus la somme, sur les termes restants, de min(di, k). C'est un test en forme close, vérifiable en temps linéaire après tri.
• L'algorithme de Havel–Hakimi, dû à Havel (1955) et indépendamment à Hakimi (1962), en est la version constructive : retirez le plus grand degré d, soustrayez 1 aux d entrées suivantes, retriez et recommencez. La suite initiale est graphique exactement lorsque cette réduction se termine sur des zéros, et les étapes servent aussi de recette pour construire un graphe qui la réalise.

Exécutez Havel–Hakimi sur l'exemple qui échoue pour le voir à l'œuvre :

(3, 3, 1, 1)   retirer le 3, soustraire 1 aux trois entrées suivantes
(2, 0, 0)      retrié
               retirer le 2, soustraire 1 aux deux entrées suivantes
(-1, -1)       négatif, la suite n'est donc PAS graphique

Et sur l'exemple récurrent, où il réussit :

(3, 3, 3, 2, 2, 1)  →  (2, 2, 1, 2, 1)  → trié (2, 2, 2, 1, 1)
(2, 2, 2, 1, 1)     →  (1, 1, 1, 1)     → trié (1, 1, 1, 1)
(1, 1, 1, 1)        →  (0, 1, 1)        → trié (1, 1, 0)
(1, 1, 0)           →  (0, 0)           → que des zéros, la suite EST donc graphique

Une mise en garde qui surprend : une suite graphique peut être réalisée par plusieurs graphes non isomorphes. Connaître tous les degrés ne détermine pas le graphe.

7. Arêtes orientées : arcs, degré entrant et degré sortant

Remplacez la paire non ordonnée par un couple ordonné et vous obtenez un graphe orienté, ou digraphe :

D = (V, A)      avec  A ⊆ V × V

Un élément (u, v) de A est un arc ou arête orientée, allant de son origine u vers son extrémité v. Comme le couple est ordonné, (u, v) et (v, u) sont des arcs différents et tous deux peuvent être présents. L'ouvrage de Bang-Jensen et Gutin, Digraphs , est la référence standard pour la terminologie, et il réserve « arc » à l'objet orienté précisément pour éviter l'ambiguïté qu'il y aurait à appeler les deux des arêtes.

Le degré se scinde en deux :

• Le degré sortant d+(v), le nombre d'arcs ayant pour origine v.
• Le degré entrant d-(v), le nombre d'arcs ayant pour extrémité v.

Le lemme des poignées de main se scinde avec lui. Chaque arc a exactement une origine et exactement une extrémité, donc compter séparément les origines et les extrémités d'arcs donne

∑v∈V d+(v)  =  ∑v∈V d-(v)  =  |A|

Notez le facteur 2 manquant : dans le cas non orienté, chaque arête apportait deux extrémités à une seule somme ; ici chaque arc apporte une extrémité à chacune de deux sommes. La comparaison complète, avec les orientations, les trois sortes de connexité et les algorithmes qui survivent, se trouve dans le guide sur les graphes orientés et non orientés. Les sommets de degré entrant 0 sont des sources et ceux de degré sortant 0 des puits, ce qui est exactement le vocabulaire sur lequel reposent le tri topologique et le flot de réseau .

8. Arêtes pondérées, et pourquoi les poids sont hors du graphe

Les problèmes de plus court chemin ont besoin de distances, les problèmes de flot de capacités, et les problèmes d'ordonnancement de durées. Rien de tout cela n'est dans G = (V, E), et ce n'est pas censé y être. Un graphe pondéré est un graphe plus une fonction :

w: E → ℝ        associe un nombre réel à chaque arête

Garder les poids dans une fonction séparée plutôt qu'à l'intérieur des arêtes est ce qui permet à un même graphe de porter plusieurs modèles de coût à la fois. Le même réseau routier est un seul graphe avec trois fonctions de poids : kilomètres, minutes et carburant. Le guide complémentaire sur les graphes pondérés et non pondérés suit cette idée à travers le choix de l'algorithme, les poids négatifs et la force d'un sommet. Changer la fonction change tous les plus courts chemins sans toucher à un seul sommet ni à une seule arête.

Cela explique aussi pourquoi les algorithmes viennent avec des conditions sur w plutôt que sur le graphe. L'algorithme de Dijkstra exige w(e) ≥ 0 pour toute arête ; Bellman-Ford tolère les poids négatifs mais pas les cycles négatifs. Ce sont des contraintes sur la fonction, et le couple d'ensembles sous-jacent y est indifférent.

9. Combien d'arêtes un graphe peut-il avoir ?

Dans un graphe simple à n sommets, une arête est un choix de 2 sommets distincts parmi n, le maximum est donc le coefficient binomial

mmax = C(n, 2) = n(n - 1) / 2

Le graphe qui l'atteint, où toute paire de sommets est adjacente, est le graphe complet Kn. Pour l'exemple récurrent, n = 6 donne un plafond de 15 arêtes, et le graphe en utilise 7. Le rapport 2m / (n(n-1)) est la densité, ici 0,47.

Cette seule borne explique pourquoi deux expressions dominent la littérature algorithmique :

• Un graphe dense a m proche de son maximum, donc m = Θ(n2).
• Un graphe creux a m très en dessous, typiquement m = O(n) ou O(n log n). Presque tous les grands réseaux réels sont creux : cartes routières, graphes sociaux et graphes du web ont un degré moyen à un ou deux chiffres, quel que soit le nombre de sommets qu'ils contiennent.

La faible densité n'est pas un détail. Elle décide de la structure de données à utiliser, ce qui est l'objet de la section suivante, et c'est la raison pour laquelle une complexité en O(m log n) bat O(n2) sur des entrées réelles alors même que les deux sont identiques dans le pire cas.

10. Stocker les sommets et les arêtes dans le code

Il y a trois façons standard de conserver V et E en mémoire, et les compromis entre elles sont exposés par Cormen, Leiserson, Rivest et Stein dans Introduction to Algorithms. La comparaison complète, y compris le format compressé par lignes et le seuil de densité à partir duquel une matrice devient la plus petite option, se trouve dans le guide sur la représentation des graphes.

La règle pratique découle de la section 9. Les parcours comme BFS et DFS passent tout leur temps d'exécution à parcourir des ensembles de voisins, donc sur un graphe creux la liste d'adjacence donne O(n + m) là où la matrice imposerait O(n2) rien que pour balayer des lignes de zéros. Sur un graphe dense, la matrice l'emporte en espace comme en simplicité. Une liste d'arêtes paraît primitive jusqu'à ce que vous rencontriez l'algorithme de Kruskal, qui trie toutes les arêtes par poids et n'a jamais besoin de consulter des voisins.

11. Décider ce que doit être un sommet

Le plus difficile, quand on applique la théorie des graphes, n'est aucun théorème. C'est de choisir ce que sont les sommets, car ce choix fixe tout le reste et est rarement unique.

Prenez un réseau routier. Le modèle évident fait des intersections les sommets et des tronçons de route les arêtes, ce qui correspond à ce que veut un moteur d'itinéraires : un chemin dans le graphe est une route sur le terrain. Mais les interdictions et les coûts de tourner se situent aux intersections, pas sur les routes, et ce modèle n'a nulle part où les mettre. Le correctif standard inverse le choix : faites de chaque tronçon de route un sommet, et reliez-en deux lorsque l'on peut légalement passer de l'un à l'autre. Désormais un virage est une arête et peut porter un coût.

Cette inversion est une construction formelle, pas un bricolage. Le graphe adjoint L(G) possède un sommet pour chaque arête de G, deux d'entre eux étant adjacents lorsque les arêtes correspondantes de G partagent une extrémité. Il remonte à l'article de Whitney de 1932 sur les graphes congruents, et c'est la raison pour laquelle un problème portant sur les arêtes peut souvent être confié à un algorithme qui ne connaît que les sommets. Les problèmes de couplage, par exemple, deviennent des problèmes d'ensemble indépendant sur le graphe adjoint.

Une courte liste de contrôle qui évite la plupart des erreurs de modélisation :

• Deux de vos sommets peuvent-ils être reliés plus d'une fois ? Si oui, il vous faut un multigraphe, ou bien agréger les arêtes parallèles en un seul poids.
• La relation est-elle symétrique ? « Est ami avec » l'est généralement, « suit » et « dépend de » ne le sont pas. Vous tromper là-dessus, c'est utiliser un algorithme non orienté sur un problème orienté.
• La relation met-elle en jeu plus de deux choses à la fois ? Une arête relie exactement deux sommets. Un comité de cinq personnes, ou une réaction chimique à trois réactifs, est une arête de type hypergraphe , et l'écraser en arêtes ordinaires fait perdre de l'information.
• La structure change-t-elle au cours du temps ? Un graphe standard est un instantané. Les graphes temporels ou dynamiques sont des modèles distincts, avec leur propre littérature.

12. Pièges de terminologie d'un manuel à l'autre

La théorie des graphes a grandi dans plusieurs domaines à la fois, si bien que le même objet porte plusieurs noms et que quelques noms désignent des choses différentes selon les auteurs. Voici ceux qui causent réellement des erreurs :

L'habitude sûre est celle que suit tout article : énoncez vos conventions une fois au début, puis tenez-vous-y. Quand vous citez un théorème, citez la définition sous laquelle il a été démontré.

13. Glossaire des symboles

La notation utilisée sur ce site et dans les références ci-dessous.

15. 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 (paru en 1741), 128 à 140. Le mémoire sur les ponts de Königsberg, et l'origine de l'argument sur les degrés.
2. Sylvester, J. J. (1878). "Chemistry and Algebra." Nature 17, 284. La note qui a introduit le mot « graphe » dans son sens moderne.
3. Whitney, H. (1932). "Congruent Graphs and the Connectivity of Graphs." American Journal of Mathematics 54(1), 150 à 168. Source de la construction du graphe adjoint.
4. König, D. (1936). Theorie der endlichen und unendlichen Graphen. Leipzig : Akademische Verlagsgesellschaft. Le premier livre entièrement consacré à la théorie des graphes.
5. Havel, V. (1955). "A remark on the existence of finite graphs" (en tchèque). Časopis pro pěstování matematiky 80, 477 à 480.
6. Erdős, P. et Gallai, T. (1960). "Graphs with prescribed degrees of vertices" (en hongrois). Matematikai Lapok 11, 264 à 274. Le critère exact des suites graphiques.
7. Hakimi, S. L. (1962). "On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I." Journal of the Society for Industrial and Applied Mathematics 10(3), 496 à 506.
8. Harary, F. (1969). Graph Theory. Reading, Massachusetts : Addison-Wesley. Le classique qui appelle les sommets « points » et les arêtes « lignes ».
9. Bollobás, B. (1998). Modern Graph Theory. Graduate Texts in Mathematics 184. New York: Springer.
10. 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.
11. Bondy, J. A. et Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. Londres : Springer. Source de la formulation avec fonction d'incidence utilisée à la section 4.
12. Bang-Jensen, J. et Gutin, G. (2009). Digraphs: Theory, Algorithms and Applications, 2e édition. Londres : Springer. Référence standard pour les arcs et les degrés orientés.
13. Cormen, T. H., Leiserson, C. E., Rivest, R. L. et Stein, C. (2009). Introduction to Algorithms, 3e édition. Cambridge, Massachusetts : MIT Press. Source des coûts de représentation de la section 10.
14. Diestel, R. (2017). Graph Theory, 5e édition. Graduate Texts in Mathematics 173. Berlin : Springer. Source de la définition citée à la section 1.