<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\section{Annales.}  
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
%                         AmÃ©rique du nord juin 2003
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\subsection{AmÃ©rique du nord juin 2003}

Soit le graphe G joint en annexe constituÃ© des sommets A, B, C, D, E, F et G.

\begin{enumerate} 
\item Quel est son ordre et le degrÃ© de chacun de ses sommets ?
\item Reproduire sur la copie et complÃ©ter le tableau des distances entre deux sommets de G :

\medskip
\begin{center} 
\begin{tabular}{|l|c|c|c|c|c|c|c|}\hline
Distance    &amp;    A  &amp;   B   &amp;   C   &amp;   D   &amp;   E   &amp;   F   &amp;   G   \\ \hline
A           &amp;    X  &amp;       &amp;       &amp;       &amp;       &amp;       &amp;       \\ \hline
B           &amp;    X  &amp;   X   &amp;       &amp;       &amp;       &amp;       &amp;       \\ \hline
C           &amp;    X  &amp;   X   &amp;   X   &amp;       &amp;       &amp;       &amp;       \\ \hline
D           &amp;    X  &amp;   X   &amp;   X   &amp;   X   &amp;       &amp;       &amp;       \\ \hline
E           &amp;    X  &amp;   X   &amp;   X   &amp;   X   &amp;   X   &amp;       &amp;       \\ \hline
F           &amp;    X  &amp;   X   &amp;   X   &amp;   X   &amp;   X   &amp;   X   &amp;       \\ \hline
G           &amp;    X  &amp;   X   &amp;   X   &amp;   X   &amp;   X   &amp;   X   &amp;   X   \\ \hline
\end{tabular}
\end{center}

\medskip
En dÃ©duire le diamÃ¨tre de ce graphe.
\item 
   \begin{enumerate} 
   \item Donner un sous-graphe complet d'ordre 3 de G.

Qu'en dÃ©duire pour le nombre chromatique de G ?
   \item Proposer une coloration du graphe G et en dÃ©duire son nombre chromatique.
   \end{enumerate}
\item Donner la matrice M associÃ©e Ã&nbsp; G (vous numÃ©roterez les lignes et les  colonnes dans l'ordre alphabÃ©tique).
\item En utilisant la matrice $ M_2$ donnÃ©e en annexe 1, dÃ©duire le nombre de chaÃ®nes de longueur 2 partant de A sans y revenir.
\end{enumerate}

\medskip
\begin{minipage}[]{10cm}
\begin{tikzpicture}
    \Vertex[x=1.3,y=3.8]{A}
    \Vertex[x=4.2,y=5.5]{B}
    \Vertex[x=7.3,y=4]{C}
    \Vertex[x=8.5,y=1.5]{D}
    \Vertex[x=5,y=0]{E}
    \Vertex[x=3.6,y=4]{F}  
    \Vertex[x=0.7,y=1]{G}
    \Edges(A,B,C,D,E,G,A,F,E,C)
    \Edge(B)(F)
\end{tikzpicture}
\end{minipage}
\begin{minipage}[]{5cm}
M$^2 =
\begin{pmatrix}
    3   &amp;   1   &amp;   1   &amp;   0   &amp;   2   &amp;   1   &amp;   0\\
    1   &amp;   3   &amp;   0   &amp;   1   &amp;   2   &amp;   1   &amp;   1\\
    1   &amp;   0   &amp;   3   &amp;   1   &amp;   1   &amp;   2   &amp;   1\\
    0   &amp;   1   &amp;   1   &amp;   2   &amp;   1   &amp;   1   &amp;   1\\
    2   &amp;   2   &amp;   1   &amp;   1   &amp;   4   &amp;   0   &amp;   0\\
    1   &amp;   1   &amp;   2   &amp;   1   &amp;   0   &amp;   3   &amp;   2\\
    0   &amp;   1   &amp;   1   &amp;   1   &amp;   0   &amp;   2   &amp;   2\\
\end{pmatrix}$
\end{minipage}

\medskip
\begin{tkzexample}[code only]
\begin{tikzpicture}
    \Vertex[x=1.3,y=3.8]{A}     \Vertex[x=4.2,y=5.5]{B}
    \Vertex[x=7.3,y=4]{C}       \Vertex[x=8.5,y=1.5]{D}
    \Vertex[x=5,y=0]{E}         \Vertex[x=3.6,y=4]{F}
    \Vertex[x=0.7,y=1]{G}
    \Edges(A,B,C,D,E,G,A,F,E,C) \Edge(B)(F)
\end{tikzpicture}
\end{tkzexample}

%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\vfill\newpage
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
%                         Antilles-Guyane juin 2003
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\subsection{Antilles-Guyane juin 2003 }\label{ag03} 
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\begin{enumerate}
\item Un musÃ©e est constituÃ© de 9 salles notÃ©es A, B, C, D, E, F, G, H et S.

Le plan du musÃ©e est reprÃ©sentÃ© ci-dessous :

\medskip
\begin{center}
\begin{tikzpicture}
\draw (0,0) rectangle (8,6);
\draw(2,0)--(2,0.7);
\draw(2,1.3)--(2,2.7);
\draw(2,3.3)--(2,4.7);
\draw(2,5.3)--(2,6);
\draw(4,0)--(4,0.7);
\draw(4,1.3)--(4,2.7);
\draw(4,3.3)--(4,4.7);
\draw(4,5.3)--(4,6);
\draw(6,0)--(6,0.7);
\draw(6,1.3)--(6,2.7);
\draw(6,3.3)--(6,4.7);
\draw(6,5.3)--(6,6);
\draw(2,5.3)--(2,6);
\draw(4,5.3)--(4,6);
\draw(6,5.3)--(6,6);
\draw(2,2)--(2.7,2);
\draw(3.3,2)--(4.7,2);
\draw(5.3,2)--(6,2);
\draw(2,4)--(2.7,4);
\draw(3.3,4)--(4.7,4);
\draw(5.3,4)--(8,4);
\node at (1,3){S};
\node at (3,3){G};
\node at (3,1){D};
\node at (3,5){A};
\node at (5,1){H};
\node at (5,3){E};
\node at (5,5){B};
\node at (7,2){F};
\node at (7,5){C};
\end{tikzpicture}
\end{center}

\medskip
Ainsi, un visiteur qui se trouve dans la salle S peut atteindre directement les salles  A, B ou G. S'il se trouve dans la salle C, il peut se rendre directement dans la salle B, mais pas dans la salle F.

On s'intÃ©resse au parcours d'un visiteur dans ce musÃ©e. On ne se prÃ©occupe pas de la maniÃ¨re dont le visiteur accÃ¨de au musÃ©e ni comment il en sort. Cette situation peut Ãªtre modÃ©lisÃ©e par un graphe, les sommets Ã©tant les noms des salles, les arÃªtes reprÃ©sentant les portes de communication.

   \begin{enumerate} 
   \item Dessiner un graphe modÃ©lisant la situation dÃ©crite.
   \item Est-il possible de visiter le musÃ©e, en empruntant chaque porte une fois et une seule ?

Justifier en utilisant un thÃ©orÃ¨me du cours sur les graphes.
\item Pour rompre une Ã©ventuelle monotonie, le conservateur du musÃ©e souhaite diffÃ©rencier chaque salle de sa ou des salles voisines (c'est-Ã&nbsp;-dire accessibles par une porte)  par la moquette posÃ©e au sol. Quel est le nombre minimum de types de moquettes nÃ©cessaires pour  rÃ©pondre Ã&nbsp; ce souhait ? Justifier.
   \end{enumerate}
\item On note $M$ la matrice Ã&nbsp; 9 lignes et 9 colonnes associÃ©e au graphe prÃ©cÃ©dent, en  convenant de l'ordre suivant des salles S, A, B, C, D, E, F, G, H. Le graphe n'Ã©tant pas orientÃ©,  comment cela se traduit-il sur la matrice ?
\item  On donne la matrice :

\[M^4 = 
\begin{pmatrix}
18  &amp;   12  &amp;   11  &amp;   02  &amp;   20  &amp;   12  &amp; 06    &amp; 12    &amp; 12\\
12  &amp;   20  &amp;   03  &amp;   06  &amp;   11  &amp;   20  &amp; 05    &amp; 18    &amp; 05\\
11  &amp;   03  &amp;   16  &amp;   00  &amp;   19  &amp;   03  &amp; 08    &amp; 04    &amp; 12\\
02  &amp;   06  &amp;   00  &amp;   03  &amp;   01  &amp;   07  &amp; 01    &amp; 04    &amp; 01\\
20  &amp;   11  &amp;   19  &amp;   01  &amp;   31  &amp;   09  &amp; 11    &amp; 12    &amp; 19\\
12  &amp;   20  &amp;   03  &amp;   07  &amp;   09  &amp;   28  &amp; 09    &amp; 20    &amp; 09\\
06  &amp;   05  &amp;   08  &amp;   01  &amp;   11  &amp;   09  &amp; 09    &amp; 08    &amp; 09\\
12  &amp;   18  &amp;   04  &amp;   04  &amp;   12  &amp;   20  &amp; 08    &amp; 20    &amp; 06\\
12  &amp;   05  &amp;   12  &amp;   01  &amp;   19  &amp;   09  &amp; 09    &amp; 06    &amp; 17\\
\end{pmatrix}\]

   \begin{enumerate} 
   \item Combien y-a-t-il de chemins qui en 4 Ã©tapes, partent de D et reviennent Ã&nbsp; D ?
   \item Combien y-a-t-il de chemins qui en 4 Ã©tapes, partent de S et reviennent Ã&nbsp; C ? Les citer.
   \item Est-il toujours possible de joindre en 4 Ã©tapes deux salles quelconques ? Justifier.
   \end{enumerate}
\end{enumerate}

%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\vfill\newpage
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
Code du graphe prÃ©cÃ©dent, uniquement fait avec tikz sans tkz-berge

\bigskip
\begin{tkzexample}[code only]
\begin{tikzpicture}
  \draw (0,0) rectangle (8,6);
  \draw(2,0)--(2,0.7);
  \draw(2,1.3)--(2,2.7);
  \draw(2,3.3)--(2,4.7);
  \draw(2,5.3)--(2,6);
  \draw(4,0)--(4,0.7);
  \draw(4,1.3)--(4,2.7);
  \draw(4,3.3)--(4,4.7);
  \draw(4,5.3)--(4,6);
  \draw(6,0)--(6,0.7);
  \draw(6,1.3)--(6,2.7);
  \draw(6,3.3)--(6,4.7);
  \draw(6,5.3)--(6,6);
  \draw(2,5.3)--(2,6);
  \draw(4,5.3)--(4,6);
  \draw(6,5.3)--(6,6);
  \draw(2,2)--(2.7,2);
  \draw(3.3,2)--(4.7,2);
  \draw(5.3,2)--(6,2);
  \draw(2,4)--(2.7,4);
  \draw(3.3,4)--(4.7,4);
  \draw(5.3,4)--(8,4);
  \node at (1,3){S};
  \node at (3,3){G};
  \node at (3,1){D};
  \node at (3,5){H};
  \node at (5,1){H};
  \node at (5,3){E};
  \node at (5,5){B};
  \node at (7,2){F};
  \node at (7,5){C};
\end{tikzpicture}
\end{tkzexample}


%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\vfill\newpage
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
%                         Asie juin 2003
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\subsection{Asie juin 2003 }\label{asj03} 
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;


\bigskip 
\begin{minipage}[l]{0,58\textwidth}
Dans la ville de GRAPHE, on s'intÃ©resse aux principales rues permettant de relier diffÃ©rents lieux ouverts au public, Ã&nbsp; savoir la mairie (M), le centre commercial (C), la bibliothÃ¨que (B), la piscine (P) et le lycÃ©e (L). Chacun de ces lieux est dÃ©signÃ© par son initiale. Le tableau ci-contre donne les rues existant entre ces lieux.
\end{minipage}\hfill
\begin{minipage}[]{0,38\textwidth}
\begin{center}
     \begin{tabular}{|*{5}{c|} c|} \cline{2-6}
        \multicolumn{1}{c|}{}
          &amp; B   &amp; C &amp; L &amp; M &amp; P \\ \hline
        B &amp;     &amp; X &amp;   &amp; X &amp; X \\ \hline
        C &amp; X   &amp;   &amp; X &amp; X &amp;   \\ \hline
        L &amp;     &amp; X &amp;   &amp; X &amp;   \\ \hline
        M &amp; X   &amp; X &amp; X &amp;   &amp; X \\ \hline
        P &amp; X   &amp;   &amp;   &amp; X &amp;   \\ \hline
    \end{tabular}
\end{center}
\end{minipage}

\medskip
\begin{enumerate} 
\item Dessiner un graphe reprÃ©sentant cette situation.
\item Montrer qu'il est possible de trouver un trajet empruntant une fois et une seule toutes les rues de ce plan. Justifier. Proposer un tel trajet.

Est-il possible d'avoir un trajet partant et arrivant du mÃªme lieu et passant une fois et une seule par toutes les rues ?


\begin{minipage}[b]{0,3\textwidth}
\item
 Dimitri habite dans cette ville ; le graphe ci-contre  donne le \textbf{nouveau} plan du quartier avec les sens de circulation dans les diffÃ©rentes rues et le temps de parcours entre les diffÃ©rents lieux.
\end{minipage}
\hspace{1cm}
 \begin{minipage}[c]{0,68\textwidth}
    \begin{tikzpicture}[&gt;=latex]
      \SetGraphUnit{4}
      \tikzset{VertexStyle/.style  = {shape         = circle,
                                      draw          = black,
                                      inner sep     = 2pt,%
                                      minimum size  = 6mm,
                                      outer sep     = 0pt,
                                      fill          = gray!60}}
      \Vertex {P}
      \NOEA(P){B}
      \SOEA(P){M}
      \NOEA(B){D}
      \SOEA(B){C}
      \SOEA(C){L}
      \tikzset{LabelStyle/.style = {fill=white}}
      \tikzset{EdgeStyle/.style  = {&lt;-&gt;}}
      \Edge[label=$4$](P)(M)
      \Edge[label=$9$](C)(M)
      \Edge[label=$4$](C)(L)
      \Edge[label=$5$](C)(D)
      \Edge[label=$10$](B)(M)
      \tikzset{EdgeStyle/.style  = {&lt;-&gt;,bend right}}
      \Edge[label=$11$](L)(D)
      \tikzset{EdgeStyle/.style  = {-&gt;}}
      \Edge[label=$3$](C)(B)
      \Edge[label=$10$](D)(B)
      \Edge[label=$10$](L)(M)
      \Edge[label=$10$](B)(P)
    \end{tikzpicture}
  \end{minipage}
\end{enumerate}

%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\vfill\newpage
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
Code du graphe prÃ©cÃ©dent

\bigskip
\begin{tkzexample}[code only]
\begin{minipage}[c]{0,68\textwidth}
\begin{tikzpicture}[&gt;=latex]
    \SetGraphUnit{4}
    \tikzset{VertexStyle/.style  = {shape         = circle,
                                    draw          = black,
                                    inner sep     = 2pt,%
                                    minimum size  = 6mm,
                                    outer sep     = 0pt,
                                    fill          = gray!60}}
    \Vertex {P}
    \NOEA(P){B}
    \SOEA(P){M}
    \NOEA(B){D}
    \SOEA(B){C}
    \SOEA(C){L}
    \tikzset{LabelStyle/.style = {fill=white}}
    \tikzset{EdgeStyle/.style  = {&lt;-&gt;}}
    \Edge[label=$4$](P)(M)
    \Edge[label=$9$](C)(M)
    \Edge[label=$4$](C)(L)
    \Edge[label=$5$](C)(D)
    \Edge[label=$10$](B)(M)
    \tikzset{EdgeStyle/.style  = {&lt;-&gt;,bend right}}
    \Edge[label=$11$](L)(D)
    \tikzset{EdgeStyle/.style  = {-&gt;}}
    \Edge[label=$3$](C)(B)
    \Edge[label=$10$](D)(B)
    \Edge[label=$10$](L)(M)
    \Edge[label=$10$](B)(P)
\end{tikzpicture}
\end{minipage}
\end{tkzexample}

%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\vfill\newpage
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
%                         France juin 2003
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\subsection{France juin 2003 }\label{frj03} 
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;

Un concert de solidaritÃ© est organisÃ© dans une grande salle de spectacle. Ã€ ce concert sont conviÃ©s sept artistes de renommÃ©e internationale Luther Allunison (A), John Biaise (B), Phil Colline (C), Bob DitlÃ¢ne (D), Jimi Endisque (E), Robert Fripe (F) et Rory Garaguerre (G).

Les diffÃ©rents musiciens invitÃ©s refusant de jouer avec certains autres, l'organisateur du concert doit prÃ©voir plusieurs parties de spectacle. Les arÃªtes du  graphe $\Gamma$ ci-dessous indiquent quels sont les musiciens qui refusent de jouer entre eux.

\medskip
\begin{center}
\begin{tikzpicture}
  \SetGraphUnit{4}
  \GraphInit[vstyle=Normal]
  \tikzset{EdgeStyle/.style = {line width = 2pt}}
  \tikzset{VertexStyle/.append style = {line width = 2pt}}
  \Vertex{D}
  \SOEA(D){E}
  \EA(E){F}
  \NOEA(F){G}
  \NOWE(G){A}
  \NOWE(A){B}
  \SOWE(B){C}
  \Edges(F,G,A,D,F,B,E,G,C,F,A,E,C,B)
\end{tikzpicture}
\end{center}

\medskip
\begin{enumerate} 
\item DÃ©terminer la matrice associÃ©e au graphe $\Gamma$ (les sommets de $\Gamma$ Ã©tant classÃ©s dans l'ordre alphabÃ©tique).
\item Quelle est la nature du sous-graphe de $\Gamma '$ constituÃ© des sommets A, E, F et G ?

Que peut-on en dÃ©duire pour le nombre chromatique $\chi(\Gamma)$ du graphe $\Gamma$ ?
\item Quel est le sommet de plus haut degrÃ© de $\Gamma$ ?

En dÃ©duire un encadrement de $\chi(\Gamma)$.
\item AprÃ¨s avoir classÃ© l'ensemble des sommets de $\Gamma$ par ordre de degrÃ© dÃ©croissant, colorier le graphe $\Gamma$ figurant en annexe.
\item Combien de parties l'organisateur du concert doit-il  prÃ©voir ?

Proposer une rÃ©partition des musiciens pour chacune de ces parties.
\end{enumerate}

\medskip

\begin{tkzexample}[code only]
\begin{tikzpicture}
  \SetGraphUnit{4}
  \GraphInit[vstyle=Normal]
  \tikzset{EdgeStyle/.style = {line width = 2pt}}
  \tikzset{VertexStyle/.append style = {line width = 2pt}}
  \Vertex{D}
  \SOEA(D){E}\EA(E){F}
  \NOEA(F){G}\NOWE(G){A}
  \NOWE(A){B}\SOWE(B){C}
  \Edges(F,G,A,D,F,B,E,G,C,F,A,E,C,B)
\end{tikzpicture}
\end{tkzexample}


%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\vfill\newpage
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
%                        CE juin 2003
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\subsection{Centres Ã‰trangers juin 2003 }\label{cej03} 
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;

\bigskip
Un livreur d'une sociÃ©tÃ© de vente Ã&nbsp; domicile doit, dans son aprÃ¨s-midi, charger son camion Ã&nbsp; l'entrepÃ´t notÃ© A, livrer cinq clients que nous noterons B, C, D, E et F, puis retourner Ã&nbsp; l'entrepÃ´t. Le rÃ©seau routier, tenant compte des sens de circulation, et les temps de parcours (en minutes) sont indiquÃ©s sur le graphe G suivant :

\medskip
\begin{center}
  \begin{tikzpicture}[&gt;=latex]
    \SetGraphUnit{4}
    \Vertex {F}
    \NOWE(F){A}
    \NOEA(F){B}
    \SOEA(F){C}
    \SOWE(F){D}
    \SOWE(A){E}
    \tikzstyle{EdgeStyle}=[-&gt;]
    \tikzstyle{LabelStyle}=[fill=white]
    \Edge[label=$4$](A)(E)
    \Edge[label=$4$](E)(D)
    \Edge[label=$9$](D)(A)
    \Edge[label=$2$](B)(A)
    \Edge[label=$11$](C)(B)
    \Edge[label=$3$](D)(F)
    \Edge[label=$6$](F)(A)
    \tikzstyle{EdgeStyle}=[-&gt;,bend left=15]
    \Edge[label=$2$](D)(C)
    \Edge[label=$2$](C)(D)
    \Edge[label=$3$](F)(B)
    \Edge[label=$3$](B)(F)
    \Edge[label=$6$](F)(C)
    \Edge[label=$6$](C)(F)
  \end{tikzpicture}
\end{center}

\begin{enumerate} 
\item Donner la matrice M associÃ©e au graphe G.

On utilisera le modÃ¨le suivant :

\begin{center}
    \begin{tabular}{|*{7}{c|}}\cline{2-7}
    \multicolumn{1}{c|}{}%
        &amp; A &amp; B &amp; C &amp; D &amp; E &amp; F \\ \hline
    A   &amp;   &amp;   &amp;   &amp;   &amp;   &amp;   \\ \hline
    B   &amp;   &amp;   &amp;   &amp;   &amp;   &amp;   \\ \hline
    C   &amp;   &amp;   &amp;   &amp;   &amp;   &amp;   \\ \hline
    D   &amp;   &amp;   &amp;   &amp;   &amp;   &amp;   \\ \hline
    E   &amp;   &amp;   &amp;   &amp;   &amp;   &amp;   \\ \hline
    F   &amp;   &amp;   &amp;   &amp;   &amp;   &amp;   \\ \hline
    \end{tabular}
\end{center}

\item  On donne la matrice M$^6$ :

\[\text{M}^6 = 
\begin{pmatrix}
    8   &amp;   6   &amp;   6   &amp;   3   &amp;   4   &amp;   6 \\
    19  &amp;   11  &amp;   12  &amp;   9   &amp;   6   &amp;   16\\
    36  &amp;   28  &amp;   23  &amp;   22  &amp;   18  &amp;   34\\
    37  &amp;   24  &amp;   25  &amp;   17  &amp;   15  &amp;   31\\
    15  &amp;   12  &amp;   9   &amp;   10  &amp;   8   &amp;   15\\
    28  &amp;   22  &amp;   19  &amp;   15  &amp;   15  &amp;   26\\
\end{pmatrix}\]

On s'intÃ©resse aux chemins partant de l'entrepÃ´t A et se terminant en A.

   \begin{enumerate} 
   \item Combien existe-t-il de chemins de longueur 6 reliant A Ã&nbsp; A ?
   \item Citer ces chemins.
   \item Parmi ceux qui passent par tous les sommets du graphe, lequel minimise le temps de parcours ?
   \item Quelle consÃ©quence peut tirer le livreur du dernier rÃ©sultat ?
   \end{enumerate}
\item Au dÃ©part de sa tournÃ©e, le livreur a choisi de suivre l'itinÃ©raire le plus rapide. Malheureusement, le client C n'est pas prÃ©sent au passage du livreur et celui-ci dÃ©cide de terminer sa livraison par ce client. Indiquer  quel est le chemin le plus rapide pour revenir Ã&nbsp; l'entrepÃ´t A Ã&nbsp; partir de C. La rÃ©ponse devra Ãªtre justifiÃ©e.
\end{enumerate}

%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\vfill\newpage
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
Code du graphe prÃ©cÃ©dent

\bigskip
\begin{tkzexample}[code only]
\begin{tikzpicture}[&gt;=latex]
  \SetGraphUnit{3}
  \Vertex {F}
  \NOWE(F){A}
  \NOEA(F){B}
  \SOEA(F){C}
  \SOWE(F){D}
  \SOWE(A){E}
  \tikzstyle{EdgeStyle}=[-&gt;]
  \tikzstyle{LabelStyle}=[fill=white]
  \Edge[label=$4$](A)(E)
  \Edge[label=$4$](E)(D)
  \Edge[label=$9$](D)(A)
  \Edge[label=$2$](B)(A)
  \Edge[label=$11$](C)(B)
  \Edge[label=$3$](D)(F)
  \Edge[label=$6$](F)(A)
  \tikzstyle{EdgeStyle}=[-&gt;,bend left=15]
  \Edge[label=$2$](D)(C)
  \Edge[label=$2$](C)(D)
  \Edge[label=$3$](F)(B)
  \Edge[label=$3$](B)(F)
  \Edge[label=$6$](F)(C)
  \Edge[label=$6$](C)(F)
\end{tikzpicture}
\end{tkzexample}
\vfill\newpage
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
%                         AmÃ©rique du Nord mai 2004
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\subsection{AmÃ©rique du Nord juin 2004 }\label{anm04} 
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;


\textbf{Les parties A et B sont indÃ©pendantes.}

\textbf{Partie A}

On considÃ¨re le graphe G$_{1}$ ci-dessous :

\bigskip

\begin{center}
\begin{tikzpicture}[&gt;=latex]
    \SetGraphUnit{6}
    \Vertex{F}%
    \NOEA(F){B}
    \SOEA(F){E}
    \EA(B){C}
    \EA(E){D}
    \NO(D){A}
    \Edges(B,F,E,D,A,E,B,A,F,B,C,F,D)
\end{tikzpicture}
\end{center}

\medskip

\begin{enumerate}
\item Justifier les affirmations suivantes :

A$_{1}$ : \og le graphe G$_1$ admet au moins une chaÃ®ne eulÃ©rienne \fg.

A$_{2}$ ; \og La chaÃ®ne DABCFBEFAE n'est pas une chaÃ®ne eulÃ©rienne de G$_1$ \fg.

\item DÃ©terminer un sous-graphe complet de G$_1$, ayant le plus grand ordre possible. En dÃ©duire un minorant du nombre chromatique $\gamma$ de ce graphe.

\item DÃ©terminer un majorant de ce nombre chromatique. (On justifiera la rÃ©ponse).

\item En proposant une coloration du graphe G$_1$, dÃ©terminer son nombre chromatique.

\end{enumerate}

\medskip

\textbf{Partie B}

Soit la matrice M d'un graphe orientÃ© G$_2$ dont les sommets A, B, C, D et E sont pris dans l'ordre alphabÃ©tique.

On donne \[
    M = 
\begin{pmatrix}
    0   &amp;   1   &amp;   1   &amp;   1   &amp;   0\\
    1   &amp;   0   &amp;   1   &amp;   0   &amp;   1\\
    1   &amp;   1   &amp;   0   &amp;   0   &amp;   1\\
    0   &amp;   1   &amp;   0   &amp;   0   &amp;   1\\
    1   &amp;   1   &amp;   0   &amp;   1   &amp;   0\\
\end{pmatrix}
\]
~et~
\[
    \text{M}^3 = 
\begin{pmatrix}
    6   &amp;   6   &amp;   4   &amp;   5   &amp;   3\\
    5   &amp;   6   &amp;   5   &amp;   3   &amp;   6\\
    5   &amp;   7   &amp;   4   &amp;   3   &amp;   6\\
    3   &amp;   5   &amp;   3   &amp;   3   &amp;   3\\
    6   &amp;   6   &amp;   3   &amp;   3   &amp;   5\\
\end{pmatrix}.
\]
\begin{enumerate}
\item Construire le graphe G$_2$.
\item DÃ©terminer le nombre de chaÃ®nes de longueur 3 reliant B Ã&nbsp; D. Les citer toutes.
\end{enumerate}

%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\vfill\newpage
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
Code du graphe prÃ©cÃ©dent

\bigskip
\begin{tkzexample}[code only]
\begin{tikzpicture}[&gt;=latex]
  \SetGraphUnit{6}
  \Vertex{F}
  \NOEA(F){B}
  \SOEA(F){E}
  \EA(B){C}
  \EA(E){D}
  \NO(D){A}
  \Edges(B,F,E,D,A,E,B,A,F,B,C,F,D)
\end{tikzpicture}
\end{tkzexample}

%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\vfill\newpage
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
%                         CE mai 2004
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\subsection{Centres Ã©trangers  mai 2004 }\label{cem04} 
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;

\bigskip
Un jardinier possÃ¨de un terrain bien ensoleillÃ© avec une partie plus ombragÃ©e.

Il dÃ©cide d'y organiser des parcelles oÃ¹ il plantera 8 variÃ©tÃ©s de lÃ©gumes :

\medskip
\begin{center}\begin{minipage}[t]{0.48\textwidth}
    \begin{itemize}
    \item de l'ail (A),
    \item des courges (Co),
    \item des choux (Ch),
    \item des poireaux (Px),
    \item des pois (Po),
    \item des pommes de terre (Pt),
    \item des radis (R),
    \item et des tomates (T).
    \end{itemize}
\end{minipage}\end{center}

\medskip
Il consulte un almanach oÃ¹ figurent des incompatibilitÃ©s de plantes, donnÃ©es par les deux tableaux :

\medskip

\begin{minipage}[t]{0.46\textwidth}
\begin{tabular}{|l|l|}\hline
    \multicolumn{2}{|p{7cm}|}{Expositions incompatibles de plantes}\\
\hline
    \multicolumn{1}{|p{3.5cm}|}{Plantes d'ombre partielle}
    &amp;\multicolumn{1}{|p{3.5cm}|}{Plantes de plein soleil}\\ 
\hline
    &amp;                       \\
    &amp;   choux               \\
        pois    &amp;   tomates \\
        radis   &amp;   courges \\
    &amp;                       \\
    &amp;                       \\ 
\hline
    \multicolumn{2}{|p{7cm}|}{Par exemple : les pois sont incompatibles avec les
    choux, les tomates et les courges}\\ \hline
\end{tabular}
\end{minipage}
\hfill
\raisebox{6pt}{\begin{minipage}[t]{0.46\textwidth}
\begin{tabular}{|l|l|}\hline
\multicolumn{2}{|p{7cm}|}{Associations incompatibles de} \\
\multicolumn{2}{|p{7cm}|}{plantes dans une mÃªme parcelle}\\ \hline
 pois &amp; ail, poireaux\\ \hline
pommes de &amp; courges, radis et\\
terre &amp; tomates\\ \hline
&amp; tomates, ail\\
choux &amp; poireaux et courges\\ \hline
courges &amp; tomates\\ \hline
\multicolumn{2}{|p{7cm}|}{Par exemple : les pois sont incompatibles avec
l'ail et les poireaux}\\ \hline
\end{tabular}
\end{minipage}}

\medskip

Pour tenir compte de ces incompatibilitÃ©s le jardinier dÃ©cide de modÃ©liser la situation sous la forme d'un graphe de huit sommets, chaque sommet reprÃ©sentant un lÃ©gume.
\medskip
\begin{enumerate}
\item Sur la feuille annexe : complÃ©ter le graphe mettant en Ã©vidence les incompatibilitÃ©s d'exposition ou les associations incompatibles indiquÃ©es dans les deux tableaux ci-dessus.

\item Calculer la somme des degrÃ©s des sommets du graphe, en dÃ©duire le nombre de ses arÃªtes.

\item Rechercher un sous-graphe complet d'ordre 4, qu'en dÃ©duit-on pour le nombre chromatique du graphe ?

\item Donner le nombre chromatique du graphe et l'interprÃ©ter en nombre minimum de parcelles que le jardinier devra crÃ©er.

\item Donner une rÃ©partition des plantes pur parcelle de faÃ§on Ã&nbsp; ce que chaque parcelle contienne exactement deux types de plantes et que le nombre de parcelles soit minimum.

\item Donner une rÃ©partition des plantes de faÃ§on Ã&nbsp; ce qu'une parcelle contienne trois plantes et que le nombre de parcelles soit minimum.
\end{enumerate}

\medskip
\begin{center}
  \begin{tikzpicture}
     \tikzstyle{VertexStyle}= [shape       = circle,
                               fill         = white,%
                               minimum size = 26pt,%
                               draw]
      \Vertex[x=1,y=0.8]{R}
      \Vertex[x=0.2,y=3.3]{Po}
      \Vertex[x=0,y=2]{Pt}
      \Vertex[x=0.9,y=5]{Px}
      \Vertex[x=3.5,y=5]{A}
      \Vertex[x=5.6,y=3.4]{T}
      \Vertex[x=5.3,y=2]{Co}
      \Vertex[x=3.3,y=0.2]{Ch}
      \Edges(Po,Px,Po,A,Po,T,Po,Co,Po,Ch)
    \end{tikzpicture}
\end{center}

%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\vfill\newpage
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
Code du graphe prÃ©cÃ©dent

\bigskip
\begin{tkzexample}[code only]
\begin{tikzpicture}
 \tikzstyle{VertexStyle}= [shape       = circle,
                           fill         = white,%
                           minimum size = 26pt,%
                           draw]
  \Vertex[x=1,y=0.8]{R}
  \Vertex[x=0.2,y=3.3]{Po}
  \Vertex[x=0,y=2]{Pt}
  \Vertex[x=0.9,y=5]{Px}
  \Vertex[x=3.5,y=5]{A}
  \Vertex[x=5.6,y=3.4]{T}
  \Vertex[x=5.3,y=2]{Co}
  \Vertex[x=3.3,y=0.2]{Ch}
  \Edges(Po,Px,Po,A,Po,T,Po,Co,Po,Ch)
\end{tikzpicture}
\end{tkzexample}

%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\vfill\newpage
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
%                         France mai 2004
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\subsection{France  juin 2004}
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;

Le graphe ci-dessous indique, sans respecter d'Ã©chelle, les parcours possibles entre les sept bÃ¢timents d'une entreprise importante.

\medskip
\begin{tikzpicture}
  \SetGraphUnit{5}
  \Vertex{A}
  \NOEA(F){B}
  \SOEA(F){E}
  \EA(B){C}
  \EA(E){D}
  \NO(D){A}
  \Edges(F,E,F,D,F,C,F,A,F,B,A,E,E,D,D,A,B,A,C,B,E,B)
\end{tikzpicture}

Un agent de sÃ©curitÃ© effectue rÃ©guliÃ¨rement des rondes de surveillance. Ses temps de parcours en minutes entre deux bÃ¢timents sont les
suivants :

\medskip
\begin{center}
\begin{minipage}{0.5\textwidth}
    \begin{itemize}
    \item AB : 16 minutes ;
    \item AG : 12 minutes ;
    \item BC : 8 minutes ;
    \item BE : 12 minutes ;
    \item BG : 8 minutes ;
    \item CD : 7 minutes ;
    \item CE : 4 minutes ;
    \item CG : 10 minutes ;
    \item DE : 2 minutes ;
    \item EF : 8 minutes ;
    \item EG : 15 minutes ;
    \item FG : 8 minutes.
    \end{itemize}
\end{minipage}
\end{center}

\medskip
Sur chaque arÃªte, les temps de parcours sont indÃ©pendants du sens de parcours.

\begin{enumerate}
\item En justifiant la rÃ©ponse, montrer qu'il est possible que l'agent de sÃ©curitÃ© passe une fois et une seule par tous les chemins de cette usine. Donner un exemple de trajet.

\item L'agent de sÃ©curitÃ© peut-il revenir Ã&nbsp; son point de dÃ©part aprÃ¨s avoir parcouru une fois et une seule tous les chemins ? Justifier la rÃ©ponse.

\item Tous les matins, l'agent de sÃ©curitÃ© part du bÃ¢timent A et se rend au bÃ¢timent D.

En utilisant un algorithme que l'on explicitera, dÃ©terminer le chemin qu'il doit suivre pour que son temps de parcours soit le plus court possible, et donner ce temps de parcours.
\end{enumerate}

\medskip
\begin{tkzexample}[code only]
\begin{tikzpicture}
   \SetGraphUnit{5}
    \Vertex{A}   \NOEA(F){B}  \SOEA(F){E}
    \EA(B){C}    \EA(E){D}    \NO(D){A}
    \Edges(F,E,F,D,F,C,F,A,F,B,A,E,E,D,D,A,B,A,C,B,E,B)
\end{tikzpicture}
\end{tkzexample}
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\vfill\newpage
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;

%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
%                         La Reunion mai 2004
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\subsection{La RÃ©union juin 2004 }\label{larj04} 
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;


\textbf{Partie A}

On note $G$ le graphe reprÃ©sentÃ© ci-dessous et $M$ sa matrice obtenue en prenant les sommets dans l'ordre alphabÃ©tique. La matrice $M^3$ est Ã©galement donnÃ©e.

\medskip
\begin{center}
\begin{tikzpicture}[&gt;=latex]
    \SetGraphUnit{4.5}
    \Vertex {e}
    \NOEA(e){f}
    \SOEA(e){d}
    \SOEA(f){h}
    \Vertex[position={above of=e,yshift=2cm}]{g}
    \Vertex[position={left  of=g,xshift=-1cm}]{c} 
    \Vertex[position={left  of=d,xshift=-2cm}]{a} 
    \SOWE(c){b}
    \Edges(a,c,g)  \Edges(d,h,f,e,d,a,e,g,a,b,c,e)
    \Edge[style={bend left}](g)(h)
\end{tikzpicture}
\end{center}

\bigskip
\begin{center}
 $M^3 = \begin{pmatrix}
    10  &amp;   8   &amp;   11  &amp;   10  &amp;   12  &amp;   5   &amp;   13  &amp;   4\\
    8   &amp;   2   &amp;   7   &amp;   3   &amp;   5   &amp;   2   &amp;   4   &amp;   3\\
    11  &amp;   7   &amp;   8   &amp;   6   &amp;   12  &amp;   3   &amp;   10  &amp;   5\\
    10  &amp;   3   &amp;   6   &amp;   2   &amp;   11  &amp;   1   &amp;   4   &amp;   8\\
    12  &amp;   5   &amp;   12  &amp;   11  &amp;   8   &amp;   8   &amp;   13  &amp;   3\\
    5   &amp;   2   &amp;   3   &amp;   1   &amp;   8   &amp;   0   &amp;   2   &amp;   6\\
    13  &amp;   4   &amp;   10  &amp;   4   &amp;   13  &amp;   2   &amp;   6   &amp;   9\\
    4   &amp;   3   &amp;   5   &amp;   8   &amp;   3   &amp;   6   &amp;   9   &amp;   0\\
\end{pmatrix}$
\end{center}


\bigskip
Dire, en justifiant votre rÃ©ponse, si les affirmations suivantes sont vraies ou
 fausses :

\begin{enumerate}
\item L'ordre du graphe est Ã©gal au plus grand des degrÃ©s des sommets.
\item Le graphe $G$ contient un sous-graphe complet d'ordre $3$.
\item Les sommets de $G$ peuvent Ãªtre coloriÃ©s avec trois couleurs sans que deux sommets adjacents soient de mÃªme couleur.
\item Il est possible de parcourir ce graphe en passant une fois et une seule par chaque arÃªte.
\item Il existe au moins un chemin de longueur $3$ qui relie chaque sommet Ã&nbsp; chacun  des sept autres sommets du graphe.
\item il y a $72$ chemins de longueur $3$ qui relient le sommet $e$ Ã&nbsp; chacun des huit sommets du graphe.
\end{enumerate}

\newpage

\textbf{ Partie B}

Le graphe suivant reprÃ©sente un rÃ©seau de lignes d'autobus. Les sommets du graphe dÃ©signent les arrÃªts. Les poids des arÃªtes sont les durÃ©es de parcours,  en minutes, entre deux arrÃªts (correspondances comprises).

\medskip
\begin{center}
\begin{tikzpicture}[&gt;=latex]
      \SetGraphUnit{4.5}
    \Vertex {e}
    \NOEA(e){f}
    \SOEA(e){d}
    \SOEA(f){h}
    \Vertex[position={above  of=e,yshift=2cm}]{g}
    \Vertex[position={left  of=g,xshift=-1cm}]{c}
    \Vertex[position={left  of=d,xshift=-2cm}]{a}
    \SOWE(c){b}
    \tikzstyle{LabelStyle}=[fill=white]
    \Edge[label=$3$](a)(b)
    \Edge[label=$11$](a)(c)
    \Edge[label=$6$](a)(e)
    \Edge[label=$17$](a)(d)
    \Edge[style={pos=.25},label=$20$](a)(g)
    \Edge[label=$5$](c)(b)
    \Edge[label=$6$](c)(e)
    \Edge[label=$7$](c)(g)
    \Edge[label=$7$](f)(e)
    \Edge[label=$3$](d)(e)
    \Edge[label=$9$](d)(h)
    \Edge[label=$6$](g)(e)
    \Edge[style={bend left},label=$11$](g)(h)
    \Edge[label=$4$](f)(h)
\end{tikzpicture}
\end{center}

\medskip
DÃ©terminer, Ã&nbsp; l'aide d'un algorithme, la durÃ©e minimum pour aller de l'arrÃªt $a$  Ã&nbsp; l'arrÃªt $h$ et donner ce trajet.
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\vfill\newpage
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
Code du graphe prÃ©cÃ©dent

\medskip
\begin{tkzexample}[code only]
\begin{tikzpicture}[&gt;=latex]
    \SetGraphUnit{4.5}
    \Vertex {e}
    \NOEA(e){f}
    \SOEA(e){d}
    \SOEA(f){h}
    \Vertex[position={above of=e,yshift=2cm}]{g}
    \Vertex[position={left  of=g,xshift=-1cm}]{c} 
    \Vertex[position={left  of=d,xshift=-2cm}]{a} 
    \SOWE(c){b}
    \Edges(a,c,g)  \Edges(d,h,f,e,d,a,e,g,a,b,c,e)
    \Edge[style={bend left}](g)(h)
\end{tikzpicture}
\end{tkzexample}

et

\begin{tkzexample}[code only]
\begin{tikzpicture}[&gt;=latex]
    \SetGraphUnit{4.5}
    \Vertex {e}
    \NOEA(e){f}
    \SOEA(e){d}
    \SOEA(f){h}
    \Vertex[position={above  of=e,yshift=2cm}]{g}
    \Vertex[position={left  of=g,xshift=-1cm}]{c}
    \Vertex[position={left  of=d,xshift=-2cm}]{a}
    \SOWE(c){b}
    \tikzstyle{LabelStyle}=[fill=white]
    \Edge[label=$3$](a)(b)
    \Edge[label=$11$](a)(c)
    \Edge[label=$6$](a)(e)
    \Edge[label=$17$](a)(d)
    \Edge[style={pos=.25},label=$20$](a)(g)
    \Edge[label=$5$](c)(b)
    \Edge[label=$6$](c)(e)
    \Edge[label=$7$](c)(g)
    \Edge[label=$7$](f)(e)
    \Edge[label=$3$](d)(e)
    \Edge[label=$9$](d)(h)
    \Edge[label=$6$](g)(e)
    \Edge[style={bend left},label=$11$](g)(h)
    \Edge[label=$4$](f)(h)
\end{tikzpicture}
\end{tkzexample}

%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\vfill\newpage
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\subsection{AmÃ©rique du Sud Nov 2006}\label{amsn06} 
\begin{enumerate}
\item Ã€ l'occasion de la coupe du monde de football 2006 en Allemagne, une agence touristique organise des voyages en car Ã&nbsp; travers les diffÃ©rentes villes oÃ¹ se joueront les matchs d'une Ã©quipe nationale.

Les routes empruntÃ©es par les cars sont reprÃ©sentÃ©es par le graphe ci-dessous. Le long de chaque arÃªte figure la distance en kilomÃ¨tres sÃ©parant les villes.
Les lettres B, D, F, H, K, M, N et S reprÃ©sentent les villes Berlin, Dortmnd, Francfort, Hambourg, Kaiserslautern, Munich, Nuremberg et Stuttgart.

\bigskip

\begin{center}
\begin{tikzpicture}
  \Vertex[x=0 ,y=0]{K}
  \Vertex[x=0 ,y=2]{F}
  \Vertex[x=-1,y=4]{D}
  \Vertex[x=3 ,y=7]{H}
  \Vertex[x=8 ,y=5]{B}
  \Vertex[x=9 ,y=2]{N}
  \Vertex[x=5 ,y=0]{M}
  \Vertex[x=3 ,y=1]{S}
  \tikzstyle{LabelStyle}=[fill=white,sloped]
  \tikzstyle{EdgeStyle}=[bend left]
  \Edge[label=$120$](K)(F)
  \Edge[label=$650$](H)(S)
  \Edge[label=$780$](H)(M) 
  \Edge[label=$490$](D)(B) 
  \Edge[label=$600$](D)(M)
  \Edge[label=$580$](B)(M)
  \Edge[label=$600$](H)(N)
  \Edge[label=$490$](F)(H)
  \tikzstyle{EdgeStyle}=[bend right]
  \Edge[label=$630$](S)(B)
  \Edge[label=$210$](S)(N) 
  \Edge[label=$230$](S)(M) 
\end{tikzpicture}
\end{center}

\bigskip
En prÃ©cisant la mÃ©thode utilisÃ©e, dÃ©terminer le plus court chemin possible pour aller de Kaiserslautern Ã&nbsp; Berlin en utilisant les cars de cette agence.
\item Pour des raisons de sÃ©curitÃ©, les supporters de certaines Ã©quipes nationales participant Ã&nbsp; la coupe du monde de football en 2006 ne peuvent Ãªtre logÃ©s dans le mÃªme hÃ´tel.

On donne ci-dessous le graphe d'incompatibilitÃ© entre les supporters de diffÃ©rentes Ã©quipes : par exemple, un supporter de l'Ã©quipe A ne peut Ãªtre logÃ© avec un supporter de l'Ã©quipe P.

\bigskip
\begin{center}
\begin{tikzpicture}
 \tikzstyle{EdgeStyle}=[bend left]
 \Vertex[x=0,y=0]{G}
 \Vertex[x=0,y=3]{A} 
 \Vertex[x=3,y=5]{P}
 \Vertex[x=4,y=2]{C}
 \Vertex[x=8,y=3]{Q}
 \Vertex[x=7,y=0]{E}
 \Vertex[x=3,y=-1]{R}
 \Edges(G,A,P,Q,E) \Edges(C,A,Q) \Edges(C,R,G) \Edges(P,E,A)
\end{tikzpicture}
\end{center}

\bigskip
\begin{enumerate}
\item  DÃ©terminer le nombre chromatique de ce graphe en justifiant la valeur trouvÃ©e. 
\item  Proposer une rÃ©partition des supporters par hÃ´tel en utilisant un nombre minimum d'hÃ´tels.
\end{enumerate}
\end{enumerate}
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\vfill\newpage\null 
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
%                        Liban juin 2006
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;
\subsection{Liban juin 2006 }\label{lib06} 
%&lt;â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“â€“&gt;

\begin{enumerate}
\item  Dans un parc, il y a cinq bancs reliÃ©s entre eux par des allÃ©es.

On modÃ©lise les bancs par les sommets A, B, C, D, E et les allÃ©es par les arÃªtes du
graphe G ci-dessous :


\medskip
\begin{center}
\begin{tikzpicture}
     \SetGraphUnit{3} 
    \tikzstyle{VertexStyle}=[shape        = circle,
                             fill         = black,
                             minimum size = 20pt,
                             text         = white,
                             draw]   
    \Vertex[L= {\textbf{E}}]{E}
    \NOEA[L  = {\textbf{A}}](E){A}
    \SOEA[L  = {\textbf{D}}](E){D}
    \EA[L    = {\textbf{C}}](D){C}
    \NOEA[L  = {\textbf{B}}](C){B}  
   \tikzstyle{EdgeStyle}=[double           = orange,%
                          double distance  = 1pt,%
                          thick,%
                          bend right       = 20]
    \Edges(B,A,E,D,C,B,D)
\end{tikzpicture}
\end{center}

\medskip

\begin{enumerate}
\item On dÃ©sire peindre les bancs de faÃ§on que deux bancs reliÃ©s par une allÃ©e soient
toujours de couleurs diffÃ©rentes.

Donner un encadrement du nombre minimal de couleurs nÃ©cessaires et justifier.

DÃ©terminer ce nombre.
\item Est-il possible de parcourir toutes les allÃ©es de ce parc sans passer deux fois par
la mÃªme allÃ©e?
\end{enumerate}
\item Une exposition est organisÃ©e dans le parc. La frÃ©quentation devenant trop importante, on dÃ©cide d'instaurer un plan de circulation : certaines allÃ©es deviennent Ã&nbsp; sens unique, d'autres restent Ã&nbsp; double sens. Par exemple la circulation dans l'allÃ©e
situÃ©e entre les bancs B et C pourra se faire de B vers C et de C vers B, alors que la circulation dans l'allÃ©e situÃ©e entre les bancs A et B ne pourra se faire que de A vers B. Le graphe G$'$ ci-dessous modÃ©lise cette nouvelle situation :

\medskip
\begin{center}
\begin{tikzpicture}
     \SetGraphUnit{3} 
    \tikzstyle{VertexStyle}=[shape        = circle,
                             fill         = black,
                             minimum size = 20pt,
                             text         = white,
                             draw]   
    \tikzstyle{TempStyle}=[double           = orange,%
                           double distance  = 1pt]
    \Vertex[L= {\textbf{E}}]{E}
    \NOEA[L  = {\textbf{A}}](E){A}
    \SOEA[L  = {\textbf{D}}](E){D}
    \EA[L    = {\textbf{C}}](D){C}
    \NOEA[L  = {\textbf{B}}](C){B}  
    \tikzstyle{EdgeStyle}=[TempStyle,%
                           post,%
                           bend right      = 20]
    \Edges(A,E,D,C,B,D)
    \tikzstyle{EdgeStyle}=[TempStyle,%
                           pre,%
                           bend right      = 20]
    \Edges(B,A) 
    \tikzstyle{EdgeStyle}=[TempStyle,%
                           pre,%
                           bend left       = 20]
    \Edges(A,E,D,C,B)
\end{tikzpicture}
\end{center}

\begin{enumerate}
\item Donner la matrice M associÃ©e au graphe G$'$. (On ordonnera les sommets
par ordre alphabÃ©tique).
\item On donne M$^5
= \begin{pmatrix}
1&amp; 6&amp; 9&amp; 6&amp; 10\\
4&amp; 5&amp; 7&amp; 11&amp; 5\\
4&amp; 6&amp; 6&amp; 11&amp; 5\\
1&amp; 5&amp; 10&amp; 6&amp; 10\\
6&amp; 5&amp; 5&amp; 14&amp; 2\\
\end{pmatrix}$

Combien y a-t-il de chemins de longueur 5 permettant de se rendre du
sommet D au sommet B ?

Les donner tous.
\item Montrer qu'il existe un seul cycle de longueur 5 passant par le sommet A.

Quel est ce cycle ?

En est-il de mÃªme pour le sommet B ?
 \end{enumerate}
\end{enumerate}

\vfill\newpage\null
Code des graphes prÃ©cÃ©dents

\begin{tkzexample}[code only]
\begin{tikzpicture}
   \SetGraphUnit{3} 
   \tikzstyle{VertexStyle}=[shape        = circle,
                            fill         = black,
                            minimum size = 20pt,
                            text         = white,
                            draw]
   \Vertex[L= {\textbf{E}}]{E}
   \NOEA[L  = {\textbf{A}}](E){A}
   \SOEA[L  = {\textbf{D}}](E){D}
   \EA[L    = {\textbf{C}}](D){C}
   \NOEA[L  = {\textbf{B}}](C){B} 
   \tikzstyle{EdgeStyle}=[double           = orange,
                          double distance  = 1pt,
                          thick,
                          bend right       = 20]
    \Edges(B,A,E,D,C,B,D)
\end{tikzpicture}
\end{tkzexample}

\begin{tkzexample}[code only]
\begin{tikzpicture}
     \SetGraphUnit{3} 
    \tikzstyle{VertexStyle}=[shape        = circle,
                             fill         = black,
                             minimum size = 20pt,
                             text         = white,
                             draw]
    \tikzstyle{TempStyle}=[double           = orange,
                           double distance  = 1pt]
    \Vertex[L= {\textbf{E}}]{E}
    \NOEA[L  = {\textbf{A}}](E){A}
    \SOEA[L  = {\textbf{D}}](E){D}
    \EA[L    = {\textbf{C}}](D){C}
    \NOEA[L  = {\textbf{B}}](C){B}
    \tikzstyle{EdgeStyle}=[TempStyle,
                           post,
                           bend right      = 20]
    \Edges(A,E,D,C,B,D)
    \tikzstyle{EdgeStyle}=[TempStyle,%
                           pre,%
                           bend right      = 20]
    \Edges(B,A) 
    \tikzstyle{EdgeStyle}=[TempStyle,%
                           pre,%
                           bend left       = 20]
    \Edges(A,E,D,C,B)
\end{tikzpicture}
\end{tkzexample}

\endinput</pre></body></html>