Découvrez les graphes et leur vocabulaire

Un réseau de bus, des pages web reliées par des liens, des tâches qui dépendent les unes des autres, des utilisateurs qui se suivent sur un réseau social : tous ces objets ont la même forme. Des éléments, et des relations entre ces éléments. Un graphe est l’outil mathématique qui capture exactement cette forme, et c’est pour cela qu’il est partout en informatique.

Dans ce chapitre, vous allez poser le vocabulaire de base, puis voir comment un graphe se stocke dans la mémoire d’un ordinateur. Notre fil rouge : un petit réseau de navettes entre cinq sites rennais.

Le fil rouge : des navettes entre cinq sites

Imaginez un service de navettes qui relie cinq sites de Rennes : le campus de Beaulieu, le Centre, la Gare, le campus de Villejean et Ker Lann. Certaines lignes ne circulent que dans un sens :

• Beaulieu → Centre et Centre → Beaulieu (une ligne dans chaque sens) ;
• Centre → Gare, Gare → Villejean, Villejean → Centre ;
• Gare → Ker Lann, Ker Lann → Beaulieu.

Ce dessin est un graphe orienté. Les cinq sites sont ses sommets, les sept lignes sont ses arcs. La position des sommets sur le dessin n’a aucune importance : seule compte l’information « qui est relié à qui, et dans quel sens ».

Graphes orientés et non orientés

Les définitions

Un graphe orienté se note $G = (X, U)$ :

• $X$ est l’ensemble des sommets (vertices, ou nœuds) ;
• $U$ est l’ensemble des arcs (arcs, ou edges dirigés), chaque arc étant un couple $(x, y)$ de sommets : il part de $x$ (son origine) et arrive en $y$ (son extrémité).

Un arc $(x, x)$ qui revient sur son sommet de départ s’appelle une boucle. Si plusieurs arcs peuvent relier les mêmes deux sommets dans le même sens, on parle de multigraphe (ou de $p$-graphe, s’il y en a au plus $p$). Dans la suite du cours, sauf mention contraire, un « graphe » a au plus un arc de $x$ vers $y$ : on peut alors le décrire par sa fonction successeur $\Gamma$ et le noter $G = (X, \Gamma)$.

Quand le sens n’a pas d’importance (une rue à double sens, une amitié), on parle de graphe non orienté. Les liens s’appellent alors des arêtes (edges) et se notent $[x, y]$.

• $\Gamma(x)$ est l’ensemble des successeurs de $x$ : les sommets $y$ tels que $(x, y)$ est un arc. Ici, $\Gamma(G) = \lbrace V, K \rbrace$.
• $\Gamma^{-1}(x)$ est l’ensemble de ses prédécesseurs. Ici, $\Gamma^{-1}(C) = \lbrace B, V \rbrace$.
• L’ordre du graphe est son nombre de sommets, $n = \lvert X \rvert$ ; sa taille est son nombre d’arcs, $m = \lvert U \rvert$. Notre réseau a $n = 5$ et $m = 7$.
• La densité d’un graphe orienté sans arcs multiples est $m / n^2$ : la proportion d’arcs présents parmi tous les arcs possibles (boucles comprises). Ici, $7 / 25 = 0{,}28$.

Attention

Le vocabulaire change selon que le graphe est orienté ou non, et les confusions coûtent des points : arc et chemin pour l’orienté, arête et chaîne pour le non orienté. En anglais, on dit souvent « edge » et « path » dans les deux cas, ce qui n’aide pas.

Les degrés

Le demi-degré extérieur $d^+(x)$ est le nombre d’arcs qui partent de $x$ ; le demi-degré intérieur $d^-(x)$ est le nombre d’arcs qui y arrivent. Le degré est leur somme, $d(x) = d^+(x) + d^-(x)$ (une boucle compte deux fois).

Exemple

Pour le réseau de navettes :

Sommet	B	C	G	V	K	Total
$d^+$	1	2	2	1	1	7
$d^-$	2	2	1	1	1	7
$d$	3	4	3	2	2	14

Les deux lignes de demi-degrés ont la même somme, égale au nombre d’arcs, et la somme des degrés vaut le double.

Ce n’est pas un hasard : chaque arc a exactement une origine et une extrémité. D’où la relation, valable pour tout graphe :

$$\sum_{x \in X} d^+(x) = \sum_{x \in X} d^-(x) = m \qquad \text{et} \qquad \sum_{x \in X} d(x) = 2m$$

Une conséquence amusante (le « lemme des poignées de main ») : dans un graphe non orienté, le nombre de sommets de degré impair est toujours pair. Un graphe dont tous les sommets ont le même degré $k$ est dit $k$-régulier.

Chaque arc compte une fois dans un d⁺ (à son origine) et une fois dans un d⁻ (à son extrémité) : les deux sommes valent m = 7.

Enfin, pour un sous-ensemble de sommets $A$, le cocycle $\omega(A)$ est l’ensemble des arcs qui ont une extrémité dans $A$ et l’autre dehors. On distingue $\omega^+(A)$ (les arcs qui sortent de $A$) et $\omega^-(A)$ (ceux qui y entrent). Cette notion reviendra pour les arbres couvrants (chapitre 5) et les flots (chapitre 9).

Le cocycle de A = {B, C} : un arc sortant, C → G, et deux arcs entrants, V → C et K → B. Les arcs entre B et C, intérieurs à A, n'en font pas partie.

Se déplacer dans un graphe : chemins et chaînes

Chemins, chaînes, circuits, cycles

Un chemin est une suite d’arcs consécutifs dans le sens des flèches : B → C → G → K est un chemin de B à K. Sa longueur est son nombre d’arcs (ici 3). Une chaîne est la même idée sans tenir compte du sens : on a le droit de remonter un arc à contre-courant.

• Un chemin est simple s’il n’emprunte pas deux fois le même arc, et élémentaire s’il ne passe pas deux fois par le même sommet. Élémentaire implique simple (si vous ne repassez par aucun sommet, vous ne pouvez pas réemprunter un arc), mais pas l’inverse.
• Un circuit est un chemin simple qui revient à son point de départ : C → G → V → C en est un. En non orienté, on parle de cycle.

Un chemin et un circuit suivent les flèches ; une chaîne peut remonter un arc à contre-sens, comme G → V ici.

Piège

« Il existe une chaîne de x à y » ne dit rien sur l’existence d’un chemin. Dans notre réseau, il y a une chaîne entre V et G (l’arc G → V lu à l’envers), et il y a aussi un chemin de V à G (V → C → G). Mais dans un graphe orienté quelconque, on peut très bien être relié à un sommet sans pouvoir s’y rendre.

Eulérien ou hamiltonien ?

Deux questions célèbres se posent sur les parcours complets d’un graphe :

• Peut-on emprunter chaque arête exactement une fois ? C’est une chaîne eulérienne (un camion de déneigement qui veut passer une fois dans chaque rue).
• Peut-on visiter chaque sommet exactement une fois ? C’est une chaîne hamiltonienne (un livreur qui veut passer une fois chez chaque client).

Les deux questions se ressemblent, mais leur difficulté n’a rien à voir. Pour la première, Euler a donné en 1736 un critère très simple, à propos des sept ponts de Königsberg :

À retenir

Théorème d’Euler. Un graphe non orienté connexe (aux sommets isolés près) admet une chaîne eulérienne si et seulement s’il a 0 ou 2 sommets de degré impair. Avec 0, la chaîne peut se refermer en cycle eulérien ; avec 2, elle part forcément de l’un et finit à l’autre.

L’intuition : chaque fois que vous traversez un sommet, vous utilisez une arête pour entrer et une pour sortir. Seuls le départ et l’arrivée peuvent « consommer » un nombre impair d’arêtes. À Königsberg, les quatre quartiers avaient pour degrés 5, 3, 3 et 3 : quatre sommets impairs, donc aucune promenade possible.

Quatre sommets impairs à Königsberg : impossible. Avec exactement deux sommets impairs, la chaîne eulérienne existe et va de l'un à l'autre.

Pour la question hamiltonienne, en revanche, on ne connaît aucun critère simple : décider si un graphe admet un cycle hamiltonien est un problème NP-complet. C’est la famille du célèbre problème du voyageur de commerce. Il n’y a d’ailleurs aucun lien entre les deux propriétés : un graphe peut être eulérien sans être hamiltonien, et inversement.

Représenter un graphe en mémoire

Un dessin, c’est bien pour nous, mais un programme a besoin d’une structure de données. Il en existe trois classiques, et le choix n’est pas neutre : il change la complexité des algorithmes.

La matrice d’adjacence

On numérote les sommets de 1 à $n$ et on remplit une matrice $n \times n$ avec $M[x, y] = 1$ si l’arc $(x, y)$ existe, 0 sinon. Pour les navettes, dans l’ordre B, C, G, V, K :

	B	C	G	V	K
B	0	1	0	0	0
C	1	0	1	0	0
G	0	0	0	1	1
V	0	1	0	0	0
K	1	0	0	0	0

La somme de la ligne $x$ donne $d^+(x)$, celle de la colonne donne $d^-(x)$. Pour un graphe non orienté, la matrice est symétrique.

Les listes de successeurs

On stocke, pour chaque sommet, la liste de ses successeurs : B : [C] ; C : [B, G] ; G : [V, K] ; V : [C] ; K : [B]. En Python, c’est tout simplement un dictionnaire de listes. C’est la représentation la plus utilisée en pratique (on dit aussi listes d’adjacence).

Les mêmes sept arcs, stockés de deux façons : la matrice réserve une case par couple possible, les listes ne stockent que les arcs présents.

La matrice d’incidence sommets-arcs

On numérote aussi les arcs, et on remplit une matrice $n \times m$ : la case (sommet $x$, arc $u$) vaut $+1$ si $x$ est l’origine de $u$, $-1$ si c’est son extrémité, 0 sinon. Chaque colonne contient donc exactement un $+1$ et un $-1$ (pour un graphe sans boucle). Cette représentation est plus rare en programmation, mais très utile en optimisation : c’est elle qui apparaît dans les équations de conservation des flots.

Laquelle choisir ?

Représentation	Mémoire	Successeurs de $x$	Prédécesseurs de $x$	L’arc $(x, y)$ existe-t-il ?
Matrice d’adjacence	$n^2$	$O(n)$	$O(n)$	$O(1)$
Listes de successeurs	$n + m$	$O(d^+(x))$	$O(n + m)$	$O(d^+(x))$
Matrice d’incidence	$n \times m$	$O(m)$	$O(m)$	$O(m)$

Les graphes réels sont presque toujours creux (sparse) : un réseau social d’un million de personnes n’a pas mille milliards de liens. Avec $n = 10^6$ sommets et $m = 10^7$ arcs, une matrice d’adjacence occuperait $10^{12}$ cases, contre environ $10^7$ entrées pour des listes. Les listes gagnent donc presque toujours ; la matrice reste intéressante pour les petits graphes denses et pour les algorithmes qui testent beaucoup d’arcs (comme Roy-Warshall, au chapitre 3).

En entretien

« Pour un graphe creux, je prends des listes d’adjacence : $O(n + m)$ en mémoire et un parcours des successeurs proportionnel au degré. La matrice d’adjacence ne se justifie que pour un graphe dense ou si j’ai besoin de tester l’existence d’un arc en temps constant. En calcul scientifique, on utilise une matrice creuse au format CSR, qui combine les deux avantages. »

En Python

# Listes de successeurs : un dictionnaire de listes
navettes = {
    "B": ["C"],
    "C": ["B", "G"],
    "G": ["V", "K"],
    "V": ["C"],
    "K": ["B"],
}

m = sum(len(succ) for succ in navettes.values())       # nombre d'arcs : 7
d_plus = {x: len(succ) for x, succ in navettes.items()}
d_moins = {x: 0 for x in navettes}
for succ in navettes.values():
    for y in succ:
        d_moins[y] += 1
print(m, d_plus, d_moins)

# Matrice d'adjacence construite à partir des listes
sommets = list(navettes)                                # ["B", "C", "G", "V", "K"]
indice = {x: i for i, x in enumerate(sommets)}
M = [[0] * len(sommets) for _ in sommets]
for x, succ in navettes.items():
    for y in succ:
        M[indice[x]][indice[y]] = 1

La bibliothèque networkx fournit ces structures toutes faites, avec des centaines d’algorithmes. Nous l’utiliserons en aperçu à chaque chapitre, après avoir codé les algorithmes nous-mêmes :

import networkx as nx

G = nx.DiGraph()                        # graphe orienté (nx.Graph() pour le non orienté)
G.add_edges_from([("B", "C"), ("C", "B"), ("C", "G"), ("G", "V"),
                  ("V", "C"), ("G", "K"), ("K", "B")])
print(G.number_of_nodes(), G.number_of_edges())       # 5 7
print(list(G.successors("G")), list(G.predecessors("C")))
print(dict(G.out_degree()), dict(G.in_degree()))

En résumé

• Un graphe orienté $G = (X, U)$ est formé de sommets et d’arcs $(x, y)$ ; un graphe non orienté a des arêtes $[x, y]$.
• $\Gamma(x)$ désigne les successeurs, $\Gamma^{-1}(x)$ les prédécesseurs ; $d^+$ et $d^-$ comptent les arcs sortants et entrants, et $\sum d^+ = \sum d^- = m$.
• Chemin et circuit respectent le sens des arcs ; chaîne et cycle l’ignorent. Élémentaire (pas de sommet répété) implique simple (pas d’arc répété).
• Une chaîne eulérienne existe si et seulement si le graphe est connexe avec 0 ou 2 sommets de degré impair ; l’existence d’une chaîne hamiltonienne est un problème NP-complet.
• On stocke un graphe par matrice d’adjacence ($n^2$), listes de successeurs ($n + m$) ou matrice d’incidence ($n \times m$) ; les listes sont le bon choix pour les graphes creux.

Exercices

Exercice · Compter des degrés

facile

Un graphe non orienté a 6 sommets de degrés 3, 3, 2, 2, 2 et 2.

1. Combien a-t-il d’arêtes ?
2. Peut-on le parcourir en empruntant chaque arête une seule fois, s’il est connexe ? D’où faut-il partir ?
3. Un camarade affirme avoir dessiné un graphe à 5 sommets de degrés 3, 3, 3, 2 et 2. Est-ce possible ?

Voir la solution

1. La somme des degrés vaut $3 + 3 + 2 + 2 + 2 + 2 = 14 = 2m$, donc $m = 7$ arêtes.
2. Oui : le graphe est connexe et a exactement deux sommets de degré impair. D’après le théorème d’Euler, il admet une chaîne eulérienne, qui part forcément de l’un des deux sommets de degré 3 et se termine à l’autre. Il n’admet pas de cycle eulérien.
3. Non : la somme des degrés vaudrait $13$, un nombre impair, alors qu’elle doit être égale à $2m$. Autrement dit, il y aurait trois sommets de degré impair, ce qui est impossible.

En code

Python

degres = [3, 3, 2, 2, 2, 2]
m = sum(degres) // 2                          # la somme des degrés vaut 2m
impairs = [d for d in degres if d % 2 == 1]   # sommets de degré impair
print(m, len(impairs))                        # 7 2 : chaîne eulérienne d'un sommet de degré 3 à l'autre

autre = [3, 3, 3, 2, 2]
print(sum(autre), sum(autre) % 2 == 0)        # 13 False : somme impaire, graphe impossible

R

degres <- c(3, 3, 2, 2, 2, 2)
m <- sum(degres) / 2                          # la somme des degrés vaut 2m
impairs <- sum(degres %% 2 == 1)              # sommets de degré impair
cat(m, impairs, "\n")                         # 7 2 : chaîne eulérienne d'un sommet de degré 3 à l'autre

autre <- c(3, 3, 3, 2, 2)
cat(sum(autre), sum(autre) %% 2 == 0, "\n")   # 13 FALSE : somme impaire, graphe impossible

Exercice · Choisir une représentation

moyen

Pour chacun des cas suivants, dites s’il vaut mieux une matrice d’adjacence ou des listes de successeurs, en justifiant par la mémoire ou la complexité.

1. Le graphe des abonnements d’un réseau social : 50 millions de comptes, en moyenne 200 abonnements par compte.
2. Un graphe de 300 villes dans lequel presque toutes les paires sont reliées, et où un algorithme doit tester des millions de fois « existe-t-il une liaison directe entre x et y ? ».
3. Un algorithme qui doit, pour chaque sommet, parcourir ses prédécesseurs, sur un graphe creux.

Voir la solution

1. Listes : il y a $m \approx 5 \times 10^7 \times 200 = 10^{10}$ arcs, contre $n^2 = 2{,}5 \times 10^{15}$ cases pour une matrice. La matrice serait 250 000 fois plus grosse, et presque entièrement remplie de zéros.
2. Matrice : $n^2 = 90\,000$ cases, c’est minuscule, le graphe est dense (les listes ne feraient presque rien gagner), et le test d’un arc se fait en $O(1)$ au lieu de parcourir une liste.
3. Des listes, mais de prédécesseurs (ou les deux types de listes). Avec des listes de successeurs seules, trouver les prédécesseurs d’un sommet oblige à parcourir tout le graphe, en $O(n + m)$. On construit donc une fois pour toutes les listes inverses, ce qui coûte aussi $O(n + m)$. C’est ce que fait nx.DiGraph, qui garde les deux.

En code

Python

# 1. Réseau social : listes (n + m entrées) contre matrice (n² cases)
n = 50e6
m = n * 200
print(f"{m:.0e} {n**2:.1e} {n**2 / m:.0f}")   # 1e+10 2.5e+15 250000

# 2. 300 villes : la matrice est minuscule
print(300 ** 2)                               # 90000

# 3. Listes de prédécesseurs construites en un seul passage sur les arcs, en O(n + m)
succ = {"B": ["C"], "C": ["B", "G"], "G": ["V", "K"], "V": ["C"], "K": ["B"]}
pred = {x: [] for x in succ}
for x, liste in succ.items():
    for y in liste:
        pred[y].append(x)
print(pred)   # {'B': ['C', 'K'], 'C': ['B', 'V'], 'G': ['C'], 'V': ['G'], 'K': ['G']}

R

# 1. Réseau social : listes (n + m entrées) contre matrice (n² cases)
n <- 50e6
m <- n * 200
cat(m, n^2, n^2 / m, "\n")                    # 1e+10 2.5e+15 250000

# 2. 300 villes : la matrice est minuscule
cat(300^2, "\n")                              # 90000

# 3. Listes de prédécesseurs construites en un seul passage sur les arcs, en O(n + m)
succ <- list(B = "C", C = c("B", "G"), G = c("V", "K"), V = "C", K = "B")
pred <- setNames(vector("list", length(succ)), names(succ))
for (x in names(succ)) for (y in succ[[x]]) pred[[y]] <- c(pred[[y]], x)
str(pred)   # B : C K ; C : B V ; G : C ; V : G ; K : G

Exercice · Lire une matrice d'incidence

difficile

Construisez la matrice d’incidence sommets-arcs du réseau de navettes, en numérotant les arcs dans l’ordre u1 = (B, C), u2 = (C, B), u3 = (C, G), u4 = (G, V), u5 = (V, C), u6 = (G, K), u7 = (K, B). Que vaut la somme de chaque colonne ? Et la somme de la ligne d’un sommet, si l’on compte séparément les $+1$ et les $-1$ ?

Voir la solution

	u1	u2	u3	u4	u5	u6	u7
B	+1	-1	0	0	0	0	-1
C	-1	+1	+1	0	-1	0	0
G	0	0	-1	+1	0	+1	0
V	0	0	0	-1	+1	0	0
K	0	0	0	0	0	-1	+1

Chaque colonne contient exactement un $+1$ (l’origine) et un $-1$ (l’extrémité), donc sa somme vaut 0. Sur la ligne d’un sommet, le nombre de $+1$ donne $d^+(x)$ et le nombre de $-1$ donne $d^-(x)$ : pour C, deux $+1$ et deux $-1$, soit $d^+(C) = d^-(C) = 2$. La somme d’une ligne vaut donc $d^+(x) - d^-(x)$, ce qui servira pour écrire la conservation d’un flot au chapitre 9.

En code

Python

import numpy as np

sommets = ["B", "C", "G", "V", "K"]
arcs = [("B", "C"), ("C", "B"), ("C", "G"), ("G", "V"), ("V", "C"), ("G", "K"), ("K", "B")]

I = np.zeros((len(sommets), len(arcs)), dtype=int)
for u, (x, y) in enumerate(arcs):
    I[sommets.index(x), u] = +1               # x est l'origine de l'arc u
    I[sommets.index(y), u] = -1               # y en est l'extrémité
print(I)
print(I.sum(axis=0))                          # [0 0 0 0 0 0 0] : chaque colonne est nulle
print((I == 1).sum(axis=1))                   # d+ : [1 2 2 1 1]
print((I == -1).sum(axis=1))                  # d- : [2 2 1 1 1]
print(I.sum(axis=1))                          # d+ - d- : [-1  0  1  0  0]

R

sommets <- c("B", "C", "G", "V", "K")
arcs <- rbind(c("B", "C"), c("C", "B"), c("C", "G"), c("G", "V"),
              c("V", "C"), c("G", "K"), c("K", "B"))

I <- matrix(0, length(sommets), nrow(arcs), dimnames = list(sommets, paste0("u", 1:7)))
for (u in 1:nrow(arcs)) {
  I[arcs[u, 1], u] <- +1                      # origine de l'arc u
  I[arcs[u, 2], u] <- -1                      # extrémité de l'arc u
}
print(I)
colSums(I)                                    # 0 partout
rowSums(I == 1)                               # d+ : 1 2 2 1 1
rowSums(I == -1)                              # d- : 2 2 1 1 1
rowSums(I)                                    # d+ - d- : -1 0 1 0 0