Graphes exercices corriges bac tes Théorie des graphes

Théorie des graphes : Graphes exercices corriges bac tes

Télécharger PDF

Exercices corrigés sur les graphes (compilation de BAC TES)

Exercice n°1 : Randonnée dans les Alpes

1) a) Tableau des degrés des sommets :

Sommets : B, C, D, F, N, T

Degré des sommets : 2, 4, 4, 5, 3, 4

b) Le graphe est connexe car il existe un chemin entre chaque paire de sommets. Par exemple, la chaîne B-C-D-F-N-T relie tous les sommets.

2) Le groupe peut passer par les six sommets en empruntant chaque chemin une seule fois grâce à l'existence d'une chaîne eulérienne. En effet, le graphe possède exactement deux sommets de degré impair (F et N), ce qui permet une telle chaîne. Un exemple de trajet est : F-B-C-F-N-T-F-D-C-T-D-N.

3) a) Le nombre chromatique n est encadré par : 4 ≤ n ≤ 6.

b) Coloriage possible du graphe (algorithme glouton) :

Sommets : F, C, D, T, N, B

Couleurs : 1, 2, 3, 4, 2, 4

Le nombre chromatique est donc égal à 4.

4) La chaîne minimisant la distance entre B et N est B-C-T-N, de longueur 23 km.

Exercice n°2 : Excursions touristiques

1) Le graphe est connexe car il existe un chemin reliant chaque sommet. Par exemple, la chaîne A-B-C-D-E-F relie tous les sommets.

2) a) La plus courte chaîne reliant A à F est A-B-E-D-C-F (algorithme de Dijkstra).

b) Le temps de transport minimal est de 21 heures.

3) Ce graphe ne possède pas de chaîne eulérienne car il contient quatre sommets de degré impair (C, D, E, F). Aucun parcours ne peut emprunter toutes les routes une seule fois.

Exercice n°3 : Visite d'un musée

Première partie : Étude d'un graphe

1) a) Le graphe est connexe car il existe un chemin entre chaque paire de sommets.

b) Tableau des degrés :

Sommets : A, B, C, D, E, F, G, H, Y, Z

Degrés : 4, 4, 4, 4, 4, 2, 4, 2, 3, 1

c) Une chaîne eulérienne existe car seuls deux sommets (Y et Z) ont un degré impair.

2) a) Encadrement du nombre chromatique χ : 3 ≤ χ ≤ 5.

b) Le nombre chromatique est égal à 3. Coloriage possible :

Couleur 1 : A, E, G

Couleur 2 : B, C

Couleur 3 : D, F, H, Y, Z

Deuxième partie : Visite d'un musée

1) Le graphe représente les salles (sommets) et les portes (arêtes). Y est l'accueil et Z la boutique.

2) a) Un circuit passant par toutes les portes une seule fois existe car il y a exactement deux sommets de degré impair.

b) Exemple de circuit : Y-G-C-Y-A-C-D-G-H-E-D-B-E-F-B-A-Z.

3) Coloriage des salles avec un minimum de couleurs :

Couleur 1 : A, E, G

Couleur 2 : B, C

Couleur 3 : D, F, H, Y, Z

Exercice n°4 : Jardin pédagogique

Question préliminaire : Il y a 10 questionnaires (10 arêtes).

Partie A

1) Matrice G du graphe :

0 1 1 0 1 1

1 0 1 1 0 0

1 1 0 0 1 1

0 1 0 0 1 0

1 0 1 1 0 1

1 0 1 0 1 0

2) Le graphe est connexe mais pas complet (par exemple, E et F ne sont pas adjacents).

3) Tableau des degrés :

Sommets : A, B, C, D, E, F

Degrés : 4, 5, 3, 4, 2, 2

a) Impossible de parcourir le jardin en répondant à tous les questionnaires sans repasser deux fois devant le même, en commençant par n'importe quelle zone.

b) En commençant par la zone C, la dernière zone visitée sera B.

Partie B

1) Encadrement du nombre chromatique χ : 4 ≤ χ ≤ 6.

2) Le nombre chromatique est égal à 4. Répartition des couleurs :

Couleur 1 : B

Couleur 2 : A, D

Couleur 3 : C

Couleur 4 : E, F

Exercice n°5 : Compagnies maritimes

1) Graphe probabiliste avec deux sommets A et B, où :

Passer de A à B : 0,2

Rester dans A : 0,8

Passer de B à A : 0,1

Rester dans B : 0,9

2) Matrice de transition M :

0,8 0,2

0,1 0,9

3) État initial P₀ = (0,6 0,4).

P₁ = (0,52 0,48).

4) Répartition en 2011 : P₃ = (0,4248 0,5752).

5) État stable S = (1/3 2/3), interprété comme :

À long terme, 1/3 des habitants utiliseront la compagnie A et 2/3 la compagnie B.

6) Relation de récurrence : x_n+1 = 0,7x_n + 0,1.

7) Limite de la suite (x_n) : lim_n→+∞ x_n = 1/3.

Exercice n°6 : Parfums Aurore et Boréale

1) État initial P₀ = (0,2 0,8).

2) Graphe probabiliste avec deux sommets A et B, où :

Passer de A à B : 0,1

Rester dans A : 0,9

Passer de B à A : 0,15

Rester dans B : 0,85

3) a) Matrice de transition M :

0,9 0,1

0,15 0,85

b) P₁ = (0,3 0,7).

4) a) P_n = P₀ × Mⁿ.

b) P₃ = (0,43125 0,56875).

5) a) État stable P = (0,6 0,4).

b) À terme, le parfum Aurore sera préféré par 60% de la population.

Exercice n°7 : Probabilités de victoire en tennis

Première méthode : graphe probabiliste

1) Matrice de transition M :

0,4 0,6

0,9 0,1

2) Probabilité pour que A gagne la partie de la 4^ème semaine : 0,5875.

3) État stable P = (0,6 0,4).

Limite de la suite (a_n) : lim_n→+∞ a_n = 0,6.

Deuxième méthode : probabilité et suites

1) a) Arbre pondéré avec probabilités :

P(A₁) = 0,7

P(B₁) = 0,3

P(A₂|A₁) = 0,4

P(B₂|A₁) = 0,6

P(A₂|B₁) = 0,9

b) Relation de récurrence : a_n+1 = 0,9 - 0,5a_n.

2) a) Suite géométrique de raison -0,5.

b) Expression de a_n : a_n = 0,6 + 0,1 × (-0,5)^n-1.

Limite de la suite (a_n) : lim_n→+∞ a_n = 0,6.

FAQ

1) Qu'est-ce qu'un graphe connexe ?

Un graphe est dit connexe si, pour chaque paire de sommets, il existe au moins un chemin reliant ces deux sommets.

2) Comment déterminer le nombre chromatique d'un graphe ?

Le nombre chromatique est le plus petit nombre de couleurs nécessaires pour colorier les sommets d'un graphe de sorte que deux sommets adjacents n'aient pas la même couleur. On peut utiliser un algorithme glouton ou celui de Welch et Powell pour le déterminer.

3) Qu'est-ce qu'une chaîne eulérienne ?

Une chaîne eulérienne est un chemin qui passe par chaque arête du graphe exactement une fois. Elle existe si et seulement si le graphe est connexe et possède exactement zéro ou deux sommets de degré impair.