Graphes Orientés et Non Orientés Expliqués

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Les deux définitions côte à côte

La différence entre un graphe orienté et un graphe non orienté tient à un seul mot de la définition : la paire qui relie deux sommets est-elle ordonnée ? Tout le reste de cet article, y compris la question de savoir quels algorithmes fonctionnent encore, découle de ce mot.

Un graphe non orienté est l'objet standard présenté dans le guide sur les sommets et arêtes. D'après Graph Theory de Diestel :

G = (V, E)      avec   E ⊆ [V]²      une arête est une paire non ordonnée {u, v}

Un graphe orienté, ou digraphe, remplace la paire non ordonnée par un couple ordonné :

D = (V, A)      avec   A ⊆ V × V      un arc est un couple ordonné (u, v)

Comme (u, v) et (v, u) sont des couples différents, les deux peuvent être présents à la fois, et l'on dit qu'un graphe orienté qui contient les deux possède un digone entre u et v. Dans le monde non orienté, il n'y a rien à distinguer : {u, v} et {v, u} sont le même ensemble, donc l'arête existe une fois ou pas du tout.

Diestel donne une formulation plus générale qu'il vaut la peine de connaître, car c'est celle qui résiste au contact des données réelles. Un graphe orienté est un couple (V, E) d'ensembles disjoints muni de deux applications

init: E → V        associe à chaque arête son sommet initial
ter:  E → V        associe à chaque arête son sommet terminal

Ici, un arc est un objet à part entière et non un couple, si bien que la définition admet arcs parallèles et boucles sans aucun traitement particulier. C'est le pendant orienté de la définition par fonction d'incidence dont ont besoin les multigraphes, et c'est pourquoi un planning comptant trois vols quotidiens distincts de A vers B reste un graphe orienté parfaitement valable.

Le lien formel avec la logique est exact et mérite d'être énoncé une fois : un graphe non orienté sans boucle est précisément une relation symétrique irréflexive sur V, tandis qu'un graphe orienté est une relation binaire quelconque sur V. L'orientation, c'est ce qu'on obtient quand on cesse d'exiger que la relation soit symétrique.

Ces deux graphes servent d'exemple récurrent pour tout l'article. Le graphe orienté est

V = {A, B, C, D, E}
A = { (A,B), (B,C), (C,A), (C,D), (D,E), (E,D) }        6 arcs

et le graphe non orienté de gauche est son graphe sous-jacent, avec 5 arêtes, puisque les arcs opposés entre D et E deviennent l'unique arête {D, E}.

2. Arêtes, arcs, origines et extrémités

Le vocabulaire change avec la définition, et ces changements n'ont rien de décoratif. L'ouvrage Digraphs de Bang-Jensen et Gutin, la référence standard côté orienté, prend soin de réserver des mots distincts pour qu'un énoncé ne soit jamais ambigu quant à l'objet dont il parle.

Deux termes méritent leur propre ligne, car on les confond sans cesse. Un graphe antisymétrique (oriented graph en anglais) est un graphe orienté sans digone : on a pris un graphe non orienté et choisi un sens pour chaque arête. Tout graphe antisymétrique est un graphe orienté, mais un graphe orienté contenant à la fois (u,v) et (v,u) n'est pas antisymétrique. Cette distinction est tout le sujet de la section 5.

3. Le degré se dédouble

Dans un graphe non orienté, le degré d'un sommet compte les extrémités d'arêtes qui le touchent, et le lemme des poignées de main dit que la somme de ces nombres vaut deux fois le nombre d'arêtes. Dans un graphe orienté, chaque arc a une origine et une extrémité au lieu de deux bouts symétriques, donc ce compte unique se dédouble :

• Degré sortant d+(v) : le nombre d'arcs dont l'origine est v.
• Degré entrant d-(v) : le nombre d'arcs dont l'extrémité est v.

et l'identité unique se dédouble elle aussi :

non orienté    ∑v∈V deg(v)   =  2m           chaque arête a deux extrémités

orienté        ∑v∈V d+(v)  =  ∑v∈V d-(v)  =  |A|
                                             chaque arc a une origine et une extrémité

Le facteur 2 manquant surprend souvent. Ce n'est pas un autre théorème, c'est le même argument de double comptage appliqué à un ensemble dont les éléments contribuent désormais à deux sommes distinctes au lieu de contribuer deux fois à une seule.

Vérifiez sur l'exemple récurrent. Les degrés sortants sont A 1, B 1, C 2, D 1, E 1, soit 6 au total. Les degrés entrants sont A 1, B 1, C 1, D 2, E 1, soit 6 également, le nombre d'arcs. Sur le graphe non orienté sous-jacent, les degrés sont 2, 2, 3, 2, 1, soit 10, deux fois ses 5 arêtes.

Deux types de sommets nommés en découlent immédiatement, sans aucun équivalent non orienté :

• Une source a un degré entrant nul : rien ne pointe vers elle.
• Un puits a un degré sortant nul : il ne pointe vers rien.

Sources et puits sont les points d'entrée et de sortie des réseaux de flot et les positions de départ et d'arrivée d'un ordre topologique. Dans un graphe non orienté, ces notions ne peuvent tout simplement pas s'exprimer.

4. Ce qui change dans la matrice et la liste

L'orientation se voit dans le stockage aussi clairement que dans la définition, et les différences sont celles que détaillent Cormen, Leiserson, Rivest et Stein dans Introduction to Algorithms.

La matrice d'adjacence. Pour un graphe non orienté, la matrice est toujours symétrique, A = AT, car {u, v} et {v, u} sont la même arête. Pour un graphe orienté, elle ne l'est généralement pas, et cette asymétrie porte une vraie information :

• Les sommes des lignes sont les degrés sortants, les sommes des colonnes les degrés entrants. Dans le cas non orienté, les deux donnent le degré, c'est pourquoi la distinction n'apparaît jamais.
• La transposée AT est exactement le graphe inverse, où chaque arc est retourné. Inverser un graphe non orienté ne change rien, ce qui revient à dire que A = AT.
• Le coefficient (Ak)uv compte les marches de longueur k de u à v dans les deux mondes, mais dans le cas orienté ces marches doivent respecter les flèches, donc ce nombre diffère en général de (Ak)vu.

La liste d'adjacence. Un graphe non orienté stocke chaque arête deux fois, une fois dans la liste de chaque extrémité, donc les listes contiennent 2m entrées. Un graphe orienté stocke chaque arc une fois, dans la liste de son origine, ce qui donne m entrées. Cela a une conséquence pratique qui surprend la première fois : pour parcourir un graphe orienté à rebours, il faut une seconde structure, la liste d'adjacence inverse, car la liste d'un sommet vous dit où vous pouvez aller, pas d'où vous venez. L'algorithme de Kosaraju pour les composantes fortement connexes repose directement sur cette observation et parcourt le graphe inverse lors de sa seconde passe.

Deux bornes en découlent. Un graphe simple non orienté à n sommets a au plus n(n-1)/2 arêtes. Un graphe orienté sans boucle a au plus n(n-1) arcs, exactement deux fois plus, car chaque couple ordonné est désormais une case à part.

5. Orientations et graphe sous-jacent

Les deux mondes sont reliés par deux constructions qui vont en sens opposés, et bien les nommer dissipe beaucoup de confusion.

• Étant donné un graphe orienté D, son graphe sous-jacent est ce qu'on obtient en oubliant les flèches : remplacez chaque arc (u, v) par l'arête {u, v} et supprimez les doublons. Le graphe sous-jacent de l'exemple récurrent a 5 arêtes, une de moins que les 6 arcs du graphe orienté, car le digone entre D et E se confond en une arête.
• Étant donné un graphe non orienté G, une orientation de ce graphe est un graphe orienté obtenu en choisissant exactement un sens pour chaque arête. Le résultat est antisymétrique : aucun digone, puisque chaque arête donne un seul arc.

Ce ne sont pas des opérations réciproques. Passer au graphe sous-jacent perd une information qu'aucune orientation ne peut restaurer, et un graphe à m arêtes possède 2m orientations distinctes, puisque chaque arête est un choix binaire indépendant. Le graphe sous-jacent de l'exemple récurrent a 5 arêtes, donc 32 orientations, et le graphe orienté d'origine n'en fait même pas partie, car il contient un digone.

Cela soulève la question à laquelle répond la section suivante. Parmi ces 2m orientations, y en a-t-il une bonne, au sens où l'on peut encore aller partout ?

6. Le théorème de Robbins : quelles rues peuvent passer en sens unique

En 1939, Herbert Robbins publia un court article dans la revue American Mathematical Monthly sous le titre mémorable « A theorem on graphs, with an application to a problem of traffic control ». Le problème est exactement celui d'un urbaniste : si toutes les rues passent en sens unique, les automobilistes peuvent-ils encore atteindre chaque quartier ?

Théorème de Robbins. Un graphe non orienté connexe admet une orientation fortement connexe si et seulement s'il n'a pas de pont.

Un pont, aussi appelé isthme, est une arête dont la suppression déconnecte le graphe. Un graphe connexe sans pont est exactement un graphe 2-arête-connexe, dans lequel chaque arête appartient à un cycle. (La connexité compte ici : un graphe non connexe peut être sans pont sans être 2-arête-connexe.)

Un sens de la démonstration est le plus facile et mérite d'être vu, car il explique tout le résultat. Supposons que e = {u, v} soit un pont, de sorte que sa suppression sépare le graphe en une composante contenant u et une composante contenant v. Toute orientation doit envoyer e dans un sens ou dans l'autre. S'il devient (u, v) , alors rien du côté de vne peut jamais revenir du côté de u, car e était la seule connexion et pointe désormais dans le mauvais sens. S'il devient (v, u) , le même argument s'applique à l'envers. Dans les deux cas, l'orientation n'est pas fortement connexe. La réciproque, à savoir que tout graphe connexe sans pont admet bel et bien une orientation fortement connexe, est la moitié substantielle ; la démonstration standard lance un parcours en profondeur et oriente les arêtes de l'arbre en s'éloignant de la racine et les arêtes arrière vers elle.

L'exemple récurrent rend le théorème concret. Son graphe sous-jacent contient le triangle A, B, C, sans pont, mais les arêtes {C, D} et {D, E} sont toutes deux des ponts. D'après le théorème de Robbins, aucune orientation de ce graphe n'est donc fortement connexe, et c'est précisément pourquoi le graphe orienté de la figure n'est pas fortement connexe, quelle que soit la façon dont on redessine les flèches.

Nash-Williams a généralisé le résultat en 1960 : tout graphe non orienté 2k-arête-connexe admet une orientation k-arc-connexe, dont le théorème de Robbins est le cas k = 1. La lecture pratique reste la même. Les plans de circulation à sens unique sont sûrs exactement là où le réseau routier est redondant, et une route unique reliant un quartier au reste de la ville ne peut jamais passer en sens unique sans l'isoler.

7. La connexité devient trois questions différentes

Dans un graphe non orienté, la connexité se résume à oui ou non : existe-t-il un chemin entre chaque paire de sommets ? L'orientation transforme cela en hiérarchie. La classification est due à l'ouvrage Structural Models de Harary, Norman et Cartwright, et c'est la partie de la théorie des graphes orientés la plus souvent sautée et la plus souvent nécessaire.

Chaque condition implique celle du dessous : fortement connexe implique unilatéralement connexe, qui implique faiblement connexe. L'exemple récurrent se situe exactement au milieu de la hiérarchie, ce qui est le cas courant en pratique : on peut sortir du triangle A, B, C vers D et E, mais jamais revenir.

Le raffinement utile consiste à ne plus interroger le graphe orienté entier mais ses parties. Une composante fortement connexe, ou CFC, est un ensemble maximal de sommets dans lequel chaque sommet atteint tous les autres. Tout graphe orienté se partitionne de façon unique en CFC, et contracter chacune en un seul sommet produit la condensation, qui est toujours acyclique. Ce dernier fait n'a rien d'un hasard : si la condensation contenait un circuit, chaque composante de ce circuit atteindrait toutes les autres, et elles n'auraient formé qu'une seule CFC dès le départ.

Trouver les CFC prend un temps linéaire. L'article de Tarjan de 1972, « Depth-first search and linear graph algorithms », le fait en un seul parcours en profondeur grâce aux valeurs low-link, et la méthode de Kosaraju-Sharir le fait en deux passes, la seconde sur le graphe inverse. Les deux s'exécutent en O(n + m), et aucune n'a d'équivalent non orienté, car dans un graphe non orienté les composantes connexes découlent de n'importe quel parcours.

8. Cycles, DAG et ordre topologique

Le mot « cycle » prend discrètement un sens plus strict dès que des flèches entrent en jeu, et cet écart cause de vrais bugs.

Dans un graphe simple non orienté, un cycle est une marche fermée sans sommet répété, et il lui faut au moins trois sommets, puisque suivre une arête puis revenir aussitôt ne compte pas comme un cycle. Un graphe non orienté sans cycle est une forêt, et s'il est connexe, c'est un arbre.

Dans un graphe orienté, un circuit doit suivre les flèches sur tout le tour, et un digone compte : les deux arcs (D, E) et (E, D) forment un circuit de longueur 2. Un graphe orienté sans circuit est un DAG, un graphe orienté acyclique, et les DAG possèdent une propriété qui n'a pas d'équivalent dans le monde non orienté :

Un graphe orienté admet un ordre topologique, c'est-à-dire une disposition linéaire de ses sommets où chaque arc pointe vers l'avant, si et seulement s'il est acyclique.

L'article de Kahn de 1962 dans les Communications of the ACM a donné l'algorithme standard : prenez à répétition un sommet de degré entrant nul, écrivez-le en sortie et supprimez-le avec ses arcs sortants. Si le graphe se vide, la sortie est un ordre topologique ; s'il se bloque alors qu'il reste des sommets, chaque sommet restant appartient à un circuit. Les détails se trouvent dans le guide sur le tri topologique.

Deux pièges en découlent :

• Qu'il y ait un cycle dans le graphe sous-jacent ne dit rien. Le graphe sous-jacent de l'exemple récurrent contient le triangle A, B, C, et son graphe orienté y contient bien un circuit. Mais orientez ce même triangle en A → B, A → C, B → C et vous obtenez un DAG dont le graphe sous-jacent a toujours un cycle. La détection de cycles non orientée ne peut pas répondre à une question orientée.
• La détection de cycles est un autre algorithme. Dans un graphe non orienté, un DFS trouve un cycle dès qu'il rencontre un sommet déjà visité qui n'est pas le parent d'où il vient. Dans un graphe orienté, ce test est faux : il faut trouver un arc arrière vers un sommet encore sur la pile de récursion courante, car un arc vers un sommet déjà terminé est sans danger.

9. Quels algorithmes se transposent, et lesquels cassent

La question pratique est de savoir quelles parties de la boîte à outils non orientée survivent au passage. Le schéma est plus clair qu'il n'y paraît : tout ce qui ne fait que suivre les arêtes vers l'avant se transpose, et tout ce qui repose sur la symétrie, non.

La ligne de l'arbre couvrant de poids minimum est celle qui piège même les plus expérimentés. Les algorithmes de Kruskal et de Prim sont gloutons sur une structure de coûts symétrique, et aucun ne survit à l'orientation. La bonne question orientée est celle de l'arborescence couvrante minimale : choisir un ensemble d'arcs de poids total minimal tel que chaque sommet soit accessible depuis une racine fixée. Chu et Liu en 1965 et Edmonds en 1967 l'ont résolu indépendamment, et l'algorithme ne ressemble en rien à un balayage d'arêtes triées : il sélectionne l'arc entrant le moins cher de chaque sommet, puis contracte tout circuit qui se forme et recommence.

10. Choisir : votre relation est-elle symétrique ?

La question de modélisation n'a qu'une forme : si la relation vaut de u vers v, doit-elle valoir de v vers u ? Si oui, utilisez un graphe non orienté. Si non, ou en cas de doute, utilisez un graphe orienté, car un graphe orienté peut toujours exprimer une relation symétrique, mais pas l'inverse.

Un cas mérite une attention particulière, car il a l'air symétrique sans l'être. Une arête non orientée ne peut porter qu'un seul poids. Si le coût pour aller de u à v diffère du coût du retour, la relation est mutuelle, mais le modèle doit tout de même être orienté. Monter et descendre une côte à vélo, envoyer et recevoir des données sur un lien asymétrique, changer des devises dans un sens ou dans l'autre : autant de connexions mutuelles aux coûts différents, et chacune impose un graphe orienté à deux arcs de poids différents.

11. Passer de l'un à l'autre

Trois conversions reviennent sans cesse, et chacune perd ou invente quelque chose dont il faut avoir conscience.

• Du graphe orienté au non orienté (symétrisation). Remplacez chaque arc par une arête. Cela invente de l'accessibilité : après symétrisation de l'exemple récurrent, D atteint A, ce qui était faux dans l'original. Ne l'utilisez que si vous voulez vraiment poser une question sur la structure sous-jacente, par exemple savoir si le graphe orienté est faiblement connexe. Une variante plus stricte ne garde que les couples mutuels et donne le graphe « réciproque », qui n'invente rien mais écarte beaucoup.
• Du non orienté au graphe orienté (orientation). Choisissez un sens par arête. Cela détruit l'accessibilité mutuelle, sauf si le graphe est sans pont, et c'est exactement le théorème de Robbins de la section 6.
• Le non orienté vu comme graphe orienté (doublement des arcs). Remplacez chaque arête {u, v} par les deux arcs (u, v) et (v, u). C'est ce que font en interne presque toutes les bibliothèques de graphes, et c'est fidèle pour les parcours et les plus courts chemins. Mais cela fait de chaque arête un circuit de longueur 2 : tout test de DAG répond désormais non, chaque composante connexe devient une seule composante fortement connexe, et un détecteur de cycles signale un cycle pour chaque arête. La représentation est correcte ; y exécuter des algorithmes structurels orientés ne l'est pas.

12. Erreurs courantes

• Construire la liste d'adjacence dans un seul sens pour un graphe non orienté. Le bug de graphe le plus répandu qui soit. Lire une liste d'arêtes en ajoutant seulement adj[u].push(v) produit silencieusement un graphe orienté, et votre BFS ne trouve alors aucun chemin le long d'une arête qu'il voit pourtant.
• La construire dans les deux sens pour un graphe orienté. La même erreur à l'envers, et plus difficile à repérer : le code tourne, les chemins semblent plausibles, et toutes les réponses qui dépendaient du sens sont fausses.
• Utiliser la détection de cycles non orientée sur un graphe orienté. Signaler un cycle chaque fois que le DFS rencontre un sommet visité autre que le parent fait passer beaucoup de DAG pour cycliques. Les graphes orientés ont besoin du test de l'arc arrière vers la pile de récursion.
• Supposer que l'accessibilité est symétrique. « Existe-t-il un chemin de u à v ? » et « existe-t-il un chemin de v à u ? » sont deux requêtes différentes dans un graphe orienté, et répondre à l'une ne répond pas à l'autre.
• Oublier qu'il faut le graphe inverse. « Quels sommets peuvent atteindre v ? » ne peut pas se résoudre à partir de la liste d'adjacence directe sans un balayage complet. Construisez la liste inverse une fois si vous posez souvent cette question.
• Chercher un MST sur un graphe orienté. Kruskal et Prim n'ont pas de version orientée. Ce qu'il vous faut, c'est une arborescence minimale.
• Symétriser pour réutiliser une bibliothèque. Pratique, et cela change la réponse. Chaque conversion de la section 11 a un coût, faites-la donc en connaissance de cause.

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. Robbins, H. E. (1939). "A theorem on graphs, with an application to a problem of traffic control." American Mathematical Monthly 46(5), 281 à 283. Le théorème d'orientation des graphes sans pont de la section 6.
2. Ford, L. R. et Fulkerson, D. R. (1956). "Maximal flow through a network." Canadian Journal of Mathematics 8, 399 à 404. Le flot, posé sur un graphe orienté dès l'origine.
3. Nash-Williams, C. St. J. A. (1960). "On orientations, connectivity and odd-vertex-pairings in finite graphs." Canadian Journal of Mathematics 12, 555 à 567. La généralisation de Robbins à la k-arc-connexité.
4. Kahn, A. B. (1962). "Topological sorting of large networks." Communications of the ACM 5(11), 558 à 562.
5. Chu, Y. J. et Liu, T. H. (1965). "On the shortest arborescence of a directed graph." Scientia Sinica 14, 1396 à 1400.
6. Harary, F., Norman, R. Z. et Cartwright, D. (1965). Structural Models: An Introduction to the Theory of Directed Graphs. New York : Wiley. Source de la classification en connexité forte, unilatérale et faible.
7. Edmonds, J. (1967). "Optimum branchings." Journal of Research of the National Bureau of Standards 71B(4), 233 à 240.
8. Tarjan, R. E. (1972). "Depth-first search and linear graph algorithms." SIAM Journal on Computing 1(2), 146 à 160. Composantes fortement connexes en temps linéaire.
9. Sharir, M. (1981). "A strong-connectivity algorithm and its applications in data flow analysis." Computers & Mathematics with Applications 7(1), 67 à 72. La méthode en deux passes habituellement associée au nom de Kosaraju.
10. Brin, S. et Page, L. (1998). "The anatomy of a large-scale hypertextual Web search engine." Computer Networks and ISDN Systems 30(1 à 7), 107 à 117. PageRank sur le graphe orienté du Web.
11. West, D. B. (2001). Introduction to Graph Theory, 2e édition. Upper Saddle River : Prentice Hall.
12. Bondy, J. A. et Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. Londres : Springer.
13. Bang-Jensen, J. et Gutin, G. (2009). Digraphs: Theory, Algorithms and Applications, 2e édition. Londres : Springer. La référence standard pour la terminologie des graphes orientés.
14. 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 4.
15. Chartrand, G., Lesniak, L. et Zhang, P. (2015). Graphs & Digraphs, 6e édition. Boca Raton : CRC Press. Un manuel qui développe les deux objets en parallèle.
16. Diestel, R. (2017). Graph Theory, 5e édition. Graduate Texts in Mathematics 173. Berlin : Springer. Source des deux définitions citées dans la section 1.