Chemins, circuits, chaînes, cycles
Soit $G = (V, E)$ un graphe non orienté. Un chemin de longueur $k \geq 1$ est une suite $(e_1, ..., e_k)$ de $k$ arêtes $e_i = \{v_{i, 1}, v_{i,2}\}$ telles que $v_{i,2} = v_{i+1,1}$ pour tous $i \in \{1, ..., k-1\}$ .
Un chemin est de même entièrement défini par une suite de sommets $(v_1, ..., v_{k+1})$ de manière telle que $\{v_i, v_{i+1}\}$ est une arête du graphe.
Deux sommets $a$ et $b$ sont connectés s'il existe un chemin les joignant.
Si les extrémités d'un chemin sont égales, on parle de cycle, de circuit ou encore de chemin fermé. Si l'on souhaite préciser que le chemin considéré n'est pas fermé, on parlera de chemin ouvert.
Si les arêtes d'un chemin sont deux à deux distinctes, on parle de piste ou de chemin élémentaire. Si, de plus, les sommets sont deux à deux distincts (à l'exception éventuellement des sommets de départ et d'arrivée), on parle de chemin simple.
Si $G$ est connexe, la distance entre deux sommets $a$ et $b$, notée $d(a, b)$, est la longueur du plus court chemin joignant $a$ et $b$. Le diamètre de $G$ est alors défini comme la plus grande distance entre deux sommets de $G$, c'est à dire : $$ \textrm{diam}(G) = \max_{a, b \in V} d(a, b)$$
Les définitions données précédemment s'adaptent facilement au cas d'un graphe orienté, à la différence qu'il faut désormais prendre en compte le sens des arcs. Par exemple, si $G = (V, E)$ est un graphe orienté, alors un chemin de longueur $k\geq 1$ est une suite ordonnée $(e_1, ..., e_k)$ de $k$ arcs $e_i = (v_{i, 1}, v_{i, 2})$ tels que $v_{i, 2} = v_{i+1, 1}$ pour tous $i\in \{1, ..., k-1\}$.
Si $G=(V,E)$ est un graphe pondéré par la fonction de poids $f:E\longrightarrow \mathbb R_+,$ on modifie légèrement les définitions précédentes. La longueur d'un chemin est maintenant définie comme la somme des poids des arêtes qui le composent. La distance entre deux sommets $a$ et $b$ est toujours définie comme la longueur minimale des chemins joignant $a$ à $b,$ en tenant compte de cette nouvelle définition de longueur.