Les graphes

LES GRAPHES:

I- Définitions

? Une chaîne dans un graphe est une suite de sommets reliés par des arêtes.

? Si l’origine et l’extrémité de la chaîne sont confondus, on dit que la chaîne estfermée.

? Un cycle est une chaîne simple dont les extrémités coïncident. On ne rencontre pas deux fois le même sommet, sauf celui choisi comme sommet de départ et d’arrivée.

? Une chaîne est diteulérien si chaque arête du graphe y apparaît exactement une fois.

? Un graphe connexe est un graphe dans lequel chaque paire de sommets est reliée par une chaîne. Un graphe qui n’est pas connexeest dit non connexe, et se décompose en composantes connexes.

? Un graphe pondéré est un graphe étiqueté où chaque arête est affectée d’un nombre réel positif, appelé poids de cette arête.

? Lepoids d’une chaîne est la somme des poids des arêtes qui la composent.

? Une plus courte chaîne entre deux sommets est, parmi les chaînes qui les relient, une chaîne de poids minimum.

? Un grapheest orienté si les arêtes ont un sens.

? La longueur d’une chaîne est le nombre d’arêtes utilisées, ou, ce qui revient au même, le nombre de sommets utilisés moins un.
? L’ordre d’un graphe estégal au nombre de ses sommets.

? Le degré d’un sommet est le nombre d’arêtes dont ce sommet est une extrémité.

? Si 2 sommets sont reliés par (au moins) une arête, on dit que ce sont des sommetsadjacents.

? Un sous-graphe d’un graphe est obtenu en y enlevant des sommets et toutes les arêtes incidentes à ces sommets.

? On appelle matrice d’un graphe la matrice indiquant dans la ligne iet la colonne j le nombre d’arêtes reliant le sommet i au sommet j.

? Un graphe dont les sommets sont 2 à 2 adjacents est appelé graphe complet.

? Colorer un graphe c’est à tout sommet unecouleur, tels que deux sommets adjacents aient une couleur différente (c’est-à-dire partitionne les sommets en ensembles indépendants).

? Le nombre chromatique d’un graphe c’est le nombre minimum de…