Cours

title: Graphes : représentations et vocabulaire¶

Définitions et exemples¶

Graphe non orienté, graphe orienté¶

Un graphe non orienté est un couple $G = (S, A)$ où :

$S$ est un ensemble fini de sommets ;
$A$ est un ensemble d'ensembles $\{u, v\}$ (appelés les arêtes) avec $u\in S$, $v\in S$, et $u \neq v$.

On dit que deux sommets $u\in S$ et $v\in S$ du graphe $G$ sont reliés par une arête si et seulement si $\{u, v\} \in A$.

Remarques.

Le nombre de sommets est appelé l'ordre du graphe,
Le nombre d'arêtes est appelé la taille du graphe.
Cette définition des graphe est un peu réductrice (elle définit en fait ce que l'on appelle des graphes simples). En particulier, elle interdit les graphes où deux sommets seraient reliés par plusieurs arêtes, ainsi que l'existence d'une "boucle" (une arête joignant un sommet à lui-même).

On a $G = (S, A)$ avec :

$S = \{A, B, C, D, E\}$
$\begin{aligned}[t] A = \{ &\{A, B\}, \{A, C\},\\ & \{A, D\}, \{B, D\},\\ & \{D, C\}, \{D, E\}\} \end{aligned}$

$G$ est un graphe non orienté d'ordre 5 et de taille 6.

Un graphe orienté est un couple $G = (S, A)$ où :

$S$ est un ensemble fini de sommets ;
$A$ est un ensemble de couples $(u, v)$ (appelés les arcs) avec $u\in S$, $v\in S$, et $u \neq v$.

On dit que deux sommets $u\in S$ et $v\in S$ du graphe $G$ sont reliés par un arc si et seulement si $(u, v) \in A$.

Donner les ensembles $S$ et $A$ définissant le graphe orienté $G = (S, A)$ dont on donne une représentation graphique ci-dessous. Quel est son ordre ? Sa taille ?

Notion d'adjacence dans les graphes¶

Soit $G = (S,A)$ un graphe non orienté.

Deux sommets $u\in S$ et $v\in S$ sont dit adjacents (ou voisins) lorsque $ {u, v} \in A$.

Soit $G = (S, A)$ un graphe non orienté. On appelle degré d'un sommet $u\in S$ le nombre d'arêtes issues de ce sommet. Il s'agit du nombre de voisins de $u$.

Soit $G = (S,A)$ un graphe orienté.

Les successeurs de $u$ (on parle aussi de voisins de $u$ dans ce cas) sont les sommets que l'on peut atteindre depuis $u$.

Il s'agit des sommets $v\in S$ tels que $(u, v) \in A$ - Les prédécesseurs de $u$ sont les sommets depuis lesquels on peut atteindre $u$.

Il s'agit des sommets $v\in S$ tels que $(v, u) \in A$.

Soit $G = (S, A)$ un graphe orienté, et $u\in S$ un sommet.

on appelle degré entrant le nombre d'arcs arrivant au sommet $u$ ;
on appelle degré sortant le nombre d'arcs partant du sommet $u$.
on appelle degré total d'un sommet la somme de son degré entrant et de son degré sortant.

Dans le graphe $G$ ci-dessus :

les successeurs de $1$ sont $2$ et $3$.
$2$ n'a pas de successeur mais a pour prédécesseur $1$ et $3$.
$4$ est un successeur et un prédécesseur de $3$.

Chemins dans un graphe¶

Soit $G = (S, A)$ un graphe. Un chemin du sommet $u\in S$ au sommet $v\in S$ dans le graphe $G$ est une séquence $x_0, \ldots, x_n$ de sommets de $S$ tels que : $u = x_0$, $v = x_n$ et pour tout $0 \leq i < n$, $x_{i + 1}$ est un voisin de $x_i$. On note :

$u = x_0 \text{ --- } x_1 \text{ --- } x_2 \text{ --- } \ldots \text{ --- } x_{n - 1} \text{ --- } x_n = v$ (dans le cas où $G$ est non orienté)
$u = x_0 \rightarrow x_1 \rightarrow x_2 \rightarrow \ldots \rightarrow x_{n - 1} \rightarrow x_n = v$ (dans le cas où $G$ est orienté)

La longueur de ce chemin est $n$, c'est le nombre d'arcs qui le constituent. Un chemin simple est un chemin sans répétition d’arc. Un cycle est un chemin simple de $u$ à $u$ de longueur $n > 0$.

Soient $G = (S, A)$ un graphe, $u\in S$, et $v\in S$ deux sommets.

La distance entre les sommets $u$ et $v$ est la longueur du plus court chemin reliant $u$ à $v$ dans le graphe $G$. La distance entre deux sommets n'est pas définie s'il n'existe pas de chemin entre les deux sommets. Le diamètre d'un graphe est la plus grande distance entre deux sommets du graphe.

Soit $G = (S, A)$ un graphe. Si pour toute paire de sommet $u\in S$ et $v\in S$ il existe un chemin reliant $u$ à $v$ dans le graphe $G$ on dit que :

$G$ est connexe quand $G$ est non orienté ;
$G$ est fortement connexe quand $G$ est orienté.

La composante (fortement) connexe de $u\in S$ est l'ensemble des sommets $v$ de $G$ tels qu'il existe un chemin de $u$ à $v$ dans $G$.

Le graphe orienté représenté à gauche n'est pas fortement connexe. Il possède deux composantes fortement connexes. Le graphe non orienté représenté à droite est connexe.

Implémentation des graphes¶

Dans cette section, tous les graphes $G = (S, A)$ sont des graphes orientés dont les $n$ sommets sont numérotés de $0$ à $n - 1$. On note $|S|$ l'ordre du graphe, $|A|$ la taille du graphe, et $\Delta(G)$ le degré maximum d'un sommet du graphe.

Les méthodes suivantes doivent être implémentées pour pouvoir manipuler les objets de type Graphe. Pour cela, deux façons sont possibles : soit par matrice d'adjacence, soit par listes d'adjacences.

Méthode	Description
`Graphe()`	Initialise un graphe orienté vide.
`g.ordre()`	Renvoie l'ordre du graphe `g`.
`g.taille()`	Renvoie la taille du graphe `g`.
`g.ajoute_sommet()`	Ajoute un sommet au graphe `g`.
`g.supprime_sommet()`	Supprime un sommet au graphe `g`.
`g.sommets()`	Renvoie la liste des sommets de `g`.
`g.ajoute_arc(u, v)`	Ajoute l'arc `(u, v)` au graphe `g`.
`g.supprime_arc(u, v)`	Supprime l'arc `(u, v)` du graphe `g`.
`g.arcs()`	Renvoie la liste des arcs de `g`.
`g.est_voisin(u, v)`	Renvoie `True` si `v` est un successeur du `u`, `False` sinon.
`g.voisins(u)`	Renvoie la liste des successeurs de `u`.
`g.predecesseurs(u)`	Renvoie la liste des précedesseurs de `u`.
`g.degre_sortant(u)`	Renvoie le nombre de successeurs du `u`.
`g.degre_entrant(u)`	Renvoie le nombre de prédecesseurs de `u`.

Représentation par matrice d'adjacence¶

Soit $G = (S, A)$ un graphe. La matrice d'adjacence de $G$ est le tableau $M$ de taille $n \times n$ tel que si $u\in S$ et $v\in S$, $M[u][v] = \text{True} $ si $(u, v) \in A$, $\text{False} $ sinon.

Écrire la matrice d'adjacence du graphe suivant.

La représentation par matrice d'adjacence d'un graphe nécessite de l'ordre de $|S|^2$ emplacements mémoires.

Lorsque les graphes sont représentés à l'aide d'une matrice d'adjacence :

les opérations g.est_voisin(u, v), g.ajoute_arcs(u, v) et g.supprime_arcs(u, v) s'exécutent en temps constant ;
les opérations g.voisins(u), g.predecesseurs(u), g.degre_entrant(u), g.degre_sortant(u) ont une complexité linéaire en $|S|$ ;
les opérations g.arcs(), g.taille() ont une complexité quadratique en $|S|$.

Représentation par liste d'adjacence¶

Soit $G = (S, A)$ un graphe. La représentation par listes d'adjacences de $G$ est un tableau $M$ de $|S|$ listes : si $u\in S$ alors $M[i]$ est la liste des successeurs de $u$.

Écrire la représentation par listes d'adjacences du graphe suivant.

La représentation par listes d'adjacences d'un graphe nécessite de l'ordre de $|S| + |A|$ emplacement mémoire.

Lorsque les graphes sont représentés à l'aide de listes d'adjacence :

les opérations g.voisins(u), g.degre_sortant(), g.ajoute_arc(u, v)

s'exécutent en temps constant ;
les opérations g.est_voisins(u, v), g.supprime_arc(u, v) a une complexité en $\Delta(G)$ ;
les opérations g.arcs(), g.taille(), g.successeurs(u) et g.degre_entrant(u) ont une complexité linéaire en $|S|\times \Delta(G)$.