Introduction à la théorie de graphes - fiches de révision (A)

Un graphe simple non-orienté est un couple $G = (S, A)$ où :

• $S$ est un ensemble fini non vide de sommets (ou nœuds).
• $A$ est un sous-ensemble de $\mathcal{P}_2(S)$ (l'ensemble des paires de $S$), appelé l'ensemble des arêtes.

Une arête est une paire $\{x, y\}$ de sommets distincts.

Propriétés :

• Pas de boucles (une arête ne relie pas un sommet à lui-même).
• Pas d'arêtes multiples (au plus une arête entre deux sommets).
• La relation d'adjacence est symétrique.

L'ordre d'un graphe est simplement le nombre total de ses sommets.

On le note généralement $|S|$ ou parfois $n$.

Exemple :

Si $S = \{a, b, c, d\}$, l'ordre du graphe est 4.

Deux graphes $G=(S,A)$ et $G'=(S',A')$ sont isomorphes (noté $G \cong G'$) s'il existe une bijection $\varphi : S \to S'$ qui préserve l'adjacence.

Cela signifie que pour tous sommets $x, y \in S$ :

$\{x, y\} \in A \iff \{\varphi(x), \varphi(y)\} \in A'$

Intuition :

Deux graphes sont isomorphes s'ils ont la même structure topologique, même si les sommets portent des noms différents ou s'ils sont dessinés différemment.

Un graphe complet d'ordre $n$, noté $K_n$ (ou clique), est un graphe où tous les sommets sont connectés deux à deux.

Nombre d'arêtes :

Il possède le maximum d'arêtes possible pour un graphe simple d'ordre $n$ :

$|A| = \binom{n}{2} = \frac{n(n-1)}{2}$

Exemple :

$K_3$ est un triangle (3 sommets, 3 arêtes).

Un graphe biparti complet $K_{n,m}$ est un graphe dont les sommets sont partitionnés en deux ensembles disjoints $U$ (de taille $n$) et $V$ (de taille $m$).

Règles de connexion :

• Chaque sommet de $U$ est relié à tous les sommets de $V$.
• Il n'y a aucune arête reliant deux sommets de $U$ entre eux.
• Il n'y a aucune arête reliant deux sommets de $V$ entre eux.

Son nombre total d'arêtes est $n \times m$.

Pour un graphe $G=(S, A)$, la somme des degrés des sommets est égale à deux fois le nombre d'arêtes :

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

Où :

• $d(s)$ est le degré du sommet $s$ (nombre de voisins).
• $|A|$ est le nombre total d'arêtes.

Conséquence :

La somme des degrés est toujours un nombre pair. Le nombre de sommets ayant un degré impair est nécessairement pair.

Pour un graphe avec $n$ sommets $\{s_1, \dots, s_n\}$, la matrice d'adjacence $A_G$ est une matrice carrée de taille $n \times n$ définie par :

$a_{i,j} = \begin{cases} 1 & \text{si } \{s_i, s_j\} \in A \text{ (les sommets sont reliés)} \\ 0 & \text{sinon} \end{cases}$

Propriétés clés :

• La matrice est symétrique pour les graphes non-orientés ($a_{i,j} = a_{j,i}$).
• La diagonale est nulle ($a_{i,i} = 0$) car il n'y a pas de boucles.
• La somme des éléments de la ligne $i$ donne le degré $d(s_i)$.

Méthode :

1. Trier la suite dans l'ordre décroissant : $d_1 \geq d_2 \geq \dots \geq d_n$.
2. Supprimer le premier terme $d_1$.
3. Soustraire 1 aux $d_1$ termes suivants de la suite.
4. Répéter l'opération (en réordonnant si nécessaire) jusqu'à obtenir :
   • Une suite de zéros (la suite est graphique).
   • Des nombres négatifs ou une impossibilité de soustraire (la suite n'est pas graphique).

Exemple :

Pour $(3, 3, 2, 2, 2)$ : on retire 3, on réduit les 3 suivants $\rightarrow (2, 1, 1, 2) \rightarrow$ tri $\rightarrow (2, 2, 1, 1)$...

Soit un graphe $G=(S, A)$.

• Sous-graphe : On choisit un sous-ensemble de sommets et un sous-ensemble d'arêtes existantes. On peut choisir de ne pas inclure certaines arêtes même si leurs extrémités sont présentes.
• Sous-graphe induit : On choisit un sous-ensemble de sommets $S' \subseteq S$, et on doit garder toutes les arêtes de $G$ qui relient des sommets de $S'$.

$A' = A \cap \mathcal{P}_2(S')$

Un sous-graphe induit est entièrement déterminé par le choix de ses sommets.

Le théorème de Turán donne le nombre maximum d'arêtes qu'un graphe d'ordre $n$ peut avoir sans contenir de clique de taille $r$ ($K_r$).

Formule :

Si $G$ ne contient pas de $K_r$, alors :

$|A| \leq \left( 1 - \frac{1}{r - 1} \right) \frac{n^2}{2}$

Application :

Il sert à comprendre la densité maximale d'un graphe avant qu'une certaine structure (le triangle $K_3$, le tétraèdre $K_4$, etc.) n'apparaisse obligatoirement.

Le nombre de Ramsey $R(s, t)$ est le plus petit entier $n$ tel que n'importe quel graphe d'ordre $n$ contienne obligatoirement :

• Soit une clique d'ordre $s$ ($K_s$, $s$ sommets tous reliés).
• Soit un stable d'ordre $t$ ($S_t$, $t$ sommets dont aucun n'est relié).

Exemple célèbre :

$R(3, 3) = 6$. Dans tout groupe de 6 personnes, soit 3 se connaissent toutes, soit 3 ne se connaissent pas du tout.