Graphe orienté : sommets, arcs et représentations

Un graphe orienté est un ensemble de sommets reliés par des arcs, c'est-à-dire des flèches qui vont d'un sommet vers un autre. On le représente de trois façons équivalentes : par un dessin, par le tableau des successeurs (ou des prédécesseurs) de chaque sommet, et par une matrice d'adjacence faite de 0 et de 1. Ce chapitre pose le vocabulaire de tout le cours et t'apprend à passer d'une représentation à l'autre, la première question de presque tous les exercices de graphes de l'E3.

Définition d'un graphe orienté

Un graphe fini simple orienté G est la donnée :

• d'un ensemble fini S de sommets ;
• d'un ensemble U d'arcs : chaque arc est un couple (x, y) de sommets, qu'on dessine par une flèche de x vers y.

Dans l'arc (x, y), x est l'origine (ou extrémité initiale) et y l'extrémité (ou extrémité finale). On dit que y est un successeur de x et que x est un prédécesseur de y. Un arc (x, x), qui part d'un sommet et y revient, s'appelle une boucle.

« Simple » veut dire qu'il y a au plus un arc de x vers y : on ne dessine jamais deux flèches parallèles dans le même sens. Rien n'empêche en revanche d'avoir à la fois l'arc (x, y) et l'arc (y, x) : ce sont deux couples différents. Le nombre de sommets s'appelle l'ordre du graphe.

L'exemple fil rouge : le cycle de vie d'un ticket

Dans un outil de gestion des incidents comme GLPI, un ticket passe par plusieurs états. On en retient cinq :

• A : nouveau ;
• B : attribué à un technicien ;
• C : en cours de traitement ;
• D : résolu ;
• E : clos.

Les passages autorisés d'un état à l'autre sont les arcs du graphe :

• A → B : le ticket est attribué ; A → E : un doublon est clos tout de suite ;
• B → A : le technicien rend le ticket, qui revient dans la file ; B → C : il commence à le traiter ;
• C → C : chaque mise à jour (un commentaire, une relance) laisse le ticket en cours, c'est une boucle ;
• C → D : la solution est proposée ;
• D → C : l'utilisateur refuse la solution et le ticket est rouvert ; D → E : il accepte et le ticket est clos.

Ce graphe G a 5 sommets, S = {A, B, C, D, E}, et 8 arcs :

U = {(A, B) ; (A, E) ; (B, A) ; (B, C) ; (C, C) ; (C, D) ; (D, C) ; (D, E)}.

Il servira d'exemple jusqu'au chapitre 4. Tu y vois déjà les situations à repérer : deux arcs opposés entre A et B, deux autres entre C et D, une boucle sur C, et un sommet E d'où ne part aucun arc.

Successeurs et prédécesseurs

Pour chaque sommet x, on note :

• Γ⁺(x) l'ensemble de ses successeurs, les sommets vers lesquels part une flèche depuis x ;
• Γ⁻(x) l'ensemble de ses prédécesseurs, les sommets d'où part une flèche vers x.

(Γ est la lettre grecque gamma majuscule ; certains manuels écrivent Γ(x) pour Γ⁺(x), ou parlent de « suivants » et de « précédents ».)

Le graphe G est entièrement décrit par le tableau des successeurs :

ou, aussi bien, par le tableau des prédécesseurs :

Pour passer de l'un à l'autre, relis chaque arc dans l'autre sens : l'arc (B, C) met C parmi les successeurs de B, donc B parmi les prédécesseurs de C. Avec la boucle (C, C), C est à la fois successeur et prédécesseur de lui-même.

Un sommet sans prédécesseur est une source (ou entrée) du graphe, un sommet sans successeur un puits (ou sortie). Dans G, il n'y a pas de source (chaque sommet est l'extrémité d'au moins un arc) et E est un puits. Ces deux notions reviennent au chapitre 5 pour les niveaux, et en ordonnancement pour les tâches de début et de fin.

La matrice d'adjacence

La matrice d'adjacence d'un graphe à n sommets rangés dans un ordre fixé est la matrice carrée M de taille n × n dont le coefficient situé à la ligne i et à la colonne j vaut :

• 1 s'il existe un arc du i-ème sommet vers le j-ème sommet ;
• 0 sinon.

On l'appelle aussi matrice booléenne du graphe, puisqu'elle ne contient que des 0 et des 1. Avec les sommets dans l'ordre alphabétique A, B, C, D, E, la matrice de G est :

Les lignes correspondent aux origines, les colonnes aux extrémités : le 1 de la ligne D, colonne E, code l'arc (D, E).

Ce que la matrice permet de lire tout de suite :

• la ligne d'un sommet donne ses successeurs : la ligne B, (1 0 1 0 0), donne Γ⁺(B) = {A, C} ;
• la colonne d'un sommet donne ses prédécesseurs : la colonne C, de haut en bas (0 1 1 1 0), donne Γ⁻(C) = {B, C, D} ;
• un 1 sur la diagonale signale une boucle : le coefficient ligne C, colonne C vaut 1 ;
• le nombre de 1 est le nombre d'arcs : 8 ici ;
• une ligne de 0 est un puits (E), une colonne de 0 serait une source.

Passer d'une représentation à l'autre

Le programme demande de savoir passer de n'importe quelle représentation à n'importe quelle autre. Une seule idée suffit : chaque arc (x, y) est un 1 à la ligne x, colonne y, et une flèche de x vers y.

Du dessin à la matrice. Parcours les sommets dans l'ordre. Pour chacun, écris sa ligne : un 1 dans la colonne de chacun de ses successeurs, des 0 ailleurs. Vérifie enfin que le nombre de 1 est égal au nombre de flèches du dessin.

De la matrice au dessin. Place les sommets, puis lis la matrice ligne par ligne : chaque 1 de la ligne x, colonne y, devient une flèche de x vers y, et chaque 1 sur la diagonale une boucle.

Exemple. Le graphe H de sommets A, B, C, D a pour matrice :

• Ligne A : des 1 en colonnes B et C, d'où les arcs (A, B) et (A, C).
• Ligne B : un 1 en colonne D, d'où (B, D).
• Ligne C : des 1 en colonnes B et D, d'où (C, B) et (C, D).
• Ligne D : un 1 en colonne A, d'où (D, A).

H a 6 arcs. Son tableau des successeurs est : A → B, C ; B → D ; C → B, D ; D → A. Son tableau des prédécesseurs se lit dans les colonnes : Γ⁻(A) = {D}, Γ⁻(B) = {A, C}, Γ⁻(C) = {A}, Γ⁻(D) = {B, C}. La diagonale ne contient que des 0 : H n'a pas de boucle. Ce graphe reviendra dans les exercices du chapitre 3.

Graphe orienté ou non orienté ?

Quand le sens d'un lien n'a pas d'importance (deux routeurs reliés par un câble, deux amis sur un réseau social), on utilise un graphe non orienté : ses liens s'appellent des arêtes et se dessinent sans flèche. Sa matrice d'adjacence est symétrique par rapport à la diagonale. Le programme du BTS SIO ne traite que les graphes orientés ; une arête peut toujours être vue comme deux arcs opposés. Les notions propres aux graphes non orientés (degré, chaîne, cycle, connexité) sont présentées en complément au chapitre 11.

Où trouve-t-on des graphes en informatique ?

Partout où des objets sont reliés par des relations :

• les réseaux : les routeurs sont les sommets, les liaisons les arcs, et les protocoles de routage comme OSPF cherchent des plus courts chemins dans ce graphe (chapitre 7) ;
• le web : chaque page est un sommet, chaque lien hypertexte un arc ; les moteurs de recherche analysent ce graphe pour classer les pages ;
• les dépendances : un paquet logiciel dépend d'autres paquets, une tâche d'un pipeline d'intégration continue attend la fin d'autres tâches ; ces graphes ne doivent pas avoir de circuit (chapitre 5) ;
• l'historique Git : chaque commit pointe vers son ou ses parents ;
• les bases de données : le schéma relationnel est un graphe dont les arcs sont les clés étrangères, et une requête récursive parcourt une hiérarchie stockée dans une table (CTE récursive) ;
• la gestion de projet : les tâches et leurs contraintes d'antériorité forment le graphe de l'ordonnancement (chapitre 8).

En Python : représenter un graphe

Un programme stocke un graphe de deux façons, qui correspondent aux représentations du cours : un dictionnaire des successeurs (le tableau des successeurs) ou une liste de listes (la matrice d'adjacence).

# Le graphe G du ticket : dictionnaire des successeurs
G = {
    "A": ["B", "E"],
    "B": ["A", "C"],
    "C": ["C", "D"],
    "D": ["C", "E"],
    "E": [],
}

def matrice_adjacence(graphe):
    """Construit la matrice d'adjacence, sommets dans l'ordre alphabétique."""
    sommets = sorted(graphe)
    return [[1 if y in graphe[x] else 0 for y in sommets] for x in sommets]

M = matrice_adjacence(G)
for ligne in M:
    print(ligne)
# [0, 1, 0, 0, 1]
# [1, 0, 1, 0, 0]
# [0, 0, 1, 1, 0]
# [0, 0, 1, 0, 1]
# [0, 0, 0, 0, 0]

nb_arcs = sum(sum(ligne) for ligne in M)
print(nb_arcs)   # 8

Le dictionnaire prend peu de place quand le graphe a peu d'arcs ; la matrice permet de savoir en une lecture si un arc existe, et de faire les calculs matriciels des chapitres 3 et 4. Les parcours de graphe en Python (en largeur, en profondeur) sont expliqués dans le cours d'algorithmique.

Exercices

def successeurs(M, sommets):
    n = len(sommets)
    return {sommets[i]: [sommets[j] for j in range(n) if M[i][j] == 1]
            for i in range(n)}

H = [[0, 1, 1, 0],
     [0, 0, 0, 1],
     [0, 1, 0, 1],
     [1, 0, 0, 0]]
print(successeurs(H, ["A", "B", "C", "D"]))
# {'A': ['B', 'C'], 'B': ['D'], 'C': ['B', 'D'], 'D': ['A']}