Le graphe ci-dessous représente le plan d'une ville. Le sommet A désigne l'emplacement des services techniques. Les sommets B, C, D, E, F et G désignent les emplacements de jardins publics. Une arête représente l'avenue reliant deux emplacements et est pondérée par le nombre de feux tricolores situés sur le trajet.
Les parties I et II sont indépendantes.
partie I : On s'intéresse au graphe non pondéré.
Répondre sans justification aux quatre questions suivantes :
Ce graphe est-il connexe ?
La chaîne A-B-C-D-E-F-G 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.
Ce graphe est-il complet ?
Les sommets E et F ne sont pas adjacents, donc le graphe n'est pas complet.
Ce graphe admet-il une chaîne eulérienne ?
Dans un graphe non orienté, le degré d'un sommet du graphe est le nombre d'arêtes issues de ce sommet. Nous avons donc :
| Sommets | A | B | C | D | E | F | G |
| Degré des sommets du graphe | 2 | 4 | 5 | 5 | 4 | 4 | 2 |
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 (C ou D) et finissant par le deuxième sommet de degré impair.
Ce graphe admet-il un cycle eulérien ?
Tous les sommets de ce graphe ne sont pas de degé pair alors, le graphe n'admet pas de cycle eulérien.
Déterminer, en justifiant, le nombre chromatique de ce graphe.
Soit n le nombre chromatique de ce graphe.
Le plus haut degré des sommets est 5 donc et le sous graphe est un sous graphe complet d'ordre 4 donc . Ainsi,
Une coloration avec quatre couleurs est possible, comme donc le nombre chromatique du graphe est 4.
partie II : On s'intéresse au graphe pondéré.
Proposer un trajet comportant un minimum de feux tricolores reliant A à G. La réponse sera justifiée par un algorithme.
Pour déterminer le trajet comportant un minimum de feux tricolores reliant A à G, on utilise l'algorithme de Dijkstra.
| A | B | C | D | E | F | G | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | A (0) |
| 2 (A) | 1 (A) | ∞ | ∞ | ∞ | ∞ | C (1) | |
| 2 (A) | 5 (C) | 4 (C) | 6 (C) | ∞ | B (2) | ||
| 3 (B) | 4 (C) | 6 (C) | ∞ | D (3) | |||
| 4 (C) | 6 (C) | 8 (D) | E (4) | ||||
| 5 (E) | 8 (D) | F (5) | |||||
| 7 (F) | G (12) |
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. .
Le trajet comportant un minimum de feux tricolores reliant A à G est A-C-E-F-G. (Il y a 7 feux tricolores).
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.