Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Corrigé Devoir Maison Chapitre I : Introduction à la théorie des Graphes INFORM

Corrigé Devoir Maison Chapitre I : Introduction à la théorie des Graphes INFORMATIQUE S3 2020/2021 Soit le graphe G(X,U) suivant: 1- Donner Γ+(a) , Γ+(c) , Γ-(e) et Γ(f) 2- Le graphe G, est-il connexe? 3- Le graphe G est-il fortement connexe? 4- Combien le graphe G comporte-t-il de composantes connexes? Lesquelles? 5- Combien le graphe G comporte-t-il de composantes fortement connexes? Lesquelles? 6- Donner un exemple de chemin simple, de chemin élémentaire, de chemin simple et non élémentaire, de chemin non simple et de chemin non élémentaire. 7- Dessiner le sous-graphe engendré par les sommets (b, d, e et f). Est-il connexe? Est-il fortement connexe? 8- Dessiner un sous-graphe partiel engendré par les sommets (b, d, e et f). Est-il connexe? combien comporte-t-il de composantes connexes? Chapitre I: Introduction à la théorie des Graphes e d a c b f Exercice N°01: Devoir maison (Révision) Soit le graphe G(X,U) suivant: 1- Donner Γ+(a) , Γ+(c) , Γ-(e) et Γ(f) Γ+(a) = Succ(a) : l’ensemble des successeurs du sommet « a ». Γ+(a) = {d, f} Γ+(c) = {b, a} Γ-(e) = Pred(e) : l’ensemble des prédécesseurs du sommet « e ». Γ-(e) = {d, f} Γ(f) = Γ+(f) U Γ- (f) Γ(f) = {e} U {b, a} = {a, b, e} Chapitre I: Introduction à la théorie des Graphes e d a c b f Exercice N°01: Devoir maison (Révision) Soit le graphe G(X,U) suivant: 2- Le graphe G, est-il connexe? Oui, car il existe une chaîne reliant chaque paire de sommets 3- Le graphe G est-il fortement connexe? (il faut vérifier qu’il existe un chemin entre chaque deux sommets) Chapitre I: Introduction à la théorie des Graphes e d a c b f Exercice N°01: Devoir maison (Révision) a σ b  oui a σ c  oui a σ d  oui a σ e  oui a σ f  oui b σ a  oui b σ c  oui b σ d  oui b σ e  oui b σ f  oui c σ a  oui c σ b  oui c σ d  oui c σ e  oui c σ f  oui d σ a  oui d σ b  oui d σ c  oui d σ e  oui d σ f  oui e σ a  oui e σ b  oui e σ c  oui e σ d  oui e σ f  oui f σ a  oui f σ b  oui f σ c  oui f σ d  oui f σ e  oui Il existe un chemin reliant chaque deux sommets  le graphe est fortement connexe Soit le graphe G(X,U) suivant: 4- Combien le graphe G comporte-t-il de composantes connexes? Lesquelles? Le graphe est connexe  il comporte une seule composante connexe, c’est le graphe G. 5- Combien le graphe G comporte-t-il de composantes fortement connexes? Lesquelles? Le graphe est fortement connexe  il comporte une seule composante fortement connexe, c’est le graphe G. Chapitre I: Introduction à la théorie des Graphes e d a c b f Exercice N°01: Devoir maison (Révision) Soit le graphe G(X,U) suivant: 6- Donner un exemple de chemin simple, de chemin élémentaire, de chemin simple et non élémentaire, de chemin non simple et de chemin non simple et non élémentaire. c, ca, a, af, f, fe, e c, ca, a, af, f, fe, e c, ca, a, af, f, fe, e, ea, a, ad, d c, ca, a, ad, d, dc, c, ca, a, af, f c, cb, b, ba, a, ad, d, dc, c, cb, b Chapitre I: Introduction à la théorie des Graphes e d a c b f Exercice N°01: Devoir maison (Révision) Chemin simple  pas de répétition d’arcs Chemin élémentaire  pas de répétition de sommets Un chemin élémentaire est forcément simple Soit le graphe G(X,U) suivant: 7- Dessiner le sous-graphe engendré par les sommets (b, d, e et f). Est-il connexe? Oui, chaque paire de sommets est reliée par une chaîne. Est-il fortement connexe? Non, il n’y a pas de chemin reliant par exemple: b et d. 8- Dessiner un sous-graphe partiel engendré par les sommets (b, d, e et f). Il faut supprimer au moins un arc. Chapitre I: Introduction à la théorie des Graphes e d a c b f Exercice N°01: Devoir maison (Révision) e d b f X Soit le graphe G(X,U) suivant: 7- Dessiner le sous-graphe engendré par les sommets (b, d, e et f). Est-il connexe? Oui, chaque paire de sommets est reliée par une chaîne. Est-il fortement connexe? Non, il n’y a pas de chemin reliant par exemple: b et d. 8- Dessiner un sous-graphe partiel engendré par les sommets (b, d, e et f). Il faut supprimer au moins un arc. Est-il connexe? Non, les deux sommets b et d ne sont pas reliés par une chaîne. Combien comporte-t-il de composantes connexes? Chapitre I: Introduction à la théorie des Graphes e d a c b f Exercice N°01: Devoir maison (Révision) e d b f Il y’ a deux composantes connexes Soit le graphe G(X, E) 1- Ce graphe, est-il biparti? Justifier. 2-Donner δ(G) et Δ(G). Que pouvez-vous en conclure. 3- Ce graphe, est-il complet? Justifier. 4- Dessiner un sous-graphe partiel engendré par les sommets (1, 3, 5 et 8). Est-il connexe? combien comporte-t-il de composantes connexes? 5- Donner un exemple de chaîne de longueur 4 et d’un cycle de longueur 8. 6- Transformer les arêtes de ce graphe en arcs de sorte qu’il devienne fortement connexe. Chapitre I: Introduction à la théorie des Graphes Exercice N°02: Devoir maison (Révision) Soit le graphe G(X, E) 1- Ce graphe, est-il biparti? Justifier. Oui, on a deux sous-ensembles de sommets tels que les sommets de chaque sous- ensembles ne sont pas reliés entre eux mais avec les sommets de l’autre sous- ensemble. X1 ∩ X2 = ø et X1 U X2 = X Chapitre I: Introduction à la théorie des Graphes Exercice N°02: Devoir maison (Révision) 1 2 4 3 6 5 7 X1 = {1, 4, 5, 8} X2 = {2, 3, 6, 7} 8 Soit le graphe G(X, E) 2-Donner δ(G) et Δ(G). Que pouvez-vous en conclure. δ(G) : Le degré minimal du graphe δ(G) = 3 et Δ(G) : Le degré maximal du graphe Δ(G) = 3  On conclut que ce graphe est 3-régulier 3- Ce graphe, est-il complet? Justifier. Non, pour qu’il soit complet il faut que pour tout x le d(x) = n – 1 (n: le nombre de sommets) / (Remarque : Le graphe est simple) or il existe un sommet (1, par exemple) dont le degré (d(1) = 3 < 7 ) Chapitre I: Introduction à la théorie des Graphes Exercice N°02: Devoir maison (Révision) Soit le graphe G(X, E) 4- Dessiner un sous-graphe partiel engendré par les sommets (1, 3, 5 et 8). Est-il connexe? Chapitre I: Introduction à la théorie des Graphes Exercice N°02: Devoir maison (Révision) 1 3 5 8 X Soit le graphe G(X, E) 4- Dessiner un sous-graphe partiel engendré par les sommets (1, 3, 5 et 8). Est-il connexe? Non, les deux sommets 1 et 3 ne sont pas reliés par une chaîne. Combien comporte-t-il de composantes connexes? Il comporte 3 composantes connexes Chapitre I: Introduction à la théorie des Graphes Exercice N°02: Devoir maison (Révision) 1 3 5 8 Soit le graphe G(X, E) 5- Donner un exemple de chaîne de longueur 4 et d’un cycle de longueur 8. 1, 1-3, 3, 3-4, 4, 4-6, 6, 6-8, 8 :longueur = nombre d’arêtes 1, 1-7, 7, 7-5, 5, 5-6, 6, 6-8, 8, 8-2, 2, 2-4, 4, 4-3, 3, 3-1, 1 6- Transformer les arêtes de ce graphe en arcs de sorte qu’il devienne fortement connexe. Chapitre I: Introduction à la théorie des Graphes Exercice N°02: Devoir maison (Révision) 1 2 4 3 6 5 7 8 1- Est-il possible de relier 15 sommets de sorte que chaque sommet soit relié avec exactement trois autres ? Le degré de chaque sommet est : 3. donc la somme de tous les degrés est égale à 3 * 15 = 45 45 est impair  impossible de tracer ce graphe La somme des degrés = 2 * nombre d’arêtes  toujours paire 2- Existe-t-il un graphe simple d’ordre 5 dont les sommets ont les degrés suivants ? Si oui, tracer un tel graphe : a. 3, 3, 3, 3, 2 b. 1, 2, 3, 4, 5 3- Combien y-a-t-il de sommets dans un graphe régulier de degré 4 ayant 10 arêtes ? On a ∑ d(x) = 2 |E| Graphe régulier  Tous les sommets ont le même degré Chapitre I: Introduction à la théorie des Graphes Exercice N°03: Devoir maison (Révision)  La somme des degrés est pair  Oui  La somme des degrés est impair  Non 4 * nb_sommets = 2 * 10 Nb_sommets = 5 On représente sur uploads/Philosophie/ corrige-infoooo 1 .pdf