$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

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 :
Corrigé
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
Corrigé
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?
Corrigé
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é
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;
  • Benjamin ne parle plus à Adrien;
  • 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.
Corrigé
Enoncé
Cherchez le plus court chemin de $A$ à $K$ dans le graphe suivant. On détaillera les calculs.
Indication
Corrigé
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é