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 & 2 & 5 & 0 & 7 & 9 & 0 & 0 & 0\\ x_{2} & 2 & 0 & 0 & 0 & 1 & 6 & 2 & 3 & 0\\ x_{3} & 5 & 0 & 0 & 5 & 0 & 0 & 0 & 3 & 0\\ x_{4} & 0 & 0 & 5 & 0 & 8 & 0 & 2 & 3 & 9\\ x_{5} & 7 & 1 & 0 & 8 & 0 & 7 & 0 & 0 & 1\\ x_{6} & 9 & 6 & 0 & 0 & 7 & 0 & 5 & 2 & 0\\ x_{7} & 0 & 2 & 0 & 2 & 0 & 5 & 0 & 0 & 7\\ x_{8} & 0 & 3 & 3 & 3 & 0 & 2 & 0 & 0 & 0\\ x_{9} & 0 & 0 & 0 & 9 & 1 & 0 & 7 & 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} & 7 & \boxed{1} & & 8 & X & 7 & & & \boxed{1}\\\hline x_{2} & \boxed{3} & X & & 8 & X & 7 & \boxed{3} & \boxed{4} & 1\\\hline x_{9} & 3 & X & & 8 & X & 7 & 3 & 4 & X\\\hline x_{1} & X & X & 8 & 8 & X & 7 & 3 & 4 & X\\\hline x_{7} & X & X & 8 & \boxed{5} & X & 7 & X & 4 & X\\\hline x_{8} & X & X & \boxed{7} & 5 & X & \boxed{6} & X & X & X\\\hline x_{4} & X & X & 7 & X & X & 6 & X & X & X\\\hline x_{6} & X & X & 7 & 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} & 7 & \boxed{1} & & 8 & X & 7 & & & \boxed{1}\\\hline x_{2} & \boxed{2} & X & & 8 & X & 6 & \boxed{2} & \boxed{3} & 1\\\hline x_{9} & 2 & X & & 8 & X & 6 & 2 & 3 & X\\\hline x_{1} & X & X & 5 & 8 & X & 6 & 2 & 3 & X\\\hline x_{7} & X & X & 5 & \boxed{2} & X & 5 & X & 3 & X\\\hline x_{4} & X & X & 5 & X & X & 5 & X & 3 & X\\\hline x_{8} & X & X & \boxed{3} & X & X & \boxed{2} & X & X & X\\\hline x_{6} & X & X & 3 & X & X & X & X & X & X\\\hline \end{array}\]
4. 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) & 4 & 5 & 3 & 5 & 5 & 5 & 4 & 4 & 3\\\hline \end{array} \]
   2. \[\begin{array}{|c||*{9}{c|}}\hline Som & x_{2} & x_{4} & x_{5} & x_{6} & x_{1} & x_{7} & x_{8} & x_{3} & x_{9} \\\hline DSAT_{1} & 5 & 5 & 5 & 5 & 4 & 4 & 4 & 3 & 3\\\hline DSAT_{2} & {\color{darkgray} \blacksquare} & 5 & 1 & 1 & 1 & 1 & 1 & 3 & 3\\\hline DSAT_{3} & {\color{darkgray} \blacksquare} & {\color{darkgray} \blacksquare} & 2 & 1 & 1 & 2 & 2 & 1 & 1\\\hline DSAT_{4} & {\color{darkgray} \blacksquare} & {\color{darkgray} \blacksquare} & {\color{lime} \blacksquare} & 2 & 2 & 2 & 2 & 1 & 2\\\hline DSAT_{5} & {\color{darkgray} \blacksquare} & {\color{darkgray} \blacksquare} & {\color{lime} \blacksquare} & {\color{olive} \blacksquare} & 3 & 3 & 3 & 1 & 2\\\hline DSAT_{6} & {\color{darkgray} \blacksquare} & {\color{darkgray} \blacksquare} & {\color{lime} \blacksquare} & {\color{olive} \blacksquare} & {\color{green} \blacksquare} & 3 & 3 & 2 & 2\\\hline DSAT_{7} & {\color{darkgray} \blacksquare} & {\color{darkgray} \blacksquare} & {\color{lime} \blacksquare} & {\color{olive} \blacksquare} & {\color{green} \blacksquare} & {\color{lime} \blacksquare} & 3 & 2 & 3\\\hline DSAT_{8} & {\color{darkgray} \blacksquare} & {\color{darkgray} \blacksquare} & {\color{lime} \blacksquare} & {\color{olive} \blacksquare} & {\color{green} \blacksquare} & {\color{lime} \blacksquare} & {\color{lime} \blacksquare} & 3 & 3\\\hline DSAT_{9} & {\color{darkgray} \blacksquare} & {\color{darkgray} \blacksquare} & {\color{lime} \blacksquare} & {\color{olive} \blacksquare} & {\color{green} \blacksquare} & {\color{lime} \blacksquare} & {\color{lime} \blacksquare} & {\color{olive} \blacksquare} & 3\\\hline Coul & 1 & 1 & 2 & 3 & 4 & 2 & 2 & 3 & 3\\\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.

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_{3} \) .
   • On ajoute une arête entre \( x_{4} \) et \( x_{6} \) .
   • On ajoute une arête entre \( x_{5} \) et \( x_{3} \) ainsi qu'une arête entre \( x_{3} \) et \( x_{9} \) .
   Ce qui donne le circuit : \[ x_{4} x_{8} x_{6} x_{7} x_{9} x_{4} x_{2} x_{7} x_{4} x_{3} x_{5} x_{4} x_{6} x_{5} x_{9} x_{3} x_{8} x_{2} x_{1} x_{5} x_{2} x_{6} 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 4. 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 3 vilains dans le groupe 2 (couleur 2)
   • Il y a 3 vilains dans le groupe 3 (couleur 3)
   • Il y a 1 vilains dans le groupe 4 (couleur 4)
   Comme il y a plus de vilain dans le groupe 2, il est probable que le futur roi soit dans ce groupe.
3. Il s'agit de trouver le plus court chemin entre \( x_{5} \) et \( x_{3}\) ce que nous avons déjà traité par l'algorithme de Dijsktra. Le chemin est \( x_{5} \rightarrow x_{2} \rightarrow x_{8} \rightarrow x_{3} \) d'un cout de \( 7\times 100=700\) dollars.