Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Exercice n°6
...

Déterminer le degré de chacun des
sommets du graphe suivant :

Exercice n°2
...

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
...

Exercice n°3
...


0

1
On considère la matrice A =  1

0
1


1
0
1
1
1

1
1
0
1
0

0
1
1
0
0

1

1
0

0

0

Les graphes ci-dessous peuvent-ils être associés à A ?

Exercice n°4
...

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
...
Dessiner un graphe dont une matrice serait :
(plusieurs solutions sont évidement possibles)

Exercice n°5
...

Transformer ce graphe en lui rajoutant un
nombre minimal d’arêtes pour qu’il soit connexe
...

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
...
com

Exercice n°10
...

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
...

b) Calculez M 2 et M 3
c) Retrouvez alors le résultat de la question 2)
Exercice n°15
...

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
...

Exercice n°12
...

Considérons le graphe G ci-contre :
Combien y-a-t-il de chaînes de longueur 4
entre A et B ? B et A ? B et B ?

C

A
Exercice n°14
...
Ses temps
de parcours en minutes entre deux bâtiments sont les suivants :
AB : 16 minutes ; AG = 12 minutes ; BC = 8 minutes ; BE : 12 minutes;
BG : 8 minutes ; CD : 7 minutes; CE = 4 minutes ; CG : 10 minutes ;
DE : 2 minutes ; EF : 8 minutes ; EG : 15 minutes ; FG : 8 minutes
...

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
...


Page 2/12

jgcuaz@hotmail
...

3) Tous les matins, l’agent de sécurité part du bâtiment A et se rend au bâtiment D
...

F

Exercice n°17
...

Un guide touristique classe chaque année les hôtels d’une certaine région en deux
catégories selon la qualité de leurs prestations
...
On constate que, chaque année,
5% des hôtels de la catégorie A sont relégués dans la catégorie B, alors que 20%
des hôtels de la catégorie B sont promus dans la catégorie A
...

2) écrire la matrice de transition associée à ce graphe en respectant l’ordre
alphabétique
...
Calculer l’état de l’année 2003, puis l’état de l’année 2004
...


4

C

1) Existe-t-il un cycle eulérien ? une chaîne eulérienne ? Si oui indiquez-en un(e)
2) Donner une plus courte chaîne allant de A à I
...

Au 1er janvier 2000, la population d’une ville se répartit également entre locataires
et propriétaires
...

1) On désigne par pn la probabilité qu’un habitant de la ville choisi au hasard, soit
propriétaire au 1er janvier de l’année 2000+n (n entier supérieur ou égal à 0), et par
ln, la probabilité qu’il soit locataire
...

a) Représenter la situation à l’aide d’un graphe probabiliste , puis donner sa matrice
de transition M
b) Calculer l’état probabiliste P1
...
Que peut-on en conclure pour la population
de cette ville ?
2) À l’aide de la relation Pn +1 = Pn × M , démontrer que, pour tout entier naturel n,

pn +1 = 0, 7 pn + 0, 2
3) On considère la suite (un) définie, pour tout entier naturel n, par un = pn −

2
3

Exercices et problèmes de synthèse
Exercice n°20
...

2) a) Ce graphe est-il complet ? connexe ?
b) Quel est le degré de chaque sommet ? Déduisez-en le nombre d’arêtes ?
3) a) Quelle est la distance entre les sommets 1 et 5 ?
b) Quel est le diamètre du graphe ?
4) a) Est-il possible de partir d’un pays et d’y revenir après avoir franchi chaque
frontière une fois et une seule ?
b) est-il possible de partir d’un pays, de franchir chaque frontière une fois et une
seule et de terminer en un autre pays ?
5) Quel est le nombre maximum de pays sans frontière commune ? Précisez de
quels pays il s’agit
6) Colorez les huit pays avec un nombre minimum de couleurs de telle façon que
deux pays adjacents portent deux couleurs différentes

a) Démontrer que la suite (un) est une suite géométrique de raison 0,7
...
com

Exercice n°21
...

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
:

b) On donne

Combien y a-t-il de chemins de longueur 5 permettant de se rendre du sommet D
au sommet B? Les donner tous
...
Quel
est ce cycle ? En est-il de même pour le sommet B?

a) On désire peindre les bancs de façon que deux bancs reliés par une allée soient
toujours de couleurs différentes
...
Déterminer ce nombre
...
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
...
Le graphe G’ ci-dessous modélise cette nouvelle situation :

a) Donner la matrice M associée au graphe G’
...


Exercice n°22
...

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)
...

Les arêtes du graphe Γ ci-dessous indiquent quels sont les musiciens qui refusent
de jouer entre eux
...

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 χ (Γ )
...

5) Combien de parties l'organisateur du concert doit-il prévoir ?
Proposer une répartition des musiciens pour chacune de ces parties
...
com

Exercice n°23
...

Afin de promouvoir celui-ci, chacun organise une campagne de publicité
...

Chaque semaine, il interroge les mêmes personnes qui toutes se prononcent en
faveur de l’un de ces deux produits
...
Les arguments publicitaires font évoluer cette répartition :
10% des personnes préférant Aurore et 15 % des personnes préférant Boréale
changent d’avis d’une semaine sur l’autre
...

Pour tout entier naturel n, l’état probabiliste de la semaine n est défini par la
matrice ligne Pn = ( an bn ) , où an désigne la probabilité qu’une personne
interrogée au hasard préfère Aurore la semaine n et bn la probabilité que cette
personne préfère Boréale la semaine n
...
Déterminer la matrice ligne P0 de l’état probabiliste initial
...
Représenter la situation par un graphe probabiliste de sommets A et B, A pour
Aurore et B pour Boréale
...
a
...

b
...

4
...
Exprimer, pour tout entier naturel n, Pn en fonction de P0 et de n
...
En déduire la matrice ligne P3
...

5
...

a
...

b
...


Page 5/12

jgcuaz@hotmail
...
Il
n’est pas connexe car il n’existe pas de chaîne reliant 3 et 4
...

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
Degré
4
4
4
4
4
4
La somme des degrés étant égale au double du nombre d’arêtes, celui-ci vaut 12

Exercice n°5
1)

Exercice n°3
a) Si le graphe simple contient 4 sommets, chacun de ceux-ci est de degré au
maximum égal à 3, d’où une somme totale des degrés égale au plus à 12
...

b) Si le graphe simple contient 5 sommets, chacun de ceux-ci est de degré au
maximum égal à 4, d’où une somme totale des degrés égale au plus à 20
...

b) Si le graphe simple contient 10 sommets, chacun de ceux-ci est de degré au
maximum égal à 9, d’où une somme totale des degrés égale au plus à 90
...

Exercice n°4

2) Il faut procéder à une coloration du graphe
Le sommet de plus fort degré est F ou D, de degré 5
...
Le nombre chromatique χ
vérifie donc 4 ≤ χ ≤ 5 + 1 , c’est-à-dire 4 ≤ χ ≤ 6
Classons les sommets dans l’ordre décroissant de leur degré et appliquons
l’algorithme de coloration de Welch et Powell
Degré
Sommet
Couleur
5
D
Couleur 1
5
F
Couleur 2
4
B
Couleur 3
3
CH
Couleur 4
3
L
Couleur 3
2
I
Couleur 1
2
NL
Couleur 2
Exercice n°6
Graphe

Matrice

0

1
0

0
0


1)

Page 6/12

0

0
1

0

0 1 0 0

1
0
1
1

0
1
0
1

0
1
1
0

jgcuaz@hotmail
...
Pour le premier graphe, c’est impossible, tous les sommets étant
de degré impairs
...

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
...

Le deuxième ne possède pas de sommet de degré égal à 4 (« 2 »)

Pour la deuxième situation, il est nécessaire de crére un 6ème sommet nommé
« extérieur » (E)

Exercice n°8
Un graphe possible est :

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

Il existe maintenant quatre sommets de degré impairs (1,2,4 et E) , les autres étant
de degré pair, il est impossible de trouver une chaîne eulérienne associée à ce
graphe
...

Or ceci n’est possible que si et seulement si le nombre de sommets de degré impair
est égal à 0 (on aura affaire à un cycle eulérien, donc le retour se fera sur le sommet

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
...

b) il n’existe pas de chaîne eulérienne partant de C et en terminant à D
c) A-D-C-E-B-C-A est un exemple
...
com

Exercice n°13
En numérotant 1,2,3 les sommets A,B,C, La matrice associée à ce graphe est

0 1 1


A =  1 0 1  (attention, le graphe n’étant pas orienté, la matrice n’est pas symétrique)
0 1 0


 2 3 3


On calcule A =  1 4 3 
 2 1 2


4
La matrice A nous permet d’affirmer qu’il existe :
4

Exercice n°14
1) Les sommets du graphes étant les villes, et les arêtes étant les liaisons, un graphe
représentant la situation est :

Il existe au moins un vol de chaque ville Vi vers chaque ville V j , i ≠ j ,
comportant au plus deux escales, car le diamètre du graphe est égal à 3

c) On calcule :

1
0
0
1

0
1
0
0

1 0
 
0 1
+
1 0
 
 
0 0

1
0
2
0

1
0
0
1

0 1
 
1 0
+
1 0
 
 
0 1

0
2
1
0

1
0
2
0

1

1
0


1

Cette dernière matrice ne comportant pas de 0, et ne comportant que des entiers
inférieurs ou égaux à 3, il existe toujours une chaine de longueur au plus égale à 3
entre deux aéroports, c’est-à-dire un voyage comportant au plus deux escales
...


- 3 chaînes de longueur 4 entre A et B
- 1 chaînes de longueur 4 entre B et A
- 4 chaînes de longueur 4 entre B et B

0

0
3) a) La matrice M associée à ce graphe est M = 
1

0

0 1 1 0
1 0



2
 1 0 0 1  et M 3 =  0 2
b) On calcule M =
0 2 0 1
0 1


0 0 1 0

1 0




0

0
2
3
M +M +M =
1

0

1 2 2 2 


1 2 1 2 
=
1 3 2 2 

1 1 1 1 




1 0 1

0 1 0
0 0 1


1 0 0
1 1

0 1
2 0


0 1

Exercice n°15
Le premier graphe a pour diamètre 2
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
...
Un exemple de trajet est EGCBECDEFGBAG
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
de degré impair
...
com

Exercice n°17
1) Les sommets D et F sont de degré impair, et tous les autres de degré pair
...

Une chaîne eulérienne est, par exemple, DBCABFDEGHIJEF
2) On détermine le temps minimum de parcours grâce à l’algorithme de Dijkstra
A

B

C

0

D

E

F

 0, 9 0,1 
P = P0 M = ( 0,5 0, 5 ) 
1
 = ( 0,5 × 0,9 + 0,5 × 0, 2 0,5 × 0,1 + 0, 5 × 0,8 )
 0, 2 0,8 
= ( 0, 55 0, 45 )

G

H

I

6+1
=7(B)
7+4
=11(F)
9+4
=13(D)

J

11+6
=17(E)
16+3
=19(J)

On trouve pour chemin minimum le chemin ABFEJI, de poids 19
Exercice n°18
1) a) Si on note P la probabilité d’être propriétaire, et L celle d’être locataire,
l’énoncé fournit les indications p p ( P ) = 0,9 , p p ( L ) = 0,1 , pL ( P ) = 0, 2 et

pL ( L ) = 0,8

la situation se traduit par le graphe probabiliste :

de

ce

graphe

vérifie

x + y =1

0, 2 2

 x = 0, 3 = 3
−0,1x + 0, 2 (1 − x ) = 0
−0,1x + 0, 2 y
0,3 x = 0, 2


⇔
⇔
⇔

 y = 1− x
x + y = 1
 y = 1− x

 y = 1− 2 = 1

3 3

2 1
L’état stable du graphe est donc 

...

3
2) À l’aide de la relation Pn +1 = Pn × M , on écrit :

11+5 J(16)
=16(E)
I(19)

stable

y)

c)

D(9)
E(11)

L’état

(x

Sommet
choisi
C(4)
B(6)

F(7)

0+6
0+4
=6(A) =4(A)
4+4
=8(B)

7+2
=9(F)

b) On calcule

et

 0,9 0,1 
 x = 0,9 x + 0, 2 y
y)
⇔
 0, 2 0,8 
 y = 0,1x + 0,8 y
En utilisant la relation x + y = 1 , le système devient donc

(x

y) = ( x

 pn +1 = 0,9 pn + 0, 2qn
 0,9 0,1 
qn ) 
⇔
 0, 2 0,8 
qn +1 = 0,1 pn + 0,8qn
En utilisant la relation pn + qn = 1 , on déduit que pn +1 = 0,9 pn + 0, 2 (1 − pn )

( pn +1

qn +1 ) = ( pn

⇔ pn +1 = 0, 7 pn + 0, 2
7 

 pn − 15 
3) Pour tout entier n, on a un +1 = 0, 7 pn + 0, 2 − = 0, 7 pn − = 0, 7
7 

3
15

10 
C’est-à-dire un +1 = 0, 7un
...
com

b)

Ainsi,

u n = pn −

pour

tout

entier

n,

 1
un =  −  × 0, 7 n
 6

,

et

puisque

2
2
1
2
n
⇔ pn = un + , on en déduit que pn = − × ( 0,7 ) +
6
3
3
3

c) Puisque 0 < 0, 7 < 1 , lim ( 0,7 ) = 0 et par suite lim pn =
n

n →+∞

n→+∞

= ( 0,575 0, 425 ) ≠ ( 0,5 0,5)

2
3

On retrouve le résultat de la question 1) c)
Exercice n°19
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 , pA ( B ) = 0,05 , pB ( A ) = 0, 2 et pB ( B ) = 0,8
la situation se traduit par le graphe probabiliste :

 0,95 0, 05 

 0, 2 0,8 

2) La matrice de transition de ce graphe est M = 
3) L’état de l’année 2003 sera égal à :

 0, 95 0, 05 
0, 75 ) 
 = ( 0, 25 × 0,95 + 0, 2 × 0, 75 0, 25 × 0, 05 + 0, 75 × 0,8 )
 0, 2 0,8 
= ( 0, 3875 0, 6125 )

( 0, 25

 0,95 0, 05 
0,5) 

 0, 2 0,8 
= ( 0,5 × 0,95 + 0,5 × 0, 2 0,5 × 0, 05 + 0,5 × 0,8 )

( 0,5

Exercices et problèmes de synthèse
Exercice n°20
1) Une représentation possible peut être :

2) a) Ce graphe n’est pas complet (2 et 6 ne sont pas adjacents) mais est connexe
...
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
cycle 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
...

5) On doit construire un nouveau graphe ou deux pays seront adjacents s’ils n’ont
pas de frontière commune

L’état de l’année 2004 sera égal à :

 0, 95 0, 05 
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 )

( 0,3875

4) L’état = ( 0,5 0,5 ) n’est pas stable car

Le plus grand sous-graphe complet de ce graphe a pour ordre 3
Le nombre maximum de pays sans frontière commune est donc égal à 3
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 10/12

jgcuaz@hotmail
...
Ce
chemin est donc l’unique cycle contenant le sommet A, car tout cycle peut être
considéré dans n’importe quel ordre
...

En revanche, il existe 5 cycles de longueur 5 contenant le sommet B
...

Puisque le sous-graphe BCD est complet, on aura χ ≥ 3 et puisque le degré
maximum est égal à 3 (sommets B et D), on aura χ ≤ 3 + 1 , c’est-à-dire, au final,
3≤ χ ≤ 4
...
Comme il est d’ordre 4, on déduit que

χ (Γ ) ≥ 4

3) Le sommet de plus haut degré de Γ est F, de degré 6
...
com

Exercice n°23
1
...


La matrice ligne P0 de l’état probabiliste initial est donc P0 = ( 0, 2 0,8 )
2
...
L’arête reliant A à B dans le sens
A->B sera pondérée par la probabilité qu’une personne préférant Aurore une
semaine donnée, ait changé pour Boréale la semaine suivante, soit 0,1
...
a
...
On a :
 0,9 0,1 
P = P0 M = ( 0, 2 0,8 ) 

1
 0,15 0,85 

5
...
L’état stable P=(a b) est solution de l’équation matricielle
 0,9 0,1 
P = PM ⇔ ( a b ) = ( a b ) 

...
On peut donc estimer qu’à terme, 60% de la population sera favorable au parfum
Aurore, qui sera donc préféré au parfum Boréale

= ( 0, 2 × 0,9 + 0,8 × 0,15 0, 2 × 0,1 + 0,8 × 0,85 )
= ( 0,3 0,7 )

4
...
Pour tout entier naturel n, Pn = P0 M n
3

 0,9 0,1 
b
...


Page 12/12

jgcuaz@hotmail

---