graphes

[PDF] GRAPHES EXERCICES CORRIGES Compilation Lycée d 'Adultes lyceedadultes math Graphesexoscorrigés pdf

Graphes exercices et correction

[PDF] Graphes exercices et correctionmathematiques ac bordeaux graphes exos graphes exos pdf

éléments de théorie des graphes quelques exercices d application

[PDF] éléments de théorie des graphes quelques exercices d 'applicationmathematiques ac bordeaux graphes exo graphes sopena tout pdf

Introduction ? la théorie des graphes Solutions des exercices

[PDF] Introduction ? la théorie des graphes Solutions des exercices apprendre en ligne graphes corriges pdf

Theorie des graphes

[PDF] Theorie des graphes is unice ~malapert graphes slza cours pdf

Feuille TD n° 2 #8211; Exercices (Graphes)

[PDF] Feuille TD n° Exercices (Graphes)dept info labri ENSM% %Graphes% %Correction%Feuille%TD pdf

Exercices Graphes TD n°1

[PDF] Exercices Graphes TD n° graphes TD pdf

graphes

[PDF] graphessite math free terminale es cours terminale es graphes pdf

Théorie des Graphes - usthb

[PDF] Théorie des Graphes usthbperso usthb dz ~mboukala TDTG pdf

Exercices - Théorie des graphes - exercices pratiques :

Exercice Est ce le même graphe ? Master Enseignement Les deux premiers dessins représentent le même graphe Il s 'agit d 'un pentagone où tous les

[PDF] exercices histoire 5eme

[PDF] exercices histoire 6ème ? imprimer

[PDF] exercices hockey sur gazon

[PDF] exercices initiation hockey sur gazon

[PDF] exercices mathématique pdf

[PDF] exercices maths 1ere es

[PDF] exercices maths 1ere s nouveau programme

[PDF] exercices maths 1ere s pdf

[PDF] exercices maths bcpst 1

[PDF] exercices maths terminale stmg

[PDF] exercices mouvement des satellites et des planètes corrigés pdf

[PDF] exercices nombres complexes corrigés

[PDF] exercices nombres complexes terminale s

[PDF] exercices nombres complexes type bac pdf

[PDF] exercices physique nucleaire pdf

graphes

Table des matières

1 graphe, matrices d"adjacence, chaînes et cycles3

1.1 activités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 3

1.1.1 activité 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 4

1.1.2 activité 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 7

1.1.3 activité 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 8

1.2 à retenir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 9

1.3 exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 11

1.4 corrigés exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 14

2 graphe connexe, trajet Eulérien et algorithme d"Euler19

2.1 activités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 19

2.1.1 activité 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 19

2.1.2 activité 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 20

2.1.3 activité 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 21

2.2 à retenir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 22

2.3 exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 24

2.4 corrigés exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 26

3 graphe orienté, matrice d"adjacence, graphe étiqueté32

3.1 activités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 32

3.1.1 activité 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 32

3.1.2 activité 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 33

3.1.3 activité 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 34

3.2 à retenir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 35

3.3 exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 36

3.4 corrigés exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 37

4 graphes pondérés39

4.1 activités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 39

4.1.1 activité 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 39

4.1.2 activité 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 40

4.2 à retenir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 41

4.3 exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 43

4.4 corrigés exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 44

5 graphe probabiliste, matrice de transition, état stable47

5.1 activités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 47

5.1.1 activité 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 47

5.1.2 activité 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 49

5.1.3 activité 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 50

5.2 à retenir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 51

5.3 exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 52

5.4 corrigés exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . 53

5.5 travaux pratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . 55

5.5.1 tableur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 55

6 Minima58

6.1 activités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 58

6.1.1 activité 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 58

6.1.2 corrigé activité 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 59

6.1.3 activité 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 60

6.1.4 activité 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 61

6.1.5 activité 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 62

6.1.6 activité 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 63

7 Coloration d"un graphe et nombre chromatique64

7.1 activités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 64

7.1.1 activité 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 64

7.2 à retenir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 65

7.3 exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 66

8 devoir maison67

8.1 corrigé devoir maison . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . 67

9 exercices bac blanc71

1 graphe, matrices d"adjacence, chaînes et cycles1.1 activités

1.1.1 activité 1

tournois(ordre d"un graphe, degré d"un sommet, propriété des poignées de mains) un tournois est organisé entre des équipes,dans chaque cas(si possible):

- construire au moins un graphe(indiquer le degré de chaque sommet, une arête représente unmatch)

- construire un tableau de la forme

Σd=total de participations

Σa=total de matchs

- donner l"ordre du graphe(nombre de sommets)et indiquer s"il est complet(tous les sommets adjacents 2 à 2)

1. (a)

?trois équipesA,BetC

2matchs chacune

A(2)B(2)

C(2)

Σd=participations...

Σa=matchs...

(b)?trois équipesA,BetC

1match chacune

A(1)B(1)

C(1)

Σd=participations...

Σa=matchs...

2. (a)?4 équipesA,B,CetD

1match chacune

A(1)B(1)

D(1)C(1)

A(1)B(1)

D(1)C(1)

A(1)B(1)

D(1)C(1)

Σd Σa (b)?4 équipesA,B,CetD

2matchs chacune

A(2)B(2)

D(2)C(2)

A(2)B(2)

D(2)C(2)

A(2)B(2)

D(2)C(2)

Σd Σa (c)?4 équipesA,B,CetD

3matchs chacune

A(3)B(3)

D(3)C(3)

Σd Σa

3.?5 équipesA,B,C,DetE

1match chacune

A EB DC Σd Σa

4.?5 équipesA,B,C,DetE

2matchs chacune

Σd Σa A(2)

E(2)B(2)

D(2)C(2)

A(2)

E(2)B(2)

D(2)C(2)

5.?5 équipesA,B,C,DetE

3matchs chacune

Σd Σa A EB DC

6.?5 équipesA,B,C,DetE

4matchs chacune

Σd Σa A EB DC

7. (a) est-il possible d"organiser un tournois avec6équipes où chacune joue5matchs? (justifier)

(b) est-il possible d"organiser un tournois avec7équipes où chacune joue5matchs? (justifier)

sommet? (justifier)

1.1.2 activité 2

parmi les graphes ci dessous, lesquels peuvent décrire une même situation? (on pourra indiquer le degré de chaque sommet ainsi que l"ordre du graphe) ?G1 G2 G3 G4 G5G6

1.1.3 activité 3

1.2 à retenir

définition 1 :(graphe non orienté, ...)

(1) un graphe est défini par la donnée de deux ensembles,?l"ensemble de sesnsommetsS={s1,s2,...,sn},n?N?

l"ensemble de sesparêtesA={a1,a2,...,ap},p?N?? s5s 1 s 2 s 3s4a 1a2 a 6a5 a 4a 3 où chaque arête est un sous ensemble{si;sj}de deux sommets du graphe (2) un????graphe est d"ordren(n?N)??il a exactement????nsommets (3) un????sommet est de degrén(n?N)??il appartient à exactement????narêtes (4) deux sommets sont????adjacents??????il existe une arête qui les contient tous les deux (5) un graphe est????complet??tous ses sommets(distincts)sont????adjacents deux à deux exemple: le grapheGdessiné ci dessus - est d"ordre5car il a5sommets{s1;s2;s3;s4;s5} - a6arêtes{a1;a2;a3;a4;a5;a6} - le sommets1est de degré2car il appartient à exactement2arêtesa1eta2 -s1ets2sont adjacents par l"arêtea2 -s1ets3ne sont pas adjacents donc le graphe n"est pas complet propriété 1 quel que soit le graphe non orientéG? ???somme des degrés des sommets = 2×nombre d"arêtes justification: chaque arête compte pour2dans la somme des degrés exemple pour le grapheG? s5(2)s 1(2) s 2(3) s

3(2)s4(3)a

1a2 a 6a5 a 4a

3nombre d"arêtes×2=6×2 = 12

somme des degrés des sommets =2 + 3 + 2 + 3 + 2 = 12 remarques :(découle de la propriété précédente)

1. la somme des degrés des sommets d"un graphe est nécessairement pair

2. le nombre de sommets de degré impair est nécessairement pair

définition 2 :(matrice d"adjacence d"un graphe non orienté ) quel que soit le graphe non orientéGànsommets{s1,s2,...,sn}(n?N?)

Aest matrice d"adjacence deG

???Aest une matrice carrée d"ordren quel que soit le coefficientaijde la matriceA,? ???aij=nombre d"arêtes reliantsiàsj exemple pour le grapheG, matrice d"adjacence =A=((((((010 0 1

1 0 1 1 0

0 1 0 1 0

0 1 1 0 1

1 0 0 1 0))))))

12= 1car 1 arête relies1às2

31= 0car 0 arête relies3às1

s5(2)s 1(2) s 2(3) s

3(2)s4(3)a

1a2 a 6a5 a 4a 3 remarque la matrice d"adjacence d"un graphe est symétrique définition 3 :(chaîne, cycle ) quel que soit le graphe non orientéGànsommets{s1,s2,...,sn}(n?N?) (1) une????chaîne est une????liste ordonnée de sommets adjacents (2) une????chaîne est fermée si ses????extrémités sont égales (3)????un cycle est une????chaîne fermée dont toutes les????arêtes sont distinctes exemple: pour le grapheG? s5(2)s 1(2) s 2(3) s

3(2)s4(3)a

1a2 a 6a5 a 4a

3s2s3s4s2est une chaîne fermée et un cycle

2s3s4s2s3s4s2est une chaîne fermée mais pas un cycle

propriété 2

quel que soit le graphe non orientéGànsommets{s1,s2,...,sn}(n?N?) et de matrice d"adjacence deA?

???le termeaijde la matriceApoup?N? est égal au????nombre de chaînes de longueurpqui relient les sommetssietsj exemple pour le grapheG, on a :A=((((((010 0 1

1 0 1 1 0

0 1 0 1 0

0 1 1 0 1

1 0 0 1 0))))))

s5(2)s 1(2) s 2(3) s

3(2)s4(3)a

1a2 a 6a5 a 4a 3 la calculatrice donne :A3=((((((

052 1 4

5 2 4 6 1

2 4 2 4 2

1 6 4 2 5

4 1 2 5 0))))))

12= 5donc5chaînes de longueur3relients1às2:

s a

31= 2donc2chaînes de longueur3relients3às1:

3s4s2s1,s3s4s5s1

1.3 exercices

exercice 1 : soit le grapheGreprésenté ci contre :A B C D EF G H

1. quel est l"ordre de ce graphe?

128413

2. combien a t-il d"arêtes?128413

3. quel est le degré du sommetC?128413

4. quel sommet est de degré 1?ABFaucun

5. quel sommet est adjacent au sommetD?AEGH

6. combien de sommets sont adjacents au sommetH?3241

7. le graphe est-il complet?ouinonon ne peut pas savoir

8. combien ajouter d"arêtes pour que le graphe soit complet?031516

9. quelle est la longueur de la chaineABCDFH?0256

10. quelle chaine est fermée?ABDACDBABACAABDCAB

11. quelle chaine est un cycle?ABDACDBABACAABDCA

12. combien de lignes la matrice d"adjacenceMa t-elle?891213

13. combien de colonnes la matrice d"adjacenceMa t-elle?891213

14. que vaut le coefficientm33de la matrice d"adjacenceM?014on ne peut pas savoir

15. que vaut le coefficientm23de la matrice d"adjacenceM?014on ne peut pas savoir

16. que vaut le coefficientM214de la matrice d"adjacence au carréM2?012on ne peut pas savoir

exercice 2 :

1. quelle matrice peut-être la matrice d"adjacence d"un graphe non orienté?

A=((0 1 01 0 10 1 1))B=?1 0 10 1 0?C=((0 11 00 1))D=((0 1 11 0 10 1 0))E=((0 1 11 0 11 1 0))

2. soitM=((((0 1 1 11 0 1 01 1 0 11 0 1 0))))

la matrice d"adjacence d"un grapheG (a) combien de sommetGa t-il?

3416on ne peut pas savoir

(b) combien d"arêtesGa t-il?4510on ne peut pas savoir (c) quel est le degré du premier sommet?345on ne peut pas savoir (d) les2eet4esommets sont-ils adjacents?ouinonon ne peut pas savoir (e) les2eet3esommets sont-ils adjacents?ouinonon ne peut pas savoir (f) quel est le grapheG? s1s2 s4s3 s1s2 s4s3 s1s2 s4s3 (g)M2=((((3 1 2 11 2 1 22 1 3 11 2 1 2)))) ,M3=((((4 5 5 55 2 5 25 5 4 55 2 5 2)))) ,M4=((((15 9 14 9

9 10 9 10

14 9 15 9

9 10 9 10))))

i. combien de chemins de longueur2des3às3? 0123
ii. combien de chemins de longueur3des4às2?2345 iii. combien de chemins de longueur4des2às3?9101415 exercice 3 :

1. dessiner les graphes complets pourn= 2,n= 3,n= 4,n= 5

2. dessiner les graphes simples d"ordresn= 2,n= 3,n= 4,n= 5dont tous les sommets sont de degré

3. dessiner tous les graphes simples possible d"ordren= 2,n= 3,n= 4

exercice 4 :

1. est-i possible de relier en réseau,15ordinateurs tels que chacun soit relié à exactement5ordinateurs?

(justifier)

2. à une soirée ou sont présentes17personnes, est-il possible que chacune des personnes serrela main

d"exactement15personnes? (justifier)

3. dans un graphe simple(une arête au maximum entre deux sommets), combien y a t-il de sommets de

degré impair? (justifier)

4. comment tracer 5 segments sur une feuille, de telle manière que chaque segment en coupe exactement

3 autres?

1.4 corrigés exercices

corrigé exercice 1 : soit le grapheGreprésenté ci contre :A B C D EF G H

1. quel est l"ordre de ce graphe?

12 ???8413

2. combien a t-il d"arêtes??

???128413

3. quel est le degré du sommetC?128

???413

4. quel sommet est de degré 1?ABF?

???aucun

5. quel sommet est adjacent au sommetD?AEG

???H

6. combien de sommets sont adjacents au sommetH?32?

???41

7. le graphe est-il complet?oui?

???nonon ne peut pas savoir

8. combien ajouter d"arêtes pour que le graphe soit complet?0315

???16

9. quelle est la longueur de la chaineABCDFH?02?

???56

10. quelle chaine est fermée?ABDACDB

???ABACAABDCAB

11. quelle chaine est un cycle?ABDACDBABACA

???ABDCA

12. combien de lignes la matrice d"adjacenceMa t-elle??

???891213

13. combien de colonnes la matrice d"adjacenceMa t-elle??

???891213

14. que vaut le coefficientm33de la matrice d"adjacenceM??

???014on ne peut pas savoir

15. que vaut le coefficientm23de la matrice d"adjacenceM?0?

???14on ne peut pas savoir

16. que vaut le coefficientM214de la matrice d"adjacence au carréM2?01?

???2on ne peut pas savoir corrigé exercice 2 :

1. quelle matrice peut-être la matrice d"adjacence d"un graphe non orienté?

A=((0 1 01 0 10 1 1))B=?1 0 10 1 0?C=((0 11 00 1))D=((0 1 11 0 10 1 0))

E=((0 1 11 0 11 1 0))

2. soitM=((((0 1 1 11 0 1 01 1 0 11 0 1 0))))

la matrice d"adjacence d"un grapheG (a) combien de sommetGa t-il? 3 ???416on ne peut pas savoir (b) combien d"arêtesGa t-il?4 ???510on ne peut pas savoir (c) quel est le degré du premier sommet?? ???345on ne peut pas savoir (d) les2eet4esommets sont-ils adjacents?oui? ???nonon ne peut pas savoir (e) les2eet3esommets sont-ils adjacents?? ???ouinonon ne peut pas savoir (f) quel est le grapheG? s1s2 s4s3 s1s2 s4s3 s1s2 s4s3 (g)M2=((((3 1 2 11 2 1 22 1 3 11 2 1 2)))) ,M3=((((4 5 5 55 2 5 25 5 4 55 2 5 2)))) ,M4=((((15 9 14 9

9 10 9 10

14 9 15 9

9 10 9 10))))

i. combien de chemins de longueur2des3às3? 012 ???3 ii. combien de chemins de longueur3des4às2?? ???2345 iii. combien de chemins de longueur4des2às3?? ???9101415 corrigé exercice 3 :

1. dessiner les graphes complets pourn= 2,n= 3,n= 4,n= 5

n= 2n= 3 s1s2 s1s2 s4 n= 4n= 5 s1s2 s4s3 s1s2 s4s3 s5

2. graphes simples d"ordresn= 2,n= 3,n= 4,n= 5dont tous les sommets sont de degré2

n= 2: il n"y en a pas n= 3 s1s2 s4 n= 4 s1s2 s4s3 n= 5 s1s2 s4s3 s5quotesdbs_dbs19.pdfusesText_25