Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

CAHIERS DE LA CRM Introduction à la théorie des graphes Solutions des exercices

CAHIERS DE LA CRM Introduction à la théorie des graphes Solutions des exercices Didier Müller CAHIER N O 6 COMMISSION ROMANDE DE MATHÉMATIQUE 1 Graphes non orientés Exercice 1 On obtient le graphe biparti suivant (à gauche) : P1 C1 P2 C2 P3 C3 P1 C1 P2 C2 P3 C3 En colorant les arêtes de ce graphe (1 couleur = 1 heure de l’horaire), en prenant garde que chaque sommet n’ait pas deux arêtes incidentes de même couleur, on obtient le résultat de droite. De ce graphe coloré, on tire l’horaire suivant : P1 P2 P3 1ère heure (rouge) C1 C3 C2 2ème heure (vert) C1 C2 C3 3ème heure (bleu) C2 C1 C3 4ème heure (noir) C1 Exercice 2 On obtient le graphe complet K6. 2 1 3 6 4 5 Il faudra 5 jours de tournoi. Voici un calendrier possible : Jour 1 Jour 2 Jour 3 Jour 4 Jour 5 1-2 2-3 1-3 2-4 1-4 3-4 4-5 4-6 1-5 2-6 5-6 1-6 2-5 3-6 3-5 Ce calendrier a été construit d’après les cinq schémas ci-dessous : 2 1 3 6 4 5 2 1 3 6 4 5 2 1 3 6 4 5 CAHIERS DE LA CRM No 6 bis · 1 2 1 3 6 4 5 2 1 3 6 4 5 Exercice 3 On utilise le graphe qui indique les cases atteignables depuis une case courante. Les mouvements sont donc (par exemple) : c3-b1, a3-c2, a1-b3, c1-a2, b1-a3, c2-a1, b3-c1, a2-c3, c3-b1, a3-c2, a1-b3, c1-a2, b1-a3, c2-a1, b3-c1, a2-c3 Exercice 4 Comme Holmes, dessinons un graphe avec les sommets A, B, C, E, F, G et H. Dans ce graphe, on relie deux sommets i et j si les suspectes i et j se sont rencontrées au château. Pour découvrir laquelle des 7 femmes est venue plus d’une fois au château, il faut recher- cher dans le graphe des cycles reliant quatre sommets, sans diagonale. En effet, un tel carré ijkl sans diagonale indique que l’une des quatre suspectes est nécessairement venue plus d’une fois au château. Pour s’en convaincre, on peut faire le petit schéma temporel ci-dessous : On voit que i a dû venir deux fois au château pour qu’un cycle sans diagonale apparaisse dans le graphe. Le seul sommet commun à ces trois cycles est le sommet A. C’est donc Ann la coupable. 2 · No 6 bis CAHIERS DE LA CRM Exercice 5 Construisons un graphe dont les sommets représentent les six personnes ; deux sommets sont reliés par une arête noire lorsque les personnes se connaissent et rouge dans le cas contraire. Il s’agit de prouver que ce graphe contient une clique K3 dont les arêtes sont de même couleur. Si l’on ne tient pas compte de la couleur des arêtes, on obtient le graphe complet K6. De chaque sommet partent cinq arêtes, et au moins trois d’entre elles sont de même couleur (noire ou rouge). Considérons la clique K4 composée des sommets 1, 2, 3 et 4. Supposons, par exemple, que les arêtes (1, 2), (1, 3) et (1, 4) soient grises. 2 1 3 6 4 5 Considérons alors la clique K3 composée des sommets 2, 3, 4. Si toutes ces arêtes sont rouges, c’est terminé : on a trois personnes qui ne se connaissent pas. Si une de ces arêtes est grise, c’est aussi terminé : on a trois personnes qui se connaissent. Par contre, dans un K5, on peut trouver deux graphes partiels complémentaires sans K3. On le voit sur les deux graphes partiels ci-dessous, dont la "superposition" donne le graphe complet K5 : 1 2 5 3 4 "Se connaissent" 1 2 5 3 4 "Ne se connaissent pas" Exercice 6 Soit G = (V,E) un graphe simple. Quand on calcule la somme des degrés des sommets, chaque arête (x,y) de E est comptée deux fois, une première fois pour d(x) et une seconde fois pour d(y). Donc, cette somme est ﬁnalement égale à deux fois le nombre d’arêtes. Remarque Le lemme des poignées de mains reste valable pour les multigraphes avec boucles en conve- nant qu’une boucle contribue pour 2 dans le calcul du degré d’un sommet. Exercice 7 Notons P l’ensemble des sommets de degré pair et I l’ensemble des sommets de degré impair d’un graphe simple G = (V,E). P et I forment une partition de V . D’après le lemme des poignées de mains, on a : ∑ v∈V d(v) = 2·|E| = ∑ v∈P d(v)+∑ v∈I d(v) CAHIERS DE LA CRM No 6 bis · 3 Or 2 · |E| et ∑v∈P d(v) sont des entiers pairs. ∑v∈I d(v) est également pair, puisque c’est la différence de deux entiers pairs. Or, chaque terme de la somme ∑v∈I d(v) est impair. Elle ne peut donc être paire que si le nombre de termes est pair. On a ainsi montré que le cardinal de I est un entier pair. Exercice 8 Si tout le monde a au moins un ami dans l’assemblée, cela signiﬁe que tous les degrés des sommets sont compris entre 1 et n−1. Comme il y a n sommets, par le principe des tiroirs, il est certain qu’au moins deux ont le même degré, donc que deux personnes ont le même nombre d’amis. Si une personne n’a aucun ami, le degré du sommet correspondant est 0. Les degrés des n−1 autres sommets sont compris entre 1 et n−2. Même conclusion que dans le premier cas. Si plusieurs personnes n’ont pas d’amis, alors elles ont le même nombre d’amis, en l’oc- currence 0 ! Exercice 9 Considérons le graphe simple dont les sommets représentent les 15 ordinateurs ; les arêtes représentent les liaisons entre ces ordinateurs. Si chaque appareil est relié à exactement 3 ordinateurs du réseau, les sommets du graphe sont tous de degré impair. D’après le résultat établi dans l’exercice 7, un tel graphe doit posséder un nombre pair de sommets, le réseau est donc impossible. Exercice 10 La ﬁgure ci-dessous montre deux graphes 3-réguliers (on dit aussi cubiques), ayant res- pectivement 4 et 6 sommets. En effet, on constate aisément qu’il n’existe pas de graphes cubiques ayant un nombre impair de sommets : le nombre d’arêtes d’un graphe cubique à n sommets est 3n 2 , qui n’est entier que lorsque n est pair. 1 2 3 4 1 2 3 4 5 6 Exercice 11 Les suites (3, 3, 2, 1, 1), (3, 3, 2, 2) et (4, 2, 1, 1, 1, 1) sont graphiques, comme le montrent les graphes ci-dessous : A B C D E A B C D A B C D E F 4 · No 6 bis CAHIERS DE LA CRM Les graphes distincts ci-dessous correspondent tous deux à la suite (3, 2, 2, 2, 1) : A B C D E A B C D E Exercice 12 Un problème survient avec les multigraphes, car plusieurs arêtes peuvent relier deux mêmes sommets. Exercice 13 Les graphes complets. Exercice 14 Soit G = (V,E) un graphe. On appellera coloriage d’un graphe G à k couleurs toute ap- plication φ de V dans {1, ... , k}. On dira qu’un coloriage φ est propre si deux sommets voisins n’ont pas la même couleur. Soit G un graphe biparti et φ un coloriage à 2 couleurs de G. Si (x0,...,xn) est une chaîne, on a pour i ∈{0,...,n −1}, φ(xi) ̸= φ(xi+1), d’où φ(x2k) = φ(x0) et φ(x2k+1) = φ(x1). Maintenant, si cette chaîne est un cycle, on a x0 = xn, d’où φ(x0) = φ(xn), ce qui implique que n est pair. G ne possède donc pas de cycle de longueur impaire. Soit maintenant G = (V,E) un graphe ne possédant pas de cycle de longueur impaire. On doit construire un coloriage propre de G. Comme les composantes connexes ne commu- niquent pas entre elles, on peut se ramener au cas où G est connexe : il sufﬁra ensuite de recoller les applications. Soit x0 un sommet quelconque de V . Pour x ∈V , on note l(x) la longueur minimale d’un chemin reliant x0 à x. On pose alors φ(x) = 1 si l(x) est pair, φ(x) = 2 sinon. Soit {x,y} ∈E : il est facile de voir que |l(x) −l(y)| ≤1. Si on avait l(x) = l(y), on pourrait construire un cycle de longueur 2l(x) + 1 contenant le point x0 et l’arête {x,y}. Ceci est contraire à l’hypothèse selon laquelle le graphe ne contient pas de cycle de longueur impaire. On a donc |l(x)−l(y)| = 1, donc l(x) et l(y) ne sont pas de même parité, ce qui implique φ(x) ̸= φ(y). Le coloriage est donc bien propre. Exercice 15 Tous les cycles sont pairs. On peut le dessiner ainsi : 5 2 1 3 4 7 8 6 CAHIERS DE LA CRM No 6 bis · 5 Exercice 16 Soit V = {v1,...,vn} et E = {e1,...,em}. Construisons la suite de graphes Gi = (V,Ei) avec E0 := ⊘et Ei := Ei−1 ∪{ei} pour i uploads/s3/ corrige-s 2 .pdf