On considère le graphe ci-dessus.
Ce graphe est-il connexe ?
La chaîne Y-C-D-G-H-E-F-B-A-Z contient tous les sommets du graphe.
Par conséquent, pour toute paire de sommets distincts, il existe une chaîne les reliant donc le graphe est connexe.
Déterminer le degré de chacun des sommets.
On pourra donner le résultat sous forme de tableau.
Le degré d'un sommet est égal au nombre d'arêtes dont ce sommet est une extrémité.
| Sommets | A | B | C | D | E | F | G | H | Y | Z |
| Degré | 4 | 4 | 4 | 4 | 4 | 2 | 4 | 2 | 3 | 1 |
Justifier l'existence d'une chaîne eulérienne.
Le graphe est connexe et a deux sommets de degré impair (Y et Z) alors ce graphe admet une chaîne eulérienne.
Déterminer un encadrement du nombre chromatique de ce graphe.
Notons le nombre chromatique du graphe.
Donc .
Montrer que ce nombre chromatique est égal à 3.
Une coloration à l'aide de trois couleurs est possible :
et une coloration avec 3 couleurs est possible donc le nombre chromatique de ce graphe est égal à 3.
Si on considère les sommets classés par ordre de degré décroissant et par ordre alphabétique A-B-C-D-E-G-Y-F-H-Z l'algorithme de coloration de Welsh et Powell (algorithme "glouton") donne une coloration avec 4 couleurs ce qui ne permet pas de conclure.
| Sommets | A | B | C | D | E | G | Y | F | H | Z |
| Couleur | 1 | 2 | 2 | 1 | 3 | 3 | 4 | 1 | 1 | 2 |
Pour exhiber une coloration avec trois couleurs à partir de cette coloration, il suffit de changer la couleur sommet A de lui attribuer la couleur 3, ce qui permet d'affecter la couleur 1 au sommet Y.
Par contre, l'algorithme de coloration fonctionne si on classe les sommets par ordre de degré décroissant sans tenir compte de l'ordre alphabétique
| Sommets | A | B | G | D | E | C | Y | F | H | Z |
| Couleur | 1 | 2 | 1 | 3 | 1 | 2 | 3 | 3 | 2 | 1 |
Voici le plan d'un musée : les parties grisées matérialisent les portes et les visiteurs partent de l'accueil, visitent le musée et doivent terminer leur visite à la boutique.
Représenter la situation à l'aide d'un graphe en précisant ce que représentent arêtes et sommets.
On choisi de représenter la situation par un graphe tel que :
le graphe de la partie 1 convient pour représenter la situation.
Pourquoi est-il possible de trouver un circuit où les visiteurs passent une fois et une seule par toutes les portes ?
D'après la première partie le graphe admet une chaîne eulérienne alors,
il est possible pour un visiteur de visiter le musée en passant une et une seule fois par toutes les portes.
Donner un exemple d'un tel circuit.
Exemple d'un circuit commençant par l'accueil (Y) et finissant par la boutique (Z) (les deux sommets de degré impair du graphe)
Y-C-G-Y-A-B-F-E-B-D-G-H-E-D-C-A-Z
Comment colorier les salles y compris l'accueil et la boutique, en utilisant un minimum de couleurs, pour que 2 salles qui communiquent par une porte aient des couleurs différentes ?
Le nombre chromatique du graphe est 3. Il suffit de trois couleurs pour que deux salles qui communiquent par une porte aient des couleurs différentes :
La couleur 1 pour les salles A, E et G. La couleur 2 pour les salles B, C, H et la boutique. La couleur 3 pour les salles D, F et l'accueil.
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.