Un graphe est constitué de sommets dont certains sont reliés par des arêtes.

§         Si les arêtes sont orientées, le graphe est dit orienté.

§         Deux sommets reliés par une arête sont dits adjacents.

§         Le nombre de sommets du graphe est l’ordre du graphe.

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

§         Un graphe est complet lorsque tous ses sommets sont adjacents

La matrice associée à un graphe d’ordre n dont les sommets sont numérotés de 1 à n est une matrice carrée de dimension n où le terme figurant en ligne i colonne j est égal au nombre de chemins reliant i à j.

§         Une chaîne est une liste ordonnée de sommets telle que tout sommet de la liste soit adjacent au suivant.

§         La longueur d ‘une chaîne est le nombre d’arêtes qui la composent.

§         Un graphe est connexe s’il existe toujours une chaîne entre deux sommets distincts

§         Une chaîne est fermée lorsque l’origine et l’extrémité sont confondues.

§         Un cycle est une chaîne fermée dont toutes les arêtes sont distinctes.

§         Une chaîne est eulérienne si elle contient chaque arête du graphe une et une seule fois.

§         Si une chaîne eulérienne est un cycle, on parle de cycle eulérien.

§         Une chaîne est hamiltonienne lorsque tous les sommets du graphe y figurent de manière distincte une fois et une seule

§         1 - 2 - 5 est une chaîne de longueur 3.

§         Le graphe est connexe.

§         2 – 3 – 4 – 5 – 2 est une chaîne fermée.

§         1 – 2 – 3 – 4 – 5 – 1 est un cycle.

§         3 – 4 – 5 – 2 – 1 – 5 – 6 – 2 est une chaîne eulérienne.

§         2 – 1 – 5 – 6 – 2 – 3 – 4 – 5 – 2 est un cycle eulérien.

§         1 – 2 – 6 – 5 – 4 – 3 estun parcours hamiltonien.

§         La distance entre deux sommets est la plus courte longueur des chaînes qui les relient.

§         Le diamètre d’un graphe connexe est la plus grande distance entre deux sommets.

§         La distance entre le sommet 1 et le sommet 3 est 2.

§         Le diamètre du graphe est 2

§         Colorer un graphe consiste à affecter une couleur à chaque sommet de sorte que deux sommets adjacents ne portent pas la même couleur.

§         Le nombre chromatique est le plus petit nombre de couleurs nécessaire à son coloriage.

§         Une boucle est une arête orientée dont l’origine et l’extrémité sont les mêmes.

§         La matrice associée à un graphe orienté d’ordre n dont les sommets sont numérotés de 1 à n est une matrice carrée de dimension n où le terme figurant en ligne i colonne j est égal à 1 s’il existe une arête d’origine i et d’extrémité j et 0 sinon.

§         Un graphe étiqueté est un graphe orienté dont les arêtes sont affectées d’étiquettes.

§         Si toutes les étiquettes sont des réels positifs, les graphe est dit pondéré.

§         Le poids d’une chaîne est la somme des poids des arêtes orientées qui la composent.

§         Un graphe probabiliste est un graphe orienté et pondéré dont la somme des poids sortant de chaque sommet vaut 1.