\documentclass[a4paper,11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[french]{babel}
\usepackage{amsmath,amsfonts,amsthm,amssymb,amsbsy,amscd,mathrsfs}
\usepackage{lmodern}
\usepackage{fourier}
\usepackage[scaled=0.875]{helvet} % ss
\usepackage{textcomp}
\usepackage{dsfont} % pour les symboles des ensembles
\usepackage[left=2cm,right=2cm,top=2cm,bottom=2.5cm]{geometry}
\usepackage{fancyhdr} 
\fancyhf{}
\setlength{\headheight}{26pt}
\setlength{\footskip}{18pt}
\renewcommand {\headrulewidth}{0pt}
\renewcommand {\footrulewidth}{0pt}
\usepackage{lastpage}
%\usepackage{makeidx}
\usepackage{graphicx}
\usepackage{hyperxmp}
\usepackage[colorlinks=true,pdfstartview=FitV,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\pagestyle{fancy}
\usepackage{array}
\usepackage{tabularx}
\usepackage{multirow}
\usepackage{hhline}
\usepackage[table]{xcolor}
\usepackage{mathtools} %pour l'alignement des termes d'une matrice
\usepackage{fltpoint}
\usepackage{xcolor,colortbl}
\usepackage{pstricks,pst-all,pst-plot,pstricks-add,pst-tree,pst-3dplot,pst-func}
\usepackage{ifthen}
\usepackage{calc}
\usepackage{esvect}
\usepackage{pifont}
\usepackage[np]{numprint}
\setlength{\parindent}{0mm}
\usepackage [alwaysadjust]{paralist}
\setdefaultenum {1.}{a)}{}{}
\hyphenpenalty=10000 
\tolerance=2000
\emergencystretch=1em
\widowpenalty=10000
\clubpenalty=10000
\raggedbottom
\renewcommand*{\tabularxcolumn}[1]{m{#1}} %centrage vertical des cellules d'un tableau tabularx
\newcommand{\Oij}{\ensuremath{\left( {{\mathrm{O}};\vec{\imath},\vec{\jmath}} \right)}}
\newcommand{\Oijk}{$\left( {{\mathrm{O}};\vec i,\vec j ,\vec k} \right)$}
\newcommand{\euro}{\texteuro{}}
\newcommand{\R}{\mathds {R}}
%\newcommand{\C}{\mathds {C}}
\newcommand{\N}{\mathds {N}}
\newcommand{\Z}{\mathds {Z}}
\newcommand{\Q}{\mathds {Q}}
\newcommand{\e}{\mathrm {e}}
\newcommand{\dd}{\,\mathrm{d}}
\DecimalMathComma

\newcounter{nexo}    % déclaration du numéro d'exo
\setcounter{nexo}{0} % initialisation du numero
\newcommand{\exo}{%
  \stepcounter{nexo} 
  \par{\textsf{\textbf{\textcolor{blue}{{\textsc{exercice  \arabic{nexo}}}}}}}
  }%
  
\lhead{\footnotesize{\textsf{Lycée Camille SEE\\Jeudi 22 mars 2007}}}
\chead{\textsf{\textcolor{red}{\textbf{CONTRÔLE SPÉCIALITÉ}}}}
\rhead{\footnotesize{\textsf{T\textsuperscript{le} ES\\Durée 1 heure 30}}}
%pied de page                                              
\rfoot{\scriptsize{\textsf{Page~\thepage{}~sur~\pageref{LastPage}}}}
\lfoot{ \htmladdnormallink{\scriptsize{\textsf{\textsc{A. Yallouz (MATH@ES)}}}}{http://yallouz.arie.free.fr}}

\begin{document}

\exo 

\medskip

\begin{enumerate}
	\item Dessiner le graphe (non orienté) à huit sommets dont les arêtes sont :
	
$(1 ; 2)$, $(1 ; 3)$, $(2 ; 3)$, $(2 ; 4)$, $(2 ; 7)$, $(3 ; 5)$, $(3 ; 6)$, $(3 ; 7)$, $(4 ; 5)$, $(4 ; 7)$, $(5 ; 6)$, $(5 ; 7)$,  $(6 ; 7)$, $(6 ; 8)$, $(7 ; 8)$.
\item Donner la matrice $M$ associée à ce graphe.
\item Combien y a-t-il de chemins de longueur 3 permettant de se rendre du sommet 1 au sommet 8 ? Les donner tous.
\item Est-il possible de parcourir toutes les arêtes de ce graphe sans passer plus d'une fois par la même arête ?
\item Existe-il un cycle passant une fois et une seule par toutes les arêtes du graphe ?
\end{enumerate}


\bigskip

\exo 

\medskip
 

On considère le graphe $\mathcal{G}$ ci-dessous. On note $\Gamma$  son nombre chromatique.
\begin{center}
\psset{unit=2cm,linecolor=darkgray,linewidth=0.5pt}
\begin{pspicture*}(-0.25,-0.25)(4.25,3.25)
\cnodeput(2,3){A}{\textsf{\small{A}}}
\cnodeput(0,2){B}{\textsf{\small{B}}}
\cnodeput(2,2){C}{\textsf{\small{C}}}
\cnodeput(4,2){D}{\textsf{\small{D}}}
\cnodeput(0,1){E}{\textsf{\small{E}}}
\cnodeput(2,1){F}{\textsf{\small{F}}}
\cnodeput(4,1){G}{\textsf{\small{G}}}
\cnodeput(1,0){H}{\textsf{\small{H}}}
\cnodeput(3,0){I}{\textsf{\small{I}}}
\psset{linecolor=gray}
\ncline{-}{A}{B}
\ncline{-}{A}{C}
\ncline{-}{A}{D}
\ncline{-}{A}{G}
\ncline{-}{B}{C}
\ncline{-}{B}{E}
\ncline{-}{C}{D}
\ncline{-}{C}{F}
\ncline{-}{C}{E}
\ncline{-}{C}{G}
\ncline{-}{D}{G}
\ncline{-}{E}{F}
\ncline{-}{E}{H}
\ncline{-}{F}{H}
\ncline{-}{F}{I}
\ncline{-}{F}{G}
\ncline{-}{G}{I}
\ncline{-}{H}{I}
\end{pspicture*}
\end{center}
\begin{enumerate}
	\item Donner un encadrement du nombre chromatique.
\item Donner une coloration de ce graphe.
\item En déduire la valeur du nombre chromatique de $\mathcal{G}$.
\end{enumerate}


\bigskip

\exo 

\medskip
 

Le graphe ci-dessous indique les différentes liaisons entre plusieurs lieux. Le long de chaque arête figure la distance en kilomètres séparant les différents lieux.

En précisant la méthode utilisée, déterminer le plus court chemin possible pour aller de A à L.

\begin{center}
\psset{unit=3cm,linecolor=darkgray,linewidth=0.5pt}
\begin{pspicture*}(-0.25,-0.25)(3.25,2.25)
\cnodeput(0,2){A}{A}
\cnodeput(0,1){E}{E}
\cnodeput(0,0){I}{I}
\cnodeput(1,2){B}{B}
\cnodeput(1,1){F}{F}
\cnodeput(1,0){J}{J}
\cnodeput(2,2){C}{C}
\cnodeput(2,1){G}{G}
\cnodeput(2,0){K}{k}
\cnodeput(3,2){D}{D}
\cnodeput(3,1){H}{H}
\cnodeput(3,0){L}{L}
\psset{linecolor=gray}
\ncline{-}{I}{E}\naput{1}
\ncline{-}{I}{J}\nbput{2}
\ncline{-}{J}{E}\ncput*{4}
\ncline{-}{E}{A}\naput{2}
\ncline{-}{F}{J}\naput{2}
\ncline{-}{E}{F}\naput{6}
\ncline{-}{A}{B}\naput{10}
\ncline{-}{A}{F}\ncput*{8}
\ncline{-}{B}{F}\naput{3}
\ncline{-}{B}{C}\naput{2}
\ncline{-}{C}{D}\naput{5}
\ncline{-}{C}{G}\naput{1}
\ncline{-}{B}{G}\ncput*{5}
\ncline{-}{F}{G}\naput{3}
\ncline{-}{F}{J}\naput{2}
\ncline{-}{J}{G}\ncput*{6}
\ncline{-}{G}{K}\naput{8}
\ncline{-}{G}{H}\naput{10}
\ncline{-}{G}{D}\ncput*{3}
\ncline{-}{D}{H}\naput{2}
\ncline{-}{L}{G}\ncput*{9}
\ncline{-}{K}{L}\nbput{3}
\ncline{-}{H}{L}\naput{3}
\end{pspicture*}
\end{center}

\end{document}
