Une compagnie aérienne propose des vols directs entre certaines villes, notées A, B, C, D, E, F et G.
Cela conduit au graphe suivant, dont les sommets sont les villes et les arêtes représentent les liaisons aériennes :
Le graphe est-il complet ? Quel est l'ordre de ?
Un graphe non orienté est complet lorsque tous ses sommets sont adjacents les uns avec les autres. Or il n'y a pas d'arête reliant les sommets A et G .
Donc le graphe n'est pas complet.
L'ordre d'un graphe est le nombre de sommets de ce graphe.
Donc le graphe est d'ordre 7.
Sur les cartes d'embarquement, la compagnie attribue à chaque aéroport une couleur, de sorte que deux aéroports liés par un vol direct aient des couleurs différentes.
Proposer un coloriage adapté à cette condition.
On effectue un coloriage du graphe à l'aide de l'algorithme "glouton" :
Classer les sommets dans l'ordre décroissant des sommets : B (5); E (5); C (4); D (4); A (3); G (3); F (2).
Choisir la couleur d'usage (1) et colorier avec cette couleur le sommet B de degré 5.
Parcourir le graphe dans l'ordre de la liste et examiner tous les sommets non colorés, choisir le sommet de degré le plus élevé qui n'est pas adjacent à B et lui attribuer la couleur la couleur d'usage (1). F aura la couleur (1).
Choisir une autre couleur d'usage (2), colorier le sommet E et recommencer le parcours. E et A , ont la couleur (2).
Avec l'algorithme "glouton", une coloration du graphe à l'aide de 4 couleurs est possible :
Couleur (1) les sommets B et F; couleur (2) les sommets E et A; couleur (3) les sommets C et G couleur (4) le sommet D.
Que peut-on en déduire sur le nombre chromatique de ?
En utilisant l'algorithme "glouton", quatre couleurs suffisent pour colorier le graphe :
Le nombre chromatique de est inférieur ou égal à 4.
Quelle est la nature du sous graphe formé par les sommets A, B, C et D ?
Tous les sommets du sous graphe sont adjacents :
Le sous graphe formé par les sommets A, B, C et D est complet.
Quel est le nombre minimal de couleurs que la compagnie doit utiliser pour pouvoir attribuer une couleur à chaque aéroport en respectant les conditions du 2. ?
Notons le nombre chromatique du graphe .
Ainsi, . D'autre part, dans la question 2 il a été établi que . Donc .
Le nombre minimal de couleurs est 4.
En considérant les sommets dans l'ordre alphabétique, construire la matrice M associée à .
La matrice M associée à est
On donne :. Combien y a-t-il de chemins de longueurs 8 qui relient B à D ?
le nombre de chemins de longueur 8 permettant de se rendre du sommet B au sommet D est le terme situé à l'intersection de la ligne 2 et de la colonne 4 de la matrice .
Il y a exactement 12636 chemins de longueurs 8 qui relient B à D .
Pourquoi est-il impossible pour un voyageur de construire un itinéraire qui utilise chaque liaison aérienne une et une seule fois ?
Construire un itinéraire qui utilise chaque liaison aérienne une et une seule fois signifie que le graphe comporte une chaîne eulérienne.
Le graphe a quatre sommets de degré impair
Les sommets B et E sont de degré 5, les sommets A et G sont de degré 3 d'apès le théorème d'Euler : 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. il n'existe pas de chaîne eulérienne.
Il est impossible de de construire un itinéraire qui utilise chaque liaison aérienne une et une seule fois.
Montrer qu'il est possible de construire un tel itinéraire en ajoutant une seule liaison qui n'existe pas déjà et que l'on précisera.
Tous les termes de la matrice sont strictement positifs, il existe au moins une chaîne de longueur 8 permettant de relier deux sommets quelconques de ce graphe. Donc ce graphe est connexe.
Le graphe étant connexe, pour obtenir une chaîne eulérienne il suffit de rajouter des liaisons de manière à n'avoir au maximum que deux sommets de degré impair.
Or les sommets de degré impair B et E sont adjacents, alors que les sommets de degré impair A et G ne sont pas adjacents.
Il suffit d'ajouter une liaison entre les sommets A et G, pour que le graphe ne contienne plus que deux sommets de degré impair et admette une chaîne eulérienne d'extrémités les sommets B et E.
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.