Déjà plus de
1 million
d'inscrits !
Graphes
Déjà plus de
1 million
d'inscrits !
Avant de commencer, regarde les vidéos
Introduction :
Cette leçon introduira tout d’abord la notion de graphe non orienté, avec sa matrice d’adjacence ainsi que ses éventuels chaînes et cycles, puis nous verrons les graphes orientés et leurs particularités. Nous aborderons enfin l’algorithme de Dijkstra-Moore qui permet de rechercher la plus courte chaîne d’un graphe.
Graphes non orientés
Définitions et propriétés
Graphe :
La somme des degrés des sommets d’un graphe non orienté est égale au double du nombre total d’arêtes.
Ce graphe possède sommets (, , , , ) ; c’est un graphe d’ordre .
Le tableau ci-dessous représente les degrés des sommets du graphe :
Sommet | |||||
Degré |
On peut compter sur le graphes que le nombre total d’arêtes est et la somme des degrés des sommets est (soit le double du nombre total d’arêtes).
Ce graphe qui possède sommets (, , , ) est un graphe d’ordre complet car tous ses sommets sont adjacents.
Le tableau ci-dessous représente les degrés des sommets du graphe :
Sommet | ||||
Degré |
Le nombre total d’arêtes est et la somme des degrés des sommets est soit le double du nombre total d’arêtes.
Matrice d’adjacence
Matrice d’adjacence :
La matrice d’adjacence associée à un graphe non orienté d’ordre dont les sommets sont numérotés de 1 à la matrice carrée d’ordre où le terme situé en ligne et colonne est égal au nombre d’arêtes reliant et .
La matrice d’adjacence associée à ce graphe d’ordre est la matrice suivante :
Les sommets doivent être classés dans l’ordre alphabétique, ainsi par exemple le coefficient situé en ligne et colonne signifie qu’il y a une arête qui relie à .
Le coefficient situé en ligne et colonne signifie qu’il n’y a pas d’arête qui relie à .
La matrice d’adjacence d’un graphe non orienté sera toujours symétrique par rapport à sa première diagonale.
Chaînes et cycles
Une chaîne est une suite d’arêtes qui, mises bout à bout, permettent d’aller d’un sommet à un autre. Dans une chaîne, on peut prendre plusieurs fois la même arête.
Chaîne :
Autrement dit, pour qu’une chaîne soit un cycle il faut qu’elle soit fermée et que chacune de ses arêtes n’ait été prise qu’une seule fois.
-- est une chaîne et ---- est un cycle.
Trouver dans un graphe un nombre de chaînes de longueur donnée
Soit un entier naturel et la matrice d’adjacence associée à un graphe non orienté dont les sommets sont numérotés.
Le terme (ligne colonne ) de la matrice donne le nombre de chaînes de longueur reliant et .
donc
Graphes connexes et trajets eulériens
Graphe connnexe :
Un graphe est connexe s’il existe toujours une chaîne entre deux sommets distincts, c’est-à-dire si le graphe est « d’un seul tenant ».
Ce graphe est connexe.
Ce graphe n’est pas connexe.
Chaîne eulérienne :
Une chaîne est eulérienne lorsqu’elle contient chaque arête du graphe une et une seule fois. Si cette chaîne est un cycle, on dit qu’il s’agit d’un cycle eulérien.
Théorème d’Euler :
Un graphe connexe admet une chaîne eulérienne si, et seulement si, le nombre de sommets de degré impair vaut ou .
Un graphe connexe admet un cycle eulérien si, et seulement si, tous ses sommets sont de degré pair.
Le théorème d’Euler permet de savoir rapidement si un graphe connexe comporte une chaîne eulérienne ou un cycle eulérien.
Tableau des degrés des sommets de ce graphe :
Sommet | |||||
Degré |
Comme le graphe comporte sommets de degré impair, il existe une chaîne eulérienne (par exemple, ----- est une chaîne eulérienne).
En revanche, comme tous les sommets ne sont pas de degré pair, il n’existe pas de cycle eulérien. Cela signifie qu’aucune chaîne ne permet de revenir au sommet de départ.
Graphes orientés
Définition
Graphe orienté :
Un graphe orienté est un graphe dont les arêtes sont orientées. Chaque arête ne peut être parcourue que dans le sens de la flèche. Une boucle est une arête orientée dont l’origine et l’extrémité sont les mêmes.
Il s’agit d’un graphe orienté de degré .
Il comprend une boucle qui relie le sommet à lui-même.
Matrice d’adjacence
Tout comme pour les graphes non orientés, on peut associer à chaque graphe orienté une matrice d’adjacence.
Matrice d’adjacence :
La matrice d’adjacence associée à un graphe orienté d’ordre , dont les sommets sont numérotés de à , est une matrice carrée d’ordre où le terme figurant en ligne et colonne est égal à s’il existe une arête menant de à et à sinon.
La matrice d’adjacence associée à ce graphe d’ordre est :
Les sommets doivent être classés dans l’ordre alphabétique ou dans l’ordre croissant, ainsi par exemple le coefficient « » situé en ligne et colonne signifie qu’il y a une arête orientée qui mène de ① vers ②.
Le coefficient « » situé en ligne et colonne signifie qu’il n’y a pas d’arête orientée qui mène de ③ vers ③ (pas de boucle au sommet n°).
Contrairement à la matrice d’adjacence d’un graphe non orienté, celle d’un graphe orienté n’est pas forcément symétrique par rapport à sa première diagonale.
Trouver dans un graphe un nombre de chaîne d’une longueur donnée
Soit un entier naturel et la matrice d’adjacence associée à un graphe orienté dont les sommets sont numérotés. Le terme (ligne colonne ) de la matrice donne le nombre de chaînes de longueur reliant et .
Cette propriété est exactement la même pour les graphes non orientés.
donc
La matrice nous indique qu’il y a chaînes de longueur menant de ① à ②.
Ces chaînes sont : ①-①-①-①-② ; ①-①-②-①-② et ①-②-①-①-②
Graphes étiquetés et graphes pondérés
Graphe étiqueté :
Un graphe étiqueté est un graphe orienté où chacune des arêtes est affectée d’une lettre ou d’un mot ou de tout autre symbole. Ces symboles sont appelés des étiquettes.
À partir de ce graphe étiqueté on peut former certains mots.
Graphe pondéré :
Un graphe pondéré est un graphe étiqueté dont toutes les étiquettes sont des nombres positifs.
Poids d’une chaîne :
Le poids d’une chaîne est la somme du poids des arêtes qui la composent. Une plus courte chaîne entre deux sommets est, parmi les chaînes qui relient ces deux sommets, une chaîne de poids minimal.
Soit le graphe pondéré d’ordre ci-contre :
La longueur d’une chaîne est le nombre d’arêtes qui la composent.
Algorithme de Dijkstra-Moore
ALGORITHME DE DIJKSTRA-MOORE
L’algorithme de Dijkstra-Moore permet de trouver la plus courte chaîne reliant un sommet à un autre dans un graphe :
Étapes de l’Algorithme de Dijkstra-Moore
Dans ce graphe, on cherche à déterminer la plus courte chaîne menant de à .
/ | ||||||
/ | ||||||
/ | ||||||
/ | ||||||
/ | ||||||
/ |
Ici, le poids de la chaîne - est alors que le poids de la chaîne - est .
/ | ||||||
/ | ||||||
/ | ||||||
/ | ||||||
/ | ||||||
/ |
On recommence alors la deuxième étape, on cherche le sommet de coefficient minimal, on le repère et on raye toutes les cases vides sous ce sommet.
On recommence la troisième étape.
En regardant bien le graphe, tu peux remarquer que, pour atteindre le sommet , on a le choix entre - de poids ou -- de poids .
On inscrit le poids minimal dans le tableau en on complète avec le coefficient sous les sommets non adjacents.
/ | ||||||
/ | / | |||||
/ | / | |||||
/ | / | |||||
/ | / | |||||
/ | / |
On recommence l’opération jusqu’à ce que tous les sommets soient sélectionnés.
/ | ||||||
/ | / | |||||
/ | / | / | ||||
/ | / | / | / | |||
/ | / | / | / | / | ||
/ | / | / | / | / | / |