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


Les avengers ont, par voyage dans le temps, réuni les pierres de l'infini dans le présent.
  1. La pierre de l'espace lors de la seconde guerre mondiale (Captain America - First Avenger)
  2. La pierre de la puissance (Les gardiens de la Galaxie - Volume I)
  3. La pierre de la réalité (Thor - Le monde des ténèbres)
  4. La pierre de l'âme (Avengers - Infinity War)
  5. Le présent (Avengers - End Game)
  6. La pierre de l'espace à New York en 2012 (Avengers I)
  7. La pierre du temps (Docteur Strange)
  8. La pierre de l'esprit (Avengers - L'ère d'Ultron)
  9. La pierre du spoil dans le bureau d'un prof (Thyrion ne meurt pas)
Mais pour éviter des failles du continum espace-temps il faut voyager à nouveau dans le temps pour les remettre dans leur zone de temporalité. A cette fin, il faut utiliser les particules de Pym, mais elles sont en quantité limitées et la consommation varie lorsque l'on passe d'une zone à une autre. De plus, les ponts Einstein-Rosen de passage d'une zone à l'autre ne sont pas tous ouverts. Dans le graphe ci-dessous on a indiqué les ponts ouverts entre les zones ainsi que la consommation de particule Pym pour le voyage. \[\xymatrix@C=0.619cm@R=0.919cm{ &&&x_{1}\ar@{-}[lld]|-{\boxed{8}}\ar@{-}@/^1pc/[rrrd]|-{\boxed{3}}\ar@{-}[dddd]|-{\boxed{5}}\ar@{-}@/^7pc/[rrrrdddd]|-{\boxed{6}}\ar@{-}[lldddddd]|-{\boxed{5}}\ar@{-}@/^5pc/[rrrdddddd]|-{\boxed{8}}\ar@{-}@/^4pc/[ddddddd]|-{\boxed{7}}&&&&\\ &x_{2}\ar@{-}@/^5pc/[rrrrr]|-{\boxed{8}}\ar@{-}@/^1pc/[rrddd]|-{\boxed{9}}\ar@{-}[ddddd]|-{\boxed{8}}\ar@{-}@/_1pc/[rrdddddd]|-{\boxed{4}}&&&&&x_{3}\ar@{-}@/^1.5pc/[lllddd]|-{\boxed{1}}\ar@{-}@/_2pc/[lllllddddd]|-{\boxed{1}}\ar@{-}[ddddd]|-{\boxed{8}}\ar@{-}[ddddddlll]|-{\boxed{1}}&\\ &&&&&&&\\ &&&&&&&\\ x_{4}\ar@{-}@/^0.5pc/[rrr]|-{\boxed{2}}\ar@{-}@/^5pc/[rrrrrrr]|-{\boxed{3}}\ar@{-}[rdd]|-{\boxed{2}}\ar@{-}@/_5pc/[rrrddd]|-{\boxed{1}}&&&x_{5}\ar@{-}@/^1pc/[lldd]|-{\boxed{8}}\ar@{-}[rrrdd]|-{\boxed{1}}&&&&x_{6}\ar@{-}@/^2pc/[lllllldd]|-{\boxed{7}}\ar@{-}@/^5pc/[llllddd]|-{\boxed{9}}\\ &&&&&&&\\ &x_{7}\ar@{-}[rrd]|-{\boxed{8}}&&&&&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 Dijkstra partant de \( x_{5} \) , 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} \]
  3. 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. Captain America part du présent (sommet \( \) x_5 \( ) et a besoin de passer par toutes les zones temporelles pour gagner un pari avec Faucon. Pour y arriver il peut forcer, à l'aide de Heimdal, l'apparition temporaire d'un pont entre des zones (des arêtes inexistantes). Expliquez quel trajet Captain va devoir emprunter et les voies éventuelles qu'il va demander d'ouvrir à Heimdal.
  2. A chaque zone, un vilain y demeure :
    1. Crane rouge
    2. Ronan l'accusateur
    3. Malekith
    4. Celui-dont-on-ne-doit-pas-prononcer-le-nom
    5. Thanos
    6. Loki
    7. Kaecilius
    8. Ultron
    9. ataraXy
    Pour tenter d'arêter Capitain ils décident de s'allier et pour se coordonner correctement d'élir un chef. Mais cela s'avère compliqué car chacun d'eux vote pour lui-même. De plus lorsque deux vilains sont reliés par un pont Einstein-Rosen ils se détestent au plus haut point. Monsieur HD, dans sa grande sagesse, a réussi à convaincre tous les vilains de ne pas voter pour eux même. Ils vont donc voter pour un vilain qu'il ne déteste pas. Combien de groupe de méchand qui ne se détestent pas existe-t-il au minimum ? Dans quel groupe a-t-on le plus de chance de trouver le chef des méchants ?
  3. Pour pouvoir suivre les aventures de Captain à travers les zones, ses alliés avengers décident de mettre en place une radio quantique dont les ondes parcours les ponts. Il est donc nécessaire que chaque zone soit connectée à au moins une autre pour pouvoir capter. Pour emmetre à travers les ponts il faut utiliser des particules de Pym mais Captain les a toutes prises pour ses voyages. Un certain DeadPool propose de vendre sur le deep web des particules \) 100\( dollars l'unité. Puisque le plus riche des avengers ne peut plus les aider financièrement, ils sont limités en terme de budget. Quelles sont les ponts qui serviront de relais radio et quel sera le coût ?
Cliquer ici pour afficher la solution

Exercice



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

Seconde partie.
  1. 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_{2} \) et \( x_{8} \) .
    • On ajoute une arête entre \( x_{5} \) et \( x_{7} \) .
    • On ajoute une arête entre \( x_{8} \) et \( x_{9} \) .
    • On ajoute une arête entre \( x_{7} \) et \( x_{8} \) .
    • On ajoute une arête entre \( x_{4} \) et \( x_{5} \) .
    • On ajoute une arête entre \( x_{7} \) et \( x_{9} \) .
    • On ajoute une arête entre \( x_{4} \) et \( x_{7} \) .
    • On ajoute une arête entre \( x_{6} \) et \( x_{7} \) .
    • On ajoute une arête entre \( x_{1} \) et \( x_{3} \) .
    • On ajoute une arête entre \( x_{4} \) et \( x_{6} \) .
    • On ajoute une arête entre \( x_{3} \) et \( x_{6} \) .
    • On ajoute une arête entre \( x_{1} \) et \( x_{4} \) ainsi qu'une arête entre \( x_{4} \) et \( x_{3} \) .
    • On ajoute une arête entre \( x_{6} \) et \( x_{5} \) ainsi qu'une arête entre \( x_{5} \) et \( x_{9} \) .
    Ce qui donne le circuit : \[ x_{7} x_{8} x_{9} x_{7} x_{4} x_{7} x_{6} x_{9} x_{4} x_{3} x_{8} x_{5} x_{9} x_{3} x_{1} x_{8} x_{2} x_{5} x_{4} x_{6} x_{5} x_{7} x_{2} x_{9} x_{1} x_{1} x_{6} x_{3} x_{7} x_{1} x_{1} x_{4} x_{3} x_{5} x_{1} x_{1} x_{2} x_{3} x_{1} \]
  2. Deux vilains partageant un même pont Einstein-Rosen 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 5. De plus la coloration proposé par l'algorithme de Brelaz nous indique que :
    • Il y a 2 vilains dans le groupe 1 (couleur 1)
    • Il y a 2 vilains dans le groupe 2 (couleur 2)
    • Il y a 2 vilains dans le groupe 3 (couleur 3)
    • Il y a 2 vilains dans le groupe 4 (couleur 4)
    • Il y a 1 vilains dans le groupe 5 (couleur 5)
    Comme il y a plus de vilain dans le groupe 1, il est probable que le futur roi soit dans ce groupe.
  3. 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 15 ce qui représente la centaine de dollars à investir. Le prix sera donc de \( 100\times15=1500\) dollars.