172665_prof_CH11

7/30/2019 172665_prof_CH11

1/16

Nathan2012TransmathTerm.

ES-L

doit en repartir par une arte nouvelle : le degr de toutsommet intermdiaire doit donc tre pair. Or les degrs de

tous les sommets du graphe sont impairs.

Le thorme dEuler (che-cours 2 , p. 297) permet de

justier rigoureusement limpossibilit dun tel parcours,

que les sommets de dpart et darrive soient distincts ou

non.

Problme3

1. Chemins possibles reliant D et A : D-B-A ; D-C-A ;

D-B-C-A et D-C-B-A.

2. Le plus court chemin entre D et A, cest--dire ici celui

qui minimise la somme dpense en pages, est D-C-A

(dpense : 50).

Problme4

a 1. Somme des degrs : 54, do le nombre dartes :

542

= 27.

2. Pour tout i de 1 10, la somme des termes de la i-ime

ligne de la matrice est gale au degr de Xi.

Le sommet dont le degr est le plus grand tant X3

(de

degr 7), cest la somme des termes de la troisime ligne

(gale 7) qui est la plus grande.

Les sommets dont le degr est le plus petit tant X1

et X10

(de degr 3), cest la somme des termes des premire et

dixime lignes (gale 3) qui est la plus petite.

b 1. ) X2

ait conance X1, X

3et X

5.

) Il y a conance rciproque entre X2 et X5, ainsi quentreX

3et X

5.

) X1

ne ait conance qu lui-mme ; X6

ne ait conance

personne, et personne ne lui ait conance.

Problme1

2. Tout sous-ensemble de magasins pouvant tre simul-

tanment ouverts en nocturne est un sous-ensemble des

points A, B, C, D, E vriant la proprit (Q) suivante :

deux points quelconques de ce sous-ensemble sont relis

par un segment ; la rsolution du problme (P) quivaut

donc la dtermination dun sous-ensemble des points A,

B, C, D, E vriant la proprit (Q) et contenant le plus

possible de ces points.

3. (P1) quivaut il existe un sous-ensemble de quatre

points vriant la proprit (Q) , cest--dire il existedans le schma un quadrilatre dont les diagonales sont

traces (P2).

4. Les cinq magasins ne peuvent pas tre ouverts

simultanment ; le schma ne contenant aucun quadrilatre

(et donc a ortiori aucun quadrilatre dont les diagonales

sont traces), quatre quelconques des cinq magasins ne

peuvent pas tre ouverts simultanment.

Par contre, le schma contient un triangle : le triangle BCE ;

les trois magasins B, C et E peuvent donc tre ouverts

simultanment. Cest la solution du problme pos.

Problme2

2. Lexistence dun itinraire passant une ois et une seule

par chaque pont quivaut lexistence dans le graphe

dun parcours qui, partir dun sommet de dpart ,

emprunte successivement toutes les artes du graphe une

ois et une seule, et sachve au sommet de dpart ou en un

autre sommet.

3. Quel que soit le sommet de dpart, les tentatives pour

obtenir un tel parcours chouent.Lexistence dun tel parcours implique en eet que, chaque

ois que lon arrive en un sommet intermdiaire (autre

que les sommets de dpart et darrive) par une arte, on

rsolution de Problmes(page 294)

11

CHAPitre

1Chapitre 11 Graphes

Graphes

7/30/2019 172665_prof_CH11

2/16


ES-L

2 Chapitre 11 Graphes

2. ) C

L

P

V

A

F

G

Q

G1

) Dans G1, le seul sommet adjacent G est V, et le seul

sommet adjacent Q est P ; on en dduit que les binmes

(V-G) et (P-Q) ont ncessairement partie dune rpartition

en binmes idale.

3. )C

L

A

F

G2

) Rpartition en binmes idale :

5(T-B), (V-G), (P-Q), (C-A), (L-F)6ou 5(T-B), (V-G), (P-Q), (C-F), (L-A)62.

Problme6

1. et 2. Pour tout k: Gkest dordre 2k 1.

3. Chacun de ces graphes est connexe car on peut le

dessiner sans lever le crayon de la euille .

4. ) Nombre de sommets = nombre dartes + 1.

) Pour tout k, dans Gk: le sommet de niveau 1 (la racine

de larbre) est de degr 2, les 2k1 sommets de niveau

maximum son de degr 1, tous les autres sommets (il y en a

2 + 22 + + 2k2, soit 2k1 2) sont de degr 3.

) Par suite, la somme des degrs est :

S = 2 + (2k1 2)3 + 2k1 = 4(2k1 1). Le nombre dartes est

m = (2k 1) 1 (daprs 2. et 4. ), cest--dire m = 2k 2.

On a bien S = 2m.

Problme7

a 1. Deux sommets quelconques sont relis par une

chane extraite de la chane (E-F-D-A-C-B) qui passe

par tous les sommets.

2. Daprs le thorme dEuler, le graphe G, connexe et

ayant exactement deux sommets de degr impair : A et B,

admet une chane eulrienne dextrmits A et B.

b 3. La chane (A-D-B-A-C-B) ne contient pas toutes les

artes du graphe, elle nest donc pas eulrienne.4. On insre la chane erme (D-E-F-D) dans la chane

(A-D-B-A-C-B) pour obtenir la chane eulrienne (A-D-E-

F-D-B-A-C-B).

2. La matrice du graphe est la matrice suivante (non

symtrique) :

1 0 0 0 0 0

1 0 1 0 1 0

0 0 0 0 1 0

0 0 1 1 0 0

0 1 1 1 0 0

0 0 0 0 0 0

2.

c 1. Non.

2. La personne la plus populaire est X3.

3. Matrice (non symtrique) :

0 1 1 0 1

1 0 1 1 0

0 0 0 0 0

0 1 1 0 0

0 0 0 1 0

2.

Problme5

a 2. Somme des degrs S = 24, nombre dartes m = 12 ;

on a bien S = 2 m.

3. Dans une rpartition en binmes idale, les cinq binmes

sont des paires disjointes dlves, constitues dun lve

de X et dun lve de Y ayant des anits ; ces cinq

binmes sont donc reprsents par cinq artes du graphe G

nayant pas dextrmit commune.

b C = 1, L = 2, P = 3, T = 4, V = 5, A = 6, B = 7, F = 8,G = 9, Q = 10.

1. M = 0 0 0 0 0 1 0 1 0 0

0 0 0 0 0 1 0 1 0 0

0 0 0 0 0 1 0 1 0 1

0 0 0 0 0 0 1 0 1 1

0 0 0 0 0 0 0 1 1 0

1 1 1 0 0 0 0 0 0 0

0 0 0 1 0 0 0 0 0 0

1 1 1 0 1 0 0 0 0 0

0 0 0 1 1 0 0 0 0 0

0 0 1 1 0 0 0 0 0 0

2Les deux sous-matrices carres correspondant aux cinq

premires lignes et colonnes et aux cinq dernires lignes et

colonnes sont nulles.

2. Plus gnralement, les sommets dun graphe biparti

peuvent tre rpartis en deux sous-ensembles X et Y, tels

quaucune arte ne relie deux sommets dun mme sous-

ensemble. Si lon numrote de 1 |X| les sommets de X

et de |X| + 1 |X| + |Y| les sommets de Y, alors la sous-

matrice carre de la matrice du graphe orme par les |X|

premires lignes et colonnes, et la sous-matrice orme par

les |Y| dernires lignes et colonnes, sont nulles.

c 1. Le seul sommet adjacent B est T : le binme

(T-B) ait donc ncessairement partie dune rpartition en

binmes idale.

7/30/2019 172665_prof_CH11

3/16


ES-L


parmi les sommets 2, 8, 4, 5, 6 qui soit quidistant de

3 et 7 ; la droite (15) est donc mdiatrice de larte (3-7),

qui est donc obtenue, la quatrime tape du processus,

comme lune des trois artes perpendiculaires (1-5).

(Conrmation dans le planning donn la question 3.)

Le processus permet donc dobtenir toutes les artes du

graphe.

) Il y a sept tapes dans le processus ; au cours de chaquetape, on slectionne quatre nouvelles artes : le nombre

dartes du graphe est donc gal 28.

N.B. (dnombrement direct des artes) : le graphe est

complet dordre 8, chaque sommet est donc de degr 7,

la somme des degrs est donc gale 56, donc le nombre

dartes 56

2= 28.

3. Planning possible.

Remarques :

la i-ime tape du processus sera appele i-ime tour ;

les quatre artes du i-ime tour peuvent se dduire des

quatre artes du (i-1)e tour en eectuant la permutationcirculaire : 1 1, 2 3 4 5 6 7 8 2

gomtriquement : en eectuant une rotation de centre 1et dangle

2p

7 2.Rencontres du 1er tour (1-2), (3-8), (4-7), (5-6)

Rencontres du 2e tour (1-3), (4-2), (5-8), (6-7)






c Planning possible avec six joueurs :

Rencontres du 1er tour (1-2), (3-6), (4-5)

Rencontres du 2e tour (1-3), (4-2), (5-6)




Problme10

Chacun des mots db , deci , daabi , deaci peut

tre choisi comme code daccs.

Par contre, les mots debci et deabi ne sont pas

reconnus.

Problme11

2. ) N = 0 2 0 10 0 1 1

1 1 0 0

1 0 0 02

Problme8

1. Le fux horaire maximum pouvant circuler sur le trajet

(A-B-C-E) sans crer de bouchons est celui pouvant

circuler sur larte (B-C), soit 400.

Le fux horaire maximum pouvant circuler sur le trajet

(A-D-E) sans crer de bouchons est celui pouvant circulersur larte (D-E), soit 300.

Le maximum de vhicules/heure aire partir de A, de sorte

quils puissent arriver E sans bouchons, est donc de 700 :

400 sur (A-B) et 300 sur (A-D).

2. Le doublement du poids de larte (C-E) na aucune

incidence sur le fux horaire maximum pouvant circuler sur

le trajet (A-B-C-E) sans crer de bouchons, qui est toujours

gal celui pouvant circuler sur larte (B-C), soit 400.

On ne peut donc pas aire partir davantage de vhicules

de A pour aller jusqu E sans bouchons.

Problme9

a 1. Deux sommets quelconques sont relis par une arte,

puisque les deux joueurs reprsents par ces deux sommets

doivent se rencontrer : le graphe est donc complet.

2. A

13

2

3

1

2

D

CB

b 1. Il y a quatre parties chaque tour.

2. ) La droite (12) est la mdiatrice des artes (3-8),

(4-7) et (5-6) qui sont donc perpendiculaires larte (1-2).

Artes obtenues : (1-2), (3-8), (4-7), (5-6).

La droite (13) est la mdiatrice des artes (4-2), (5-8) et

(6-7) qui sont donc perpendiculaires larte (1-3). Artes

obtenues : (1-3), (4-2), (5-8), (6-7).

Le processus sachve avec larte (1-8) et ses trois artes

perpendiculaires (2-7), (3-6) et (4-5).

Montrons que toute arte du graphe est obtenue une fois

et une seule dans le processus prcdent.

Cest vident pour tout arte (1-i), i [2 ; 8].

Montrons-le pour toute arte dont le sommet 1 nest pas une

extrmit. Soit (j-k) une telle arte. Parmi les cinq sommets

autres quej, ket 1, un nombre pair se trouve dun ct de

larte (j-k) et un nombre impair de lautre ct ; le sommet

mdian de ces derniers sommets est quidistant dej et k

(et cest le seul des cinq sommets qui a cette proprit).

Notons-le i ; la droite (1-i) est donc mdiatrice de larte

(j-k), qui est donc obtenue la (i-1)e tape du processus

comme lune des trois artes perpendiculaires (1-i).Exemple : (j-k) = (3-7) ; deux sommets : 2 et 8 dun ct

de (3-7), trois sommets : 4, 5 et 6 de lautre ; le sommet

mdian de 4, 5 et 6 est le sommet 5 qui est le seul

7/30/2019 172665_prof_CH11

4/16



ES-L

) Oui : 4 3 1

2 5

) Non (il ny a pas, dans ce graphe, de sommet de degr 4,

alors que la deuxime ligne de A comporte quatre 1 ).

20 Sommet 1 2 3 4 5 6 7

Degr 4 5 6 4 3 6 4

Somme des degrs : S = 32.

Nombre dartes :S

2= 16.

21 1.

A

FH

G

D

CB

E

2.

0 1 0 0 1 0 0 0

1 0 1 0 1 0 0 0

0 1 0 1 0 0 0 00 0 1 0 0 0 1 0

1 1 0 0 0 1 0 0

0 0 0 0 1 0 1 1

0 0 0 1 0 1 0 1

0 0 0 0 0 1 1 023. ) Parcours :A

B C

D

G

HF

E

) Suppression possible de (B-E) et (F-G).

22

1

2

3

4

5

678

9

10

2. ) Proprit quaurait le graphe : lexistence dune chane

de longueur 2 entre deux sommets implique lexistence

dune arte entre ces deux sommets.

RepRsenteR une situation

laide dun gRaphe

Dans les exercices 11 13, S dsigne la somme des degrs

des sommets du graphe, m le nombre de ses artes ; on

vrie que S = 2m.

La matrice du graphe est note A.

11 S = 4, m = 2 ; A = 0 1 0

1 0 1

0 1 02

12 S = 4, m = 2 ; A = 0 1 0 0

1 0 1 0

0 1 0 0

0 0 0 02

13 S = 8, m = 4 ; A = 0 0 0 0 1

0 0 0 1 1

0 0 0 1 0

0 1 1 0 0

1 1 0 0 02

14 A = 0 1 0 1

1 0 1 0

0 1 0 0

1 0 0 02

15 A =

0 1 0 0 0

1 0 1 1 00 1 0 1 1

0 1 1 0 0

0 0 1 0 0216 A =

0 1 0 0 0 0

1 0 1 0 0 0

0 1 0 0 0 0

0 0 0 0 1 1

0 0 0 1 0 1

0 0 0 1 1 0

217

1 ou (graphe orient)1

2

3

2

3

18 1

2

3

41

2

3

4

ou (graphe orient)

19 ) Oui : 2

1 3

45

eXerCiCes entranmnt(page 314)

7/30/2019 172665_prof_CH11

5/16



ES-L

26 1. Les nombres de poignes de main changes parles cinq personnes autres que M. Graeuil sont, puisque 4

en est le nombre maximum : 0, 1, 2, 3 et 4.

2. ) Le sommet S4, de degr 4, est reli tous les autres

sommets sau S0, qui nest reli aucun sommet, et qui

reprsente donc son conjoint.

) S1

est reli S4

seulement, donc les trois sommets

adjacents S3 sont S2, S4 et S ; le conjoint de S3 est donc S1.3. Les deux sommets adjacents S

2tant dj identis, le

graphe reprsentant la situation est donc le suivant :

S

S4

S3

S2

S1

S0

Conclusion : lpouse de M. Graeuil est reprsente par

le sommet S2; M. et Mme Graeuil ont, tous les deux, serr

la main aux deux personnes reprsentes par les sommets

S3

et S4.

27 1. ) La somme des degrs des sommets dun grapheest gale deux ois le nombre dartes : cest donc un

nombre pair.

) La somme des degrs des sommets dun graphe dordre 5

dont tous les sommets sont de degr 3 serait gale 5 3 = 15

qui est impair ; un tel graphe nexiste donc pas.

2. La somme des degrs des sommets dun graphe dordre2k+ 1 dont tous les sommets sont de degr 3 serait gale

(2k + 1) 3 qui est un nombre impair ; un tel graphe

nexiste donc pas.

3. Un graphe dordre 4 dont tous les sommets sont de

degr 3 est un graphe complet dordre 4.

4. Graphe dordre 6 rpondant la question : un hexagone,

en prenant pour artes les six cts de lhexagone : (1-2),

(2-3), (3-4), (4-5), (5-6), (6-1) (chaque sommet tant alors

de degr 2), et trois diagonales aisant passer le degr de

chaque sommet de 2 3, par exemple (1-4), (2-5) et (3-6).

28 1. La somme des degrs des sommets dun graphe,gale au double du nombre dartes, est un entier pair.

Dans le graphe dordre 7 dont les sommets sont les sept

quipes et dans lequel une arte relie deux sommets i etj

si lquipe i rencontre lquipe j, les sommets ne peuvent

donc pas tre tous de degr 5, car alors la somme des

degrs serait gale 7 5 = 35, qui est impair. Il est donc

impossible de aire jouer cinq matchs chaque quipe.

2. La question est celle de lexistence dun graphe dordre 7

dont tous les sommets soient de degr 4. On va construire

un tel graphe.

On part dun heptagone, en prenant pour artes les septcts de lheptagone : (1-2), (2-3), (3-4), (4-5), (5-6),

(6-7), (7-1) : tous les sommets sont donc, pour linstant,

de degr 2.

) Ladage nest pas vri car, par exemple, il y a une

chane de longueur 2 reliant les sommets 8 et 6 (la chane

(8-2-6)) sans que larte 8-6 existe.

23 1. A B

C

DE

2. ) Problme (P) : il sagit de trouver un sous-ensemble

de magasins, contenant le plus grand nombre de magasins

possible, tel que deux magasins quelconques de ce sous-

ensemble puissent tre ouverts simultanment. Cela qui-

vaut trouver dans le graphe un sous-ensemble de sommets

ayant le plus grand nombre de sommets possible et tel que

deux sommets quelconques de ce sous-ensemble ne soient

pas relis par une arte (contrainte C).

) Sous-ensembles de cardinal maximum respectant la

contrainte C :

contenant A : {A, E} ;

contenant B : {B, C, E} ;

contenant C : {B, C, E} ;

contenant D : {B, D} ;

contenant E : {B, C, E}.

Do la solution : {B, C, E}.

24 1. 2 3

4

56

1

2. Degrs respectis des sommets : 1, 3, 1, 1, 4, 2 ; somme

des degrs : 12, nombre dartes 12 2 = 6.

3. Le nombre maximum de personnes pouvant tre invites

sans risque dambiance dicile est celui de tout sous-

ensemble de sommets, de cardinal maximum, tel que deux

sommets quelconques de ce sous-ensemble ne soient pas

relis par une arte.

Lensemble des six sommets ne convient pas ; aucun des

sous-ensembles de cinq sommets ne convient ; par contre,

un (et un seul) sous-ensemble de quatre sommets convient :{1, 3, 4 et 6}, et ournit donc la solution.

25 1. Construisons le graphe dordre 7 dont les sommetsreprsentent les commissions et les artes reprsentent les

conseillers.

Chaque conseiller est reprsent par larte reliant les

deux sommets qui reprsentent les deux commissions dont

il ait partie (rgle 1).

Daprs la rgle 2, deux sommets quelconques sont relis

par une arte (et une seule). Le graphe est donc complet.

2. Chaque sommet est de degr 6 ; la somme des degrs est

donc gale 7 6 = 42 ; do le nombre dartes :42

2= 21.

3. Il y a donc 21 conseillers gnraux et 6 membres dans

chaque commission.

7/30/2019 172665_prof_CH11

6/16



ES-L

) Solution du problme : la tourne 1-2-4-3-1

(ou 1-3-4-2-1).

2. La solution est la mme tourne, mais avec dpart de 4 et

retour en 4, cest--dire : 4-3-1-2-4 (ou 4-2-1-3-4).

connexit

32 G est connexe. En eet, la chane C = (2-3-1-4-5-6)passe par tous les sommets de G, donc deux sommets

quelconques sont relis par une chane extraite de C.

33 G nest pas connexe. En eet, il nexiste pas, parexemple, de chane reliant les sommets 2 et 5.

34 G est connexe. En eet, la chane C = (1-3-2-4-5-6)passe par tous les sommets de G, donc deux sommets

quelconques sont relis par une chane extraite de C.

35 G nest pas connexe. En eet, il nexiste pas, parexemple, de chane reliant les sommets 1 et 6.

36 1. G est connexe. En eet, si C est la chane passantpar tous les sommets de G, alors deux sommets quelconques

sont relis par une chane extraite de C.

2. ) 21

7

6

5

4

3

) La chane (2-3-7-1-6-4-5) passe par tous les sommets

de G. On en dduit que G est connexe.

37 1. G1

nest pas connexe. En eet, il nexiste pas, par

exemple, de chane reliant les sommets 1 et 4.

Par contre, G1

peut tre dcompos en deux graphes

connexes :

G1:

1

2

3

et G1:

4

5

(composantes connexes de G1).

G2

nest pas connexe, mais peut tre dcompos en trois

graphes connexes :

G2

:4

1

2

3

, G2

:6 7

5

et G2 :

89

(composantes connexes de G2).

On ajoute deux artes nouvelles quelconques : les quatre

sommets extrmits de ces deux artes sont donc dsormais

de degr 3.

On relie deux quelconques des trois autres sommets au

troisime : ce dernier est donc de degr 4, et les six autres

sont de degr 3.

On relie enn ces six sommets par paires : dans le graphe

obtenu, tous les sommets sont de degr 4.Exemple de choix dartes : (1-5) et (3-7), puis (2-6) et

(4-6), enn (1-3), (2-5) et (4-7).

29 1. 6 8

4

1

2

3 5 7

2. La somme des termes dune ligne i quelconque de A est

gale au nombre dartes orientes dorigine le sommet i :

elle indique donc le nombre de chapitres ncessitant en

prrequis le chapitre i.

Le chapitre rviser en priorit est donc celui qui correspond

la ligne de A dont la somme des termes est la plus grande :

il sagit du chapitre 1.

30 1. On prend comme origine du temps la date dedbut du chantier.

La tche T2

est excutable ds que la tche T1, de dure 2,

est acheve, cest--dire au plus tt la date 2.

La tche T3 est excutable ds que les tches T1 et T2 sontacheves ; or T1

est acheve au plus tt la date 2, et T2

dont lexcution dmarre au plus tt la date 2 et dure trois

jours la date 5 ; la date de dbut au plus tt de T3

est

donc gale max(2,5), cest--dire 5.

La tche T4

est excutable ds que les tches T2

et T3

sont

acheves, cest--dire au plus tt la date calcule par

max(2 + 3, 5 + 2), soit 7.

La tche T5

est excutable ds que les tches T2, T

3et T

4

sont acheves, cest--dire au plus tt la date calcule par

max(2 + 3, 5 + 2, 7 + 4), soit 11.

La n du chantier T6

survient ds que les tches T4

et T5

sont acheves, cest--dire au plus tt la date calcule par

max(7 + 4, 11 + 3), soit 14.

N.B. : la date au plus tt de lexcution dune tche Tj

(respectivement de la n du chantier T6) est le poids dun

plus long chemin de T1

Tj

(respectivement de T1

T6).

31 1. ) Liste exhaustive des tournes de G : 1-2-3-4-1,1-2-4-3-1, 1-3-2-4-1, 1-3-4-2-1, 1-4-2-3-1, 1-4-3-2-1.

) En ait, les tournes 1-2-3-4-1 et 1-4-3-2-1, 1-2-4-3-1

et 1-3-4-2-1, 1-3-2-4-1 et 1-4-2-3-1 ne dirent que par le

sens de parcours, elles ont le mme kilomtrage.

)

Tourne 1-2-3-4-1et

1-4-3-2-1

1-2-4-3-1et

1-3-4-2-1

1-3-2-4-1et

1-4-2-3-1

Kilomtrage 173 168 221

7/30/2019 172665_prof_CH11

7/16



ES-L

45 2. G nest pas complet, mais il est connexe.

3. ) Le problme est celui de lexistence dune chane

eulrienne erme dans le graphe. Or, le graphe est connexe,

mais tous les sommets ne sont pas de degr pair ; il nexiste

donc pas de telle chane.

) Le problme est celui de lexistence dune chane

eulrienne dans le graphe. Or, le graphe est connexe et

admet exactement deux sommets de degr impair : 6 et 8 ;

il existe donc une chane eulrienne reliant 6 et 8, par

exemple : (6-5-4-3-2-4-6-7-1-2-8-3-1-8), do une rponse

positive la question pose.

46 1. Les graphes de cet exercice sont complets doncconnexes.

2

1

0

4 3

G (graphe complet dordre 5).

2. Lalignement des deux dominos n1 n2 et n3 n4nest possible que si n

2= n

3cest--dire si les artes repr-

sentatives (n1

n2) et (n

3 n

4) orment, dans G, une chane

de longueur 2 dextrmits n1

et n4.

Lalignement de tous les dominos nest donc possible que

sil existe dans G une chane eulrienne ( tous les dominos

sont utiliss une seule ois).

3. Tous les sommets de G tant de degr pair, une telle

chane existe, plus prcisment : il existe une chane eul-

rienne erme dans G, par exemple (0-1-2-3-4-0-2-4-1-3-0)

et donc une solution au problme (P) obtenue en intercalant

les doubles .

4. ) Dans le graphe complet G dordre 4 reprsentant la

situation, les quatre sommets sont de degr 3 donc impair ;

donc pas de chane eulrienne dans G et donc pas de

solution au problme (P).

) Les sept sommets sont de degr 6 donc pair, do

lexistence dune chane eulrienne erme dans G par

exemple : (0-1-2-3-4-5-6-0-2-4-6-1-3-5-0-3-6-2-5-1-4-0),

et donc dune solution au problme (P) dans ce cas, obtenue

en intercalant les doubles .

47 1. Le problme est celui de lexistence dune chaneeulrienne dans le graphe. Or, le graphe est connexe et

admet exactement deux sommets de degr impair : E et G ;

il existe donc une chane eulrienne reliant E et G, par

exemple la chane : (E-D-C-B-A-G-F-E-C-G-E-B-G).

2. Le problme est celui de lexistence dune chaneeulrienne erme dans le graphe.

Or le graphe est connexe, mais tous les sommets ne sont

pas de degr pair ; il nexiste donc pas de telle chane.

2. )

4

1

2 6 7

5

3

) (Il ny a pas dautre solution.)

chanes eulRiennes

Dans les exercices 38 40, les graphes considrs sont

connexes.

38 ) Oui ; (2-1-5-2-3-4).) Non (quatre sommets de degr impair).

39 ) Oui ; (1-2-3-1-4-5-6-3-4).) Non (quatre sommets de degr impair).

40 ) Tous les sommets sont de degr pair, donc legraphe admet une chane eulrienne erme, par exemple :

(1-2-3-4-1-3-6-5-1).

) Non (quatre sommets de degr impair).

41 1. Le graphe est connexe, mais le nombre de sommetsde degr impair est gal 4.

2. En rajoutant une arte reliant deux sommets de degr

impair, le nombre de sommets de degr impair du graphe

obtenu a ortiori connexe est gal 2 ; le graphe obtenuadmet donc une chane eulrienne. Si, par exemple, on

rajoute larte (1-6), le graphe obtenu admet la chane

eulrienne (2-1-6-5-4-3-2-4).

42 1. Le problme est celui de lexistence dune chaneeulrienne dans le graphe. Or, le graphe est connexe, mais

quatre sommets sont de degr impair (A, B, D, I). Il nadmet

donc pas de chane eulrienne.

2. Si lon supprime larte (B-D), le graphe obtenu reste

connexe, et na plus que deux sommets de degr impair (A

et I) ; il admet donc une chane eulrienne dextrmits A

et I, par exemple : (A-B-C-I-E-D-A-G-D-H-G-F-H-E-F-I),parcours permettant au promeneur de parcourir toutes les

rues sau (B-D) sans passer deux ois par la mme rue.

Autres solutions : suppression de larte (A-B) ou (A-D).

43 Le problme est celui de lexistence dune chaneeulrienne dans le graphe du site internet. Or ce graphe est

connexe, mais quatre sommets sont de degr impair (A, B,

D, G) ; il nadmet donc pas de chane eulrienne, cest--

dire quil nexiste pas de parcours passant une seule ois

par tous les liens de pages.

44 1. Le graphe est connexe et tous ses sommets sont dedegr pair. Daprs le thorme dEuler, il admet donc une

chane eulrienne erme.

2. Exemple dune telle chane : (A-B-C-A-E-C-F-E-D-A).

7/30/2019 172665_prof_CH11

8/16


Dijkstra :

A B C D ESommet

slectionn

0 A

0 + 3

3 (A)

0 + 5

5 (A) B

3 + 14 (B)

3 + 25 (B)

C

4 + 2

5 (B)

4 + 3

7 (C)D

5 + 2

7 (C)E

Do un plus court chemin de A E : (A-B-C-E).

N.B. :Lors de la dernire mise jour ventuelle du coecient

de E, on compare 5 + 2 au coecient de E gal 7 ; les

deux nombres tant gaux, on garde, conventionnellement,

7(C) ; mais le ait que le coecient 7 soit gal signie

quil existe un autre chemin de longueur 7 de A E, dontlavant-dernier sommet est D : le chemin (A-B-D-E).

51 Poids des chemins de A E ne passant pas deux oispar le mme sommet :

Chemin (A-E) (A-C-E) (A-B-C-E) (A-B-D-C-E)

Poids 5 4 7 11

Plus court chemin de A E : (A-C-E), de poids 4.

Dijkstra :

A B C D E

Sommet

slectionn

0 A

0 + 2

2 (A)

0 + 1

1 (A)

0 + 5

5 (A)C

1 + 2

2 (A)

1 + 4

5 (C)

1 + 3

4 (C)B

2 + 2

4 (B)4 (C) D

4 (C) E

Do un plus court chemin de A E : (A-C-E), de poids 4.

Remarque concernant la slection du sommet D : on auraitpu choisir le sommet E qui est aect du mme coecient

(4) ; lalgorithme se serait alors termin avec cette slection

de E.


Chemin (A-B-C-D-E) (A-B-C-E) (A-B-D-C-E) (A-B-D-E) (A-B-E)

Poids 4 +x 6 6 +x 4 4

Chemin (A-C-B-D-E) (A-C-B-E) (A-C-D-B-E) (A-C-D-E) (A-C-E)

Poids 4 4 4 +x 2 +x 4

Donc (A-C-D-E) est un plus court chemin de A E si et

seulement six< 2.Nathan2012TransmathTerm.

ES-L

48 a. 1. Deux sommets quelconques sont relis par unechane extraite de la chane (Y-C-D-G-H-E-F-B-A-Z) : le

graphe est donc connexe.

2. Sommet Y A B C D E F G H Z

Degr 3 4 4 4 4 4 2 4 2 1

3. Daprs le thorme dEuler, le graphe admet une chane

eulrienne dextrmits les deux sommets de degr impair :

Y et Z.

b. 1. La situation peut tre reprsente par un graphe ayant

pour sommets Y (accueil), A, B, C, D, E, F, G, H (les salles

dexposition du muse), et Z (boutique), et dans lequel une

arte relie deux sommets si et seulement si les deux salles

reprsentes par ces sommets communiquent par une porte.

Le graphe ainsi obtenu est le graphe du a.

2. Le rsultat du a.3. assure alors lexistence dun parcours

partant de laccueil Y, passant une ois et une seule par

toutes les portes intrieures du muse et arrivant la

boutique Z. Exemple dun tel parcours : (Y-G-H-E-F-B-E-D-B-A-C-G-D-C-Y-A-Z).

N.B. : considrons le graphe obtenu en rajoutant un

sommet X (billetterie/livre dor, lextrieur du muse,

proximit de laccueil et de la boutique), ainsi quune arte

(X-Y) reprsentant la porte daccs laccueil, et une arte

(Z-X) reprsentant la porte de sortie de la boutique ; dans

ce graphe (connexe !), tous les sommets sont de degr pair,

et il existe donc une chane eulrienne erme, obtenue, par

exemple, en concatnant larte (X-Y), la chane eulrienne

de Y Z propose ci-dessus, et larte (Z-X).

49 1. Sommet A B C D E F

Degr 4 5 3 4 2 2

La somme des degrs des sommets est gale 20, le nombre

dartes est donc gal 20

2= 10.

2. Le graphe est connexe. En eet, deux sommets quel-

conques sont relis par une chane extraite de la chane

(F-A-B-C-D-E) qui passe par tous les sommets.

Par ailleurs, deux sommets sont de degr impair : B et C.

Daprs le thorme dEuler, le graphe admet donc une

chane eulrienne dextrmits B et C. Exemple de chaneeulrienne : (B-A-C-B-F-A-D-E-B-D-C).

RecheRche dun plus

couRt chemin


Chemin(A-B-

C-E)

(A-B-C-

D-E)

(A-B-

D-E)

(A-B-D-

C-E)(A-C-E)

(A-C-

D-E)

(A-C-B-

D-E)

Poids 7 8 7 10 8 9 10

Plus courts chemins ex quo de A E : (A-B-C-E) et (A-B-

D-E), de poids 7.

7/30/2019 172665_prof_CH11

9/16



ES-L

allant de 3 1 ; ces sommets sont : 3, puis a31

= 4, puis a41

= 2,

puis a21

= 1 : on retrouve bien le chemin (3-4-2-1).

Autre exemple. Les sommets rencontrs sur le plus court

chemin allant de 1 4 sont : 1, puis a14

= 2, puis a24

= 4 ; on

retrouve bien le chemin (1-2-4).

56 1. ) Sommet A B C D E F

Degr 4 3 4 4 3 2

) Deux sommets quelconques sont relis par une chane

extraite de la chane (E-D-A-C-B-F) qui passe par tous les

sommets : le graphe est donc connexe.

2. ) Il sagit de justier lexistence, dans le graphe, dune

chane eulrienne.

Or le graphe est connexe et a exactement deux sommets de

degr impair, E et B ; il admet donc une chane eulrienne

reliant E et B.

) Exemple dune telle chane :

(E-D-C-A-E-C-B-A-D-F-B).

3. Dijkstra :

E A C D B FSommet

slectionn

0 E

0 + 30

30 (E)

0 + 40

40 (E)

0 + 10

10 (E) D

10 + 10

20 (D)

10 + 40

50 (E)

10 + 70

80 (D)A

20 + 10

30 (A)

20 + 40

60 (A)80 (D) C

30 + 20

50 (C)80 (D) B

50 + 20

70 (B)F

Le chemin minimisant la dpense est donc :

(E-D-A-C-B-F), de cot 70.

57 1. ) Tout chemin empruntant larte (A-B) ne peutpas tre un plus court chemin, puisque le chemin obtenu en

substituant la chane (A-C-B) ou (B-C-A) larte (A-B) a

un poids inrieur (de 7-6, cest--dire 1).

Larte (A-B) ne ait donc partie daucun plus court

chemin : elle peut donc, lors de toute recherche dun plus

court chemin, tre supprime .

) Plus gnralement, si, dans un triangle inclus dans un

graphe, le poids dune arte est suprieur la somme des

poids des deux autres, alors cette arte ne ait partie daucun

plus court chemin et peut donc, lors de toute recherche dun

plus court chemin, tre supprime .

N.B. : si, dans un triangle inclus dans un graphe, le poids

dune arte v est gal la somme des poids des deux autres,

alors, pour tout chemin empruntant v, le chemin obtenu en

substituant v la chane orme par les deux autres artesa le mme poids ; lors de toute recherche dun plus court

chemin, on peut donc, dans ce cas galement, supprimer

larte v.

53 Dijkstra :

A B C D E FSommet

slectionn

0 A

0 + 3

3 (A)

0 + 1

1 (A)F

1 + 1

2 (F)

1 + 2

3 (F)

1 + 6

7 (F)B

2 + 4

3 (F) 7 (F) C

3 + 9

12 (C)7 (F) E

7 + 3

10 (E)D

Dans le graphe suivant, pour tout sommet X A, lunique

chemin de A X est un plus court chemin de A X ; son

poids est indiqu ct de X entre parenthses.

E(7)

D(10)

C(3)B(2)

A

F(1)

54 Dijkstra :

a b c d e f g hSommet

slectionn

0 a0 + 3

3 (a)

0 + 11

11 (a)

0 + 17

17 (a)

0 + 16

16 (a) b

3 + 5

8 (b)17 (a) 16 (a) c

17 (a)8 + 6

14 (c)

8 + 7

15 (c) e

14 + 3

17 (a)

14 + 7

21 (e)

14 + 6

20 (c) g

17 (a) 21 (e)15 + 11

26 (g)d

21 (e)17 + 9

26 (g)f

21 + 4

25 (f)h

Le trajet de dure minimum est : (a-b-c-e--h), de dure

25 minutes.

55 1. Plus courts cheminsreliant les sommets

1 et 2 1 et 3 1 et 4 2 et 3 2 et 4 3 et 4

(1-2)

et

(2-1)

(1-2-4-3)

et

(3-4-2-1)

(1-2-4)

et

(4-2-1)

(2-4-3)

et

(3-4-2)

(2-4)

et

(4-2)

(3-4)

et

(4-3)

3. Dcrivons, par exemple, partir des termes (aij) de la

matrice A, les sommets rencontrs sur le plus court chemin

7/30/2019 172665_prof_CH11

10/16



ES-L

61 Directement : le plus court chemin de E B est(E-C-B), de poids 8 (les deux autres chemins de E B tant

(E-B), de poids 10, et (E-A-B), de poids 11). On en dduit

que le chemin (E-C-B-S) est un plus court chemin de E

S, car son poids (12) est inrieur celui (13) du chemin

(E-S).

62 Dijkstra :

1 2 3 4 5 6Sommet

slectionn

0 1

0 + 7

7 (1)

0 + 1

1 (1) 3

1 + 5

6 (3)

1 + 2

3 (3)

1 + 8

9 (3)5

3 + 2

5 (5)

3 + 5

8 (5)9 (3) 2

5 + 4

8 (5)

5 + 2

7 (2) 6

8 (5) 4

Do, pour chaque sommet i, un plus court chemin allant

de 1 i :

Chemin (1-3-5-2) (1-3) (1-3-5-4) (1-3-5) (1-3-5-2-6)

Poids 5 1 8 3 7

63 Dijkstra :

1 2 3 4 5 6 7 8Sommet

slectionn

0 10 + 20

20 (1)

0 + 10

10 (1)

0 + 25

25 (1) 3

20 (1)10 + 12

22 (3)

10 + 16

25 (1)

10 + 35

45 (3) 2

20 + 16

22 (3)

20 + 7

25 (1)

20 + 26

45 (3)

20 + 30

50 (2)4

25 (1)22 + 15

37 (4)45 (3) 50 (2) 5

25 + 16

37 (4)

25 + 14

39 (5)50 (2) 6

37 + 7

39 (5)

37 + 19

50 (2)7

39 + 9

48 (7)8

Le parcours (1-5-7-8) minimise le kilomtrage de la ville 1

la ville 8 (48 km).

2. Tout chemin (1--i) extrait du plus court chemin

(1-5-7-8) est un plus court chemin de 1 i. (Sil existait

en eet un chemin de 1 i de poids inrieur, alors, en

concatnant ce chemin avec le chemin (i--8) extrait

du chemin (1-5-7-8), on obtiendrait un chemin de 1 8 de

poids inrieur au chemin (1-5-7-8)).Un plus court chemin pour aller de la ville 1 la ville 5 est

donc (1-5) et un plus court chemin pour aller de la ville 1

la ville 7 est donc (1-5-7).

2. )1 2 3 4 5

Sommet

slectionn

0 1

0 + 4

4 (1)

0 + 8

8 (1)

0 + 11

11 (1)

0 + 4

4 (1)2

4 + 3

7 (2)

4 + 10

11 (1)

4 + 2

4 (1)5

4 + 5

7 (2)

4 + 6

10 (5)3

7 + 2

9 (3)4

Un plus court chemin de 1 4 est donc : (1-2-3-4), de

poids 9.

) On peut supprimer , dans la recherche de plus courts

chemins, les artes : (1-3) (triangle (1-3-2)), (1-4) (triangle

(1-4-5)), (2-4) (triangle (2-4-3)), (3-5) (triangle (3-5-2),

poids ((3-5)), poids ((2-3)) + poids ((2-5))).

) Dans le graphe obtenu aprs la suppression de ces quatreartes, on peut eectuer une recherche directe dun plus

court chemin de 1 4 en numrant les chemins de 1 4

ne passant pas deux ois par le mme sommet : (1-5-4), de

poids 10, (1-5-2-3-4), de poids 11, (1-2-5-4), de poids 12 et

(1-2-3-4), de poids 9, que lon retrouve bien comme un plus

court chemin de 1 4.

58 1. En comparant les poids des dirents chemins de1 7 ne passant pas deux ois par le mme sommet, on

trouve comme plus court chemin le chemin (1-3-5-7), de

poids 10.2. Quand le poids de chaque arte est augment de deux

units, le poids dun chemin quelconque augmente de deux

ois le nombre de ses artes ( sa longueur ).

Le poids du chemin (1-3-5-7) passe donc

10 + (2 3) = 16, alors que le poids du chemin (1-4-7)

devient gal 11 + (2 2) = 15.

Le chemin (1-3-5-7) nest donc plus un plus court chemin.

59 1. Si chaque arte a le mme poids, k, alors le poidsdun chemin est gal kois le nombre de ses artes ( sa

longueur ). La recherche dun plus court chemin dun

sommet un autre quivaut donc la recherche dun

chemin, reliant ces deux sommets, dont le nombre dartes

est minimum.

2. Voici, pour chaque sommet i, un plus court chemin allant

de 1 i :

Chemin (1-2) (1-3) (1-4) (1-6) (1-2-5) (1-3-7) (1-6-9) (1-3-7-8)

Poids 3 3 3 3 6 6 6 9

60 Un chemin, allant dun sommet a un sommet b,passant deux ois par un mme sommet s, ne peut pas tre

un plus court chemin de a b.En eet, si on supprime la partie du chemin comprise entre

les deux passages par s, on obtient un chemin de a b de

poids strictement inrieur.

7/30/2019 172665_prof_CH11

11/16



ES-L

) Mots reconnus : bb et bba .

Liste des mots de quatre lettres reconnus : aaba,

aabb, bbaa, bbab, bbba, bbbb.

Ensemble des mots reconnus : ensemble des mots forms

avec les lettres a et b, commenant par bb ou par aab.

66 ) Liste des mots de trois lettres reconnus : aaa, aba, baa.


avec les lettres a et b, ne comportant pas deux b cons-

cutis et se terminant par a.

) Liste des mots de trois lettres reconnus : aab,

aba, baa, bbb.

Ensemble des mots reconnus : ensemble des mots for-

ms avec les lettres a et b, comportant un nombre impair

de b.

67 ) Ensemble des mots reconnus : ensemble des motssur {a, b} comportant exactement deux b.

) Ensemble des mots reconnus : ensemble des mots or-ms avec les lettres a et b, comportant un seul a et se

terminant par un b.

68 b

bi = f

a a

puissance n-ime de la matRice

associe un gRaphe

69 1

3

2

Aucune chane oriente de longueur 3, donc A3 = (0).

70 3

2

1

Aucune chane oriente de longueur 3, donc A3 = (0).

71 1. Deux chanes orientes de longueur 2 allant dusommet 1 au sommet 3 : (1-2-3) et (1-4-3) ; une seule

chane oriente de longueur 3 reliant ces deux sommets :

(1-3-4-3).

2. M = 0 1 1 1

0 0 1 0

0 0 0 1

0 0 1 02

3. M2 =

0 0 2 1

0 0 0 1

0 0 1 00 0 0 12

; M3 =

0 0 1 2

0 0 1 0

0 0 0 10 0 1 02

.

On retrouve les rsultats du 1. puisque llment (1, 3) de

M2 est gal 2 et que llment (1, 3) de M3 est gal 1.

64 1. Dijkstra :

1 2 3 4 5 6 7 8 9 10 11Sommet

slectionn

0 1

0 + 14

14 (1)

0 + 12

12 (1)

0 + 13

13 (1) 3

14 (1) 13 (1) 12 + 921 (3)

12 + 1022 (3)

12 + 1325 (3)

4

14 (1) 21 (3)13 + 7

20 (4)

13 + 11

24 (4) 2

14 + 6

20 (2)

14 + 8

20 (4)24 (4) 5

20 (4) 24 (4)20 + 11

31 (5)

20 + 6

26 (5) 6

24 (4)20 + 7

27 (6)

20 + 9

26 (5)

20 + 5

25 (6) 7

27 (6) 26 (5)

24 + 5

25 (6) 10

27 (6) 26 (5)25 + 11

36 (10)9

27 (6)26 + 9

35 (9)8

27 + 7

34 (8)11

Le projet dont le cot total est minimum correspond au

trac (1-4-6-8-11).

2. Compte tenu de laugmentation uniorme de 5 %, le

cot de chaque tronon est multipli par 1,05, et donc le

cot total correspondant nimporte quel trac allant de la

ville 1 la ville 11 est lui aussi multipli par 1,05.

Le projet correspondant au trac (1-4-6-8-11) reste donc le

moins coteux.

gRaphes tiquets

65 ) Mot reconnu : bab. Liste des mots de quatre lettres reconnus :

aaab, abab, baab.

Ensemble des mots reconnus : ensemble des mots formsavec les lettres a et b, ne comportant pas deux b cons-

cutis et se terminant par b .

) Mots reconnus : aba, bba , baba et bababa.

Liste des mots de quatre lettres reconnus :

abba, baba et bbba.


avec les lettres a et b, ne comportant pas deux a cons-

cutis et se terminant par a .

) Mots reconnus : bba et baba.

Liste des mots de quatre lettres reconnus : aaaa,

aaba, abaa, abba, baaa, baba, bbaa,bbba.


avec les lettres a et b, se terminant par a.

7/30/2019 172665_prof_CH11

12/16



ES-L

2.

1

5 4

3

2

3. (M2)52

= 2, il y a donc deux chanes orientes de lon-

gueur 2 de 5 vers 2 : (5-1-2) et (5-3-2).

4. ) On calcule le terme (M3)45

en eectuant le produit

matriciel de la quatrime ligne de M2 :

(1 2 2 2 2) par la cinquime colonne 1

1

0

0

0

2 de M ;on trouve : (M3)

45= 3.

Il y a donc trois chanes orientes de longueur 3 du sommet 4vers le sommet 5 : (4-3-1-5), (4-1-2-5) et (4-3-2-5).

) De mme :

(M3)13

= (2 1 2 2 1) 1

1

0

1

1

2 = 6. Il y a donc six chanesorientes du sommet 1 vers le sommet 3 : (1-3-1-3), (1-5-1-3),

(1-3-2-3), (1-2-4-3), (1-3-4-3) et (1-2-5-3).

76 1.

V3

V2

V4

V1

2. Lexistence dun vol de Vi

vers Vj

comportant au

plus deux escales quivaut lexistence, dans le graphe

prcdent, dune chane oriente de longueur < 3 allant

de Vi V

j. On vrie quil existe de telles chanes pour tout

(i,j), ij :

(V1

V2), (V

1 V

2 V

3), (V

1 V

4) ;

(V2

V3

V1), (V

2 V

3), (V

2 V

3 V

4) ;

(V3 V1), (V3 V1 V2), (V3 V4) ;(V

4 V

2 V

3 V

1), (V

4 V

2), (V

4 V

2 V

3).

3. ) On numrote V1, V

2, V

3, V

4respectivement 1, 2, 3, 4.

M = 0 1 0 1

0 0 1 0

1 0 0 1

0 1 0 02

) M2 = 0 1 1 0

1 0 0 1

0 2 0 1

0 0 1 02 ; M3 =

1 0 1 1

0 2 0 1

0 1 2 0

1 0 0 12

) Notons M = (aij), M2 = (bij), M3 = (cij).Lexistence dau moins un vol dau plus deux escales de

chaque ville Vivers chaque ville V

j(ij) quivaut : pour

tout (i,j), ij, lun au moins des lments aij, b

ij, c

ijest un

72 1.1

2

3

2. M2 = 0 0 1

0 0 0

0 0 02 : on en dduit quil existe dans le

graphe une seule chane oriente de longueur 2, qui va du

sommet 1 au sommet 3 (rsultat que lon peut acilement

visualiser sur le graphe : cest la chane (1-2-3)).

3. M3 est la matrice nulle dordre 3 : on en dduit quil

nexiste dans le graphe aucune chane oriente de longueur 3

(rsultat visuellement vident sur le graphe).

73 1. M = 0 1 0 1 1

1 0 1 1 0

0 1 0 0 1

1 1 0 0 1

1 0 1 1 0

22. ) On dnombre sept chanes de longueur 3 reliant les

sommets 1 et 5 : (1-2-1-5), (1-2-3-5), (1-2-4-5), (1-4-1-5),

(1-5-1-5), (1-5-3-5), (1-5-4-5).

) On peut calculer M2, puis llment (1, 5) de M3 ; plus

astucieusement, on calcule seulement la premire ligne de

M2 = (3 1 2 2 1), llment (1, 5) de M3 sobtenant

en eectuant le produit matriciel de la premire ligne de M2

par la cinquime colonne de M :

(3 1 2 2 1) 1

0

1

1

0

2 = (7)On retrouve le rsultat du ).

74 1. M = 0 1 0 0 0 1 1

1 0 1 0 0 1 0

0 1 0 1 1 0 0

0 0 1 0 1 0 0

0 0 1 1 0 1 1

1 1 0 0 1 0 0

1 0 0 0 1 0 0

22. ) Premire ligne de M2 = (3 1 1 0 2 1 0).

) Le nombre de chanes de longueur 2 partant de A et

arrivant en un autre sommet est gal la somme des termes

de la premire ligne de M

2

autres que le premier, cest--dire 5.

75 1. ) Les termes m45

et m54

de la matrice M sont nuls :

il ny a donc pas darte reliant les sommets 4 et 5 ; par

consquent G nest pas complet.

) Les sommets 4 et 5 sont les seuls qui ne sont pas relis

par une arte ; mais, puisque (M2)54

= 1, il existe une chane

oriente de longueur 2 allant du sommet 5 au sommet 4 ; le

graphe G est donc connexe.

N.B. : la connexit de G peut tre justie partir de la

seule matrice M2. En eet, tous les termes de M2 sau (M2)25

sont non nuls : toute paire de sommets, sau la paire 2-5, estdonc relie (dans les deux sens !), par au moins une chane

oriente ; et les sommets 2 et 5 sont, puisque (M2)52

= 2,

relis par deux chanes orientes de 5 vers 2.

7/30/2019 172665_prof_CH11

13/16



ES-L

82 Soit A = (aij) une matrice carre dordre n ayant

un seul terme non nul : ai0i0

= 1 (1 < i0 1 : la seule chane de longueur n est donc

la chane obtenue en parcourant n ois la boucle en le

sommet i0, et donc An = A.

83 Le graphe orient

3

21

admet A pour

matrice associe. Les chanes orientes de longueur 2 sont :

(1-3-2), (2-1-3), (3-2-1), do A2 = 0 1 0

0 0 1

1 0 12 ;

les chanes orientes de longueur 3 sont : (1-3-2-1), (2-1-3-2),

(3-2-1-3), do A3 = 1 0 00 1 0

0 0 1 2 = I3 ;puis A4 = A, , A3n = I

3, A3n+1 = A, A3n+2 = A2.

84 1. G est dordre 7.

Sommet A B C D E F G

Degr 3 3 3 2 4 3 2

2. M =

0 1 0 0 0 1 1

1 0 1 0 0 1 0

0 1 0 1 1 0 00 0 1 0 1 0 0

0 0 1 1 0 1 1

1 1 0 0 1 0 0

1 0 0 0 1 0 023. Le nombre de chanes de longueur 2 partant de A sans yrevenir est gal la somme des termes de la premire ligne

de M2 autres que le premier, cest--dire 5.

pouR la logique

85 1. Faux (par exemple : deg A = 1, deg B = 3).2. Vrai (N = M).

3. Faux (si M = A, alors, N 6, N M : deg N deg M).

86 1. Faux (la somme des degrs des sommets dungraphe quelconque est gale au double du nombre de ses

artes : cest donc un entier pair).

2. Vrai (graphe ayant la conguration dun triangle).

87 1. Vrai (x ]0 ; 0,5[, (A-D-C) est le plus courtchemin de A C).

2. Faux (x ]0,5 ; 0,6[, le plus court chemin de A C est

(A-C)).

entier strictement positi. On vrie acilement quil en est

bien ainsi.

N.B. : compte tenu de la positivit de aij, b

ij, c

ij, cette

condition quivaut galement chaque lment non

diagonal de M + M2 + M3 est strictement positi .

77 ) Le graphe :

2

1

3

admet A pour matrice associe.

Dans ce graphe :

i dsignant lun quelconque des trois sommets,j et kles

deux autres sommets, il y a trois chanes de longueur 2

dorigine et dextrmit i : (i-i-i), (i-j-i) et (i-k-i) ;

i etj dsignant deux sommets dirents quelconques et

k le troisime sommet, il y a trois chanes de longueur 2

dorigine i et dextrmitj : (i-i-j), (i-j-j) et (i-k-j).

Do A2 = 3 3 3

3 3 3

3 3 32

78 1. Par dnition.2. La plus longue chane oriente du graphe est la chane

(1-2-3-4) de longueur 3 ; il nexiste donc pas de chane de

longueur 4.

3. Par consquent, tous les termes de la matrice A4 sont

nuls, et par suite An = 0 pour tout n> 4.

79 Le graphe admettant la chane oriente (1-2-4-1-2)

de longueur 4, le terme (A4)12 de la matrice A4 est gal 1.

La matrice A4 nest donc pas nulle.

N.B. : il y a trois autres chanes orientes de longueur 4 :

(1-2-4-1-3), (2-4-1-2-4) et (4-1-2-4-1) et donc

(A4)13

= (A4)24

= (A4)41

= 1.

80 Le graphe 1 2 a pour matrice A.Les chanes de longueur 2 de ce graphe sont (1-2-1) et

(2-1-2), do A2 = 1 00 12 = I2.Les chanes de longueur 3 du graphe sont (1-2-1-2) et

(2-1-2-1), do A

3

= 0 1

1 02 = A.Par suite A4 = A3 A = A A = A2,A5 = A4 A = A2 A = A3 = A.

De proche en proche A2p = I2, A2p+1 = A.

(Les chanes de longueur 2p sont : (1-2-1- 2-1) et

(2-1-2- 1-2) ; les chanes de longueur 2p + 1 sont :

(1-2-1-2- 1-2) et (2-1-2-1- 2-1).)

81 Dans un graphe non orient, pour tout entier n> 1 :pour toute paire (i,j) de sommets distincts, lexistence dune

chane de longueur n reliant i j quivaut lexistence

dune chane de longueur n reliant j i. Le nombre de

chanes reliant i j est donc gal au nombre de chanesreliantj i. Do la symtrie de An.

7/30/2019 172665_prof_CH11

14/16



ES-L

si n> 4, alors au moins quatre sommets sont de degr

impair : le graphe nadmet donc pas de chane eulrienne.

Dans un graphe complet (donc connexe) dordre n> 3 et

impair, chaque sommet est de degr (n 1), donc pair ; le

graphe admet donc une chane eulrienne erme.

91 1. La somme S des degrs des sommets dun graphequelconque, gale au double du nombre dartes, est

un entier pair ; or S = SP

+ SI, o S

P(respectivement S

I)

dsigne la somme des degrs des sommets de degr pair

(respectivement de degr impair) ; SP

est videmment un

entier pair ; par suite SI= S S

Pest un entier pair, et donc le

nombre de sommets de degr impair est pair.

2. Considrons le graphe dont les sommets sont les

personnes ayant assist la nale de la coupe du monde de

ootball en 2010, deux sommets tant relis par une artesi et seulement si les deux personnes reprsentes par ces

sommets ont chang une poigne de main.

Le nombre de personnes ayant chang un nombre impair

de poignes de main est gal au nombre de sommets du

graphe dont le degr est impair. Daprs le rsultat dmontr

la question 1., ce nombre est pair.

92 1.On suppose que les graphes cherchs sont sansboucle, et tels quentre deux sommets il existe au plus une

arte.

) Dans un graphe dordre 5 dont les degrs des sommetssont tous distincts, ces degrs ont pour valeurs 4, 3, 2, 1, 0 ;

or, il ne peut exister simultanment un sommet de degr 4,

qui est adjacent aux quatre autres sommets, et un sommet

de degr 0 qui nest adjacent aucun sommet.

Un tel graphe ne peut donc pas exister.

) Plus gnralement, dans un graphe dordre n> 2 dont

les degrs des sommets sont tous distincts, ces degrs ont

pour valeurs n 1, n 2, , 2, 1, 0 ; or, il ne peut exister

simultanment un sommet de degr n 1, qui est adjacent

aux n 1 autres sommets, et un sommet de degr 0 qui nest

adjacent aucun sommet.

Un tel graphe ne peut donc pas exister.

2. On dduit du rsultat dmontr en 1. ) que, dans un

graphe dordre n> 2, il y a au moins deux sommets de

mme degr. Ce corollaire sapplique, en particulier, au

graphe, dordre n> 2, dont les sommets sont les personnes

du groupe et dont les artes reprsentent les paires damis.

Do la conclusion demande.

93 Dans chacun des cas, le graphe de la situation asix sommets, reprsentant les six personnes ; une arte

relie deux sommets si et seulement si les deux personnes

reprsentes par ces sommets ont discut entre elles aucours de la rception. On note que ce graphe est sans

boucle, et tel quentre deux sommets il existe au plus une

arte.

soutien

88 Sommet A B C D E F G H

Degr 5 7 4 5 7 6 4 4

(Pour les degrs de A et E, la boucle compte pour 2 ).

La somme des degrs des sommets vaut 42. Le nombre

dartes de G est donc gal 42

2= 21.

89 1. G1

est connexe et tous ses sommets sont de

degr pair : il existe donc, dans G1, au moins une chane

eulrienne erme.

Exemples de telles chanes : (A-B-C-A), (B-A-C-B).

2. ) G2

est connexe et a exactement deux sommets de

degr impair : B et D. Il existe donc, dans G2, une chane

eulrienne dextrmits B et D.Exemples de telles chanes : (B-A-C-B-D), (D-B-C-A-B).

) Toute chane erme, dorigine lun quelconque des

quatre sommets, emprunte deux ois larte (B-D) (une ois

dans chaque sens) : elle nest donc pas eulrienne.

appRofondissement

90 Dans les graphes complets dont il est question, onsuppose que deux sommets distincts quelconques sont

relis par une arte et une seule ; uniquement par souci

de simplifcation, on suppose aussi que ces graphes sont

sans boucle (mme si la prsence de boucles ne modife pas

les parits des degrs des sommets et, par consquent, ne

modife pas les conclusions obtenues).

On pourra, par ailleurs, sintresser lexercice 46,

page 319, qui porte sur le mme thme.

1. On remarque dabord quun graphe complet est connexe.

)n = 2 : les deux sommets sont de degr impair (1), le

graphe admet une chane eulrienne constitue par sa seule

arte.

)n = 3 : les trois sommets sont de degr pair, le graphe

admet donc une chane eulrienne erme, constitue par

ses trois artes.

)n = 4 : les quatre sommets sont de degr impair (3), le

graphe nadmet donc pas de chane eulrienne.

)n = 5 : les cinq sommets sont de degr pair (4), le graphe

admet donc une chane eulrienne erme.

2. ) Le cas n = 2 mis part, il semble quun graphe complet

dordre n admette une chane eulrienne (erme) si n est

impair, et nadmette pas de chane eulrienne si n est pair.

) Dans un graphe complet (donc connexe) dordre n pair,

chacun des n sommets est de degr (n 1), donc impair ;

do : si n = 2, alors les deux sommets sont de degr impair

(1), le graphe admet une chane eulrienne constitue par

sa seule arte ;

eXerCiCes Accompagnmnt prsonnais(page 327)

7/30/2019 172665_prof_CH11

15/16

7/30/2019 172665_prof_CH11

16/16

Dautre part, H a exactement deux sommets de degr

impair : 1 et 5.

Daprs le thorme dEuler, H admet une chane eulrienne

dextrmits les sommets 1 et 5.

La rponse ) est ausse, car tous les sommets de H ne

sont pas de degr pair.

La rponse ) est ausse, car, par exemple, il ny a pas

darte reliant 1 et 3.


ES-L

La rponse ) est ausse, car il y a douze 1 dans la

matrice, donc six artes, puisquune arte induit deux 1

dans la matrice.

La rponse ) est ausse, car, par exemple, m12

= m21

= 0,

il ny a donc pas darte reliant A et B.

98 Rponse exacte : ). En eet H est connexe car deuxsommets quelconques sont relis par une chane extraite de

la chane (1-2-3-4-5) qui passe par tous les sommets.

Documents

172665_prof_CH11