\( %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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}{\text{\Large$\varepsilon\!\!\varepsilon$}} \newcommand{\supere}{\text{\Large$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{\vv}{\overrightarrow{v}} \newcommand{\vu}{\overrightarrow{u}} \newcommand{\vup}{\overrightarrow{u'}} \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]{\dpl{\left\langle #1\right\rangle}} \newcommand{\trans}[1]{{\vphantom{#1}}^{t}{#1}} \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.


La semaine du 20 au 26 mai 2018 les apprentis en deuxième année du département réseaux et Télécommunications et département informatique sont partis en Estonie pour une découverte des entreprises locales et du milieu universitaire de ce pays en pleine explosion numérique. Le programme de la semaine était le suivant :

A.
Départ samedi de Paris pour arriver à la capitale Estonienne de Tallin dans la journée.

B.
Visite de l'incubateur Mektory le lundi matin.

C.
Visite d'une usine d'Ericsson le lundi après-midi.

D.
Présentation des installations de télévision et radiodifusion publique (ERR) le mardi matin.

E.
Exposé du principe de résident numérique par E-residency le mardi après-midi.

F.
Discussion autour des formations de l'université de Tallin le mercredi matin.

G.
Départ de Tallin pour Tartu, la ville-étudiante, le mercredi après-midi.

H.
Visite d'entreprise de la sTARTUp HUB le jeudi matin.

I.
Discussion autour de l'apprentissage à la française à l'université de Tartu le jeudi après-midi.

J.
Visite guidé de l'observatoire de Tartu par l'ancien directeur le vendredi matin.

K.
Demi-journée de relâche (ça veux dire piscine) le vendredi après-midi.

-.
Retour à Tallin puis à Paris le samedi 26.
On modélise la situation sur la carte d'Estonie que l'on ramène à un graphe dont une représentation sagittale est donnée ci-dessous. Les lieux de visite/présentation représentent les sommets de ce graphe que l'on dénomine par les items de la liste précédente ($ A$ , $ B$ , $ C$ , etc.). Les arêtes représentant les routes offrants le meilleur du tourisme Estonien. On augmente ce graphe de la valuation réprensentant la distance séparant les lieux, mesurée en kilomètres. $$\xymatrix@C=3.19cm{ & &C \ar@{-}[d]|-{\boxed{2}}& & \\ &D &E \ar@{-}[ldd]|-{\boxed{2}}& & \\ B \ar@{-}@/^2pc/[rruu]|-{\boxed{2}}\ar@{-}[rd]|-{\boxed{1}} & & & & \\ &F &A \ar@{-}@/^3pc/[llu]|-{\boxed{3}}\ar@{-}@/_2pc/[uuu]|-{\boxed{1}}\ar@{-}@/^2pc/[luu]|-{\boxed{1}}\ar@{-}[uu]|-{\boxed{6}}\ar@{-}[rddd]|-{\boxed{70}} & & \\ & & & & \\ & & & & \\ & & &G \ar@{-}[ld]|-{\boxed{1}}\ar@{-}@/_2pc/[dddlll]|-{\boxed{5}}\ar@{-}@/^2pc/[dd]|-{\boxed{4}}& \\ & &H \ar@{-}[lldd]|-{\boxed{2}}& &I \ar@{-}[ld]|-{\boxed{2}}\\ & & &K & \\ J \ar@{-}[rrru]|-{\boxed{2}}& & & & }$$

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|c|c} &A&B&C&D&E&F&G&H&I&J&K\\\hline\hline A&&&&&&&&&&&\\\hline B&&&&&&&&&&&\\\hline C&&&&&&&&&&&\\\hline D&&&&&&&&&&&\\\hline E&&&&&&&&&&&\\\hline F&&&&&&&&&&&\\\hline G&&&&&&&&&&&\\\hline H&&&&&&&&&&&\\\hline I&&&&&&&&&&&\\\hline J&&&&&&&&&&&\\\hline K&&&&&&&&&&& \end{array} $$
  2. Compléter ce tableau en appliquant l'algorithme de Prim (initialisé en $ E$ de préférence), comme nous l'avons vu en cours. $$\begin{array}{c||c|c|c|c|c|c|c|c|c|c|c} &A&B&C&D&E&F&G&H&I&J&K\\\hline\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|c|c|}\hline \bullet&A&B&C&D&E&F&G&H&I&J&K\\\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|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 DSAT_{10}&&&&&&&&&&&\\\hline DSAT_{11}&&&&&&&&&&&\\\hline\hline Coul&&&&&&&&&&&\\\hline \end{array} $$
    3. Quelle est la valeur exacte du nombre chromatique de ce graphe.

Seconde partie.
L'histoire.
  1. En organisant ce voyage, les étudiants (car ce sont bien les étudiants qui ont (presque) tout organisé) souhaiteraient réaliser leur parcours en passant une et une seule fois par chaque route touristique dès leur atterrissage en visitant si nécessaire plusieurs fois les même lieux. Il n'est peut-être pas possible de réaliser ce trajet sauf en passant éventuellement par des voies non touristique, c'est à dire des arêtes non existantes. Expliquer s'il est possible de parcourir chaque route touristique ou non en justifiant précisément. Si ce n'est pas possible indiquer quelles voies non touristique il faudrait rajouter au circuit pour y arriver. Donner alors le chemin. Justifier précisément.
  2. Pour rendre compte de leur travail, il a été demandé aux apprentis participants de réaliser une compte rendu de chacune des visites. Tout apprentis qu'ils soient, ils n'en restent pas moins des étudiants (c'est à dire très heureux avec le moins de devoir à faire). Après maintes et maintes plaintes ils ont réussi à faire valoir les régles suivantes aux enseignants :
    • Se mettre en groupe pour faire les rapports
    • Les groupes sont de tailles et de composition entièrement déterminés par les étudiants
    • Les rapports de deux visites réliées par une route touristique ne peuvent pas être écrit par les même groupes
    Déterminer le nombre de groupe minimum que les enseignants devront demander. En tant qu'étudiant, dans quel groupe ne souhaiteriez-vous pas être ? Justifier.
  3. L'Estonie est le pays du tout numérique, à l'aube de la 5G et de fibre optique dans les lieux publiques. Mais les apprentis décident d'y relever un challenge et souhaite mettre le système de sécurité du pays à rude épreuve. Ils prévoient une attaque simultanée de tous les endroits qu'ils ont visités. Pour cela ils prévoient de placer lors de leur voyage des mini antenne wifi entre les différents lieux mais ces antennes n'ont qu'une portée de 100 mètres et coutent 5 euros l'unité. Sur quelles voies seront placées les relais wifi et combien coutera cette installation ?
Cliquer ici pour afficher la solution

Première partie.
  1. $$\begin{array}{c||ccccccccccc} & A & B & C & D & E & F & G & H & I & J & K\\\hline\hline A & 0 & 3 & 1 & 1 & 6 & 0 & 70 & 0 & 0 & 0 & 0\\ B & 3 & 0 & 2 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ C & 1 & 2 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 0\\ D & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ E & 6 & 0 & 2 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 0\\ F & 0 & 1 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 0\\ G & 70 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 5 & 4\\ H & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 2 & 0\\ I & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2\\ J & 0 & 0 & 0 & 0 & 0 & 0 & 5 & 2 & 0 & 0 & 2\\ K & 0 & 0 & 0 & 0 & 0 & 0 & 4 & 0 & 2 & 2 & 0\end{array}$$
  2. $$\begin{array}{|c|*{11}{c|}}\hline Som & A & B & C & D & E & F & G & H & I & J & K\\\hline Init & & & & & \boxed{0} & & & & & & \\\hline E & 6 & & \boxed{2} & & X & 2 & & & & & \\\hline C & \boxed{1} & \boxed{2} & X & & X & 2 & & & & & \\\hline A & X & 2 & X & \boxed{1} & X & 2 & \boxed{70} & & & & \\\hline D & X & 2 & X & X & X & 2 & 70 & & & & \\\hline B & X & X & X & X & X & \boxed{1} & 70 & & & & \\\hline F & X & X & X & X & X & X & 70 & & & & \\\hline G & X & X & X & X & X & X & X & \boxed{1} & & 5 & 4\\\hline H & X & X & X & X & X & X & X & X & & \boxed{2} & 4\\\hline J & X & X & X & X & X & X & X & X & & X & \boxed{2}\\\hline K & X & X & X & X & X & X & X & X & \boxed{2} & X & X\\\hline \end{array}$$
    1. $$ \begin{array}{|r||c|c|c|c|c|c|c|c|c|c|c|}\hline \bullet&A&B&C&D&E&F&G&H&I&J&K\\\hline d^{+1}(\bullet) & 5 & 3 & 3 & 1 & 3 & 2 & 4 & 2 & 1 & 3 & 3\\\hline \end{array} $$
    2. $$\begin{array}{|c||*{11}{c|}}\hline Som & A & G & B & C & E & J & K & F & H & D & I\\\hline DSAT_{1} & 5 & 4 & 3 & 3 & 3 & 3 & 3 & 2 & 2 & 1 & 1\\\hline DSAT_{2} & {\color{blue} \blacksquare} & 1 & 1 & 1 & 1 & 3 & 3 & 2 & 2 & 1 & 1\\\hline DSAT_{3} & {\color{blue} \blacksquare} & 2 & 1 & 1 & 1 & {\color{blue} \blacksquare} & 1 & 2 & 1 & 1 & 1\\\hline DSAT_{4} & {\color{blue} \blacksquare} & {\color{lime} \blacksquare} & 1 & 1 & 1 & {\color{blue} \blacksquare} & 2 & 2 & 2 & 1 & 1\\\hline DSAT_{5} & {\color{blue} \blacksquare} & {\color{lime} \blacksquare} & 1 & 1 & 1 & {\color{blue} \blacksquare} & {\color{pink} \blacksquare} & 2 & 2 & 1 & 1\\\hline DSAT_{6} & {\color{blue} \blacksquare} & {\color{lime} \blacksquare} & 2 & 1 & 2 & {\color{blue} \blacksquare} & {\color{pink} \blacksquare} & {\color{blue} \blacksquare} & 2 & 1 & 1\\\hline DSAT_{7} & {\color{blue} \blacksquare} & {\color{lime} \blacksquare} & {\color{lime} \blacksquare} & 2 & 2 & {\color{blue} \blacksquare} & {\color{pink} \blacksquare} & {\color{blue} \blacksquare} & 2 & 1 & 1\\\hline DSAT_{8} & {\color{blue} \blacksquare} & {\color{lime} \blacksquare} & {\color{lime} \blacksquare} & {\color{pink} \blacksquare} & 3 & {\color{blue} \blacksquare} & {\color{pink} \blacksquare} & {\color{blue} \blacksquare} & 2 & 1 & 1\\\hline DSAT_{9} & {\color{blue} \blacksquare} & {\color{lime} \blacksquare} & {\color{lime} \blacksquare} & {\color{pink} \blacksquare} & {\color{lime} \blacksquare} & {\color{blue} \blacksquare} & {\color{pink} \blacksquare} & {\color{blue} \blacksquare} & 2 & 1 & 1\\\hline DSAT_{10} & {\color{blue} \blacksquare} & {\color{lime} \blacksquare} & {\color{lime} \blacksquare} & {\color{pink} \blacksquare} & {\color{lime} \blacksquare} & {\color{blue} \blacksquare} & {\color{pink} \blacksquare} & {\color{blue} \blacksquare} & {\color{pink} \blacksquare} & 1 & 1\\\hline DSAT_{11} & {\color{blue} \blacksquare} & {\color{lime} \blacksquare} & {\color{lime} \blacksquare} & {\color{pink} \blacksquare} & {\color{lime} \blacksquare} & {\color{blue} \blacksquare} & {\color{pink} \blacksquare} & {\color{blue} \blacksquare} & {\color{pink} \blacksquare} & {\color{lime} \blacksquare} & 1\\\hline Coul & 1 & 2 & 2 & 3 & 2 & 1 & 3 & 1 & 3 & 2 & 1\\\hline \end{array}$$
    3. D'après l'algorithme de Brelaz, nous avons déterminer une coloration à 3 couleurs. Ceci implique que le nombre chromatique du graphe est inférieur à 3. De plus on observe que $ \Kk_{3}$ est un sous graphe de ce graphe. Ceci implique que le nombre chromatique du graphe est majoré par 3. Ceci implique que nécessairement le nombre chromatique de ce graphe est exactement 3.

Seconde partie.
  1. L'énoncé reviens à se demander s'il existe, dans ce graphe, un circuit eulérien (partant de $ A$ , 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 $ A $ et $ I $ .
    • On ajoute une arête entre $ B $ et $ D $ .
    • On ajoute une arête entre $ C $ et $ J $ .
    • On ajoute une arête entre $ E $ et $ K $ .
    Une chaine eulérienne est alors : $$ AGHJCEKGJKIADBFEABCA $$
  2. 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 3. De plus la coloration proposée par l'algorithme de Brelaz nous indique que :
    • Le groupe 1 devra réaliser 4 rapports
    • Le groupe 2 devra réaliser 4 rapports
    • Le groupe 3 devra réaliser 3 rapports
    En tant qu'étudiant, c'est à dire partisan du moindre effort, mieux vaut éviter d'être dans le groupe 1 sinon on fera 4 de rapports
  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 $$ \{AC\}, \{BC\}, \{CE\}, \{DA\}, \{FB\}, \{GA\}, \{HG\}, \{IK\}, \{JH\}, \{KJ\} $$ Son poids est de 84 c'est à dire qu'il faut couvrir 84000 mètres de parcours à couvrir ; soit 840 centaine de mètres. Le prix sera donc de $ 5\times 840 = 4200$ euros... pauvres apprentis ;-)