Synthèse

Contenu démonstrateur — Cette page sert à tester l’interface, les blocs pédagogiques, les mathématiques, Mermaid et la recherche. Elle devra être remplacée progressivement par du contenu sourcé du cours.

Vue d’ensemble

La théorie des graphes étudie des objets formés de sommets reliés par des arêtes. Les notions de chemin, cycle, connexité, arbre et bipartition servent ensuite de base à de nombreux algorithmes.

graph LR A --- B A --- C B --- D C --- D D --- E

À mémoriser

Dans un graphe non orienté fini,

$$\sum_{v\in V}\deg(v)=2|E|.$$

La somme des degrés est donc toujours paire.

Définitions et résultats essentiels

Graphes et degré

Définition

Un graphe non orienté est un couple $G=(V,E)$, où $V$ est l’ensemble des sommets et $E$ l’ensemble des arêtes.

• son ordre est $|V|$ ;
• sa taille est $|E|$ ;
• le degré d’un sommet $v$, noté $\deg(v)$, est le nombre d’arêtes incidentes à $v$.

Théorème — Lemme des poignées de main

Pour tout graphe non orienté fini,

$$\sum_{v\in V}\deg(v)=2|E|.$$

Chaque arête contribue exactement deux fois à la somme des degrés, une fois pour chacune de ses extrémités.

Exemple

Dans le graphe ci-dessus, les degrés sont

$$\deg(A)=2,\quad \deg(B)=2,\quad \deg(C)=2,\quad \deg(D)=3,\quad \deg(E)=1.$$

On obtient bien

$$2+2+2+3+1=10=2|E|.$$

Chemins, cycles et connexité

Définition

Un chemin est une suite de sommets consécutifs reliés par des arêtes. Un cycle est un chemin fermé dont le premier et le dernier sommet coïncident. Un graphe est connexe lorsqu’il existe un chemin entre toute paire de sommets.

Résultat clé

Un arbre est un graphe connexe et sans cycle. Pour un arbre fini $T=(V,E)$,

$$|E|=|V|-1.$$

Réciproquement, un graphe connexe ayant $|V|-1$ arêtes est un arbre.

Piège

L’égalité $|E|=|V|-1$ ne suffit pas, à elle seule, à garantir qu’un graphe est un arbre : la connexité reste indispensable.

Graphes bipartis

Définition

Un graphe $G=(V,E)$ est biparti s’il existe une partition

$$V=V_1\cup V_2,\qquad V_1\cap V_2=\varnothing,$$

telle que chaque arête relie un sommet de $V_1$ à un sommet de $V_2$.

Théorème

Un graphe est biparti si et seulement s’il ne contient aucun cycle impair.

Exemple

Le cycle $C_4$ est biparti : on peut alterner les sommets entre deux classes. En revanche, le cycle $C_5$ ne l’est pas, car sa longueur est impaire.

Méthodes et pièges fréquents

Vérifier si un graphe est biparti

Méthode — Coloration en deux couleurs

On peut vérifier la bipartition avec un parcours BFS ou DFS :

1. choisir un sommet de départ et lui attribuer une première couleur ;
2. attribuer la couleur opposée à chacun de ses voisins ;
3. poursuivre le parcours en alternant les couleurs ;
4. si une arête relie deux sommets de même couleur, le graphe n’est pas biparti ;
5. sinon, les deux couleurs définissent les deux parties.

Piège

L’absence de triangle ne suffit pas pour conclure qu’un graphe est biparti. Un cycle impair de longueur $5$, $7$, etc. suffit déjà à empêcher toute bipartition.

Formules et résultats à connaître

• $\sum_{v\in V}\deg(v)=2|E|$ ;
• pour un arbre fini, $|E|=|V|-1$ ;
• arbre $\Longleftrightarrow$ connexe et acyclique ;
• biparti $\Longleftrightarrow$ absence de cycle impair.