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

\Cb{Exercices de recherche}

\Exop{
Peut-on parcourir une fois et une seule les arêtes des graphes ci-dessous sans lever le crayon ?}
\begin{multicols}{2}
 \begin{center}
  \begin{psmatrix}[mnode=circle]
A &  &  &  & B \\ 
 &  & E \\ 
D &  &  &  & C 
\end{psmatrix}
\psset{arrows=-}
\ncline{1,1}{1,5}
\ncline{1,1}{3,1}
\ncline{1,1}{2,3}
\ncline{1,5}{3,5}
\ncline{1,5}{2,3}
\ncline{3,5}{3,1}
\ncline{3,5}{2,3}
\ncline{3,1}{2,3}

\begin{psmatrix}[mnode=circle]
A &  &  &  & B \\ 
 &  & E \\ 
D &  &  &  & C \\ 
 &  & F 
\end{psmatrix}
\psset{arrows=-}
\ncline{1,1}{1,5}
\ncline{1,1}{3,1}
\ncline{1,1}{2,3}
\ncline{1,5}{3,5}
\ncline{1,5}{2,3}
\ncline{3,5}{3,1}
\ncline{3,5}{2,3}
\ncline{3,5}{4,3}
\ncline{3,1}{2,3}
\ncline{3,1}{4,3}
 \end{center}
\end{multicols}

\Exop{
Le nombre de personnes ayant vécu ou qui vivent encore sur la terre et qui ont donnée un nombre impair de poignées de 
mains est-il pair ou impair ?
}

\Exop{
Au XVIIIème siècle, les habitants de Königsberg (actuellement Kaliningrad, région de la Russie
frontalière de la Pologne et de la Lituanie) aimaient se promener le dimanche. La ville de Königsberg
comprenait 7 ponts, disposés selon le schéma ci-dessous. Le souhait des habitants de Königsberg
était de faire un trajet passant une fois et une seule par chaque pont. Comment faire ?
\begin{center}
\includegraphics{ponts.eps} 
\end{center}
}

\Exop{
Peut-on aligner tous les pions d’un jeu de domino suivant la règle du domino ? On commencera par
étudier la question avec un jeu dont les dominos comportent les chiffres jusqu'à n, pour n=2,3,4.\\
}


\newpage

\Cb{Exercices d'application du cours}


\Exop{Représenter la situation suivante ci-dessous à l'aide d'un graphe :\\
Trois pays envoie chacun à une conférence deux espions ; chaque espoins doit espionner tous les espions des autres pays.
}

\Exop{Une ligue de football comporte 5 équipes.
\begin{itemize}
 \item Il est décidé par le bureau de la ligue que lors d'un we d'entraînement, chaque équipe jouera quatre matches
(deux équipes ne peuvent pas se rencontrer plus d'une fois). Comment l'organiser (chacun est libre de ses règles d'organisation) ?
 \item Le calendrier étant trop chargé, les organisateurs décident que chaque équipe ne jouera que trois matches. Comment l'organiser ?
\end{itemize}
}

\Exop{
M. et Mme Euler assistent à une réunion. Il y a trois autres couples dans l'assistance et plusieurs
poignées de mains sont échangées. Personne ne serre sa propre main et les époux ne se serrent pas
la main. Deux personnes quelconques de l’assemblée se serrent la main au plus une fois. M. Euler
constate que les 7 autres personnes ont échangé des poignées de mains en nombres tous distincts.
Combien de poignées de mains M. et Mme Euler ont-ils échangé avec les autres membres de la
réunion ?
}




\newpage

\Cb{Exercices de recherche 2}

\Exop{
On trouve ci-après le graphe d'incompatibilité de six produits chimiques. Quel est le nombres de wagons nécessaires à leur transport ?
\begin{center}
\begin{psmatrix}[mnode=circle]
 &  & P1 \\ 
P6 &  &  & P2 \\ 
 & P5 \\ 
 &  & P4 &  & P3 
\end{psmatrix}
\psset{arrows=-}
\ncline{1,3}{2,4}
\ncline{1,3}{4,3}
\ncline{2,4}{4,5}
\ncline{2,4}{3,2}
\ncline{4,5}{4,3}
\ncline{3,2}{2,1}
\end{center}
}

\Exop{
Une chèvre, un chou et un loup  se trouvent sur la rive d'un fleuve. Un passeur souhaite les transporter sur l'autre rive
mais sa barque étant trop petite, il ne peut transporter qu'un seul d'entre eux à la fois. Comment doit-il procéder
afin de ne jamais laisser ensemble sans surveillant le loup et la chèvre, ainsi que la chèvre et le chou ?
}

\Exop{
\begin{multicols}{2}
 On veut colorer chaque pays de la carte ci-dessous de telle sorte que deux pays voisins ne soient pas
de la même couleur. Montrer qu’il faut disposer d’au moins quatre couleurs et que quatre couleurs
suffisent. (Deux pays dont les frontières n’ont qu’un nombre fini de points communs ne sont pas
considérés comme voisins).
\begin{center}
\includegraphics[scale=0.8]{carte.eps} 
\end{center}
\end{multicols}
}\\




\end{document}
