\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}{Exemples introductifs à la théorie des graphes}}
\end{center}

\emph{\textcolor{blue}{On ne cherchera pas à donner de justification.}}



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


\subsection{}
Peut-on dessiner les figures ci-dessous sans lever le crayon et sans tracer deux fois le même segment ?\\
\begin{center}
\psset{unit=0.4}\begin{pspicture}(0,0)(6,4)
\psframe(0,0)(6,4)
\psline(0,0)(6,4)
\psline(0,4)(6,0)
\psdots(0,0)(6,0)(6,4)(0,4)(3,2)
\end{pspicture}\\

\begin{pspicture}(0,0)(6,6)
\psframe(0,0)(6,4)
\psline(0,0)(6,4)
\psline(0,4)(6,0)
\psline(0,4)(3,6)
\psline(6,4)(3,6)
\psdots(0,0)(6,0)(6,4)(0,4)(3,2)(3,6)
\end{pspicture}

\end{center}

\subsection{\textcolor{blue}{Ponts de Königsberg}}
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}
\psset{unit=1cm}
\begin{pspicture}(8,4)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\newrgbcolor{grisb}{.96 .96 .98}
\pscustom[linewidth=1pt,linecolor=bleu,fillstyle=solid,fillcolor=grisb]{%
\pscurve(0,2)(.8,2.1)(2,3.2)(5,3.1)(6,2.7)(8,3.4)
\pscurve[liftpen=1](8,.7)(7,.9)(5.8,1.3)(4.7,.85)(2,.65)(1,1.4)(.5,1.5)(0,1.5)}
\psccurve[linewidth=1pt,linecolor=bleu,fillstyle=solid,fillcolor=white](1.5,2.2)(3,3)(5.65,2)(4.5,1.2)(2.2,1)
\pscurve[linewidth=1pt,linecolor=bleu,fillstyle=solid,fillcolor=white,liftpen=1](8,3)(7.5,2.8)(5.95,2)(8,1)
\psframe[linewidth=.5pt,linecolor=bleu](0,0)(8,4)
\def \pont{\psframe[fillstyle=solid,fillcolor=white,linecolor=white](-.15,-.3)(.15,.3)
\psline[linewidth=1pt,linecolor=bleu](-.25,.3)(-.15,.3)(-.15,-.3)(-.25,-.3)
\psline[linewidth=1pt,linecolor=bleu](.25,-.3)(.15,-.3)(.15,.3)(.25,.3)
} 
\rput{-15}(2.5,.7){\pont
\rput[b]{0}(0,-.5){\prune{$a$}}}
\rput{18}(4.7,1.1){\pont
\rput[b]{0}(0,-.5){\prune{$b$}}} 
\rput{90}(5.8,2){\pont
\rput[r]{*0}(0,-.5){\prune{$c$}}}
\rput{-15}(4.8,3){\pont
\rput[t]{0}(0,.5){\prune{$d$}}} 
\rput{12}(2.5,3.15){\pont
\rput[t]{0}(0,.5){\prune{$e$}}}
\rput{-15}(7,1){\pont
\rput[b]{0}(0,-.5){\prune{$f$}}}  
\rput{15}(7,2.8){\pont
\rput[t]{0}(0,.5){\prune{$g$}}}  
\rput(3.5,2){\bleu{$A$}}
\rput(1,.5){\bleu{$B$}}
\rput(1,3.2){\bleu{$C$}} 
\rput(7,2){\bleu{$D$}}      
\end{pspicture}
\end{center}

Est-il possible de se promener en ne passant qu'une seule fois sur chacun des sept ponts ?

\columnbreak

\subsection{}
Cinq pays sont représentés ci-contre avec leurs frontières.\\
Est-il possible de partir d'un pays et d'y revenir en franchissant chaque frontière une fois et une seule ?
\begin{center}
\psset{unit=1}
\begin{pspicture}(0,0,)(6,6)
\psframe(0,0)(3,3)\psframe(3,0)(6,3)
\psframe(0,3)(2,5)\psframe(2,3)(4,5)\psframe(4,3)(6,5)
\uput[u](1.5,1.5){$P_{4}$}\uput[u](4.5,1.5){$P_{5}$}
\uput[u](1,3.8){$P_{1}$}\uput[u](3,3.8){$P_{2}$}\uput[u](5,3.8){$P_{3}$}
\end{pspicture}
\end{center}

\subsection{}
Une chaîne de cinq magasins décide d'ouvrir ses magasins en nocturne avec les contraintes suivantes :
\begin{itemize}
\item les deux premiers magasins ne peuvent pas être ouverts ensemble ;
\item il en est de même pour les deux derniers ;
\item au plus un seul magasin peut être ouvert parmi les magasins 1, 3, 4.
\end{itemize}
Trouver un état qui maximise le nombre de magasins ouverts en nocturne, tout en respectant les contraintes.


\subsection{}
Une ligue de foot comporte 5 équipes.\\
Il est décidé par le bureau de la ligue que lors d’un week-end d’entraînement, chaque équipe jouera 4 matchs. Comment l’organiser ?
Le calendrier étant trop chargé, les organisateurs décident que chaque équipe ne jouera que 3 matchs. Comment l'organiser ?

\end{multicols}


\newpage
\setcounter{subsection}{0}
Solutions :

\subsection{}
De tels tracés sont possibles si le graphe correspondant admet un chemin eulérien, c’est-à-dire s’il contient exactement 0 ou 2 sommets de degré impair. La réponse est donc positive uniquement pour la deuxième figure.

\subsection{}

\label{fin}
\end{document}  