cours1 min de lecture

Graphes

Sommets et arêtes, orientés ou non — matrice d'adjacence et liste de successeurs, et le passage de l'une à l'autre.

programme

Introduction

Un graphe modélise des relations entre des entités : un réseau routier (villes et routes), un réseau social (utilisateurs et amitiés), une page web (URL et liens), un réseau électrique (composants et fils). Là où un arbre impose une hiérarchie stricte avec une racine unique, le graphe autorise des cycles, des relations multiples, des composantes disjointes.

L'exemple le plus parlant reste le plan du métro parisien : les stations sont les sommets, les liaisons directes entre stations voisines sont les arêtes. On peut tourner en rond (cycle), bifurquer, traverser des composantes séparées (les terminus d'une ligne disjointe).

L'item demande deux choses :

savoir modéliser une situation par un graphe ;
savoir implémenter un graphe de deux manières (matrice d'adjacence, liste de successeurs) et passer de l'une à l'autre.

Vocabulaire

Terme	Définition
Sommet (ou nœud)	Élément du graphe.
Arête	Lien non orienté entre deux sommets, noté $\{u, v\}$ .
Arc	Lien orienté d'un sommet vers un autre, noté $(u, v)$ .
Graphe non orienté	Composé d'arêtes — la relation est symétrique.
Graphe orienté	Composé d'arcs — la relation a un sens.
Successeur de $u$	Sommet $v$ tel qu'il existe un arc $(u, v)$ .
Prédécesseur de $u$	Sommet $v$ tel qu'il existe un arc $(v, u)$ .
Voisin de $u$ (non orienté)	Sommet $v$ tel qu'il existe une arête $\{u, v\}$ .
Ordre	Nombre de sommets, noté $n$ .
Taille	Nombre d'arêtes ou d'arcs, noté $m$ .

Routier ↔ non orienté (une route va dans les deux sens), Internet ↔ orienté (un lien hypertexte d'une page A vers B ne crée pas le lien réciproque). Le choix orienté/non orienté découle de la situation modélisée.

Dans un graphe orienté, (u,v)(u, v)(u,v) et (v,u)(v, u)(v,u) représentent…

Représentation 1 — matrice d'adjacence

On numérote les sommets de $0$ à $n - 1$ . La matrice d'adjacence $M$ est un tableau carré $n \times n$ où :

$M[i][j] = \begin{cases} 1 & \text{s'il existe un arc (ou une arête) de } i \text{ vers } j \\ 0 & \text{sinon} \end{cases}$

Pour un graphe non orienté, la matrice est symétrique : $M[i][j] = M[j][i]$ .

class GrapheMatrice:
    """Graphe à n sommets numérotés 0..n-1, représenté par matrice d'adjacence."""

    def __init__(self, n, oriente=False):
        self.n = n
        self.oriente = oriente
        self.M = [[0] * n for _ in range(n)]

    def ajouter_arete(self, u, v):
        self.M[u][v] = 1
        if not self.oriente:
            self.M[v][u] = 1

    def sont_adjacents(self, u, v):
        return self.M[u][v] == 1

    def voisins(self, u):
        return [v for v in range(self.n) if self.M[u][v] == 1]

Coûts :

Espace : $\mathcal{O}(n^2)$ — quel que soit le nombre d'arêtes.
Test d'adjacence sont_adjacents : $\mathcal{O}(1)$ .
Liste des voisins : $\mathcal{O}(n)$ (parcours d'une ligne).

Représentation 2 — liste de successeurs

Pour chaque sommet $u$ , on stocke la liste de ses successeurs (ou voisins, pour un graphe non orienté). En Python, on utilise un dictionnaire dont les clés sont les sommets et les valeurs sont des listes.

class GrapheListe:
    """Graphe représenté par une liste de successeurs (dictionnaire)."""

    def __init__(self, sommets, oriente=False):
        self.oriente = oriente
        self.succ = {s: [] for s in sommets}

    def ajouter_arete(self, u, v):
        self.succ[u].append(v)
        if not self.oriente:
            self.succ[v].append(u)

    def sont_adjacents(self, u, v):
        return v in self.succ[u]

    def voisins(self, u):
        return list(self.succ[u])

Coûts (où $d(u)$ est le degré de $u$ , c'est-à-dire son nombre de voisins) :

Espace : $\mathcal{O}(n + m)$ — économique pour les graphes creux.
Test d'adjacence : $\mathcal{O}(d(u))$ .
Liste des voisins : $\mathcal{O}(d(u))$ .

Règle pratique : matrice d'adjacence si le graphe est dense (

m \approx n^2

) ou si les tests d'adjacence sont fréquents ; liste de successeurs si le graphe est creux (

m \ll n^2

) ou si l'on parcourt souvent les voisins.

Pour un réseau social avec 1 million d'utilisateurs et 100 amis moyens, quelle représentation est viable ?

Passer d'une représentation à l'autre

Le BO demande explicitement de savoir convertir. Voici les deux sens, en Python :

def matrice_vers_liste(M):
    """De matrice d'adjacence vers liste de successeurs."""
    n = len(M)
    succ = {i: [] for i in range(n)}
    for i in range(n):
        for j in range(n):
            if M[i][j] == 1:
                succ[i].append(j)
    return succ

def liste_vers_matrice(succ):
    """De liste de successeurs vers matrice d'adjacence."""
    n = len(succ)
    M = [[0] * n for _ in range(n)]
    for u, vs in succ.items():
        for v in vs:
            M[u][v] = 1
    return M

Complexités :

matrice_vers_liste : $\mathcal{O}(n^2)$ — on lit toute la matrice.
liste_vers_matrice : $\mathcal{O}(n + m)$ — on alloue la matrice, on parcourt les arêtes.

Liste de prédécesseurs (cas orienté)

Pour un graphe orienté, on peut symétriquement vouloir, pour chaque sommet, la liste de ses prédécesseurs. Elle se construit à partir des successeurs en inversant les arcs :

def predecesseurs(succ):
    pred = {u: [] for u in succ}
    for u, vs in succ.items():
        for v in vs:
            pred[v].append(u)
    return pred

Pour un graphe non orienté, successeurs et prédécesseurs coïncident — c'est la liste des voisins.

Pour aller plus loin

Le chapitre TE exploite ces représentations pour les parcours (BFS, DFS) et les algorithmes de plus court chemin (Dijkstra). Le choix de la représentation influence directement la complexité de ces algorithmes — vous y reviendrez.