Introduction à la théorie des graphes : du vocabulaire

La théorie des graphes est une branche des mathématiques qui étudie les structures formées par des objets reliés entre eux par des liens. Ces structures sont appelées des graphes et sont utilisées pour modéliser diverses situations dans des domaines tels que l'informatique, les réseaux, la biologie, et bien d'autres.

I. Le vocabulaire

1. Graphe, Sommets, Arêtes

Graphe : Un graphe G est constitué d'un ensemble de sommets (ou nœuds) et d'un ensemble d'arêtes (ou liens) qui relient ces sommets.

$\checkmark$ Sommets : Les sommets sont les éléments de base d'un graphe. Ils peuvent représenter des entités comme des villes, des personnes, des objets, etc. Pour faciliter la lecture, ils sont numérotés ou nommés.

$\checkmark$Arêtes : Les arêtes sont les connexions entre les sommets. Elles peuvent être dirigées (flèches) ou non dirigées (lignes simples).

2. Graphe Complet

$\checkmark$Graphe Complet : Un graphe est dit complet si chaque sommet est relié à tous les autres sommets par une arête. Un graphe complet à $n$ sommets est noté $K_n$​.

3. Sommets Adjacents et Degré

$\checkmark$ Sommets Adjacents : Deux sommets sont adjacents s'ils sont reliés par une arête.

$\checkmark$Degré d'un Sommet : Le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes. Dans un graphe non orienté, c'est simplement le nombre de voisins du sommet.

4. Ordre d'un Graphe

$\checkmark$Ordre : L'ordre d'un graphe est le nombre total de sommets qu'il contient.

5. Chaîne et Longueur d'une Chaîne

$\checkmark$ Chaîne : Une chaîne est une liste ordonnée de sommets où chaque sommet est relié au suivant par une arête.

$\checkmark$ Longueur d'une Chaîne : La longueur d'une chaîne est le nombre d'arêtes qu'elle contient.

$\checkmark$ Chaîne fermée : Une chaîne fermée est une chaîne dont l'origine et l'extrémité sont confondues.

$\checkmark$ Chaîne eulérienne : Une chaîne eulérienne est une chaîne satisfaisant aux deux conditions suivantes :

- elle contient toutes les arêtes du graphe

- chaque arête n'est décrite qu'une seule fois

$\checkmark$ Cycle : suite d'arêtes consécutives distinctes (chaîne simple) dont les deux sommets extrémités sont identiques.

$\checkmark$ Cycle eulérien : chaîne eulérienne fermée

6. Graphe Connexe

$\checkmark$ Graphe Connexe : Un graphe est connexe s'il existe une chaîne entre chaque paire de sommets. En d'autres termes, on peut

Propriété :

Tout graphe complet est connexe.

Théorème d'Euler

G étant un graphe connexe, les deux propriétés suivantes sont équivalentes :

$\checkmark$ Tous les sommets de G sont de degré pair

$\checkmark$ G admet un cycle eulérien.

G étant un graphe connexe, les deux propriétés suivantes sont équivalentes :

$\checkmark$ Deux sommets A et B (et deux seulement) de G sont de degré impair

$\checkmark$ G admet une chaîne eulérienne d'extrémités A et B.

Graphe orienté :

On appelle graphe orienté, tout graphe non orienté, dont les arêtes sont munies d'un sens de parcours. Un arête s'appelle alors un arc et une chaîne s'appelle un chemin.

Graphe pondéré : Un graphe, orienté ou non, est pondéré lorsque à chaque arête ou arc est associé un nombre réel positif appelé poids.

II. Propriétés

Relation entre degrés et nombre d'arêtes

La somme des degrés d'un graphe non orienté est égale à 2 fois le nombre d'arêtes du graphe (la somme des degrés est donc toujours paire).

Nombre chromatique

Définition :

Le nombre chromatique d'un graphe est le plus petit nombre de couleurs permettant de le colorer.

Ici 3 couleurs ont suffi. Si $d(G)$ est le plus haut degré des sommets du graphe $G$, on sait montrer que :

Propriété :

Le nombre chromatique d'un graphe $G$ est toujours inférieur ou égal à $d(G)+1$.

III. Exemple

Dans le graphe ci-dessus :

$\checkmark$ 1-4-3-5 est une chaîne.

$\checkmark$ 1-2-3-5-2-1 est une chaîne fermée du graphe, mais ce n'est pas un cycle.

$\checkmark$ 1-2-4-4-1 est un cycle.

$\checkmark$ 2-1-4-3-2-5-3 est une chaîne eulérienne.