1$\text{Graphe}$
$\text{Ensemble fini } S \text{ et } A \subset S^2$
2$\text{Sommets d'un graphe } G = (S, A)$
$S$
3$\text{Arêtes / Arcs d'un graphe } G = (S, A)$
$A$
4$\text{Graphe pondéré}$
$\text{Graphe } G (S, A) \text{ muni d'une fonction } w: A \rightarrow \mathbb R^+$
5$\text{Fonction de pondération}$
$\text{Fonction qui est associé au graphe dans un graphe pondéré}$
6$\text{Graphe non orienté}$
$\text{Graphe dans lequel les arrêtes sont des paires non ordonées, c'est-à-dire } (u, v) = (v, u)$
7$\text{Signification de } e = (u, v) \in A \text{ du point de vue de } e$
$u \text{ et } v \text{ sont les extrémités de } e$
8$\text{Signification de } e = (u, v) \in A \text{ du point de vue de } u \text{ et } v$
$e \text{ est incidente à } u \text{ et } v$
9$\text{Signification de } e = (u, v) \in A \text{ pour } u \text{ et } v$
$u \text{ et } v \text{ sont voisins / adjacents}$
10$\text{Boucle}$
$\text{Arête de la forme } e = (u, u) \in A$
11$\text{Dégré d'un sommet}$
$\text{Nombre de sommets adjacents}$
12$\text{Lemme des poignées de main}$
$\sum_{u \in S} d(u) = 2 |A|$
13$\text{Chemin de } u \text{ à v}$
$\text{Suite finie de sommet } (v_0, ..., v_p) \text{ tel que : }$
$\begin{cases}v_0 = u \\ v_p = v \\ \forall i \in \llbracket 0, p-1 \rrbracket \quad (v_i, v_{i+1}) \in A\end{cases}$
14$\text{Longueur d'un chemin } (v_0, ..., v_p)$
$p$
15$\text{Extrémités d'un chemin } (v_0, ..., v_p)$
$v_0 \text{ et } v_p$
16$\text{Chemin simple}$
$\text{Chemin qui ne passe pas 2 fois par la même arête}$
17$\text{Cycle}$
$\text{Chemin dont les extrémités sont égales}$
18$\text{Chemin élémentaire}$
$\text{Chemin qui passse pas deux fois par le même sommet, sauf éventuellement les extrémités}$
19$\text{Distance entre 2 sommets}$
$\text{Longueur d'un plus court chemin entre les sommets}$
20$\text{Graphe connexe}$
$\text{Pour tous sommets } (u, v) \in S^2, \text{il existe un chemin de } u \text{ à } v$
21$\text{Composantes connexes}$
$\text{Sous-graphes connexes de taille maximale}$