[PDF] graphes PDF graphes.pdf

1 4 corrigés exercices 2 graphe connexe, trajet Eulérien et algorithme d'Euler 19 2 1 activités 5 graphe probabiliste, matrice de transition, état stable 47

1 Représenter la situation par un graphe probabiliste de sommets A et B 2 Écrire la matrice de transition M de ce graphe en prenant les sommets

[PDF] Exercices : graphes probabilistes - Normale Sup

Exercices : graphes probabilistes Exercice 1 (Nouvelle-Calédonie, Novembre 2006, 5 points) Une association sportive propose à ses adhérents de pratiquer

[PDF] graphes

1 4 corrigés exercices 2 graphe connexe, trajet Eulérien et algorithme d'Euler 19 2 1 activités 5 graphe probabiliste, matrice de transition, état stable 47

[PDF] Correction des exercices sur les graphes probabilistes (état stable

Correction des exercices sur les graphes probabilistes (état stable) : feuille no 1 (a) Voilà un graphe probabiliste traduisant les données de l'énoncé : A B

[PDF] PDF 2 - Maths Bordeaux

D Corrigés des exercices d'un graphe probabiliste à 2 ou 3 sommets graphes : sommets, sommets adjacents, arêtes, degré d'un sommet, ordre

[PDF] Baccalauréat ES spécialité Index des exercices avec des graphes

Représenter la situation par un graphe probabiliste de sommets A et B 2 Écrire la matrice de transition M associée à ce graphe en prenant les sommets dans

[PDF] Corrigé Exercice 3 Centres Étrangers Bac ES - Freemaths

Exercice 3 Corrigé Le sujet est composé de 4 exercices indépendants le candidat A On représente ce modèle par un graphe probabiliste (G) de sommets

[PDF] CORRIGÉ DEVOIR SURVEILLÉ N° 5 TERMINALE - Dominique Frin

CORRIGÉ DEVOIR SURVEILLÉ N° 5 TERMINALE ES spé EXERCICE 1 : Dans le 1 a) Le graphe probabiliste de sommets A et B décrivant la situation :

[PDF] Exercices

La théorie des graphes est rarement abordée en France dans le cursus universitaire Contenu : graphe probabiliste ; matrice de transition ; état probabiliste

[PDF] Suite de Matrices - Spé Maths Évolution - Arbre et Graphe

Évolution - Arbre et Graphe probabiliste Exercices Corrigés en vidéo avec le cours sur avec des probabilités données par le graphe probabiliste ci-dessous

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

[PDF] [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

Σd=total de participations

Σa=total de matchs

1. (a)

2matchs chacune

A(2)B(2)

Σd=participations...

Σa=matchs...

1match chacune

A(1)B(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)