Ataraxy

\( %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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} } \)

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@{-}[lld]|-{\boxed{3}}\ar@{-}[dddd]|-{\boxed{7}}\ar@{-}@/^7pc/[rrrrdddd]|-{\boxed{9}}&&&&\\ &x_{2}\ar@{-}[lddd]|-{\boxed{1}}\ar@{-}@/^1pc/[rrddd]|-{\boxed{8}}\ar@{-}@/^3pc/[rrrrrrddd]|-{\boxed{2}}\ar@{-}@/_4pc/[dddddrrrrr]|-{\boxed{1}}\ar@{-}@/_1pc/[rrdddddd]|-{\boxed{5}}&&&&&x_{3}\ar@{-}@/_3pc/[llllllddd]|-{\boxed{8}}\ar@{-}@/^1.5pc/[lllddd]|-{\boxed{8}}\ar@{-}@/_2pc/[lllllddddd]|-{\boxed{6}}\ar@{-}[ddddd]|-{\boxed{5}}\ar@{-}[ddddddlll]|-{\boxed{1}}&\\ &&&&&&&\\ &&&&&&&\\ x_{4}\ar@{-}@/^5pc/[rrrrrrr]|-{\boxed{8}}&&&x_{5}\ar@{-}@/^1pc/[lldd]|-{\boxed{5}}\ar@{-}[ddd]|-{\boxed{6}}&&&&x_{6}\ar@{-}@/^2pc/[lllllldd]|-{\boxed{3}}\ar@{-}[ldd]|-{\boxed{9}}\ar@{-}@/^5pc/[llllddd]|-{\boxed{2}}\\ &&&&&&&\\ &x_{7}\ar@{-}@/_5pc/[rrrrr]|-{\boxed{7}}&&&&&x_{8}\ar@{-}@/^1pc/[llld]|-{\boxed{1}}&\\ &&&x_{9}&&&& }\]

Première partie.

Résultats préliminaires

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} \]
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.

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.
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 ?
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

Exercice

Première partie.

\[\begin{array}{c||ccccccccc} & x_{1} & x_{2} & x_{3} & x_{4} & x_{5} & x_{6} & x_{7} & x_{8} & x_{9} \\\hline\hline x_{1} & 0 & 3 & 0 & 0 & 7 & 9 & 0 & 0 & 0\\ x_{2} & 3 & 0 & 0 & 1 & 8 & 2 & 0 & 1 & 5\\ x_{3} & 0 & 0 & 0 & 8 & 8 & 0 & 6 & 5 & 1\\ x_{4} & 0 & 1 & 8 & 0 & 0 & 8 & 0 & 0 & 0\\ x_{5} & 7 & 8 & 8 & 0 & 0 & 0 & 5 & 0 & 6\\ x_{6} & 9 & 2 & 0 & 8 & 0 & 0 & 3 & 9 & 2\\ x_{7} & 0 & 0 & 6 & 0 & 5 & 3 & 0 & 7 & 0\\ x_{8} & 0 & 1 & 5 & 0 & 0 & 9 & 7 & 0 & 1\\ x_{9} & 0 & 5 & 1 & 0 & 6 & 2 & 0 & 1 & 0\end{array}\]
\[\begin{array}{|c|*{9}{c|}}\hline Som & x_{1} & x_{2} & x_{3} & x_{4} & x_{5} & x_{6} & x_{7} & x_{8} & x_{9} \\\hline Init & & & & & \boxed{0} & & & & \\\hline x_{5} & 7 & 8 & 8 & & X & & \boxed{5} & & 6\\\hline x_{7} & 7 & 8 & 6 & & X & \boxed{3} & X & 7 & 6\\\hline x_{6} & 7 & \boxed{2} & 6 & 8 & X & X & X & 7 & 2\\\hline x_{2} & \boxed{3} & X & 6 & \boxed{1} & X & X & X & \boxed{1} & 2\\\hline x_{4} & 3 & X & 6 & X & X & X & X & 1 & 2\\\hline x_{8} & 3 & X & 5 & X & X & X & X & X & \boxed{1}\\\hline x_{9} & 3 & X & \boxed{1} & X & X & X & X & X & X\\\hline x_{3} & 3 & X & X & X & X & X & X & X & X\\\hline \end{array}\]
1. \[ \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) & 3 & 6 & 5 & 3 & 5 & 6 & 4 & 5 & 5\\\hline \end{array} \]
2. \[\begin{array}{|c||*{9}{c|}}\hline Som & x_{2} & x_{6} & x_{3} & x_{5} & x_{8} & x_{9} & x_{7} & x_{1} & x_{4} \\\hline DSAT_{1} & 6 & 6 & 5 & 5 & 5 & 5 & 4 & 3 & 3\\\hline DSAT_{2} & {\color{violet} \blacksquare} & 1 & 5 & 1 & 1 & 1 & 4 & 1 & 1\\\hline DSAT_{3} & {\color{violet} \blacksquare} & 1 & {\color{violet} \blacksquare} & 2 & 2 & 2 & 1 & 1 & 2\\\hline DSAT_{4} & {\color{violet} \blacksquare} & 1 & {\color{violet} \blacksquare} & {\color{cyan} \blacksquare} & 2 & 3 & 2 & 2 & 2\\\hline DSAT_{5} & {\color{violet} \blacksquare} & 2 & {\color{violet} \blacksquare} & {\color{cyan} \blacksquare} & 3 & {\color{magenta} \blacksquare} & 2 & 2 & 2\\\hline DSAT_{6} & {\color{violet} \blacksquare} & 3 & {\color{violet} \blacksquare} & {\color{cyan} \blacksquare} & {\color{cyan} \blacksquare} & {\color{magenta} \blacksquare} & 3 & 2 & 2\\\hline DSAT_{7} & {\color{violet} \blacksquare} & {\color{olive} \blacksquare} & {\color{violet} \blacksquare} & {\color{cyan} \blacksquare} & {\color{cyan} \blacksquare} & {\color{magenta} \blacksquare} & 4 & 3 & 3\\\hline DSAT_{8} & {\color{violet} \blacksquare} & {\color{olive} \blacksquare} & {\color{violet} \blacksquare} & {\color{cyan} \blacksquare} & {\color{cyan} \blacksquare} & {\color{magenta} \blacksquare} & {\color{magenta} \blacksquare} & 3 & 3\\\hline DSAT_{9} & {\color{violet} \blacksquare} & {\color{olive} \blacksquare} & {\color{violet} \blacksquare} & {\color{cyan} \blacksquare} & {\color{cyan} \blacksquare} & {\color{magenta} \blacksquare} & {\color{magenta} \blacksquare} & {\color{magenta} \blacksquare} & 3\\\hline Coul & 1 & 4 & 1 & 2 & 2 & 3 & 3 & 3 & 2\\\hline \end{array}\]
3. D'après l'algorithme de Brelaz, nous avons déterminer une coloration à 4 couleurs. Ceci implique que le nombre chromatique du graphe est inférieur à 4. De plus on observe que $ \Kk_{4}$ est un sous graphe de ce graphe. Ceci implique que le nombre chromatique du graphe est majoré par 4. Ceci implique que nécessairment le nombre chromatique de ce graphe est exactement 4.

Seconde partie.

L'énoncé reviens à se demander s'il existe, dans ce graphe, un circuit eulérien (partant de $ x_{1} $ , mais puisque c'est un circuit, le point de départ n'importe pas). D'après le cours, un tel circuit existe si tous les sommets sont de degrés paire. Ce qui n'est pas le cas ici. Il y a des sommets de degrés impaire. On va donc rajouter à ces sommets des degrés (via l'ajout d'arête) pour répondre à la question. Voici par exemple une solution :
- On ajoute une arête entre $ x_{1} $ et $ x_{3} $ .
- On ajoute une arête entre $ x_{4} $ et $ x_{5} $ .
- On ajoute une arête entre $ x_{8} $ et $ x_{1} $ ainsi qu'une arête entre $ x_{1} $ et $ x_{9} $ .
Ce qui donne le circuit : \[ x_{5} x_{7} x_{8} x_{9} x_{5} x_{3} x_{8} x_{6} x_{9} x_{3} x_{3} x_{5} x_{4} x_{6} x_{7} x_{3} x_{1} x_{8} x_{2} x_{9} x_{1} x_{1} x_{5} x_{2} x_{6} x_{1} x_{1} x_{2} x_{4} x_{3} x_{1} \]
Deux seigneurs pirate partageant une même voie de navigation ne peuvent pas être dans le même groupe. Si on associe à chaque groupe une couleur, l'énoncé reviens donc à se demander avec combien de couleur au minimum on peut colorer les sommets du graphes de sorte que deux sommets voisins n'ai pas la même couleur. Cela a été résolu précédemment, par l'application de l'algorithme de Brelaz. La réponse est 4. De plus la coloration proposé par l'algorithme de Brelaz nous indique que :
- Il y a 2 pirates dans le groupe 1 (couleur 1)
- Il y a 3 pirates dans le groupe 2 (couleur 2)
- Il y a 3 pirates dans le groupe 3 (couleur 3)
- Il y a 1 pirates dans le groupe 4 (couleur 4)
Comme il y a plus de pirate dans le groupe 2, il est probable que le futur roi soit dans ce groupe.
L'énoncé revient à chercher un arbre couvrant de poids minimal ce qui a été fait précédemment. L'arbre est donc formé des arêtes \[ 2, 2, 2, 2, 2, 2, 2, 2 \]. Son poids est de 17 ce qui représente la centaine de kilomètre à éclairer. Le prix sera donc de $ 100\times\dfrac{17\times 100}{50}=3400$ pièces d'or.