Loading [MathJax]/extensions/TeX/newcommand.js
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Mes commandes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\multirows}[3]{\multirow{#1}{#2}{$#3$}}%pour rester en mode math \renewcommand{\arraystretch}{1.3}%pour augmenter la taille des case \newcommand{\point}[1]{\marginnote{\small\vspace*{-1em} #1}}%pour indiquer les points ou le temps \newcommand{\dpl}[1]{\displaystyle{#1}}%megamode \newcommand{\A}{\mathscr{A}} \newcommand{\LN}{\mathscr{N}} \newcommand{\LL}{\mathscr{L}} \newcommand{\K}{\mathbb{K}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\M}{\mathcal{M}} \newcommand{\D}{\mathbb{D}} \newcommand{\E}{\mathcal{E}} \renewcommand{\P}{\mathcal{P}} \newcommand{\G}{\mathcal{G}} \newcommand{\Kk}{\mathcal{K}} \newcommand{\Cc}{\mathcal{C}} \newcommand{\Zz}{\mathcal{Z}} \newcommand{\Ss}{\mathcal{S}} \newcommand{\B}{\mathbb{B}} \newcommand{\inde}{\bot\!\!\!\bot} \newcommand{\Proba}{\mathbb{P}} \newcommand{\Esp}[1]{\dpl{\mathbb{E}\left(#1\right)}} \newcommand{\Var}[1]{\dpl{\mathbb{V}\left(#1\right)}} \newcommand{\Cov}[1]{\dpl{Cov\left(#1\right)}} \newcommand{\base}{\mathcal{B}} \newcommand{\Som}{\textbf{Som}} \newcommand{\Chain}{\textbf{Chain}} \newcommand{\Ar}{\textbf{Ar}} \newcommand{\Arc}{\textbf{Arc}} \newcommand{\Min}{\text{Min}} \newcommand{\Max}{\text{Max}} \newcommand{\Ker}{\text{Ker}} \renewcommand{\Im}{\text{Im}} \newcommand{\Sup}{\text{Sup}} \newcommand{\Inf}{\text{Inf}} \renewcommand{\det}{\texttt{det}} \newcommand{\GL}{\text{GL}} \newcommand{\crossmark}{\text{\ding{55}}} \renewcommand{\checkmark}{\text{\ding{51}}} \newcommand{\Card}{\sharp} \newcommand{\Surligne}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\SurligneMM}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \renewcommand{\lim}[1]{\underset{#1}{lim}\,} \newcommand{\nonor}[1]{\left|#1\right|} \newcommand{\Un}{1\!\!1} \newcommand{\sepon}{\setlength{\columnseprule}{0.5pt}} \newcommand{\sepoff}{\setlength{\columnseprule}{0pt}} \newcommand{\flux}{Flux} \newcommand{\Cpp}{\texttt{C++\ }} \newcommand{\Python}{\texttt{Python\ }} %\newcommand{\comb}[2]{\begin{pmatrix} #1\\ #2\end{pmatrix}} \newcommand{\comb}[2]{C_{#1}^{#2}} \newcommand{\arrang}[2]{A_{#1}^{#2}} \newcommand{\supp}[1]{Supp\left(#1\right)} \newcommand{\BB}{\mathcal{B}} \newcommand{\arc}[1]{\overset{\rotatebox{90}{)}}{#1}} \newcommand{\modpi}{\equiv_{2\pi}} \renewcommand{\Re}{Re} \renewcommand{\Im}{Im} \renewcommand{\bar}[1]{\overline{#1}} \newcommand{\mat}{\mathcal{M}} \newcommand{\und}[1]{{\mathbf{\color{red}\underline{#1}}}} \newcommand{\rdots}{\text{\reflectbox{$\ddots$}}} \newcommand{\Compa}{Compa} \newcommand{\dint}{\dpl{\int}} \newcommand{\intEFF}[2]{\left[\!\left[#1 ; #2\right]\!\right]} \newcommand{\intEFO}[2]{\left[\!\left[#1 ; #2\right[\!\right[} \newcommand{\intEOF}[2]{\left]\!\left]#1 ; #2\right]\!\right]} \newcommand{\intEOO}[2]{\left]\!\left]#1 ; #2\right[\!\right[} \newcommand{\ou}{\vee} \newcommand{\et}{\wedge} \newcommand{\non}{\neg} \newcommand{\implique}{\Rightarrow} \newcommand{\equivalent}{\Leftrightarrow} \newcommand{\Ab}{\overline{A}} \newcommand{\Bb}{\overline{B}} \newcommand{\Cb}{\overline{C}} \newcommand{\Cl}{\texttt{Cl}} \newcommand{\ab}{\overline{a}} \newcommand{\bb}{\overline{b}} \newcommand{\cb}{\overline{c}} \newcommand{\Rel}{\mathcal{R}} \newcommand{\superepsilon}{\varepsilon\!\!\varepsilon} \newcommand{\supere}{e\!\!e} \makeatletter \newenvironment{console}{\noindent\color{white}\begin{lrbox}{\@tempboxa}\begin{minipage}{\columnwidth} \ttfamily \bfseries\vspace*{0.5cm}} {\vspace*{0.5cm}\end{minipage}\end{lrbox}\colorbox{black}{\usebox{\@tempboxa}} } \makeatother \def\ie{\textit{i.e. }} \def\cf{\textit{c.f. }} \def\vide{ { $ {\text{ }} $ } } %Commande pour les vecteurs \newcommand{\grad}{\overrightarrow{Grad}} \newcommand{\Vv}{\overrightarrow{v}} \newcommand{\Vu}{\overrightarrow{u}} \newcommand{\Vw}{\overrightarrow{w}} \newcommand{\Vup}{\overrightarrow{u'}} \newcommand{\Zero}{\overrightarrow{0}} \newcommand{\Vx}{\overrightarrow{x}} \newcommand{\Vy}{\overrightarrow{y}} \newcommand{\Vz}{\overrightarrow{z}} \newcommand{\Vt}{\overrightarrow{t}} \newcommand{\Va}{\overrightarrow{a}} \newcommand{\Vb}{\overrightarrow{b}} \newcommand{\Vc}{\overrightarrow{c}} \newcommand{\Vd}{\overrightarrow{d}} \newcommand{\Ve}[1]{\overrightarrow{e_{#1}}} \newcommand{\Vf}[1]{\overrightarrow{f_{#1}}} \newcommand{\Vn}{\overrightarrow{0}} \newcommand{\Mat}{Mat} \newcommand{\Pass}{Pass} \newcommand{\mkF}{\mathfrak{F}} \renewcommand{\sp}{Sp} \newcommand{\Co}{Co} \newcommand{\vect}[1]{\texttt{Vect}\dpl{\left( #1\right)}} \newcommand{\prodscal}[2]{\dpl{\left\langle #1\left|\vphantom{#1 #2}\right. #2\right\rangle}} \newcommand{\trans}[1]{{\vphantom{#1}}^{t}{#1}} \newcommand{\ortho}[1]{{#1}^{\bot}} \newcommand{\oplusbot}{\overset{\bot}{\oplus}} \SelectTips{cm}{12}%Change le bout des flèches dans un xymatrix \newcommand{\pourDES}[8]{ \begin{itemize} \item Pour la ligne : le premier et dernier caractère forment $#1#2$ soit $#4$ en base 10. \item Pour la colonne : les autres caractères du bloc forment $#3$ soit $#5$ en base 10. \item A l'intersection de la ligne $#4+1$ et de la colonne $#5+1$ de $S_{#8}$ se trouve l'entier $#6$ qui, codé sur $4$ bits, est \textbf{\texttt{$#7$}}. \end{itemize} }
Accueil
Accueil
Connexion
Connexion
Liste des cours
Liste des cours
Exercices
Exercices
Projets
Projets
Département SD
Département SD
How To
How To
Exercice

L'exercice suivant est automatiquement et aléatoirement généré par ataraXy.
Si vous regénérez la page (F5) les valeurs seront changées.
La correction se trouve en bas de page.

Exercice


La Baie des naufragés est une île forteresse, bastion des seigneurs pirates. Elle peut subir un siège pendant plusieurs années ! Cette île est entourées par 8 îles plus petite et un peu moins imprenables. Chacune de ces îles est sous l'autorité d'un seigneur pirate - il y a 9 seigneurs pirates, un par île, le roi des pirates étant dans la baie des naufragés. Certaines voies de navigation ne sont jamais utilisées à cause des dangers qu'elles représentent (Kraken, Maëlstrom, Salazar, etc). La situation se modélise par un graphe métrique dont les sommets représentent les îles de l'archipel, les arêtes les voies de navigation utilisées par les pirates et la métrique la distance entre les îles correspondantes en centaine de kilomètre. Voici une représentation sagittale de ce graphe. La baie des naufragés est le sommet x_{5} .\xymatrix@C=1.919cm@R=0.919cm{ &&&x_{1}\ar@{-}@/_7pc/[llldddd]|-{\boxed{4}}\ar@{-}@/^7pc/[rrrrdddd]|-{\boxed{4}}\ar@{-}@/^5pc/[rrrdddddd]|-{\boxed{2}}\ar@{-}@/^4pc/[ddddddd]|-{\boxed{5}}&&&&\\ &x_{2}\ar@{-}[lddd]|-{\boxed{3}}\ar@{-}@/^3pc/[rrrrrrddd]|-{\boxed{3}}\ar@{-}@/_4pc/[dddddrrrrr]|-{\boxed{9}}\ar@{-}@/_1pc/[rrdddddd]|-{\boxed{6}}&&&&&x_{3}\ar@{-}@/_3pc/[llllllddd]|-{\boxed{6}}\ar@{-}[rddd]|-{\boxed{8}}\ar@{-}[ddddddlll]|-{\boxed{3}}&\\ &&&&&&&\\ &&&&&&&\\ x_{4}\ar@{-}@/^0.5pc/[rrr]|-{\boxed{1}}\ar@{-}@/_4pc/[rrrrrrdd]|-{\boxed{1}}&&&x_{5}\ar@{-}@/^1pc/[lldd]|-{\boxed{1}}\ar@{-}[rrrdd]|-{\boxed{5}}\ar@{-}[ddd]|-{\boxed{7}}&&&&x_{6}\ar@{-}[ldd]|-{\boxed{9}}\\ &&&&&&&\\ &x_{7}\ar@{-}@/_5pc/[rrrrr]|-{\boxed{8}}\ar@{-}[rrd]|-{\boxed{4}}&&&&&x_{8}&\\ &&&x_{9}&&&& }

Première partie.
Résultats préliminaires
  1. Donner la représentation matricielle du
    graphe. On pourra faire apparaitre la
    métrique dans la matrice. \begin{array}{c||c|c|c|c|c|c|c|c|c} &x_{1}&x_{2}&x_{3}&x_{4}&x_{5}&x_{6}&x_{7}&x_{8}&x_{9}\\\hline\hline x_{1}&&&&&&&&&\\\hline x_{2}&&&&&&&&&\\\hline x_{3}&&&&&&&&&\\\hline x_{4}&&&&&&&&&\\\hline x_{5}&&&&&&&&&\\\hline x_{6}&&&&&&&&&\\\hline x_{7}&&&&&&&&&\\\hline x_{8}&&&&&&&&&\\\hline x_{9}&&&&&&&&& \end{array}
  2. Compléter ce tableau en appliquant l'algorithme de Prim (initialisé en x_{5} de préférence), comme nous l'avons vu en cours. \begin{array}{|c||c|c|c|c|c|c|c|c|c|}\hline &x_{1}&x_{2}&x_{3}&x_{4}&x_{5}&x_{6}&x_{7}&x_{8}&x_{9}\\\hline\hline &&&&&&&&&\\\hline &&&&&&&&&\\\hline &&&&&&&&&\\\hline &&&&&&&&&\\\hline &&&&&&&&&\\\hline &&&&&&&&&\\\hline &&&&&&&&&\\\hline &&&&&&&&&\\\hline &&&&&&&&&\\\hline \end{array}
    1. Compléter le tableau suivant en indiquant le degrés de chaque sommet. \begin{array}{|r||c|c|c|c|c|c|c|c|c|}\hline \bullet&x_{1}&x_{2}&x_{3}&x_{4}&x_{5}&x_{6}&x_{7}&x_{8}&x_{9}\\\hline d^{+1}(\bullet) & & & & & & & & & \\\hline \end{array}
    2. Appliquer l'algorithme de Brelaz. \begin{array}{|r||c|c|c|c|c|c|c|c|c|}\hline &&&&&&&&&\\\hline\hline DSAT_1&&&&&&&&&\\\hline DSAT_2&&&&&&&&&\\\hline DSAT_3&&&&&&&&&\\\hline DSAT_4&&&&&&&&&\\\hline DSAT_5&&&&&&&&&\\\hline DSAT_6&&&&&&&&&\\\hline DSAT_7&&&&&&&&&\\\hline DSAT_8&&&&&&&&&\\\hline DSAT_9&&&&&&&&&\\\hline\hline Coul&&&&&&&&&\\\hline \end{array}
    3. Quelle est la valeur exacte du nombre chromatique de ce graphe.

Seconde partie.
L'histoire.
  1. Sparrow, le capitaine Jack Sparrow, a découvert que la compagnie des indes prépare un sale coup dans l'archipel. Il décide de tendre un piège à lord Cutler Beckectt, capitaine de la compagnie des indes dans le pacifique, responsable du mauvais coup en préparation, en plaçant des mines sur les voies de navigation. Bien que Sparrow puisse se souvenir quelle voie de navigation il a piégé, l'abus de rhum ne lui permet pas de souvenir ou il a posé les mines. Pour éviter de faire exploser son navire (le black pearl), il décide de ne passer qu'une et une seule fois par chaque voie. Il veut partir de son île, la x_{1} et revenir à son île. A cette fin, il peut même éventuellement affronter des dangers et donc emprunter des voies de navigation dangereuses (des arêtes inexistantes). Expliquer quel trajet Sparrow doit suivre.
  2. Bien que les îles appartiennent exclusivement aux seigneurs pirates qui y vivent, les voies de navigation n'appartiennent à personne (ou tout le monde). Ceci a crée des tensions parmi les seigneurs pirate de sorte que deux seigneurs dont les îles sont reliés par une voie de navigation se déteste royalement. Royale, c'est ce dont il est question aujourd'hui puisque les seigneurs pirates sont tous réunis à la baie des naufragés pour élire un nouveau roi. Chaque seigneur nome un seigneur et en général il se choisi lui même ce qui rend l'élection assez compliqué. Mais un des seigneur pirate, la capitaine Elisabeth Swan, a réussi à convaincre tous les seigneurs de voter au moins pour un pirate qu'ils ne détestent pas ce qui a donné naissance à des groupes de pirates "qui ne se détestent pas". Combien de ces groupes existe-t-il au minimum ? Quel groupe à la plus de chance d'avoir le roi des pirates ?
  3. Le nouveau roi des pirates, qui est en fait une reine (Elisabeth Swan), décide d'illuminer certaines voies de navigation en installant des "bateaux phares" (qui sont de simple épaves enflammées). Elle impose les contraintes suivantes :
    • Chaque île doit avoir au moins une voie illuminées menant à elle.
    • Il y a un "bateau phare" tous les 50 kilomètres.
    • Chaque "bateau phare" coute 100 pièces d'or
    • Il doit être possible, à partir de n'importe quelle île, d'atteindre n'importe quelle autre en n'empruntant que des voies de navigations illuminées.
    Bien sur, la reine souhaite que ça coute le moins cher possible. Quelles sont les voies devant être enflammées et quel sera le coût ?
Cliquer ici pour afficher la solution