Cours et exercices de mathématiques M. CUAZ, [Link]

fr

GRAPHES Exercice n°6.

Exercice n°1. Ecrivez la matrice associé à chaque graphe :
Déterminer le degré de chacun des
sommets du graphe suivant :

Exercice n°2.
Trois pays envoient chacun à une conférence deux espions ; chaque espion doit Exercice n°7.
espionner tous les espions des autres pays (mais pas son propre collègue!). 0 1 1 0 1
1) Représentez cette situation par un graphe d'ordre 6 dans lequel chaque arête  
reliant i et j signifie que i espionne j que et j espionne i. 1 0 1 1 1
2) Ce graphe est-il complet ? est-il connexe ? On considère la matrice A =  1 1 0 1 0
 
3) Quel est le degré de chaque sommet ? Déduisez-en le nombre d'arêtes. 0 1 1 0 0
1 1 0 0 0 
Exercice n°3. Peut-on construire un graphe simple (aucune arête n’est une bouvle 
et il y a au plus une arête entre deux sommets) ayant : Les graphes ci-dessous peuvent-ils être associés à A ?
a) 4 sommets et 7 arêtes b) 5 sommets et 11 arêtes c) 10 sommets et 46 arêtes
Exercice n°4. Etant donné un groupe de dix personnes, le tableau suivant indique
les paires de personnes qui ont une relation d'amitié.
i 1 2 3 4 5 6 7 8 9 10
Amis de i 3,6,7 6,8 1,6,7 5,10 4,10 1,2,3,7 1,3,6 2 4,5

1) Représentez cette situation par un graphe d'ordre 10 dans lequel une arête entre
les sommets i et j signifie qu'il y a une relation d'amitié entre i et j. Exercice n°8. Dessiner un graphe dont une matrice serait : 0 0 0 0 0
2) Ce graphe est-il complet ? connexe ?  
3) Si l'adage "les amis de nos amis sont nos amis" était vérifié, que pourrait-on en
(plusieurs solutions sont évidement possibles) 0 0 1 0 2
conclure sur la structure du graphe ? 0 1 0 1 0
 
0 0 1 0 0
Exercice n°5. Sur la carte suivante sont désigné 7 pays européens : 0
 2 0 0 0 
Exercice n°9.
Transformer ce graphe en lui rajoutant un
nombre minimal d’arêtes pour qu’il soit connexe.

1) Représentez cette situation par un graphe d'ordre 7 dans lequel l'existence d'une
frontière entre deux pays se traduira par une arête.
2) Combien de couleurs faut-il, au minimum, pour colorier cette graphe, de sorte
que deux pays frontaliers ne soient pas affectés de la même couleur.

Page 1/10
Cours et exercices de mathématiques M. CUAZ, [Link]
Exercice n°10. Est-il possible de tracer les figures suivantes sans lever le crayon (et encore très réduit : il existe seulement un vol direct de V1 vers V2 et vers V4 , de
sans passer deux fois sur le même trait!…)? Pourquoi ?
V2 vers V3 , de V3 vers V1 et vers V4 , de V4 vers V2
1) Représenter les données par un graphe convenable.
2) Vérifier qu’il existe au moins un vol de chaque ville Vi vers chaque ville V j ,
i ≠ j , comportant au plus deux escales.
3) a) Ecrivez la matrice M associée à ce graphe.
b) Calculez M 2 et M 3
c) Retrouvez alors le résultat de la question 2)
Exercice n°15. Quels sont les diamètres des graphes ci-dessous :
Exercice n°11.
Est-il possible de se promener dans chacune de ces maisons en passant une et une
seule fois par chacune de ses ouvertures ?

Exercice n°16. Le graphe ci-dessous indique, sans respecter d’échelle, les parcours
possibles entre les sept bâtiments d’une entreprise importante.

Exercice n°12.
Le chasse neige doit déblayer les 5 routes qui relient 5
villages A, B, C, D et E
Peut on trouver des itinéraires qui permettent de
parcourir une et une seule fois chaque route ?
a) en partant de E et en terminant par E
b) en partant de C et en terminant à D
c) en partant de A et en terminant à A B

Exercice n°13.
Considérons le graphe G ci-contre :
Combien y-a-t-il de chaînes de longueur 4 Un agent de sécurité effectue régulièrement des rondes de surveillance. Ses temps
de parcours en minutes entre deux bâtiments sont les suivants :
entre A et B ? B et A ? B et B ? C AB : 16 minutes ; AG = 12 minutes ; BC = 8 minutes ; BE : 12 minutes;
A BG : 8 minutes ; CD : 7 minutes; CE = 4 minutes ; CG : 10 minutes ;
Exercice n°14. DE : 2 minutes ; EF : 8 minutes ; EG : 15 minutes ; FG : 8 minutes.
Sur chaque arête, les temps de parcours sont indépendants du sens du parcours.
On considère quatre villes V1 , V2 , V3 , V4 dans un pays où le traffic aérien est 1) Montrer qu’il est possible que l’agent de sécurité passe une fois et une seule par
tous les chemins de cette usine. Donner un exemple de trajet.

Page 2/10
Cours et exercices de mathématiques M. CUAZ, [Link]
2) L’agent de sécurité peut-il revenir à son point de départ après avoir parcouru une Exercice n°19.
fois et une seule tous les chemins ? Justifier la réponse. Un guide touristique classe chaque année les hôtels d’une certaine région en deux
3) Tous les matins, l’agent de sécurité part du bâtiment A et se rend au bâtiment D. catégories selon la qualité de leurs prestations. Les plus confortables sont classés
En utilisant un algorithme que l’on explicitera, déterminer le chemin qu’il doit dans la catégorie A, les autres dans la catégorie B. On constate que, chaque année,
suivre pour que son temps de parcours soit le plus court possible, et donner ce 5% des hôtels de la catégorie A sont relégués dans la catégorie B, alors que 20%
temps de parcours. G 2 H des hôtels de la catégorie B sont promus dans la catégorie A.
F
4 6
1) Dessiner un graphe décrivant cette situation.
Exercice n°17. On considère le graphe ci-dessous : E 1
2) écrire la matrice de transition associée à ce graphe en respectant l’ordre
1
2 I alphabétique.
B 4 5
3 3) En 2002, le classement était tel que le quart des hôtels étaient classés dans la
6 3 catégorie A. Calculer l’état de l’année 2003, puis l’état de l’année 2004.
D J
A 4 4) L’état (0,5 ; 0,5) est-il stable ? Justifier cette réponse.
4
C Exercices et problèmes de synthèse
1) Existe-t-il un cycle eulérien ? une chaîne eulérienne ? Si oui indiquez-en un(e) Exercice n°20.
2) Donner une plus courte chaîne allant de A à I. Huit pays sont représentés ci-dessous avec leur frontière (deux pays dont les
frontières n’ont qu’un nombre fini de points ne sont pas considérés comme voisins)
Exercice n°18.
Au 1er janvier 2000, la population d’une ville se répartit également entre locataires
et propriétaires. La population globale ne varie pas mais, chaque année, pour
raisons familiales ou professionnelles, 10% des propriétaires deviennent locataires
tandis que 20% des locataires deviennent propriétaires.
1) On désigne par pn la probabilité qu’un habitant de la ville choisi au hasard, soit 1) Représentez cette situation par un graphe d’ordre 8 dont les sommets sont les
propriétaire au 1er janvier de l’année 2000+n (n entier supérieur ou égal à 0), et par pays et les arêtes les frontières.
ln, la probabilité qu’il soit locataire. La matrice P0 = (0,5 0,5) traduit l’état 2) a) Ce graphe est-il complet ? connexe ?
probabiliste initial et la matrice Pn = ( pn ln ) (avec, pour tout n ∈ ` , pn + ln = 1 ) b) Quel est le degré de chaque sommet ? Déduisez-en le nombre d’arêtes ?
l’état probabiliste après n années. 3) a) Quelle est la distance entre les sommets 1 et 5 ?
a) Représenter la situation à l’aide d’un graphe probabiliste , puis donner sa matrice b) Quel est le diamèter du graphe ?
de transition M 4) a) Est-il possible de partir d’un pays et d’y revenir après avoir franchi chaque
b) Calculer l’état probabiliste P1. frontière une fois et une seule ?
c) Déterminer l’état stable du graphe. Que peut-on en conclure pour la population b) est-il possible de partir d’un pays, de franchir chaque frontière une fois et une
de cette ville ? seule et de terminer en un autre pays ?
2) À l’aide de la relation Pn +1 = Pn × M , démontrer que, pour tout entier naturel n, 5) Quel est le nombre maximum de pays sans frontière commune ? Précisez de
quels pays il s’agit
pn +1 = 0, 7 pn + 0, 2 6) Colorez les huit pays avec un nombre minimum de couleurs de telle façon que
2 deux pays adjacents portent deux couleurs différentes
3) On considère la suite (un) définie, pour tout entier naturel n, par un = pn −
3
a) Démontrer que la suite (un) est une suite géométrique de raison 0,7.
1 2
b) Exprimer un en fonction de n et démontrer que pn = − × ( 0,7 ) +
n

6 3
c) Calculer la limite de la suite (pn) et retrouver le résultat de la question 1) c)

Page 3/10
Cours et exercices de mathématiques M. CUAZ, [Link]
Exercice n°21. b) On donne
1) Dans un parc, il y a cinq bancs reliés entre eux par des allées.
On modélise les bancs par les sommets A, B, C, D, E et les allées par les arêtes du
graphe G ci-dessous :
Combien y a-t-il de chemins de longueur 5 permettant de se rendre du sommet D
au sommet B? Les donner tous.
c) Montrer qu’il existe un seul cycle de longueur 5 passant par le sommet A. Quel
est ce cycle ? En est-il de même pour le sommet B?
Exercice n°22.
Un concert de solidarité est organisé dans une grande salle de spectacle.
A ce concert sont conviés sept artistes de renommée internationale : Luther
Allunison (A), John Biaise (B), Phil Colline (C), Bob Ditlâne (D), Jimi Endisque
(E), Robert Fripe (F) et Rory Garaguerre (G).
a) On désire peindre les bancs de façon que deux bancs reliés par une allée soient Les différents musiciens invités refusant de jouer avec certains autres,
toujours de couleurs différentes. Donner un encadrement du nombre minimal de l'organisateur du concert doit prévoir plusieurs parties de spectacle.
couleurs nécessaires et justifier. Déterminer ce nombre. Les arêtes du graphe Γ ci-dessous indiquent quels sont les musiciens qui refusent
b) Est-il possible de parcourir toutes les allées de ce parc sans passer deux fois par de jouer entre eux.
la même allée ?
2) Une exposition est organisée dans le parc. La fréquentation devenant trop
importante, on décide d’instaurer un plan de circulation : certaines allées
deviennent à sens unique, d’autres restent à double sens. Par exemple la circulation
dans l’allée située entre les bancs B et C pourra se faire de B vers C et de C vers B,
alors que la circulation dans l’allée située entre les bancs A et B ne pourra se faire
que de A vers B. Le graphe G’ ci-dessous modélise cette nouvelle situation :

1) Déterminer la matrice associée au graphe Γ (les sommets de Γ étant classés

dans l'ordre alphabétique).
2) Quelle est la nature du sous-graphe de Γ constitué des sommets A, E, F et G ?
Que peut-on en déduire pour le nombre chromatique χ (Γ) du graphe Γ ?
3) Quel est le sommet de plus haut degré de Γ ?
En déduire un encadrement de χ (Γ) .
a) Donner la matrice M associée au graphe G’. (On ordonnera les sommets par 4) Après avoir classé l'ensemble des sommets de Γ par ordre de degré décroissant,
ordre alphabétique). colorier le graphe G figurant en annexe.
5.)Combien de parties l'organisateur du concert doit-il prévoir ?
Proposer une répartition des musiciens pour chacune de ces parties.

Page 4/10
Cours et exercices de mathématiques M. CUAZ, [Link]

GRAPHES - CORRECTION 2) Ce graphe n’est pas complet car, par exemple, 1 et 2 ne sont pas adjacents. Il
Exercice n°1 n’est pas connexe car il n’existe pas de chaîne reliant 3 et 4. En revanche, il admet
Sommet A B C D E F G H I deux sous graphes connexes (1,2,3,6,7,8) (4,5,10) et un point isolé 9
3) Si l'adage "les amis de nos amis sont nos amis" était vérifié la composante
Degré 4 6 4 2 4 4 6 4 2
connexe (1,2,3,6,7,8) serait complète
Exercice n°2
Exercice n°5
Les espions d’un même pays sont notés 1 et 2 , 3 et 4, 5 et 6
1)
1) Graphe
2) Ce graphe n’est pas complet car deux espions d’un même
pays ne s’espionnent pas, donc les sommets correspondants
ne sont pas adjacents.
En revanche ce graphe est connexe car entre tout couple de
points, il existe au moins une chaîne
3) Les sommets sont tous de degré 4 car chaque espion en espionne quatre autres
Autrement dit :
Sommet 1 2 3 4 5 6
2) Il faut procéder à une coloration du graphe
Degré 4 4 4 4 4 4
Le sommet de plus fort degré est F ou D, de degré 5. Le sous-graphe complet
La somme des degrés étant égale au double du nombre d’arêtes, celui-ci vaut 12 d’ordre maximal est d’ordre 3, par exemple B,L,F,D. Le nombre chromatique χ
Exercice n°3 vérifie donc 4 ≤ χ ≤ 5 + 1 , c’est-à-dire 4 ≤ χ ≤ 6
a) Si le graphe simple contient 4 sommets, chacun de ceux-ci est de degré au Classons les sommets dans l’ordre décroissant de leur degré et appliquons
maximum égal à 3, d’où une somme totale des degrés égale au plus à 12. Puisque l’algorithme de coloration de Welch et Powell
cette somme est égale au double du nombre d’arêtes, ce nombre d’arêtes ne peut Degré Sommet Couleur
excéder 6, donc ne peut pas être égal à 7. 5 D Couleur 1
b) Si le graphe simple contient 5 sommets, chacun de ceux-ci est de degré au 5 F Couleur 2
maximum égal à 4, d’où une somme totale des degrés égale au plus à 20. Puisque 4 B Couleur 3
cette somme est égale au double du nombre d’arêtes, ce nombre d’arêtes ne peut 3 CH Couleur 4
excéder 10, donc ne peut pas être égal à 11. 3 L Couleur 3
b) Si le graphe simple contient 10 sommets, chacun de ceux-ci est de degré au 2 I Couleur 1
maximum égal à 9, d’où une somme totale des degrés égale au plus à 90. Puisque
2 NL Couleur 2
cette somme est égale au double du nombre d’arêtes, ce nombre d’arêtes ne peut
excéder 45, donc ne peut pas être égal à 46. Exercice n°6
Graphe Matrice
Exercice n°4
1) 0 1 0 0 0
 
1 0 1 1 0
0 1 0 1 1
 
0 1 1 0 0
0 0 1 0 0 


Page 5/10
Cours et exercices de mathématiques M. CUAZ, [Link]

0 1 0 0 0 0 Exercice n°11
  En numérotant les pièces et en matérialisant les portes par des arêtes, on traduit la
1 0 1 0 0 0 situation par le graphe ci-dessous :
0 1 0 0 0 0
 
0 0 0 0 1 1
0 0 0 0 0 1
 
0 0 0 0 1 0 

Exercice n°7
Le premier graphe peut être associé à la matrice A
pour cette numérotation des points : Se promener dans la maison en passant par chacune des ouvertures revient à
Les deux graphes suivants ne peuvent pas êter associées chercher l’existence d’une chaîne eulérienne
à A car ils ne possèdent pas de sommet de degré égal à 4 Seuls deux sommets étant de degré impairs (1 et 2) , les autres étant de degré pair,
(sommet « 2 ») il est possible de trouver une chaîne eulérienne associée à ce graphe.

Exercice n°8 Pour la deuxième situation, il est nécessaire de crére un 6ème sommet nommé
Un graphe possible est : « extérieur » (E)

Exercice n°9
En rajoutant deux arêtes (en rouge), on peut rendre ce graphe connexe

Il existe maintenant trois sommets de degré impairs (1,2 et E) , les autres étant de
degré pair, il est impossible de trouver une chaîne eulérienne associée à ce graphe.
Exercice n°12
Trouver des itinéraires qui permettent de parcourir une seule fois chaque route
revient à trouver une chaîne eulérienne (voire un cycle) associée à ce graphe.
Tous les sommets étant de degré pair, le théorème d’Euler assurer l’existence d’un
Exercice n°10 cycle eulérien (donc d’une chaîne eulérienne)
Tracer les figures « sans lever » le crayon revient à exhiber une chaine eulérienne. a) E-C-D-A-C-B-E
Or ceci n’est possible que si t seulement si le nombre de sommets de degré impair b) il n’existe pas de chaîne eulérienne partant de C et en terminant à D
est égal à 0 (on aura affaire à un cycle eulérien, donc le retour se fera sur le sommet c) A-D-C-E-B-C-A
de départ) ou à 2. Pour le premier graphe, c’est impossible, tous les sommets étant
de degré impairs. Pour les trois autres graphes, c’est possible.
En ce qui concerne le 3ème graphe, tous les sommets étant de degré pair, on a même
l’existence d’un cycle eulérien.

Page 6/10
Cours et exercices de mathématiques M. CUAZ, [Link]
Exercice n°13 0 1 0 1 0 1 1 0 1 0 1 1
En numérotant 1,2,3 les sommets A,B,C, La matrice associée à ce graphe est      
0 0 1 0 1 0 0 1 0 2 0 1
0 1 1 M +M +M =
2 3
+ +
  1 0 0 1 0 2 0 1 0 1 2 0
A =  1 0 1  (attention, le graphe n’étant pas orienté, la matrice n’est pas symétrique)  0     
0 1 0  1 0 0   0 0 1 0   1 0 0 1 
 
1 2 2 2 
 2 3 3  
 1 2 1 2
  =
On calcule A =  1 4 3 
4
1 3 2 2 
 2 1 2 1 1 1 1 
   
4
La matrice A nous permet d’affirmer qu’il existe : Cette dernière matrice ne comportant pas de 0, et ne comportant que des entiers
- 3 chaînes de longueur 4 entre A et B inférieurs ou égaux à 3, il existe toujours une chaine de longueur au plus égale à 3
- 1 chaînes de longueur 4 entre B et A entre deux aéroports, c’est-à-dire un voyage comportant au plus deux escales. On
- 4 chaînes de longueur 4 entre B et B retrouve le résultat précédent.
Exercice n°14 Exercice n°15
1) Les sommets du graphes étant les villes, et les arêtes étant les liaisons, un graphe Le premier graphe a pour diamètre 2
représentant la situation est : Le deuxième graphe a pour diamètre 3
Le troisième graphe a pour diamètre 4
Le quatrième graphe a pour diamètre 6
Exercice n°16
1) Puisque seuls les sommets E et G sont de degré impairs, ce graphe admet une
chaîne eulérienne. Il est possible que l’agent de sécurité passe une fois et une seule
Il existe au moins un vol de chaque ville Vi vers chaque ville V j , i ≠ j , par tous les chemins de cette usine. Un exemple de trajet est EGCBECDEFGBAG
comportant au plus deux escales, car le diamètre du graphe est égal à 3 2) L’agent de sécurité ne peut pas revenir à son point de départ car le théorème
d’Euler interdit l’existence d’un cycle eulérien, en raison des deux sommets E et G
0 1 0 1
de degré impair.
 
0 0 1 0 3) On détermine le temps minimum de parcours grâce à l’algorithme de Dijkstra :
3) a) La matrice M associée à ce graphe est M = 
1 0 0 1 A B C D E F G Sommet
  choisi
0 1 0 0  0 0+16 +∞ +∞ +∞ +∞ 0+12 G (12)
0 1 1 0 1 0 1 1 =16 (A) =12 (A)
    +∞ 12+8 12+10 +∞ 12+15 12+8 +∞ F (20)
 1 0 0 1 0 2 0 1
b) On calcule M =2
et M = 
3 =20 (G) =22 (G) =27 (G) =20 (G) C(22)
0 2 0 1 0 1 2 0 +∞ 22+7 20+8=28 (F) D(29)
   
0 0 1 0 1 0 0 1  =29 (C) 22+4=26 (C) E(26)
c) On calcule :
+∞ 26+2 D(28)
=28 (E)
On trouve pour chemin minimum le chemin AGCED, de poids 28

Page 7/10
Cours et exercices de mathématiques M. CUAZ, [Link]
Exercice n°17 b) On calcule
1) Les sommets D et F sont de degré impair, et tous les autres de degré pair. On  0,9 0,1 
conclut, grâce au théorème d’Euler, à l’existence d’une chaîne eulérienne, mais pas P1 = P0 M = ( 0,5 0,5 )   = ( 0,5 × 0,9 + 0,5 × 0, 2 0,5 × 0,1 + 0,5 × 0,8 )
à celle d’un cycle eulérien.  0, 2 0,8 
Une chaîne eulérienne est, par exemple, DBCABFDEGHIJEF = ( 0,55 0, 45 )
2) On détermine le temps minimum de parcours grâce à l’algorithme de Dijkstra
A B C D E F G H I J Sommet c) L’état stable (x y) de ce graphe vérifie x + y =1 et
choisi
 0,9 0,1   x = 0,9 x + 0, 2 y
0 0+6 0+4 C(4) (x y) = ( x y) ⇔
=6(A) =4(A) B(6)  0, 2 0,8   y = 0,1x + 0,8 y
4+4
En utilisant la relation x + y = 1 , le système devient donc
=8(B)
6+1 F(7)  0, 2 2
x= =
=7(B) −0,1x + 0, 2 y −0,1x + 0, 2 (1 − x ) = 0 0,3 x = 0, 2 
 0,3 3
7+2 7+4 D(9)  ⇔ ⇔ ⇔
=9(F) =11(F) E(11) x + y = 1  y = 1 − x  y = 1− x  y = 1− 2 = 1
9+4  3 3
=13(D)
11+6 11+5 J(16)  2 1
L’état stable du graphe est donc   . On peut ainsi conclure qu’au bout d’un
=17(E) =16(E)  3 3
16+3 I(19)
=19(J)
2
grand nombre de mois, le nombre de propriétaires tend vers une proportion de ,
3
On trouve pour chemin minimum le chemin ABFEJI, de poids 19 1
tandis que celui des locataires tend vers une proportion de .
Exercice n°18 3
1) a) Si on note P la probabilité d’être propriétaire, et L celle d’être locataire, 2) À l’aide de la relation Pn +1 = Pn × M , on écrit :
l’énoncé fournit les indications p p ( P ) = 0,9 , p p ( L ) = 0,1 , pL ( P ) = 0, 2 et  0,9 0,1   pn +1 = 0,9 pn + 0, 2qn
pL ( L ) = 0,8
( pn+1 qn +1 ) = ( pn
qn )  ⇔
 0, 2 0,8  qn +1 = 0,1 pn + 0,8qn
la situation se traduit par le graphe probabiliste : En utilisant la relation pn + qn = 1 , on déduit que pn +1 = 0,9 pn + 0, 2 (1 − pn )
⇔ pn +1 = 0, 7 pn + 0, 2

2 7  7 
3) Pour tout entier n, on a un +1 = 0, 7 pn + 0, 2 − = 0, 7 pn − = 0, 7  pn − 15 
3 15  7 
 10 
C’est-à-dire un +1 = 0, 7un . La suite (un) est donc une suite géométrique de raison
2 1 2 1
 0,9 0,1  0,7, et de premier terme u0 = p0 − = − =−
La matrice de transition de ce graphe est M =   3 2 3 6
 0, 2 0,8 

Page 8/10
Cours et exercices de mathématiques M. CUAZ, [Link]

 1  0,95 0, 05 
b) Ainsi, pour tout entier n, un =  −  × 0, 7 n , et puisque ( 0,5 0,5 )  
 6  0, 2 0,8 
2 2 1 2 = ( 0,5 × 0,95 + 0,5 × 0, 2 0,5 × 0, 05 + 0,5 × 0,8 )
⇔ pn = un + , on en déduit que pn = − × ( 0,7 ) +
n
un = pn −
3 3 6 3
2 = ( 0,575 0, 425 ) ≠ ( 0,5 0,5 )
c) Puisque 0 < 0, 7 < 1 , lim ( 0,7 ) = 0 et par suite lim pn =
n
n →+∞ n →+∞ 3
Exercices et problèmes de synthèse
On retrouve le résultat de la question 1) c)
Exercice n°20
Exercice n°19 1) Une représentation possible peut être :
1) Si on note A la probabilité pour un hôtel d’être classé dans la catégorie A, et B
celle d’être classée dans la catégorie B, l’énoncé fournit les indications
p A ( A ) = 0,95 , p A ( B ) = 0, 05 , pB ( A ) = 0, 2 et pB ( B ) = 0,8
la situation se traduit par le graphe probabiliste : 2) a) Ce graphe n’est pas complet (2 et 6 ne sont pas adjacents) mais est connexe.
b)
Sommet 1 2 3 4 5 6 7 8
Degré 4 4 4 4 2 3 2 3
La somme des degrés vaut 4+4+4+4+2+3+2+3=26. Il y a donc 13 arêtes
3) a) La distance entre les sommets 1 et 5 vaut 3
b) Ce graphe a pour diamètre 3
4) a) Puisque tous les sommets ne sont pas de degré pair, ce graphe n’admet pas de
cyvle eulérien, donc il n’est pas possible de partir d’un pays et d’y revenir après
avoir franchi chaque frontière une fois et une seule.
 0,95 0, 05  b) Puisque deux sommets exactement sont de degré impair, ce graphe admet une
2) La matrice de transition de ce graphe est M =  
 0, 2 0,8  chaîne eulérienne, donc il est possible de partir d’un pays, de franchir chaque
3) L’état de l’année 2003 sera égal à : frontière une fois et une seule et de terminer en un autre pays.
5) On doit construire un nouveau graphe ou deux pays seront adjacents s’ils n’ont
 0,95 0, 05 
( 0, 25 0, 75 )   = ( 0, 25 × 0,95 + 0, 2 × 0, 75 0, 25 × 0, 05 + 0, 75 × 0,8 ) pas de frontière commune
 0, 2 0,8 
= ( 0,3875 0, 6125 )
L’état de l’année 2004 sera égal à :
 0,95 0, 05 
( 0,3875 0, 6125 )   = ( 0,3875 × 0,95 + 0, 6125 × 0, 2 0,3875 × 0, 05 + 0, 6125 × 0,8 )
 0, 2 0,8 
= ( 0, 490625 0,509375 )
Le plus grand sous-graphe complet de ce graphe a pour ordre 4
4) L’état = ( 0,5 0,5 ) n’est pas stable car Le nombre maximum de pays sans frontière commune est donc égal à 4
6) Le degré maximum étant égal à 4, et le plus grand sous graphe complet étant
d’ordre 4 (1,2,3,8), le nombre chromatique χ du graphe vérifie 4 ≤ χ ≤ 5

Page 9/10
Cours et exercices de mathématiques M. CUAZ, [Link]
On applique l’algorithme de coloration de Welch et Powell on en déduit qu’il existe 5 chemins de longueur 5 permettant de se rendre du
Sommet Degré Couleur sommet D au sommet B (terme à l’intersection de la 4ème ligne et de la 2ème
1 4 Couleur 1 colonne)
2 4 Couleur 2 Ces chemins sont DEDEAB , DEAEAB, DEABCB, DCBDCB, DEABCB
3 4 Couleur 3 c) D’après la matrice, il existe un seul chemin de longueur 5 reliant A à A. Ce
4 4 Couleur 4 chemin est donc l’unique cycle contenant le sommet A, car tout cycle peut être
6 3 Couleur 1 considéré dans n’importe quel ordre. Ce cycle est ABCDEA.
8 3 Couleur 4 En revanche, il existe 5 cycles de longueur 5 contenant le sommet B.
5 2 Couleur 2 Exercice n°22
7 2 Couleur 2
0 0 0 1 1 1 1
On déduit de cette coloration que χ = 4  
0 0 1 0 1 1 0
Exercice n°21 0 1 0 0 1 1 1
1) a) Notons χ le nombre chromatique de ce graphe, c’est-à-dire le nombre  
1) La matrice associée au graphe Γ est M =  1 0 0 0 0 1 0
minimal de couleurs à utiliser pour que deux bancs adjacents ne soient pas de la
même couleur. 1 1 1 0 0 1 1
Puisque le sous-graphe BCD est complet, on aura χ ≥ 3 et puisque le degré  
1 1 1 1 1 0 1
maximum est égal à 3 (sommets B et D), on aura χ ≤ 3 + 1 , c’est-à-dire, au final, 1
 0 1 0 1 1 0 
3≤ χ ≤ 4.
2) Le sous graphe AEFG est complet. Comme il est d’ordre 4, on déduit que
On procède à une coloration grâce à l’algorithme de Welch et Powell : χ (Γ ) ≥ 4
Sommet Degré Couleur
3) Le sommet de plus haut degré de Γ est F, de degré 6. Ainsi χ (Γ) ≤ 6 + 1 , et on
B 3 Couleur 1
D 3 Couleur 2 déduit que 4 ≤ χ (Γ) ≤ 7
A 2 Couleur 2 4) On procède à une coloration grâce à l’algorithme de Welch et Powell :
C 2 Couleur 3 Sommet Degré Couleur
E 2 Couleur 1 F 6 Couleur 1
Ainsi χ = 3 E 5 Couleur 2
b) Le nombre de sommets de degré impair étant exactement égal à deux, il existe G 4 Couleur 3
une chaîne eulérienne, donc il est possible de se promener une seule fois dans A 4 Couleur 4
toutes allées du parc C 4 Couleur 4
0 1 0 0 1 B 3 Couleur 3
  D 2 Couleur 2
0 0 1 1 0 5) L’organisateur doit prévoir 4 parties :
2) a) La matrice M associée au graphe G’ est M = 0 1 0 1 0 Partie 1 : F
  Partie 2 : E,D
0 0 1 0 1
Partie 3 : G,B
1 0 0 1 0 
 Partie 4 : A,C
b) A partir de la matrice

Page 10/10