\documentclass[a4paper,11pt,french]{article}
\linespread{1}


\newcommand{\ch}{Chapitre 1}
\newcommand{\Ch}{Introduction \`a la %\linebreak[2] 
th\'eorie des graphes}	
\newcommand{\Cl}{T$^{\circ}$ ES Sp\'ecialit\'e}	
\newcommand{\Annee}{2010-2011}	
\newcommand{\num}{1}	
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%		Package
%\usepackage[french,lined,boxed,commentsnumbered]{algorithm2e}

\input macro_final.tex

\geometry{hmargin=2cm,vmargin=2.5cm}

\setcounter{NumLecon}{1}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%	Premiere page
\begin{document}
 
\setcounter{NumLecon}{1}

\debutDsCha

\noindent \textit{La qualité de la rédaction, la clarté et la précision des raisonnements constituent un objectif majeur pour les
épreuves écrites de mathématiques et entreront pour une part importante dans l'appréciation des copies.\\
Chaque réponse doit être justifiée par un raisonnement mathématique.}

\Exo{\hfill (4 points)
\begin{multicols}{2}
 \begin{psmatrix}[mnode=circle, colsep=0.6,rowsep=1]
 &  &  & Q \\ 
P &  &  &  &  &  & S \\ 
 &  & R &  &  & T 
\end{psmatrix}
\psset{arrows=-}
\ncline{2,1}{1,4}
\ncline{2,1}{3,3}
\ncline{2,1}{2,7}
\ncline{1,4}{2,7}
\ncline{3,3}{2,7}
\ncline{3,3}{3,6}
\ncline{2,7}{3,6}\\
\textit{On expliquera chacune des réponses ci-dessous.}\\
Dans le graphe ci-contre, est-il possible de définir 
\begin{enumerate}
 \item Une chaîne eulérienne :
\begin{itemize}
 \item Partant de $Q$ et finissant en $T$ ? 
  \item Partant de $P$ et finissant en $R$ ?
\end{itemize}
\item Un cycle eulérien ?
\item En cas de réponse affirmative dans les questions précédentes, proposer un chemin.
\end{enumerate}
\end{multicols}
}

\Exo{\hfill (2 points)\\
Les sept collèges de la ville possèdent chacun une équipe de hand-ball. Les professeurs d’EPS
souhaitent organiser des rencontres entre ces équipes dans le courant du mois de mai, de telle sorte
que chaque équipe en rencontre trois autres.
Peut-on proposer un planning de rencontres ? \\
\textit{Justifier à l'aide d'un résultat du cours}
}


\Exo{\hfill (5 points)\\
Lors d’un séminaire, des groupes de travail doivent être constitués. Les incompatibilités de travail en équipe de 9 des
participants sont résumés par le graphe ci-dessous.
\begin{center}
\begin{psmatrix}[mnode=circle,colsep=0.5,rowsep=0.5]
 & D &  & C &  & B \\ 
 &  &  &  &  &  & A \\ 
E \\ 
 & F &  &  &  &  & I \\ 
 &  & G &  & H 
\end{psmatrix}
\psset{arrows=-}
\ncline{2,7}{1,4}
\ncline{2,7}{4,2}
\ncline{2,7}{5,3}
\ncline{2,7}{5,5}
\ncline{1,6}{1,4}
\ncline{1,6}{3,1}
\ncline{1,6}{4,2}
\ncline{1,6}{5,3}
\ncline{1,6}{5,5}
\ncline{1,6}{4,7}
\ncline{1,4}{1,2}
\ncline{1,4}{3,1}
\ncline{1,4}{4,2}
\ncline{1,4}{4,7}
\ncline{1,2}{4,2}
\ncline{1,2}{5,3}
\ncline{1,2}{5,5}
\ncline{5,3}{5,5}
\ncline{5,3}{4,7}
\ncline{5,5}{4,7}
\end{center}
\begin{enumerate}
 \item Donner le degré de chaque sommet de $G$.\textit{ On présentera les résultats sous forme d'un tableau.}
 \item Trouver un sous graphe complet de $G$ d’ordre 4
 \item Déduire de 1) et 2) un encadrement du nombre chromatique de $G$ .
 \item Déterminer le nombre chromatique de $G$.
 \item Proposer une répartition des 9 participants en un minimum de groupes de travail.
\end{enumerate}
}
\newpage
\Exo{\hfill (4 points)
\begin{multicols}{2}
\begin{center}
\includegraphics[scale=1]{blaireau_carte_Europe.eps}\\ 
\end{center}
La carte ci-contre représente le statut juridique des blaireaux dans certains pays d'Europe.
\begin{enumerate}
  \item On considère le graphe dont les sommets sont les pays et les arêtes représentent la frontière commune entre eux
\textit{(inutile de le représenter)}. Ce graphe est-il connexe ? Pourquoi ?
 \item  Blaireau, un blaireau de Hongrie, se dit en voyant cette carte qu'il n'a vraiment pas de chance, car il est dans une zone chassable, alors que dans tous les pays
autour, il serait protégé. Aussi, il décide de partir en voyage. 
Il aimerait visiter la Pologne, la République Tchèque, la Slovaquie, la Autriche, la Slovénie et revenir en Hongrie.
\end{enumerate}
\end{multicols}
\begin{enumerate}
 \item[\textbf{a.}] Construire un graphe dont les sommets sont ces six pays
   et les arêtes représentent la frontière commune entre eux.
 \item[\textbf{b.}] Blaireau souhaite visiter tous ces pays en ne traversant qu’une seule fois
      chaque frontière mais en les traversant toutes.
      Il pourra éventuellement visiter plusieurs fois le même pays.
       Un tel circuit est-il possible ? \qquad \textit{Dans l’affirmative, proposer une solution.}
 \item[\textbf{c.}] Blaireau se souvient alors qu'il a une amie d'enfance qui vit à Prague, en République Tchèque. Il décide 
alors de changer son circuit, et de ne pas prévoir de retour en Hongrie pour le moment. Peut-il dans ce cas, trouver un chemin
lui permettant de visiter tous les pays sélectionnés en ne traversant qu'une seule fois chaque frontière mais en les traversant toutes ?\\
\textit{Dans l'affirmative, proposer une solution.}
 \item[\textbf{d.}] Blaireau souhaite montrer son itinéraire à sa maman. Il a donc dessiné le même graphe que vous. Combien de couleurs sont nécessaires pour le colorier ?
\end{enumerate}
}



\Exo{\hfill (5 points)
\begin{multicols}{2}
Le directeur d'un petit zoo veut réorganiser l'habitat
de telle sorte que les animaux cohabitent dans des
enclos plus vastes.
Malheureusement, il n'est pas possible de laisser
tous les animaux ensemble dans un seul enclos,
car certains sont les prédateurs des autres !
Le tableau ci-contre indique, parmi les dix races
d'animaux que possède le zoo,
lesquelles sont les prédateurs ou les proies des autres.
\begin{enumerate}
 \item Représenter le graphe des incompatibilités correspondants.
 \item Donner la distance entre $h$ et $b$, puis celle entre $d$ et $j$.
  \item Appliquer l'algorithme de coloration de Welsh et Powell à ce graphe.
 \item Trouver un cycle élémentaire du graphe d’ordre 5.
\item En déduire combien d'enclos le directeur du zoo doit-il prévoir au minimum ? \textit{Expliquer.}
\end{enumerate}
\begin{flushright}
  \begin{tabular}{*{11}{|c}|}
 \hline
  & a & b & c & d & e & f & g & h & i & j \\\hline
a &   &$*$&   &   &$*$&   &   &   &   & $*$\\\hline
b &$*$&   &   &$*$&   &   &$*$&   &   &\\\hline
c &   &   &   &   &   &   &   &$*$&   &$*$\\\hline
d &   &$*$&   &   &   &$*$&   &   &   &   \\\hline
e &$*$&   &   &   &   &   &   &   &$*$&\\\hline
f &   &   &   &$*$&   &   &   &   &   &$*$\\\hline
g &   &$*$&   &   &   &   &   &   &   &\\\hline
h &   &   &$*$&   &   &   &   &   &$*$&\\\hline
i &   &   &   &   &$*$&   &   &$*$&   &$*$\\\hline
j &$*$&   &$*$&   &   &$*$&   &   &$*$&\\\hline
\end{tabular}
\end{flushright}
\end{multicols}
}


\end{document}
