Graphes - Bac blanc ES Sujet 1 - Maths-cours 2018 (spé)
Exercice 4 (5 points)
Candidats ayant suivi l'enseignement de spécialité
Un appartement comporte 6 pièces notées A, B, C, D, E et F.
Le plan ci-après présente la disposition des pièces ainsi que les portes de communication entre ces pièces.
Par exemple, il y a une porte de communication entre les pièces A et B mais il n'y en a pas entre les pièces B et E.
La porte donnant accès à l'appartement est sans importance dans le cadre de l'exercice et n'a pas été représentée.
Toutes les réponses aux questions posées devront être justifiées.
Traduire la situation à l'aide d'un graphe (G) dont les sommets représentent les pièces et dont les arêtes représentent les portes de communication.
Le graphe (G) est-il connexe ? complet ?
Est-il possible de parcourir l'appartement en empruntant chaque porte une fois et une seule ?
Si oui, donner un exemple d'un tel chemin.Est-il possible de parcourir l'appartement en empruntant chaque porte une fois et une seule et en partant et en arrivant dans la même pièce ?
Si oui, donner un exemple d'un tel chemin.
Déterminer la matrice de transition associée au graphe précédent en prenant les sommets par ordre alphabétique.
À l'aide d'une calculatrice on trouve :
Combien existe-t-il de chemins permettant d'aller de la pièce A à la pièce D en empruntant exactement trois portes ?
Donner la liste de ces chemins.Est-il toujours possible de relier deux pièces différentes en empruntant exactement trois portes ?
Montrer qu'il existe au moins un sous-graphe complet de (G) d'ordre 3.
Le propriétaire souhaite repeindre l'appartement en respectant les règles suivantes :
chaque pièce sera repeinte avec une couleur unique ;
deux pièces adjacentes, c'est à dire reliées par une porte, seront repeintes avec des couleurs différentes.
Pourra-t-il réaliser ces objectifs en utilisant seulement trois couleurs ?
Corrigé
On place d'abord les sommets A, B, C, D, E et F qui représentent les pièces et on relie, par des arêtes, les pièces qui communiquent : A-B, A-E, A-F, B-C, C-D, C-E, D-E, E-F.
Le graphe est connexe. En effet, un graphe est connexe si deux sommets quelconques peuvent être reliés par une chaîne ce qui est le cas ici.
Le graphe n'est pas complet. Un graphe non orienté est complet si et seulement si tous ses sommets sont reliés par une arête. Ce n'est pas le cas ici pour A et C par exemple.
À retenir
Un graphe est complet si et seulement si tous ses sommets sont deux à deux adjacents (c'est à dire reliés par une arête).
Un graphe est connexe si et seulement si deux sommets quelconques peuvent être reliés par une chaîne (intuitivement cela signifie que le graphe est en « un seul morceau »).
On recherche s'il existe une chaîne eulérienne, c'est à dire une chaîne qui contient une fois et une seule chacune des arêtes du graphe.
D'après le théorème d'Euler, un graphe connexe contient une chaîne eulérienne si et seulement s'il possède 0 ou 2 sommets de degré impair.
Le degré de chacun des sommets est donné par le tableau ci-après :
Sommet A B C D E F Degré 3 2 3 2 4 2 Le graphe (G) possède deux sommets de degré impair : A et C.
Il est donc possible de parcourir l'appartement en empruntant chacune des 8 portes une fois et une seule, par exemple en suivant le trajet : A-B-C-D-E-F-A-E-C.
À retenir
Une chaîne eulérienne est une chaîne qui contient une fois et une seule chacune des arêtes du graphe.
Trouver un chemin qui emprunte chaque arête une fois et une seule revient à trouver une chaîne eulérienne.
Un graphe connexe admet une chaîne eulérienne si et seulement s'il possède 0 ou 2 sommet(s) de degré impair.
Dans cette question, on recherche l'existence d'un cycle eulérien (un cycle est une chaîne fermée).
Or, d'après le théorème d'Euler, un graphe connexe contient un cycle eulérien si et seulement s'il ne possède aucun sommet de degré impair.
Ici, A et C sont de degré impair. Toute chaîne eulérienne aura pour extrémités A et C et ne sera donc pas un cycle.
Par conséquent, il n'est pas possible de parcourir l'appartement en empruntant chaque porte une fois et une seule et en partant et en arrivant dans la même pièce.
À retenir
Un cycle eulérien est une chaîne fermée qui contient une fois et une seule chacune des arêtes du graphe.
Trouver un chemin qui emprunte chaque arête une fois et une seule et dont les sommets de départ et d'arrivée sont identiques revient à trouver un cycle eulérien.
Un graphe connexe admet un cycle eulérien si et seulement s'il ne possède aucun sommet de degré impair.
Numérotons les pièces A: 1, B: 2, C: 3, D: 4, E: 5, F: 6.
La matrice de transition associée au graphe précédent s'obtient en plaçant à la -ième ligne et à la -ième colonne :un « 1 » si les pièces numérotées et sont reliés par une arête ;
un « 0 » sinon.
On obtient alors la matrice :
Le coefficient de situé à la -ième ligne et à la -ième colonne indique le nombre de chemins de trois arêtes menant du sommet numéro au sommet numéro .
Ici, le coefficient situé à la première ligne et à la quatrième colonne est 3. Il y a donc 3 chemins permettant d'aller de la pièce A à la pièce D en empruntant exactement trois portes.
À l'aide du graphe, on trouve les chemins : A-B-C-D, A-E-C-D et A-F-E-D.
À retenir
Le coefficient de la matrice situé à la -ième ligne et à la -ième colonne correspond au nombre de chemins de longueur \bm{n} menant du sommet numéro au sommet numéro .
La matrice comporte un unique coefficient nul situé en ligne 2 et en colonne 2. Cela signifie qu'il n'est pas possible de partir de la pièce B pour revenir à la pièce B en empruntant exactement 3 portes mais que, mis à part ce cas, il est toujours possible de joindre deux pièces en empruntant exactement 3 portes.
Comme l'énoncé précise deux pièces différentes, il est effectivement toujours possible de joindre deux pièces différentes en empruntant exactement trois portes.
Considérons le sous-graphe constitué des sommets A, E et F. Chacun de ces trois sommets est relié aux deux autres, donc ce sous-graphe est complet. Le sous-graphe constitué de C, E et D est lui-aussi complet.
Il est possible de repeindre les pièces en respectant les consignes de l'énoncé et avec seulement trois couleurs.
Le sous-graphe A, E et F étant complet, il faudra nécessairement trois couleurs différentes pour peindre ces trois pièces.
Il en est de même pour les pièces C, E et D.En respectant ces contraintes, il est facile de trouver une solution au problème posé ; par exemple (mais il y a d'autres solutions ...) :
Couleur 1 : E, B
Couleur 2 : A, C
Couleur 3 : F, D.