\documentclass[12pt] {article} \usepackage[T1]{fontenc} 
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,graphicx,multicol,mathrsfs, fancyhdr,enumerate,fourier,eurosym,alterqcm,enumerate,tabularx,variations,numprint}
\usepackage[dvips]{color}
\usepackage[tikz]{bclogo}
\usepackage{pst-plot,pst-tree,pstricks,pst-node,pstricks-add,pst-math,pst-xkey,pst-eucl}
\usepackage[francais]{babel} 
\everymath{\displaystyle}
%\usepackage[colorlinks=true,pdfstartview=FitV,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\textwidth 19cm \textheight 24cm \hoffset 
-1,4cm \voffset -3.7cm \oddsidemargin 0pt 
\renewcommand{\thesubsection}{\textcolor{blue}{\Roman{subsection}}} 
\renewcommand{\thesubsubsection}{\textcolor{blue}{\Roman{subsection}}.\textcolor{blue}{\arabic{subsubsection}}} 
\pagestyle{empty}
% pour le pied de page central
\cfoot{Page \thepage/\pageref{fin}}

\begin{document}
%\tableofcontents

\begin{center}\section*{\textcolor{red}{Exercices sur les chaînes et cycles eulériens}}\end{center}



\begin{multicols}{2}
\setlength{\columnseprule}{1pt}
\setlength{\columnsep}{2 cm}

\subsection{\textcolor{blue}{\no 53 page 283}}
Une grande surface est conçue de telle façon que six secteurs A, B, C, D, E, F soient reliés par des grandes allées comme montré sur le graphe ci-dessous.

\begin{center}
\psset{unit=1}
\begin{pspicture}(-1,-1)(7,4)
%\psset{arrowsize=2.5pt 3}
 \psset{arcangle=0}
\cnodeput(0,0){A}{E}
\cnodeput(3,0){B}{A} 
\cnodeput(5,0){C}{B} 
\cnodeput(7,0){D}{F} 
\cnodeput(3,3){E}{D} 
\cnodeput(5,3){F}{C}
\ncarc{A}{B}
\ncarc{B}{C}
\ncarc{C}{D}
\ncarc{A}{E}
\ncarc{B}{E}
\ncarc{A}{F}
\ncarc{B}{F}
\ncarc{F}{C}
\ncarc{D}{E}
\ncarc{F}{E}
\end{pspicture}
\end{center}

\begin{enumerate}
\item Justifier que le graphe est connexe.\\
Dresser le tableau donnant le degré de chaque sommet.

\item Un visiteur désire parcourir l'ensemble des allées en ne passant pa celles-ci qu'une seule fois.\\
Démontrer que son souhait est réalisable et donner un exemple d'un tel parcours.
\end{enumerate}

\subsection{\textcolor{blue}{\no 56 page 284}}
On considère le graphe associé à la matrice \[M=\begin{pmatrix}1&0&0	&1&1\\0&1&1&0&0\\1&0&0&1&1\\0&0&1&0&1\\1&0&0&0&0\end{pmatrix}\]
Préciser si ces affirmations sont vraies ou fausses.
\begin{enumerate}
\item Ce graphe ne content pas de boucle.

\item Ce graphe est un graphe orienté.

\item Le degré du premier sommet est 6.

\item Il y a deux arêtes qui partent de B.

\item Il y a deux arêtes qui arrivent à B.

\item Le graphe contient 11 arêtes.
\end{enumerate}

\subsection{\textcolor{blue}{d'après Pondichéry avril 2011}}
Un orchestre doit effectuer une tournée passant par les villes A, B, C, D, E, F, G et H, en utilisant le réseau autoroutier.

\medskip
 
Le graphe $\Gamma$ ci-dessous représente les différentes villes de la tournée et les autoroutes reliant ces villes (une ville est représentée par un point, une autoroute par une arête) :

\medskip

\begin{center}
\psset{xunit=1.5cm,yunit=1.cm}
\begin{pspicture}(5,7)
\uput[ul](0.5,6.5){A} \uput[r](2.3,5.5){B} \uput[l](1,4.8){C} \uput[ur](2.5,3.4){D} 
\uput[l](0.5,3.3){E} \uput[r](4.8,3){F} \uput[dl](2,0.6){G} \uput[d](3.6,0.2){H}
\pspolygon(0.5,6.5)(2.3,5.5)(2.5,3.4)(4.8,3)(3.6,0.2)(2,0.6)(0.5,3.3)(3.6,0.2)(2.5,3.4)(1,4.8)
\psline(2.3,5.5)(1,4.8)(0.5,3.3) 
\psdots(0.5,6.5)(2.3,5.5)(2.5,3.4)(4.8,3)(3.6,0.2)(2,0.6)(0.5,3.3)(1,4.8)
\end{pspicture}
\end{center} 

Est-il possible d'organiser la tournée en passant au moins une fois par chaque ville, tout en 
empruntant une fois et une seule chaque tronçon d'autoroute? (la réponse sera justifiée).
 
Si oui citer un trajet de ce type. 


\end{multicols}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\setcounter{subsection}{0}

\textbf{\textcolor{blue}{Correction}} :

\subsection{}

\begin{enumerate}
\item \begin{tabular}{|l*{7}{c|}}\hline
sommet&A&B&C&D&E&F\\
\hline
degré&4&3&4&4&3&2\\
\hline
\end{tabular}

\item Il y a deux sommets dont le degré est impair et deux seulement : E et B. Il y a une chaîne eulérienne reliant E à B.

\item 
\begin{enumerate}[$\bullet$]
\item on commence par trouver une chaîne reliant E à B : E-D-C-B

\item On adjoint un cycle un cycle contenant des arêtes non contenues dans la chaîne précédente et d'extrémité un sommet de la chaine précédente  : \textcolor{red}{E-C-A-E}-E-D-C-B

\item On recommence : E-C-A-E-E-D-C-B-\textcolor{red}{F-D-A-B}
\end{enumerate}
\end{enumerate}

\subsection{}

\begin{enumerate}
\item Il y a des boucles en A et B (éléments de la diagonale de la matrice)

\item Le graphe est orienté (matrice non symétrique)

\item Le degré du premier sommet est 1

\item Oui, deux arêtes partent de B, donc une boucle.

\item Une seule arête arrive ne B.

\item Oui, il y a 11 arêtes.
\end{enumerate}



\subsection{\textcolor{blue}{Pondichéry}}
On cherche s'il existe une chaîne eulérienne.

La chaîne A-B-D-F-H-G-E-C contient tous les sommets du graphe.

Donc pour toute paire de sommets il existe un chemin les reliant : le graphe est connexe.

Les sommets B et E sont les seuls de degré impair : il existe donc une chaîne eulérienne partant de l'un d'eux et finissant à l'autre ; par exemple : B-A-C-D-F-H-G-E (ou inversement). 
\label{fin}
\end{document}  