Cours

MATHÉMATIQUES · Tle TI

Chapitre : Notion de graphes · Leçon 2

Quelques propriétés et algorithmes

Chaînes eulériennes, coloration, plus court chemin.

www.ndolomath.com

Cours de Mathématiques : « Quelques propriétés et algorithmes », proposé par ndolomathndolomath

Propriétés et algorithmes

💡 Idée principale : Le théorème d’Euler dit qu’un graphe connexe admet une chaîne eulérienne (passant une fois par chaque arête) si et seulement s’il a 0 ou 2 sommets de degré impair. La coloration des sommets se fait avec l’algorithme de Welsh-Powell, et l’algorithme de Dijkstra donne le plus court chemin dans un graphe pondéré.

Ce que tu vas apprendre

Utiliser le théorème d’Euler pour l’existence d’une chaîne ou d’un cycle eulérien.
Colorier un graphe avec l’algorithme de Welsh-Powell et encadrer le nombre chromatique.
Déterminer un plus court chemin avec l’algorithme de Dijkstra.

Pourquoi cette leçon ?

Un facteur veut passer une seule fois dans chaque rue ; un proviseur veut organiser des examens sans conflit d’horaires ; un GPS cherche l’itinéraire le plus court. Ces trois problèmes ont des algorithmes de résolution sur les graphes.

Prérequis : vérifie tes bases

Calcule les degrés des sommets d’un carré dont on trace une diagonale.

Peux-tu dessiner une enveloppe ouverte sans lever le crayon ni repasser sur un trait ?

Additionne les longueurs d’un trajet

A \to B \to C

de 4 km et 3 km.

Situation problème : La tournée du livreur

Un livreur de pain doit parcourir les rues d’un quartier modélisé par le graphe : $A$ – $B$ (2 km), $A$ – $C$ (5 km), $B$ – $C$ (1 km), $B$ – $D$ (4 km), $C$ – $D$ (2 km), $C$ – $E$ (6 km), $D$ – $E$ (3 km).
Peut-il passer une seule fois par chaque rue ? Quel est le plus court chemin de $A$ à $E$ ?

www.ndolomath.com

Cours de Mathématiques : « Quelques propriétés et algorithmes », proposé par ndolomathndolomath

Activité d’apprentissage

On étudie le graphe pondéré du quartier.

Calcule le degré de chaque sommet. Que dit le théorème d’Euler ?
Si une chaîne eulérienne existe, donne ses extrémités possibles et propose-en une.
Applique l’algorithme de Dijkstra à partir de $A$ .
Réponds à la situation problème.

Théorème d’Euler

Un graphe connexe admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair ; il admet une chaîne eulérienne (non fermée) si et seulement s’il a exactement deux sommets de degré impair, qui sont alors les extrémités de la chaîne.

Exemple à traiter : Le problème des ponts de Königsberg : le graphe à 4 sommets de degrés 3, 3, 3, 5 admet-il une chaîne eulérienne ?

R2 · Coloration

Colorier un graphe, c’est attribuer une couleur à chaque sommet de sorte que deux sommets adjacents aient des couleurs différentes. Le nombre chromatique

χ

vérifie

χ \leq Δ + 1

(

Δ

degré maximal) et

χ \geq

ordre du plus grand sous-graphe complet. Welsh-Powell : ranger les sommets par degrés décroissants et colorier glouton.

Exemple à traiter : Six examens

E_{1}

E_{6}

; les paires incompatibles sont

E_{1} E_{2}

E_{1} E_{3}

E_{2} E_{3}

E_{2} E_{4}

E_{3} E_{5}

E_{4} E_{5}

E_{5} E_{6}

. Combien de créneaux faut-il au minimum ?

www.ndolomath.com

Cours de Mathématiques : « Quelques propriétés et algorithmes », proposé par ndolomathndolomath

Algorithme de Dijkstra

On attribue au sommet de départ la distance 0 et

\infty

aux autres. À chaque étape, on fixe le sommet non fixé de plus petite distance, puis on met à jour les distances de ses voisins par

min (d (v), d (u) + p (u, v))

. On s’arrête quand le sommet d’arrivée est fixé.

Exemple à traiter : Applique l’algorithme de Dijkstra au graphe de la situation pour aller de

A

E

, en présentant un tableau.

Erreurs fréquentes

⚠ Graphe non connexe

Le théorème d’Euler suppose le graphe connexe.

⚠ Dijkstra

On ne fixe un sommet que lorsqu’il a la plus petite distance provisoire.

Exercice d’application

Peut-on tracer la figure du graphe complet $K_{5}$ sans lever le crayon ni repasser sur une arête ? Et $K_{4}$ ?
Détermine le nombre chromatique d’un cycle à 5 sommets, puis à 6 sommets.
Réponds à la situation problème.

À retenir

Euler : 0 sommet impair → cycle ; 2 → chaîne. Coloration :

χ \leq Δ + 1

, Welsh-Powell. Dijkstra : fixer le plus proche, mettre à jour.