Graphes

Définitions et exemples¶

Graphe non orienté, graphe orienté¶

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

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

Remarques.

Le nombre de sommets est appelé l'ordre du graphe,
Le nombre d'arêtes est appelé la taille du graphe.
Un multi-ensemble est une collection non ordonnée d'éléments pouvant apparaître plusieurs fois.

Par exemple $\{a, a, b, c, b, b\}$ et $\{a, a, b, b, b, c\}$ sont deux multi-ensembles identiques. - Lorsqu'il existe au plus $p \in \mathbb{N}^{*}$ arêtes entre deux sommets du graphe, on dit que $G$ est un $p$-graphe. - une arête reliant un sommet à lui-même est une boucle. Lorsqu'il n'y a pas de boucles et que $G$ possède au plus une arête entre deux somments, on dit que le graphe est simple.

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

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

$G$ est un $2$-graphe non orienté d'ordre 4 et de taille 7. Il n'est pas simple.

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

$S$ est un ensemble de sommets ;
$A$ est un multi-ensemble de couples $(u, v)$ (appelés les arcs) avec $u\in S$ (le sommet de départ) et $v\in S$ (le sommet d'arrivée).

$G$ est un $1$-graphe orienté d'ordre $4$ et de taille $7$. Il n'est pas simple.

Sommets adjacents¶

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

Deux sommets $u\in S$ et $v\in S$ sont dit adjacents lorsque $ {u, v} \in A$ (il existe une arête reliant $u$ à $v$). L'ensemble des sommets adjacents à $u$ est appelé l'ensemble des voisins de $u$.

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

Deux sommets $u \in S$ et $v \in S$ sont adjacents lorsque $(u, v) \in A$ (il existe un arc reliant $u$ à $v$).

Les successeurs de $u$ sont les sommets que l'on peut atteindre depuis $u$.

Il s'agit des sommets $v\in S$ tels que $(u, v) \in S$ - 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 S$.

Soit $G = (S, A)$ un graphe non orienté. On appelle degré d'un sommet le nombre d'arêtes issues de ce sommet.

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$.

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$.

Chemins dans un graphe¶

Soient $G = (S, A)$ un graphe non orienté, $u\in S$ et $v\in S$ deux sommets, $n\in \mathbb{N}$.

Une chaine de longueur $n$ reliant $u$ à $v$ dans le graphe $G$ est une suite finie $a_0, a_1, \ldots a_{n - 1}$ de $n$ arêtes consécutives, avec $u \in a_0$ et $v\in a_{n - 1}$.

Lorsque le graphe est orienté, on parle de chemin. On dit que :

le chemin est simple si tous les arcs utilisés sont distincts.
le chemin est élémentaire lorsqu'il ne passe pas deux fois par le même sommet.
le chemin est fermé si $u = v$.
le chemin est un cycle lorsqu'il contient au moins un arc et qu'il est simple et fermé.

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 non orienté.

On dit que $G$ est connexe si pour toute paire de sommet $u\in S$ et $v\in S$ il existe un chemin reliant $u$ à $v$ dans le graphe $G$. La composante connexe de $u\in S$ est l'ensemble des sommets $v$ de $G$ tels qu'il existe un chemin de $u$ à $v$ dans $G$.

Lorsque le graphe est orienté on dit qu'il est faiblement connexe si le graphe non orienté obtenu en "oubliant" le sens des arcs est connexe. On dit d'un graphe orienté est fortement connexe si pour toute paire $u$ et $v$ de sommets il existe un chemin de $u$ à $v$.

Le graphe orienté $G$ n'est pas fortement connexe mais est faiblement connexe. Il possède deux composantes fortement connexes.