Remerciez-le!

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

Bibm@th.net Rechercher sur le site... Bibm@th Rechercher sur le site... Accueil

Bibm@th.net Rechercher sur le site... Bibm@th Rechercher sur le site... Accueil Ressources Bibliothèques Références Thèmes Forum Bibliothèque d'exercicesBibliothèque de problèmes Accueil Ressources Collège Math Sup Math Spé Capes Agreg interne BTS Bibliothèques Bibliothèque d'exercices Bibliothèque de problèmes Références Dictionnaire Biographie de mathématiciens Formulaire Lexique français/anglais Thèmes Cryptographie et codes secrets Jeux et énigmes Carrés magiques Mathématiques au quotidien Dossiers Forum Ressources mathématiques > Exercices de théorie des graphes et d'algorithmique > Accéder à mon compte > Accéder à ma feuille d'exercices > Exercices corrigés - Théorie des graphes - exercices pratiques Exercice 1 - Est-ce le même graphe? [Signaler une erreur] [Ajouter à ma feuille d'exos] Enoncé Dire parmi les dessins suivants lesquels représentent le même graphe : Exercices corrigés -Théorie des graphes - exerci... http://www.bibmath.net/ressources/index.php?a... 1 of 6 1/30/18, 1:15 AM Indication Corrigé Les deux premiers dessins représentent le même graphe. Il s'agit d'un pentagone où tous les sommets sont reliés à trois autres (pour former un cycle), sauf un sommet qui lui est relié à tous les autres. Les troisième et quatrième dessins ne représentent pas le même graphe. Par exemple, le troisième admet un cycle d'ordre 3, ce qui n'est pas le cas du quatrième. Exercice 2 - Sans lever le crayon [Signaler une erreur] [Ajouter à ma feuille d'exos] Enoncé On considère le dessin suivant : Est-il possible de le dessiner sans lever le crayon et en passant une, et une seule fois, par chaque trait? Indication Exercices corrigés -Théorie des graphes - exerci... http://www.bibmath.net/ressources/index.php?a... 2 of 6 1/30/18, 1:15 AM Corrigé Si on considère que ceci représente un graphe, on cherche à tracer un chemin eulérien dans ce graphe. D'après le théorème d'Euler, c'est possible si et seulement si tous les sommets sont de degré pair, sauf au plus. Donnons un nom aux sommets, comme sur le dessin suivant : Alors les sommets et sont de degré 3. C'est donc impossible! Exercice 3 - Choix d'options [Signaler une erreur] [Ajouter à ma feuille d'exos] Enoncé A un examen, les candidats peuvent choisir 2 ou 3 options parmi les 6 options proposées : graphes, vélo, langue régionale, guitare, latin et natation. Certains élèves ont choisi les options graphes, langue régionale, guitare. D'autres vélo et latin; D'autres enfin langue régionale et natation. Les élèves passent au plus une épreuve chaque jour. A l'aide de la théorie des graphes, répondez aux questions suivantes : 1. Combien peut-on programmer d'épreuves d'option au maximum dans une journée? 2. Quelle est la durée minimum de l'ensemble des épreuves optionnelles? Indication Corrigé On va associer un graphe à ce problème, où les sommets sont les options possibles, et où il y a une arête entre deux sommets si et seulement si ces deux options sont choisies simultanément par au moins un étudiant. On obtient le graphe suivant (on a renuméroté en A,B,C,D,E,F les 6 options, dans l'ordre). 1. D'après le graphe, on voit qu'on peut proposer jusque 3 options dans la même journée, par exemple. 2. On obtient le nombre de journées nécessaires en calculant le nombre chromatique du graphe (une couleur donnée à un sommet signifie que les épreuves ayant cette couleur ont lieu le même jour). Ici, notre graphe contient le graphe complet à 3 sommets. Son nombre chromatique est donc au moins égal à 3. En fait, il lui est exactement égal. Par exemple On donne à et ; On donne à et ; On donne à . Exercice 4 - Transports dangeureux [Signaler une erreur] [Ajouter à ma feuille d'exos] Enoncé Une société doit transporter par camions six produits chimiques, notés P1,...,P6, depuis l'usine de production jusqu'à l'entreprise utilisatrice. Pour des raisons de sécurité, certains produits ne peuvent pas être transportés ensemble : P1 et P2, P1 et P4, P2 et P3, P2 et P5, P3 et P4, P5 et P6. Déterminer le nombre minimum de camions nécessaires. Indication Corrigé On introduit le graphe dont les sommets sont les produits, et une arête joint deux sommets si on ne peut pas les transporter simultanément. On obtient le graphe suivant : On cherche le nombre chromatique de ce graphe, que l'on peut calculer avec l'algorithme de Welch et Powell par exemple. On ordonne les sommets par degré décroissant, par exemple P2, P1, P3, P4, P5, P6. Puis on attribue une première couleur à P2, P4 et P6; A, E B A, B, F C1 A, B F C2 C E C3 D Exercices corrigés -Théorie des graphes - exerci... http://www.bibmath.net/ressources/index.php?a... 3 of 6 1/30/18, 1:15 AM une seconde couleur à P1, P3, P5. Le nombre chromatique du graphe est au plus 2, et c'est en fait exactement 2 (on ne peut pas colorier avec la même couleur P1 et P2). Il faut donc au minimum deux camions pour tout transporter. Exercice 5 - Incompatibilité d'humeur [Signaler une erreur] [Ajouter à ma feuille d'exos] Enoncé Huit jeunes hommes veulent travailler dans un supermarché dans lequel trois postes sont disponibles. Le responsable, soucieux d'éviter les problèmes, veut tenir compte des inimitiés entre ces jeunes hommes : Adrien ne peut supporter Damien et Cyril; Cyril refuse de travailler avec Benjamin; Damien ne supporte pas Greg; Eric ne veut cotoyer ni Benjamin, ni Frank, ni Hector; Frank n'apprécie pas Greg et Hector; Greg ne s'entend pas avec Adrien; Hector refuse de travailler avec Frank ou Cyril. 1. Construire un graphe non-orienté traduisant cette situation d'incompatibilité d'humeur. 2. Eric a le meilleur CV. Qui peut-on embaucher avec lui? 3. Donner une autre combinaison possible de trois jeunes, autres qu'Eric, que l'on peut embaucher. Indication Corrigé 1. Le graphe est formé de 8 sommets A,B,C,D,E,F ,G,H qui représentent les 8 jeunes hommes et d'arêtes qui expriment les incompatibilités d'humeur. On obtient alors le graphe suivant : 2. Il faut embaucher deux personnes qui ne sont pas reliées à Éric, et qui ne sont pas reliées entre elles. Par exemple, ici on peut embaucher aussi Adrien et Cyril (ce n'est pas le seul choix possible, on aurait pu aussi recruter Cyril et Greg par exemple). 3. Là encore, il faut trouver 3 sommets qui n'ont aucune arête entre eux. C'est le cas par exemple de A, C et F . On aurait pu aussi faire une coloration du graphe, et trouver 3 sommets qui sont colorés et de la même couleur. Exercice 6 - Plus court chemin [Signaler une erreur] [Ajouter à ma feuille d'exos] Enoncé Cherchez le plus court chemin de à dans le graphe suivant. On détaillera les calculs. Indication Corrigé A K Exercices corrigés -Théorie des graphes - exerci... http://www.bibmath.net/ressources/index.php?a... 4 of 6 1/30/18, 1:15 AM On applique l'algorithme de Dijkstra, et on obtient le tableau suivant : La longueur de à est donc égale à 45, et le plus court chemin est . Exercice 7 - Homme, femme et maitresse [Signaler une erreur] [Ajouter à ma feuille d'exos] Enoncé Un homme, sa femme jalouse et sa maîtresse souhaitent traverser une rivière. Mais la barque du passeur est trop petite, et il ne peut transporter que deux personnes à la fois. Comment faire, sachant que la femme jalouse ne veut pas que son mari et la maîtresse soient seuls sur une rive, et que l'homme ne veut pas que sa femme et se maitresse soient seules sur une rive? Indication Corrigé On va modéliser la situation par un graphe dont les sommets sont toutes les situations possibles. On désigne par P le passeur, par H l'homme, par F la femme et par M la maitresse. Le sommet (PM/HF) signifie que sur la première rive on a le passeur et la maîtresse, et sur la rive d'arrivée, on a l'homme et sa femme. On n'inscrit pas les sommets prohibés, comme (PF/HM) et (PF/FM). Il y a une arête entre deux sommets si on peut passer d'une situation à l'autre par une traversée de barque. Le problème est de savoir s'il y a un chemin entre le sommet (PHFM/) et le sommet (/PHFM). Le graphe que l'on obtient est : Il est effectivement possible de trouver un chemin entre les deux sommets voulus, il est matérialisé sur le graphe par des traits en pointillés. Remarquons que dans un cadre plus compliqué, comprenant plus de sommets, on pourrait automatiser la recherche de l'existence d'un chemin en introduisant la matrice d'adjacence et en calculant ses puissances successives. Discussions des forums Résolubilité d'une équati … Peut-on m'expliquer certa … crible en python Comment calculer l'angle … démonstration: condition … Solution généralisée des … Cryptographie Fonctions dérivées série entière l'arithémtique de Peano s … Dm de maths 1*S fonctions Exercice 1 S equation de la physique m … Aide pour chiffrage avec … problème 4eme nombre divisible Accéder aux forums A 0 B ∞ 4 3(C) C ∞ 1(A) D ∞ ∞ 8 8(B) E ∞ ∞ 10 10 10(F) F ∞ ∞ 8 6(B) G ∞ ∞ ∞ ∞ 16 16 15(E) H ∞ ∞ ∞ ∞ ∞ ∞ 42 42 42 36(I) I ∞ ∞ ∞ ∞ ∞ ∞ 30 30 28(J) J ∞ ∞ ∞ ∞ uploads/s3/ theorie-des-graphes-exercices-pratiques.pdf