Chapitre 25 : Graphe

$\text{Ensemble fini } S \text{ et } A \subset S^2$

$S$

$A$

$\text{Graphe } G (S, A) \text{ muni d'une fonction } w: A \rightarrow \mathbb R^+$

$\text{Fonction qui est associé au graphe dans un graphe pondéré}$

$\text{Graphe dans lequel les arrêtes sont des paires non ordonées, c'est-à-dire } (u, v) = (v, u)$

$u \text{ et } v \text{ sont les extrémités de } e$

$e \text{ est incidente à } u \text{ et } v$

$u \text{ et } v \text{ sont voisins / adjacents}$

$\text{Arête de la forme } e = (u, u) \in A$

$\text{Nombre de sommets adjacents}$

$\sum_{u \in S} d(u) = 2 |A|$

$\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}$

$p$

$v_0 \text{ et } v_p$

$\text{Chemin qui ne passe pas 2 fois par la même arête}$

$\text{Chemin dont les extrémités sont égales}$

$\text{Chemin qui passse pas deux fois par le même sommet, sauf éventuellement les extrémités}$

$\text{Longueur d'un plus court chemin entre les sommets}$

$\text{Pour tous sommets } (u, v) \in S^2, \text{il existe un chemin de } u \text{ à } v$

$\text{Sous-graphes connexes de taille maximale}$