cours terminale ES enseignement de spécialité

Introduction à la théorie des graphes

I - Graphes premières définitions

De manière générale, un graphe est un ensemble de sommets et d'arêtes (ou arcs) reliant ces sommets.
Il existe différents types de graphes, orientés ou non, ou autorisant plusieurs arcs entre deux sommets.

Graphe $G_{1}$

Graphe $G_{2}$

Graphe $G_{3}$

Graphe $G_{4}$

1 - Définitions

Un graphe non orienté $G = (S A)$ est déterminé par la donnée de deux ensembles :

un ensemble fini non vide S dont les éléments sont appelés sommets ;
un ensemble A de paires de sommets appelées arêtes.

Si $S = {x_{1}; x_{2}; \dots; x_{n}}$ est l'ensemble des sommets d'un graphe G, une arête a de l'ensemble A s'écrit $a = {x_{i}; x_{j}}$ où $x_{i}$ et $x_{j}$ sont les extrémités de a.
Les sommets $x_{i}$ et $x_{j}$ sont alors adjacents dans le graphe G et on dit qu'ils sont incidents avec l'arête a.
Lorsque les deux extrémités sont confondues $x_{i} = x_{j}$ l'arête s'appelle une boucle.
Deux arêtes sont dites parallèles lorsqu'elles ont mêmes extrémités.

ordre d'un graphe

On appelle ordre d'un graphe le nombre (n) de sommets de ce graphe.

exemple

Les graphes $G_{1}$ et $G_{2}$ sont d'ordre 4 ; le graphe $G_{3}$ est d'ordre 5 et le graphe $G_{4}$ est d'ordre 7.

graphe simple

Un graphe est dit simple si deux sommets distincts sont joints par au plus une arête et s'il est sans boucle.

graphe orienté

Un graphe peut être orienté, une arête est alors appelée un arc. Un arc est défini par un couple ordonné $(x_{i} x_{j})$ de sommets.

remarque

À tout graphe orienté, on peut associer un graphe simple.

Par exemple sur un plan de ville où sont indiquées les rues en sens uniques, un piéton ne tiendra pas compte de l'orientation pour se déplacer.

Au graphe orienté

on associe le graphe simple

sous graphe

Il arrive que dans certains problèmes on ait besoin de considérer une partie d'un graphe :

$G' = (S' A')$ est un sous-graphe de $G = (S A)$ si S' est un sous ensemble de S et A' un sous ensemble de A tel que les extrémités des arêtes de A' sont des sommets de S'.
Si A' est constitué de l'ensemble des arêtes de A ayant pour extrémités les sommets de S' alors on dit que $G' = (S' A')$ est le sous-graphe engendré par S'.

exemple


Graphe G	$G_{1}$ est un sous graphe de G	$G_{2}$ est le sous graphe de G engendré par ${S_{3}; S_{4}; S_{5}; S_{6}; S_{7}}$

graphe complet

Un graphe complet $K_{n}$ est un graphe simple d'ordre $n ⩾ 1$ dont tous les sommets sont deux à deux adjacents.


$K_{3}$	Deux représentations du $K_{4}$		$K_{5}$

2 - Degré d'un sommet

On appelle degré d'un sommet le nombre d'arêtes dont ce sommet est une extrémité (les boucles étant comptées deux fois). Ce degré vaut 0 si le sommet est isolé.

exemple

Dans le graphe ci-contre, les degrés des sommets sont :

Sommets	$S_{1}$	$S_{2}$	$S_{3}$	$S_{4}$	$S_{5}$	$S_{6}$	$S_{7}$
Degrés	2	4	2	3	2	1	0

degré d'un sommet dans un graphe orienté

Soit s un sommet d'un graphe orienté G.

On note $d^{+} (s)$ le degré extérieur du sommet s, c'est-à-dire le nombre d'arcs ayant s comme extrémité initiale.
On note $d^{-} (s)$ le degré intérieur du sommet s, c'est-à-dire le nombre d'arcs ayant s comme extrémité finale.

Le degré du sommet s est : $d (s) = d^{+} (s) + d^{-} (s)$

exemple

Dans le graphe ci-contre, les degrés des sommets sont :

$d^{+} (s_{1}) = 2$ et $d^{-} (s_{1}) = 1$ d'où $d (s_{1}) = 3$
$d^{+} (s_{2}) = 2$ et $d^{-} (s_{2}) = 3$ d'où $d (s_{2}) = 5$
$d^{+} (s_{3}) = 1$ et $d^{-} (s_{3}) = 4$ d'où $d (s_{3}) = 5$
$d^{+} (s_{4}) = 2$ et $d^{-} (s_{4}) = 1$ d'où $d (s_{4}) = 3$
$d^{+} (s_{5}) = 2$ et $d^{-} (s_{5}) = 1$ d'où $d (s_{5}) = 3$
$d^{+} (s_{6}) = 1$ et $d^{-} (s_{6}) = 0$ d'où $d (s_{6}) = 1$

remarque

Dans un graphe orienté, la somme des degrés extérieurs et la somme des degrés intérieurs sont égales au nombre d'arcs.
Si on note a le nombre d'arcs d'un graphe orienté alors $\sum d^{+} (s) = \sum d^{-} (s) = a$ .

Par exemple si dans une réunion on échange des cadeaux, le nombre de cadeaux offerts est égal au nombre de cadeaux reçus, c'est le nombre de cadeaux échangés.

théorème

La somme des degrés de tous les sommets d'un graphe est égale à deux fois le nombre d'arêtes de ce graphe ; c'est donc un nombre pair.

démonstration

Lorsqu'on additionne les degrés des sommets, une arête est comptée deux fois, une fois pour chaque extrémité.

exemple

Est-il possible de tracer cinq segments sur une feuille, de telle manière que chaque segment en coupe exactement trois autres ?

On modélise la situation à l'aide d'un graphe d'ordre 5 dont les sommets représentent les segments. Deux sommets sont adjacents si les deux segments ont une intersection.

Ainsi, il faudrait tracer un graphe d'ordre 5 dont tous les sommets seraient de degré 3. Ce qui est impossible puisque la somme des degrés de tous les sommets d'un graphe est un nombre pair.

corollaire

Dans un graphe, le nombre de sommets impairs est un entier pair.

démonstration

Soit p la somme des degrés des sommets pairs et m la somme des degrés des sommets impairs.
$m + p$ est égal à la somme des degrés des sommets c'est donc un nombre pair comme p est un nombre pair, on en déduit que m est un nombre pair.
Or une somme d'entiers impairs est paire si, et seulement si, il y a un nombre pair de termes.
Par conséquent, le nombre de sommets impairs est un entier pair.

proposition

Dans un graphe simple d'ordre $n > 1$ , il existe deux sommets distincts $s_{i}$ et $s_{j}$ ayant le même degré.

démonstration

Soit G un graphe simple d'ordre $n > 1$ . Le degré d'un sommet s quelconque du graphe G est un entier $d (s)$ tel que : $0 ⩽ d (s) ⩽ n - 1$ .

Supposons que les degrés des sommets soient différents.
Les degrés des n sommets sont les entiers ${0; 1; \dots; n - 1}$ et il existe un sommet $s_{i}$ de degré 0 et un sommet $s_{j}$ de degré $n - 1$ .

Or si $d (s_{j}) = n - 1$ cela signifie qu'il est adjacent à tous les sommets du graphe et en particulier au sommet $s_{i}$ donc $d (s_{i}) ⩾ 1$ . Ce qui est en contradiction avec $d (s_{i}) = 0$ .

3 - Représentation matricielle d'un graphe

Soit $G = (S A)$ un graphe d'ordre n dont les sommets sont numérotés de 1 à n.
La matrice d'adjacence de G est égale à la matrice carrée $M = (m_{i, j})$ de dimension $n \times n$ où le terme $m_{i, j}$ est égal au nombre d'arêtes d'extrémités les sommets $s_{i}$ et $s_{j}$ .
Dans le cas d'un graphe orienté, $m_{i, j}$ est égal au nombre d'arcs ayant pour origine le sommet $s_{i}$ et pour extrémité finale le sommet $s_{j}$ .

exemples

La matrice d'adjacence du graphe orienté $G_{1}$ est $M (G_{1}) = (\begin{matrix} 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{matrix})$
La matrice d'adjacence du graphe simple $G_{2}$ est $M (G_{2}) = (\begin{matrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix})$

remarques

La matrice d'adjacence d'un graphe non orienté est symétrique.
La diagonale de la matrice d'adjacence d'un graphe simple ne comporte que des 0.
La demi somme de tous les coefficients de la matrice d'adjacence d'un graphe non orienté est égale au nombre d'arêtes de ce graphe.
La somme de tous les coefficients de la matrice d'adjacence d'un graphe orienté est égale au nombre d'arcs de ce graphe.
- La somme des coefficients de la ligne i est égale au nombre de successeurs du sommet $s_{i}$ .
- La somme des coefficients de la colonne i est égale au nombre de prédécesseurs du sommet $s_{i}$ .

4 - Graphes isomorphes

Deux graphes isomorphes ont la même structure : peu importe la façon dont ils sont dessinés, il est possible de déplacer les sommets pour que l'un soit la copie conforme de l'autre.

exemple

Considérons les trois graphes ci-dessous :

Les trois graphes ont le même ordre (6), le même nombre d'arêtes (6) et les sommets des trois graphes sont tous de degré 3.

Or dans B il y a deux sous graphes complets d'ordre 3 ce qui n'est pas le cas pour les graphes A et C. Donc B n'est pas isomorphe à A et C.

Montrons que les graphes A et C sont isomorphes.

Les sommets étant numérotés comme indiqué ci-dessus les deux graphes ont la même matrice d'adjacence : $M_{A} = M_{C} = (\begin{matrix} 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \end{matrix})$ .
Donc les graphes A et C sont isomorphes.

remarques

Le graphe B est planaire : on peut le dessiner sans que ses arêtes se croisent.
Le graphe C (ou A) est un graphe biparti : il existe une partition de son ensemble S de sommets en deux sous-ensembles X et Y telle que chaque arête du graphe a une extrémité dans X et l'autre dans Y. (Par exemple $X = {c_{1}; c_{3}; c_{5}}$ et $Y = {c_{2}; c_{4}; c_{6}}$ . )
Ce n'est pas un graphe planaire, il est impossible de le dessiner sans que ses arêtes se croisent.

suivant>> Chaîne, cycle

[ Accueil ]

Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.