Un groupe d'amis organise une randonnée dans les Alpes.
On a représenté par le graphe ci-dessous les sommets B, C, D, F, T, N par lesquels ils peuvent choisir de passer. Une arête entre deux sommets coïncide avec l'existence d'un chemin entre les deux sommets.
Recopier et compléter le tableau suivant :
Dans un graphe non orienté, le degré d'un sommet du graphe est le nombre d'arêtes issues de ce sommet.
| Sommets | B | C | D | F | N | T |
| Degré des sommets du graphe | 2 | 4 | 4 | 5 | 3 | 4 |
Justifier que le graphe est connexe.
La chaîne B-C-D-N-F-T 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.
Le groupe souhaite passer par les six sommets en passant une fois et une seule par chaque chemin. Démontrer que leur souhait est réalisable. Donner un exemple de trajet possible.
Passer par les six sommets en passant une fois et une seule par chaque chemin revient à chercher une chaîne eulérienne.
Or le graphe est connexe et contient seulement deux sommets de degré impair par conséquent, il existe une chaîne eulérienne commençant par un des deux sommets de degré impair (F ou N) et finissant par le deuxième sommet de degré impair.
Il est possible de passer par les six sommets en passant une fois et une seule par chaque chemin par exemple N - D - C - B - F - N - T - D - F - T - C - F .
Le groupe souhaite associer chaque sommet à une couleur de sorte que les sommets reliés par un chemin n'ont pas la même couleur. On note n le nombre chromatique du graphe.
Montrer que .
Le plus haut degré des sommets est 5 donc
Le sous graphe d'ordre 4 est complet donc
Ainsi,
Proposer un coloriage du graphe permettant de déterminer son nombre chromatique.
On attribue la couleur 1 au sommet F, la couleur 2 aux sommets C et N, la couleur 3 aux sommets T et B et la quatrième couleur au sommet D.
Une coloration avec quatre couleurs est possible, comme donc le nombre chromatique du graphe est 4.
Le groupe se trouve au sommet B et souhaite se rendre au sommet N. Les distances en kilomètres entre chaque sommet ont été ajoutées sur le graphe.
Indiquer une chaîne qui minimise la distance du trajet. Justifier la réponse.
Pour déterminer le trajet le plus court pour se rendre du sommet B au sommet N, on utilise l'algorithme de Dijkstra.
| B | C | D | F | N | T | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | B (0) |
| 12 (B) | ∞ | 15(B) | ∞ | ∞ | C (12) | |
| 14 (C) | 15(B) | ∞ | 17(C) | D (14) | ||
| 15 (B) | 26(D) | 17(C) | F (15) | |||
| 26(D) | 17 (C) | T (17) | ||||
| 24 (T) | N (21) |
Le sommet N étant marqué, pour lire la chaîne de poids minimal, on part de N et on "remonte" la chaîne en suivant les prédécesseurs. .
La plus courte chaîne reliant le sommet B au sommet N est B-C-T-N. Le trajet le plus court pour se rendre du sommet B au sommet N est de 24 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.