Sous-graphe: # = (Y. B) est un sous-graphe de G = (X. A) si YX et BCA. ⚫ Graphe partiel : H = (Y, B) est un graphe partiel de G = (X. A) si Y = X et BCA • Ordre d'un graphe: l'ordre d'un graphe est le nombre de sommets de ce graphe. ⚫ Chaîne: suite finie de sommets reliés entre eux par une arête. ⚫ Chaîne simple: chaîne qui n'utilise pas deux fois la même arête. ⚫ Chaine culérienne : chaîne simple passant par toutes les arêtes d'un graphe. ⚫ Chaîne hamiltonienne: chaîne simple passant par tous les sommets d'un graphe une et une seule fois. ⚫ Chemin : suite de sommets reliés par des arcs dans un graphe orienté. ⚫ Cycle: chaîne qui revient à son point de départ. ⚫ Cycle eulérien : cycle simple passant par toutes les arêtes d'un graphe une et une seule fois. ⚫ Cycle hamiltonien: cycle simple passant par tous les sommets d'un graphe une et une seule fois. ⚫ Graphe connexe : un graphe G est dit connexe si pour toute paire de sommets {y} de G, il existe une chaîne de premier termer et de dernier terme y. • Arbre: graphe connexe sans cycle simple et sans boucle. • Graphe culérien : graphe qui possède un cycle eulérien. ⚫ Graphe semi-culérien : graphe qui possède une chaîne eulérienne. ⚫ Graphe hamitonien: graphe qui possède un cycle hamiltonien. ⚫ Graphe semi-hamiltonien: graphe qui possède une chaîne hamiltonienne. ⚫ Graphe valué: graphe où des réels sont associés aux arêtes. Dans cet exposé, on ne considérera que des valuations positives. • Longueur d'une chaîne: nombre des arêtes qui composent la chaîne. Valeur d'une chaîne: somme des valeurs des arêtes (arcs) d'une chaîne d'un graphe valué. Distance entre deux sommets: longueur de la plus courte chaîne joignant ces deux sommets. Diamètre d'un graphe: maximum des distances entre les sommets d'un graphe. . Indice chromatique : nombre minimal de couleurs permettant de colorier les