MATHÉMATIQUES

video-mathematiques-vocabulaire-des-graphes-1183

VOCABULAIRE DES GRAPHES

Vocabulaire des graphes

 

Définition

 

Un graphe est un ensemble de points reliés entre eux. 

Dans la suite, on considéra comme exemple le graphe suivant.

3129f524b9ee3bbdb0da73fe42d82657deeb9c58.png

 

Les points sont appelés des sommets. Le nombre total de sommets est appelé l'ordre : ici l'ordre vaut 4. 
Deux sommets sont adjacents si ils sont reliés entre eux. Par exemple, $B$ et $D$ ne sont pas adjacents.

Les segments reliant deux sommets sont des arêtes

Le degré d'un sommet correspond au nombre d'arêtes partant de ce commet. Par exemple, trois arêtes partent du sommet $A$ : $A$ est de degré 3.

Une chaîne de sommets est une liste de sommets reliés par des arêtes. Un cycle est une chaîne débutant par un sommet et terminant par ce même sommet. Par exemple $ABCD$ est une chaîne et $ABCA$ est un cycle. 

La longueur d'une chaîne est le nombre d'arêtes composant cette chaine. Il ne faut donc pas compter le nombre de sommets ! Ainsi, la longueur de la chaine $ABCD$ est 3.

Un graphe est complet si tous les sommets sont reliés entre eux par une arête. Ici, $B$ et $D$ ne sont pas reliés entre eux, le graphe n'est donc pas complet. 

Un graphe est connexe si tous les sommets sont reliés par une chaine quelconque. Ici le graphe est connexe.

Une chaine eulérienne est une chaine qui passe par chaque arête une seule fois : c'est le cas de la chaine $CDACBA$.

Un cycle eulérien est une chaîne fermée passant par chaque arête d'un graphe. Ici, il n'existe pas de cycle eulérien.

La matrice du graphe contient des 0 et des 1. Si il y a un 1 à l'intersection de la ligne $i$ et de la colonne $j$, alors il existe une arête reliant le sommet $i$ au sommet $j$. Sinon, aucune arête relit ces deux sommets et on l'indique alors par un 0.

f91b3d4a7128163d9cb7b8adff8110e6bca4223b.png

 

Propriétés : 

 

La somme des degrés des sommets vaut le double du nombre d'arêtes. 

Si sur l'ensemble des sommets, seulement deux sont de degré impair, alors il existe une chaîne eulérienne. Cette propriété montre l'existence d'une telle chaîne mais ne la donne pas.

Si tous les degrés sont pairs, alors il existe un cycle eulérien.