Mathématiques 2: Géométrie
Les graphes
Chaînes et cycles
Chaîne eulérienne et cycle eulérien
Chaîne hamiltonienne et cycle hamiltonien

Lorsqu'on se présente devant un ensemble de données et les liens qui les unissent, comme voyager d'une ville à une autre, organiser des matchs entre des équipes sportives, ..., il est intéressant d'utiliser des graphes pour représenter ces situations en d'en tirer des conclusions.

1. Définition

Soit P un ensemble de points P = {A, B, C, D, E, F, ...}. Les tracés des lignes entres divers points de cet ensemble forment le graphe de cet ensemble.

Un graphe est l'ensemble des liens qui existent entre les éléments d'un ensemble.

Les éléments de l'ensemble sont représentés par des points appelés sommets. Les liens sont rprésentés par des lignes appelées arêtes.

Lorsqu'un lien n'existe que dans un sens unique, alors la ligne correspondante est orientée (avec une flèche).

2. Exemple:

Voici, selon la LNH, quelques matchs de hockey qui auront lieu le mois d'octobre 2015.



On peut représenter ce tableau à l'aide du graph G suivant:



En extension:

G = {MO, OM, TD, DT, BW, CS, PTB}

En utilisant la notion de couples:

G = {(M,O), (O,M), (T,D), (D,T), (B,W), (C,S), (P,TB)}

Dans cet exemple, le lien MO ou (M,O) signifie Montréal aura un match avec Ottawa. L'équipe de Montréal est visiteuse et celle d'Ottawa est locale, c'est à dire que les canadiens iront chez les sénateurs.

Dans le graphe G, Il ya deux matchs MO et OM comme pour TD et DT. Le lien est ainsi orienté. Le graphe G est orienté,

Ainsi, dans le cas d'un graphe orienté, MO signifie que la flèche part du point M et se dirige vers le point O.

Maintenenant si on définie le lien suivant: « Une équipe joue contre l'autre » , sans préciser si une ou l'autre des équipes est visiteuse ou locale, le gaphe G ne sera pas orienté et nous aurons une arête unique et sans flèche entre les sommets du graphe.

Lorsque le graphe est non-orienté (sans flèche), les arêtes sont les mêmes. MO = OM, TD = DT.

3. Propriétés d'un graphe

• Ordre d'un graphe

L' ordre d'un graphe est le nombre de ses sommets.
Le graphe G est d'ordre 9.

• Sommets adjacents

Deux sommets reliés par une arête (orienté ou non) sont dits adjacents.

• Degré d'un sommet

Le nombre d'arêtes sur un sommet est le degré de ce sommet.

Pour le graphe G, on a le tableau suivant :

Sommet	M	W	TB	T	C	S	B	O	P	D
Degré	2	1	1	2	1	1	1	2	1	2

• Boucle

Une arête peut partir d'un point et se terminer au même point, on obtient alors une boucle.

Dans notre example d'équipes de Hockey le lien « A dispute un match avec B » , ne permet pas d'avoir des boucles, puisq'une équipe de jouera pas contre elle-même. Le lien ainsi défini ne donne pas lieu à des boucles: « A dispute un match avec A » est irréalisable.

Une boucle sur un sommet lui procure un degré de 2.

Avec le lien suivant: « l'équipe A souhaite la coupe Stanley à l'équipe B », nous aurons que des boucles partout avant les séries éliminatoires, puis des liens orientés uniques entre deux équipes.

La structure d'un graphe dépend du lien fixé pour le construire

• Graphe connexe

Un graphe est dit connexe si tout sommet est relié à tout autre sommet par une arête ou par plusieurs arêtes.

C'est à dire, Il y a toujours un chemin, par des arêtes, pour passer d'un point à un autre.

Le graphe G de la figure 1 n'est pas connexe. Il n'existe pas de chemin pour passer de TB à T par exemple.

Le graphe H de la figure 2 ci-dessus est connexe.

• Graphe complet

Un graphe est complet s'il existe une arête entre toute paire de sommets distincts.

Le graphe I de la figure 3 ci-dessous n'est pas complet car il manque les arêtes TD, TO, BM, et DM.

Le graphe J de la figure 4 ci-dessous est complet.

• Chaîne

Une chaîne est un trajet qui permet de partir d'un sommet et d'arriver à un autre sommet (ou au sommet de départ).

Durant le trajet, on peut passer plusieurs fois par un même sommet ou un même arête.

Lorsqu'il n'y a pas de répétition d'arête, la chaîne est dite simple..

Dans la figure 5, MCBSTBSO est une chaine; MCBSTO est une chaîne simple. Toutes les deux permettent d'aller du sommet M au sommet O.

• Longueur d'une chaîne

La longueur d'une chaîne est le nombre d'arêtes comprises dans la chaîne.

Dans la figure 5, la chaîne MCB est de longueur 2, la chaîne MCBSTO est de longueur 5 tandis que la chaîne MCBSTBSO est de longueur 7.

La longueur d'une chaîne correspond au nombre de sommets dans la chaîne - 1.

• Distance entre 2 sommets

La distance entre 2 sommets A et B est la longueur de la chaîne la plus courte qui permet de partir de A et d'arriver à B.

Dans le graphe de la figure 5 ci-dessus, on a :
d(M,T) = 2 , d(M,O) = 2.

• Cycle

Un cycle est une chaîne qui part d'un sommet et qui se termine au même sommet.

Si le cycle ne passe pas 2 fois par la même arête, on dit que c'est un cycle simple.

Dans le graphe de la figure 5, BSOTB est un cycle simple, MSOTSBCM est aussi un cycle simple. MCBSTBCM est un cycle mais n'est pas un cycle simple car on utilise 2 fois l'arête CB et deux fois l'arrête MC.

4.Chaînes et cycles particuliers

• Chaîne eulérienne et cycle eulérien

Dans un graphe connexe, une chaîne qui passe par toutes les arêtes, une et une seule fois, est appelée une chaîne eulérienne.

Si cette chaîne est fermée, c'est un cycle eulérien.

• Chaîne eulérienne

Pour représenter une chaîne eulérienne, il faut s'assuer qu'il y ait exactement 2 sommets de degré impair.
la chaîne part alors d'un des sommets de degré impair et se termine à l'autre sommet de degré impair.



Dans la figure 7, les 2 sommets de degré impair (qui est 3) sont TB et B.

la chaîne part donc du sommet TB ou du sommet A et se termine à l'autre sommet A ou TB respectivement.

Le graphe L de la figure 7 représente une chaîne eulérienne partant de B et arrivant à TB.

Exercice: on demande de représenter le graphe de la deuxième chaîne eulérienne possible qui partira de TB et arriver à B.

• Cycle eulérien

Pour représenter un cycle eulérien , il faut s'assuer que tous les sommets soient de degré pair.
Le cycle peut partir alors de n'importe quel sommet.



Dans la figure 8, les 3 sommets S, O, B sont de degré pair (qui est 2), et les 4 sommets M, D, T, et C sont de degré pair (qui est 4) .

SMTDCTOBCMDS est un cycle eulérien possible.

• Chaîne hamiltonienne ou cycle hamiltonien

Dans un graphe connexe, une chaîne qui passe par touts les sommets , une et une seule fois, est appelée une chaîne hamiltonienne .

Si cette chaîne est fermée, c'est un cycle hamiltonien .

• Chaîne hamiltonienne

Lorsqu'il y a un sommet de degré 1 dans le graphe, on doit partir ou finir la chaîne à ce sommet.



Dans le graphe N de la figure 9, M W T O S C B représente une chaîne hamiltonienne partant de M et arrivant à B.

B T O S C W M représente une autre chaîne hamiltonienne partant de B et arrivant à M.

• Cycle hamiltonien

Relativement aux nombres de sommets ou d'arêtes, Il n'y a pas de règle qui permette de savoir s'il existe, ou non, un cycle hamiltonien.



Dans le graphe O de la figure 10, W M O S T B C W représente un cycle hamiltonien partant de W et revenant à W.

T B M W C S O T représente un autre cycle hamiltonien partant de T et revenant à T.

5 Graphes orientés

Un graphe orienté est un graph formé de un ou plusieurs liens orienté. Un lien orienté entre deux sommets, représenté par une flèche, indique dans quel sens le lien s'effectue.

Dans le cas ou les matchs se disputent une seule fois entre deux équipes, ce lien donne un graphe du type ci-contre.