Sur la carte ci-dessous, sont représentés sept pays avec leurs frontières.
On s'intéresse aux frontières séparant ces pays. :
Traduire cette carte par un graphe dont les sommets sont les pays et où chaque arête représente une frontière entre deux pays.
On appelle M la matrice associée à ce graphe, les sommets étant pris dans l'ordre alphabétique. Une des trois matrices R, S ou T est la matrice Sans calculs, indiquer quelle est la matrice .
; ;
Les sommets étant classés dans l'odre alphabétique, les termes de la matrice donnent le nombre de chaînes de longueur 3 reliant deux sommets quelconques.
Les matrices R et T ne conviennent pas pour plusieurs raisons, entre autres :
Il existe plus d'une chaîne de longueur 3 qui relient les sommets A et G ( A-C-D-G, A-B-D-G, A-D-E-G, … ) or et .
Le graphe n'est pas orienté et la matrice T n'est pas symétrique.
Il existe au moins une chaîne de longueur 3 qui relient les sommets C et F par exemple B-D-E-F or et .
La matrice S est la seule susceptible d'être égale à
Est-il possible, dans tous les cas, de se rendre d'un pays à un autre en franchissant exactement trois frontières ?
Les termes de la matrice sont différents de 0 alors, il est possible, dans tous les cas, de se rendre d'un pays à un autre en franchissant exactement trois frontières.
Est-il possible de visiter tous les pays en franchissant une et une seule fois chacune des frontières ?
Visiter tous les pays en franchissant une et une seule fois chacune des frontières revient à chercher une chaîne eulérienne Un graphe connexe admet une chaîne eulérienne si et seulement si le nombre de ses sommets de degré impair est 0 ou 2.
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.
Déterminons le degré de chacun des sommets.
Sommets | A | B | C | D | E | F | G |
Degré | 4 | 4 | 3 | 5 | 4 | 2 | 4 |
Le graphe est connexe et il existe deux sommets de degré impair, il admet donc 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. Par exemple :
Il existe une chaîne eulérienne donc il est possible de visiter tous les pays en franchissant une et une seule fois chacune des frontières.
Proposer une coloration de la carte (ou du graphe) avec le minimum de couleurs afin que deux pays qui ont une frontière commune aient des couleurs différentes.
Soit X le nombre chromatique du graphe.
Le plus haut degré des sommets est 5 donc .D'autre part, est un sous graphe complet d'ordre 4 donc . Ainsi, .
Or à l'aide de l'algorithme de Welsh et Powell on obtient une coloration avec 4 couleurs. Donc le nombre nombre chromatique du graphe est égal à 4.
Quatre couleurs sont nécessaires pour colorier la carte.
Une personne désire se rendre en train d'une ville située dans le pays A à une autre ville du pays F. Le graphe pondéré ci-dessous donne, en heures, les durées moyennes des liaisons ferroviaires existantes entre les différents pays en tenant compte des temps d'attente entre deux correspondances.
En précisant la méthode utilisée, déterminer le trajet le plus court que cette personne devra utiliser pour son voyage. Combien de temps faut-il prévoir pour effectuer ce trajet ?
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) |
4 (A) | 3 (A) | 7 (A) | ∞ | ∞ | 6 (A) | C (3) | |
4(A) | 5 (C) | ∞ | ∞ | 6 (A) | B (4) | ||
5 (C) | 7 (B) | ∞ | 6 (A) | D (5) | |||
7 (B) | ∞ | 6 (A) | G (6) | ||||
7 (B) | 10 (G) | E (7) | |||||
9 (E) | F (9) |
Le sommet F étant marqué, pour lire la chaîne de poids minimal, on part de F et on "remonte" la chaîne en suivant les prédécesseurs. .
Le trajet le plus court possible pour aller de A à F est A-B-E-F. Il faudra prévoir environ 9 heures pour effectuer ce trajet.
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.