Dans le graphe ci-dessous, les sept sommets A, B, C, D, E, F et G correspondent à sept sites touristiques.
Une arête reliant deux de ces sommets indique l'existence d'une liaison routière entre les deux sites correspondants.
Pour mieux visualiser sur le graphe les différents sites, on veut les colorier de telle sorte que deux sommets adjacents ne soient pas de la même couleur.
Donner un encadrement du nombre chromatique du graphe. Justifier la réponse.
Soit χ le nombre chromatique du graphe :
Le plus haut degré des sommets est 5 (sommet D) donc .
A-B-C-D est un sous graphe complet d'ordre 4. donc .
Ainsi,
Quel est le nombre minimun de couleurs nécessaires à coloration de ce graphe ? Justifier la réponse.
On colorie le graphe à l'aide de l'algorithme de Welsh & Powell :
Les sommets étant classés dans l'ordre des degrés décroissants D ; B ; C ; E ; G ; A ; F :
On attribue successivement la couleur 1 au sommet D, la couleur 2 au sommet B, la couleur 3 au sommet C.
Le sommet E est adjacent aux sommets D et B la plus petite couleur disponible est la couleur 3.
Le sommet G est adjacent au sommet D la plus petite couleur qui convienne est la couleur 2.
Le sommet A est adjacent aux sommets D, B et C on lui attribue la couleur 4.
Le sommet F n'est pas adjacent au sommet D on lui attribue la couleur 1.
Une coloration avec quatre couleurs est possible et donc le nombre chromatique du graphe est égal à 4.
Est-il possible d'organiser une visite passant au moins une fois par chaque site, tout en empruntant une fois et une seule chaque liaison routière ?
Si oui citer un trajet de ce type.
Déterminer un trajet qui emprunte chaque route une fois et une seule c'est chercher si le graphe possède une chaîne eulérienne.
La chaîne A-B-C-D-E-F-G passe par tous les sommets du graphe. Donc le graphe Γ est connexe.
D'autre part les degrés des sommets sont :
| Sommets | A | B | C | D | E | F | G |
| Degrés | 3 | 4 | 4 | 5 | 4 | 2 | 4 |
Le graphe est connexe et contient deux sommets de degré impair il admet donc une chaîne eulérienne par exemple D - G - E - F - G - C - B - E - D - B - A - D - C - A.
Le graphe est complété ci-dessous par les distances en kilomètres de chaque route (les longueurs des segments ne sont pas proportionnelles aux distances).
Une personne souhaite aller du site A au site F.
En expliquant la méthode utilisée, déterminer le trajet qu'il faut suivre pour que la distance parcourue soit la plus courte possible et donner cette distance.
Pour déterminer le trajet le plus court pour aller de A à F, on utilise l'algorithme de Dijkstra.
| A | B | C | D | E | F | G | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | A (0) |
| 18 (A) | 25 (A) | 32 (A) | ∞ | ∞ | ∞ | B (18) | |
| 25 (A) | 29 (B) | 42 (B) | ∞ | ∞ | C (25) | ||
| 29 (B) | 42 (B) | ∞ | 55 (C) | D (29) | |||
| 41 (D) | ∞ | 55 (C) | E (41) | ||||
| 68 (E) | 53 (E) | G (53) | |||||
| 67 (G) | F (67) |
Le sommet G étant marqué, pour lire la chaîne de poids minimal, on part de G et on "remonte" la chaîne en suivant les prédécesseurs. .
Pour aller de A à F, le trajet qu'il faut suivre pour que la distance parcourue soit la plus courte possible est A-B-D-E-G-F. La distance parcourue est de 67 km.
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.