Définition

Un graphe $G = (V, E)$ est constitué de :

Un graphe est orienté si les arêtes ont un sens (on parle d’arcs).

Vocabulaire

Degré $d(v)$ d’un sommet : nombre d’arêtes incidentes
Graphe simple : pas de boucle, au plus une arête entre deux sommets
Graphe complet $K_n$ : toutes les paires de sommets sont reliées → $\dfrac{n(n-1)}{2}$ arêtes

Lemme des poignées de mains : $\displaystyle\sum_{v \in V} d(v) = 2|E|$

Chaîne (ou chemin) : suite de sommets où chaque consécutif est relié par une arête
Chemin simple : sans répétition de sommet
Cycle : chemin fermé (commence et finit au même sommet)

Un graphe est connexe si tout couple de sommets est relié par une chaîne.

Un arbre est un graphe connexe sans cycle avec $n$ sommets et $n-1$ arêtes.

Pour un graphe à $n$ sommets, la matrice $A$ de taille $n \times n$ :

$A_{ij} = \text{nombre d'arêtes entre } i \text{ et } j$

Propriété : $(A^k)_{ij}$ = nombre de chemins de longueur $k$ entre $i$ et $j$ .

Exemple : Graphe avec 3 sommets et arêtes $\{1-2, 1-3, 2-3\}$ :

$A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}$

Chemin eulérien : passe par chaque arête exactement une fois
- Existe $\iff$ le graphe est connexe et possède exactement 0 ou 2 sommets de degré impair
Cycle hamiltonien : passe par chaque sommet exactement une fois (problème difficile en général)

Un graphe est biparti si ses sommets peuvent être divisés en deux groupes $A$ et $B$ tels que toutes les arêtes vont de $A$ vers $B$ .

Théorème : Un graphe est biparti $\iff$ il ne contient pas de cycle de longueur impaire.