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 ?
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.
Que peut-on en déduire sur le nombre chromatique de ?
Quelle est la nature du sous graphe formé par les sommets A, B, C et D ?
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. ?
En considérant les sommets dans l'ordre alphabétique, construire la matrice M associée à .
On donne :
Combien y a-t-il de chemins de longueurs 8 qui relient B à D ?
Utiliser la propriété donnant le nombre de chaînes de longueur n reliant deux sommets d'un graphe :
Le terme situé à l'intersection de la ligne i et de la colonne j de la matrice , donne le nombre de chaînes de longueur n reliant le sommet et le sommet du graphe.
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.
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.
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.