\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} % inclure le fichier graphique de pondichery 2010
\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}{$\left( {{\mathrm{O}};\vec i,\vec j} \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
% Mise en forme des algorithmes
\usepackage[french,boxed,titlenumbered,lined,longend]{algorithm2e}
  \SetKwIF {Si}{SinonSi}{Sinon}{si}{alors}{sinon\_si}{alors}{fin~si}
 \SetKwFor{Tq}{tant\_que~}{~faire~}{fin~tant\_que}
 \SetKwFor{PourCh}{pour\_chaque }{ faire }{fin pour\_chaque}
 \SetKwInput{Sortie}{Sortie}
\newcommand{\Algocmd}[1]{\textsf{\textsc{\textbf{#1}}}}\SetKwSty{Algocmd}
  \newcommand{\AlgCommentaire}[1]{\textsl{\small  #1}}  
%

\newcommand{\fvalid}{\raisebox{1ex}{\rotatebox{180}{$\Rsh$}}} % flèche entrée pour prg casio


\newcommand{\QCM}[3]{ $\bullet$ \quad #1 \hfill 
$\bullet$ \quad #2 \hfill 
$\bullet$ \quad #3 }

\newcommand{\QCMc}[4]{   #1 \\ 
\makebox[3cm][l]{\psframe(.25,.25) \qquad #2 }\hfill 
\makebox[3cm][l]{\psframe(.25,.25) \qquad #3 }\hfill 
\makebox[3cm][l]{\psframe(.25,.25) \qquad #4 }} % QCM avec cases à cocher%

% en-tête
\lhead{\footnotesize{\textsf{Lycée JANSON DE SAILLY\\ 21 décembre 2017}}} %gauche
\chead{\textsf{\textcolor{red}{\textbf{\textsc{théorie des graphes}}}}} %centre
\rhead{\footnotesize{\textsf{T\textsuperscript{le} ES 4}}}%droit
%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}}
\setcounter{secnumdepth}{3}
\makeatletter
\renewcommand\section{\@startsection {section}{1}{\z@}%
                                   {-3.5ex \@plus -1ex \@minus -.2ex}%
                                   {2.3ex \@plus.2ex}%
                                  {\reset@font\bfseries\red\sffamily\scshape}} 
                                 
\renewcommand\subsection{\@startsection {subsection}{2}{\z@}%
                                   {-3.5ex \@plus -1ex \@minus -.2ex}%
                                   {2.3ex \@plus.2ex}%
                                   {\reset@font\bfseries\sffamily\scshape\blue}}                                   
\renewcommand\subsubsection{\@startsection {subsubsection}{3}{\z@}%
	{-3.5ex \@plus -1ex \@minus -.2ex}%
	{2.3ex \@plus .2ex}%
	{\reset@font\bfseries\sffamily\scshape\small}}
\makeatother
\setcounter{secnumdepth}{2}

\renewcommand\thesection{\Roman {section}}
\renewcommand\thesubsection{\arabic {subsection}}
%%%% debut macro %%%%
\makeatletter
\renewcommand\theequation{\thesection.\arabic{equation}}
\@addtoreset{equation}{section}
\makeatother
%%%% fin macro %%%%

\newcounter{nexo}           % déclaration du numéro d'exo
\setcounter{nexo}{0}        % initialisation du numero

\newcommand{\exo}{
  \refstepcounter{nexo} 
  \par{\textsf{\textbf{\textcolor{blue}{{\small{EXERCICE \; \arabic{nexo}}}}}}}}
  
  \newcounter{nactivite}           % déclaration du numéro d'exo
\setcounter{nactivite}{0}        % initialisation du numero

\newcommand{\act}{
  \stepcounter{nactivite} 
  \par{\textsf{\textbf{\textcolor{blue}{{\small{\textsc{activité} \; \arabic{nactivite}}}}}}}}

%%%% debut macro %%%%
\makeatletter
\@addtoreset{nactivite}{section}
\makeatother
%%%% fin macro %%%%

\newrgbcolor{Rfond}{.995 0.945 .985}  
\newrgbcolor{Rougef}{.8 0.1 .2}
\newrgbcolor{Rbord}{.6 0.1 .4}

\newcommand{\cadreR}[1]{%
\psframebox[framesep=.8em,linecolor=black,linewidth=0.25pt,framearc=0.2,fillstyle=solid,fillcolor=Rfond]{\begin{minipage}{\linewidth-1.6em}%
#1\end{minipage}}}
\newcommand{\cadreB}[1]{%
\psframebox[framesep=.8em,linecolor=black,linewidth=0.25pt,framearc=0.2]{\begin{minipage}{\linewidth-1.6em}%
#1\end{minipage}}}

\newcommand{\dem}{
 \medskip
  \par{\textsf{\textsc{{\small{\ding{106}\: démonstration}}}}}%
   \medskip}
  

   \newcommand{\preuve}{
 \medskip
  \par{\textsf{\textsc{{\small{\ding{106}\: preuve}}}}}%
   \medskip} 
    

\newcommand{\encadrer}[1]{
{\setlength{\fboxsep}{2mm}
\fbox{#1}}}

\hypersetup{
pdftitle={Graphes.}, 
pdfauthor={Arié Yallouz},   
pdfsubject={Graphes : Premières notions.}, 
pdfkeywords={Graphes, définitions, chaîne, cycle,connexité,chaîne eulérienne, algorithme de Dijkstra, cours, exercices.},
pdfcontacturl={http//yallouz.arie.free.fr/},
pdflang={fr},
baseurl={http://yallouz.arie.free.fr/terminale_cours/index_terminale_cours.php}
}

\begin{document}


\section{graphes premières définitions}


De manière générale, un graphe est un ensemble de sommets et d'arêtes (ou arcs) reliant ces sommets.

Il existe différents types de graphes, orientés ou non, ou autorisant plusieurs arcs entre deux sommets.

{\psset{unit=.7cm}
\begin{pspicture}(0,0)(4,3.5)
\newrgbcolor{bleu}{0.1 0.05 .5}
\rput(2,-.5){\small{\textsf{Graphe } $G_1$}}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\dotnode(2,0){A}  \dotnode(3.5,.5){B}
\dotnode(4,3){C} \dotnode(0,3){D}
\nccircle[nodesep=2pt]{B}{.4cm}
\nccurve[angleA=-40,angleB=-90] {C}{D}  
\nccurve[angleA=40,angleB=150] {A}{C}
\ncarc[arcangle=40]{A}{D}
\ncarc[arcangle=40]{D}{A}
\end{pspicture}}\hfill
{\psset{unit=.7cm}
\begin{pspicture}(0,0)(4,3.5)
\newrgbcolor{bleu}{0.1 0.05 .5}
\rput(2,-.5){\small{\textsf{Graphe } $G_2$}}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\dotnode(1,0){A}  \dotnode(2.5,2){B}
\dotnode(4,3){C} \dotnode(0,3){D}
\ncline{-}{A}{B}
\ncline{-}{A}{D}  
\ncarc[arcangle=-40]{A}{C}
\ncline{-}{B}{C}   
\ncline{-}{B}{D}  
 \ncline{-}{C}{D}
\end{pspicture}}\hfill
{\psset{unit=.7cm}
\begin{pspicture}(0,0)(4,3.5)
\newrgbcolor{bleu}{0.1 0.05 .5}
\rput(2,-.5){\small{\textsf{Graphe } $G_3$}}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu,arrowscale= 1.8 1.2,ArrowInside=->}
\dotnode(4,0){A}  \dotnode(1.8,2){B}
\dotnode(3.5,3){C} \dotnode(0,3){D} \dotnode(0.5,.5){E}
\ncarc[arcangle=-15]{A}{C}
\ncarc[arcangle=-15]{C}{A}
\ncline{C}{B}   
\ncline{B}{D} 
\ncline{B}{A}   
\ncline{C}{D}
\ncline{E}{B}   
\ncline{D}{E}   
\end{pspicture}} \hfill
{\psset{unit=.7cm}
\begin{pspicture}(0,0)(4,3.5)
\newrgbcolor{bleu}{0.1 0.05 .5}
\rput(2,-.5){\small{\textsf{Graphe } $G_4$}}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\dotnode(0,1.5){A}  \dotnode(2,2.5){B} \dotnode(2,0.5){C}
\dotnode(4,0){D} \dotnode(4,1){E}\dotnode(4,2){F} \dotnode(4,3){G}
\ncline{A}{B}
\ncline{A}{C}  
\ncline{B}{G}
\ncline{B}{F} 
\ncline{C}{E}
\ncline{C}{D} 
\end{pspicture}}

\subsection{définitions}

\cadreB{
Un graphe non orienté $G = (S,A)$ est déterminé par la donnée de deux ensembles :
\begin{itemize}
	\item un ensemble fini  non vide $S$ dont les éléments sont appelés \emph{sommets}
\item un ensemble $A$ de paires de sommets appelées \emph{arêtes}.
\end{itemize}
}

\medskip

Si  $S = \left\{x_1,  x_2, \cdots ,x_n \right\}$ est l'ensemble des sommets d'un graphe $G$, une arête  $a$ de l'ensemble $A$ s'écrit $a = \{x_i, x_j\}$ où $x_i$ et $x_j$ sont les \emph{extrémités} de $a$. 

Les sommets  $x_i$ et $x_j$ sont alors  \emph{adjacents} dans le graphe $G$ et on dit qu'ils sont \emph{incidents}  avec  l'arête $a$.

Lorsque les deux extrémités sont confondues $\left(x_i=x_j\right)$ l'arête s'appelle une \emph{boucle}.

Deux arêtes sont dites parallèles lorsqu'elles ont mêmes extrémités.

\subsubsection{ordre d'un graphe}

\cadreR{On appelle ordre d'un graphe le nombre $(n)$ de sommets  de ce graphe. }

\medskip

Par exemple :

les graphes $G_1$ et $G_2$ sont d'ordre 4 ; le graphe $G_3$ est d'ordre 5 et le graphe $G_4$ est d'ordre 7.

\subsubsection{graphe simple}

\cadreB{
Un graphe est dit \emph{simple} si deux sommets distincts sont joints par au plus une arête et s'il est sans boucle.
}


\subsubsection{graphe orienté}

\cadreB{Un graphe peut être orienté, une arête est alors appelée un \emph{arc}. Un arc est défini par un couple ordonné $\left(x_i, x_j\right)$ de sommets.}

\medskip

\textsf {\textsc{\small{remarque}}}

\`A tout graphe orienté, on peut associer un graphe simple. 

Par exemple sur un plan de ville où sont indiquées les rues en sens uniques, un piéton ne tiendra pas compte de l'orientation pour se déplacer.

\medskip

\begin{tabularx}{\linewidth}{l m{4cm} l >{\raggedright \arraybackslash}X}	
Au  graphe orienté & \psset{unit=.8cm}
\begin{pspicture}(4,3)
\newrgbcolor{bleu}{0.1 0.05 .5}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu,arrowscale= 1.8 1.2,ArrowInside=->}
\dotnode(3.5,0){A}  \dotnode(1.5,.5){B} \dotnode(4,2){C} \dotnode(2,3){D} \dotnode(0,2){E}
\ncarc[arcangle=-15]{A}{C}
\ncarc[arcangle=-15]{C}{A}
\ncline{C}{B}   
\ncarc[arcangle=-15]{B}{D}
\ncarc[arcangle=-15]{D}{B}
\ncline{B}{A}
\ncline{E}{B}   
\ncline{D}{E}   
\end{pspicture}&
on associe le graphe simple &
\psset{unit=.8cm}
\begin{pspicture}(4,3)
\newrgbcolor{bleu}{0.1 0.05 .5}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\dotnode(3.5,0){A}  \dotnode(1.5,.5){B} \dotnode(4,2){C} \dotnode(2,3){D} \dotnode(0,2){E}
\ncline{A}{C}
\ncline{C}{B}  
\ncline{D}{B}
\ncline{B}{A}
\ncline{E}{B}   
\ncline{D}{E}   
\end{pspicture}
\end{tabularx}

\subsubsection {sous graphe}

Il arrive que dans certains problèmes on ait besoin de considérer une partie d'un graphe : 

\medskip

\cadreB{
$G' = (S',A')$ est un sous-graphe de $G = (S,A)$ si $S'$ est un sous ensemble de $S$ et $A'$ un sous ensemble de $A$ tel que les extrémités des arêtes de $A'$ sont des sommets de $S'$.

Si $A'$ est constitué de toutes les arêtes de $A$ ayant pour extrémités les sommets de $S'$ alors on dit que $G' = (S',A')$ est le sous-graphe engendré par $S'$.
}

\medskip

\textsf {\textsc{\small{exemple}}}

\medskip

\begin{tabularx}{\linewidth}{*{3}{>{\centering \arraybackslash}X}}
\psset{unit=.8cm}
\begin{pspicture}(6,4)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\dotnode(1,2.5){S1}  \dotnode(4,3){S2}  \dotnode(3,0){S3} \dotnode(0,1){S4} \dotnode(2,1.5){S5}  \dotnode(6,2){S6} \dotnode(6,1){S7}
\uput[ul](1,2.5){\prune{\footnotesize{$s_1$}}} \uput[dr](4,3){\prune{\footnotesize{$s_2$}}} \uput[d](3,0){\prune{\footnotesize{$s_3$}}} \uput[dl](0,1){\prune{\footnotesize{$s_4$}}}   \uput[ul](2,1.5){\prune{\footnotesize{$s_5$}}}  \uput[u](6,2){\prune{\footnotesize{$s_6$}}} \uput[d](6,1){\prune{\footnotesize{$s_7$}}}   
\ncline{S1}{S2}  \ncline{S2}{S3}  \ncline{S3}{S4}  \ncline{S4}{S1}  \nccircle[nodesep=2pt]{S2}{.3cm} \ncline{S3}{S5} \ncline{S3}{S6} \ncline{S3}{S7}\ncline{S6}{S7} \ncarc[arcangle=-15]{S6}{S5} \ncarc[arcangle=-15]{S5}{S6} 
\end{pspicture}
& 
\psset{unit=.8cm}
\begin{pspicture}(6,2)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\dotnode(3,0){S3} \dotnode(0,1){S4} \dotnode(2,1.5){S5}  \dotnode(6,2){S6} \dotnode(6,1){S7}
\uput[d](3,0){\prune{\footnotesize{$s_3$}}} \uput[dl](0,1){\prune{\footnotesize{$s_4$}}}   \uput[ul](2,1.5){\prune{\footnotesize{$s_5$}}}  \uput[u](6,2){\prune{\footnotesize{$s_6$}}} \uput[d](6,1){\prune{\footnotesize{$s_7$}}}   
 \ncline{S4}{S3}  \ncline{S3}{S5} \ncline{S5}{S6} \ncline{S6}{S7} \ncline{S7}{S3}
\end{pspicture}
&
\psset{unit=.8cm}
\begin{pspicture}(6,2.5)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\dotnode(3,0){S3} \dotnode(0,1){S4} \dotnode(2,1.5){S5}  \dotnode(6,2){S6} \dotnode(6,1){S7}
\uput[d](3,0){\prune{\footnotesize{$s_3$}}} \uput[dl](0,1){\prune{\footnotesize{$s_4$}}}   \uput[ul](2,1.5){\prune{\footnotesize{$s_5$}}}  \uput[u](6,2){\prune{\footnotesize{$s_6$}}} \uput[d](6,1){\prune{\footnotesize{$s_7$}}}   
 \ncline{S3}{S4}  \nccircle[nodesep=2pt]{S2}{.3cm} \ncline{S3}{S5} \ncline{S3}{S6} \ncline{S3}{S7}\ncline{S6}{S7} \ncarc[arcangle=-15]{S6}{S5} \ncarc[arcangle=-15]{S5}{S6} 
\end{pspicture}\\ 
\small{\textsf{Graphe } $G$}& \small{$G_1$ \textsf{ est un sous graphe de} $G$} & \small{$G_2$ \textsf{ est le sous graphe de } $G$ \textsf{ engendré par } $\{S_3 , S_4 ,S_5 ,S_6 ,S_7 \}$}\\
 \end{tabularx}
 
 \subsubsection {graphe complet}
 
\cadreR{
Un graphe complet $K_n$ est un graphe simple d'ordre $n\geqslant 1$ dont tous les sommets sont deux à deux adjacents.
}

\medskip

\psset{unit=1cm}
\begin{pspicture}(0,-1)(3.5,3)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\rput{0}(1.6,.57){\multido{\n=90+120,\i=1+1}{3}{\dotnode(1.54;\n){S\i}}
\rput(0,-1.2){$K_3$}}
\ncline{S1}{S2}  \ncline{S1}{S3}   \ncline{S2}{S3} 
\end{pspicture}
\hfill
\psset{unit=1cm}
\begin{pspicture}(0,-1)(6.5,3)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\rput{0}(1.5,1){\multido{\n=45+90,\i=1+1}{4}{\dotnode(1.732;\n){S\i}}}
\rput{0}(5,.57){\multido{\n=90+120,\i=6+1}{3}{\dotnode(1.54;\n){S\i}}
\dotnode(0,0){S5}
\rput(-2,-1.2){Deux représentations du $K_4$}}
\ncline{S1}{S2}  \ncline{S1}{S3}  \ncline{S1}{S4}  \ncline{S2}{S3}  \ncline{S2}{S4}  \ncline{S3}{S4}  \ncline{S5}{S6}  \ncline{S5}{S7}  \ncline{S5}{S8}  \ncline{S6}{S7}  \ncline{S6}{S8}  \ncline{S7}{S8} 
\end{pspicture}
\hfill
\psset{unit=1cm}
\begin{pspicture}(0,-1)(3.5,3)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\rput{0}(1.6,1){\multido{\n=18+72,\i=1+1}{5}{\dotnode(1.5;\n){S\i}}
\rput(0,-1.6){$K_5$}}
\ncline{S1}{S2}  \ncline{S1}{S3}  \ncline{S1}{S4}  \ncline{S1}{S5} \ncline{S2}{S3}  \ncline{S2}{S4}  \ncline{S2}{S5}  \ncline{S3}{S4}  \ncline{S3}{S5} \ncline{S4}{S5}
\end{pspicture}

\subsection{degré d'un sommet}

\cadreR{
On appelle degré d'un sommet le nombre d'arêtes dont ce sommet est une extrémité (les boucles étant comptées deux fois).  Ce degré vaut 0 si le sommet est isolé.}

\medskip

\textsf {\textsc{\small{exemple}}}


\parbox{11cm}{ 
Dans le graphe ci-contre, les degrés des sommets sont :

\medskip

\begin{tabularx}{\linewidth}{|l|*{7}{>{\centering \arraybackslash}X|}}	\hline
Sommets & $s_1$ & $s_2$ & $s_3$ & $s_4$ & $s_5$ & $s_6$ & $s_7$ \\ \hline
Degrés & 2 & 4 & 2 & 3 & 2 & 1 & 0 \\ \hline
 \end{tabularx}
}\hfill  \parbox{5cm}{\begin{flushright}
 \psset{unit=.8cm}
\begin{pspicture}(6,4)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\dotnode(1,2.5){S1}  \dotnode(4,3){S2}  \dotnode(3,0){S3} \dotnode(0,1){S4} \dotnode(2,1.5){S5}  \dotnode(6,2){S6} \dotnode(5,1){S7}
\uput[ul](1,2.5){\prune{\footnotesize{$s_1$}}} \uput[dr](4,3){\prune{\footnotesize{$s_2$}}} \uput[d](3,0){\prune{\footnotesize{$s_3$}}} \uput[dl](0,1){\prune{\footnotesize{$s_4$}}}   \uput[ul](2,1.5){\prune{\footnotesize{$s_5$}}}  \uput[u](6,2){\prune{\footnotesize{$s_6$}}} \uput[d](5,1){\prune{\footnotesize{$s_7$}}}   
\ncline{S1}{S2}\ncline{S2}{S3}  \ncline{S3}{S4}  \ncline{S4}{S1}  \nccircle[nodesep=2pt]{S2}{.3cm} \ncline{S3}{S5}  \ncline{S5}{S6} 
\end{pspicture}
 \end{flushright}
 }


\subsubsection{degré d'un sommet dans un graphe orienté}

\cadreB{
Soit $s$ un sommet d'un graphe orienté $G$.
\begin{itemize}
	\item On note $d^+(s)$ le degré extérieur du sommet $s$, c'est-à-dire le nombre d'arcs ayant $s$ comme extrémité initiale.
	\item On note $d^-(s)$ le degré intérieur du sommet $s$, c'est-à-dire le nombre d'arcs ayant $s$ comme extrémité finale. 
\end{itemize}
Le degré du sommet $s$ est : \[d(s) = d^+(s) + d^-(s)\]
}

\medskip

\textsf {\textsc{\small{exemple}}}

\medskip

\begin{tabularx}{\linewidth}{@{}m{10cm} >{\raggedleft \arraybackslash}X@{}}
Dans le graphe ci-contre, les degrés des sommets sont :

\begin{itemize}
	\item [] $d^+(s_1)=2$ et $d^-(s_1) = 1$ d'où $d\left(s_1\right)=3$
	\item [] $d^+(s_2)=2$ et $d^-(s_2) = 3$ d'où $d\left(s_2\right)=5$
		\item [] $d^+(s_3)=1$ et $d^-(s_3) = 4$ d'où $d\left(s_3\right)=5$
	\item [] $d^+(s_4)=2$ et $d^-(s_4) = 1$ d'où $d\left(s_4\right)=3$
	\item [] $d^+(s_5)=2$ et $d^-(s_5) = 1$ d'où $d\left(s_5\right)=3$
	\item [] $d^+(s_6)=1$ et $d^-(s_6) = 0$ d'où $d\left(s_6\right)=1$
\end{itemize}
 &
\psset{unit=.8cm}
\begin{pspicture}(6,3)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu,arrowscale= 1.8 1.2,ArrowInside=->}
\dotnode(1,2.5){S1}  \dotnode(4,3){S2}  \dotnode(3,0){S3} \dotnode(0,0){S4} \dotnode(5,.5){S5}  \dotnode(6,2.5){S6}
\uput[ul](1,2.5){\prune{\footnotesize{$s_1$}}} \uput[dr](4.05,3){\prune{\footnotesize{$s_2$}}} \uput[d](3,0){\prune{\footnotesize{$s_3$}}} \uput[dl](0,0){\prune{\footnotesize{$s_4$}}}   \uput[dr](5,.5){\prune{\footnotesize{$s_5$}}}  \uput[u](6,2.5){\prune{\footnotesize{$s_6$}}}  
\ncline{S1}{S2} \ncline{S1}{S3} \ncline{S2}{S3}  \ncarc[arcangle=-15]{S3}{S4} \ncarc[arcangle=-15]{S4}{S3} \ncline{S4}{S1}  \nccircle[nodesep=2pt]{->}{S2}{.3cm} \ncline{S5}{S2} \ncline{S5}{S3}  \ncline{S6}{S5} 
\end{pspicture}\\
 \end{tabularx}
 
\medskip

\textsf {\textsc{\small{remarque}}}

\medskip

Dans un graphe orienté, la somme des degrés extérieurs et la somme des degrés intérieurs sont égales au nombre d'arcs.

Si on note $a$ le nombre d'arcs d'un graphe orienté alors $\sum d^+(s)= \sum d^-(s) =a$.

\medskip

Par exemple si dans une réunion on échange des cadeaux, le nombre de cadeaux offerts est égal au nombre de cadeaux reçus, c'est le nombre de cadeaux échangés.

\subsubsection{théorème}

\cadreR{
La somme des degrés de tous les sommets d'un graphe est égale à deux fois le nombre d'arêtes de ce graphe; c'est donc un nombre pair.}

\medskip
 
\dem
 
 \medskip

Lorsqu'on additionne les degrés des sommets, une arête est comptée deux fois, une fois pour chaque extrémité.

\subsubsection{corollaire}

\cadreR{
Dans un graphe, le nombre de sommets impairs est un entier pair.}

\medskip
 
\dem
 
 \medskip

Soit $p$ la somme des degrés des sommets pairs et $m$ la somme des degrés des sommets impairs.

$m+p$ est égal à la somme des degrés des sommets c'est donc un nombre pair donc $m$ est un nombre pair.

Or une somme d'entiers impairs est paire si, et seulement si, il y a un nombre pair de termes. 

On en déduit que le nombre de sommets impairs est un entier pair.
 
\subsubsection{proposition}

\cadreR{
Dans un graphe simple d'ordre $n>1$, il existe deux sommets distincts $s_i$ et $s_j$ ayant le même degré.}

\medskip
 
\dem
 
 \medskip
 
Soit $G$ un graphe simple d'ordre $n>1$. Le degré d'un sommet $s$ quelconque du graphe $G$ est un entier $d(s)$ tel que : $0 \leqslant d(s) \leqslant n-1$.

Supposons que les degrés des sommets soient différents.
 
Les degrés des $n$ sommets sont les entiers $\left \{ 0, 1 , \cdots , n-1 \right\}$ et il existe un sommet $s_i$ de degré $0$ et un sommet $s_j$ de degré $n-1$.

Or si  $d\left(s_j\right) = n-1$ cela signifie qu'il est adjacent à tous les sommets du graphe et en particulier au sommet $s_i$ donc $d\left(s_i\right) \geqslant 1$


Ce qui est en contradiction avec $d\left(s_i\right) = 0$.

\subsection{représentation matricielle d'un graphe}

\cadreR{
Soit $G = (S, A)$ un graphe d'ordre $n$ dont les sommets sont numérotés de 1 à $n$. 

La matrice d'adjacence de $G$ est égale à la matrice carrée $M = \left(m_{i j} \right)$ de dimension $n \times n$ où $m_{i j}$ est égal au nombre d'arêtes d'extrémités les sommets $s_i$ et $s_j$. 

Dans le cas d'un graphe orienté, $m_{i j}$ est égal au nombre d'arcs ayant pour origine le sommet $s_i$ et pour extrémité finale le sommet $s_j$.}

\medskip

\textsf {\textsc{\small{exemples}}}

\medskip
\begin{enumerate}
	\item  \hfill
	
	 \psset{unit=.8cm}
\begin{pspicture}(0,.5)(4,2.5)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu,arrowscale= 1.8 1.2,ArrowInside=->}
\dotnode(.5,2.5){S1}  \dotnode(3,2){S2}  \dotnode(2,0){S3} \dotnode(4,0.5){S4} 
\uput[dl](.5,2.5){\prune{\footnotesize{$s_1$}}} \uput[r](3,2){\prune{\footnotesize{$s_2$}}} \uput[d](2,0){\prune{\footnotesize{$s_3$}}} \uput[d](4,0.5){\prune{\footnotesize{$s_4$}}}   
\nccircle[nodesep=1pt]{->}{S1}{.3cm} 
 \ncarc[arcangle=-15]{S1}{S2} \ncarc[arcangle=-15]{S2}{S1} \ncline{S3}{S1} \ncline{S3}{S2}  \ncline{S4}{S3}
 \uput[dr](0,1.5){\bleu{\small{$G_1$}}}
\end{pspicture}\hfill 
La matrice d'adjacence du graphe orienté $G_1$ est $M\left(G_1\right) = \begin{pmatrix}
1 &1 &0 & 0\\
1 &0 &0 & 0\\
1&1 &0 & 0\\
0 &0 &1 & 0\\
\end{pmatrix}$

\item  \hfill
	
\psset{unit=.8cm}
\begin{pspicture}(0,.5)(4,2.5)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\dotnode(.5,2.5){S1}  \dotnode(3,2){S2}  \dotnode(2,0){S3} \dotnode(4,0.5){S4} 
\uput[u](.5,2.5){\prune{\footnotesize{$s_1$}}} \uput[r](3,2){\prune{\footnotesize{$s_2$}}} \uput[d](2,0){\prune{\footnotesize{$s_3$}}} \uput[d](4,0.5){\prune{\footnotesize{$s_4$}}}   
 \ncline{S1}{S2} \ncline{S3}{S1} \ncline{S3}{S2}  \ncline{S4}{S3}
 \uput[dr](0,1.5){\bleu{\small{$G_2$}}}
\end{pspicture}\hfill 
La matrice d'adjacence du graphe simple $G_2$ est $M\left(G_2\right) = \begin{pmatrix}
0 &1 &1 & 0\\
1 &0 &1 & 0\\
1&1 &0 & 1\\
0 &0 &1 & 0\\
\end{pmatrix}$
\end{enumerate}

\textsf {\textsc{\small{remarques}}}

\medskip

\begin{enumerate}
\item La matrice d'adjacence d'un graphe non orienté est symétrique.
	\item La diagonale de la matrice d'adjacence d'un graphe simple ne comporte que des 0.
	\item La demi somme de tous les coefficients de la matrice d'adjacence d'un graphe non orienté est égale au nombre d'arêtes de ce graphe.
		\item La somme de tous les coefficients de la matrice d'adjacence d'un graphe orienté est égale au nombre d'arcs de ce graphe.
		
\begin{itemize}
	\item La somme des coefficients de la ligne $i$ est égale au nombre de successeurs du sommet $s_i$.
	\item La somme des coefficients de la colonne $i$ est égale au nombre de prédécesseurs du sommet $s_i$.
\end{itemize}		
\end{enumerate}

\subsection{graphes isomorphes}

Deux graphes isomorphes  ont la même structure : peu importe la façon dont ils sont dessinés, il est possible de déplacer les sommets pour que l'un soit la copie conforme de l'autre.

\medskip

\textsf {\textsc{\small{exemple}}}

\medskip

Considérons les trois graphes ci-dessous :


\psset{unit=.8cm}
\begin{pspicture}(5,5)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\rput{0}(2.5,2.5){\multido{\n=0+60,\i=1+1}{6}{\dotnode(2;\n){S\i}}} 
 \ncline{S1}{S2} \ncline{S1}{S4} \ncline{S1}{S6}  \ncline{S2}{S3} \ncline{S2}{S5} \ncline{S3}{S4} \ncline{S3}{S6} \ncline{S4}{S5} \ncline{S5}{S6}
 \uput[dr](0,1.5){\bleu{\small{$A$}}}
\end{pspicture}\hfill
\begin{pspicture}(5,5)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\rput{0}(2.5,2.5){\multido{\n=-45+90,\i=1+1}{4}{\dotnode(2.44;\n){S\i}}
\dotnode(-.5,0){S5} \dotnode(.5,0){S6}
} 
 \ncline{S1}{S2} \ncline{S1}{S4} \ncline{S1}{S6}  \ncline{S2}{S3} \ncline{S2}{S6} \ncline{S3}{S4} \ncline{S3}{S5} \ncline{S4}{S5} \ncline{S5}{S6}
 \uput[dr](0,1.5){\bleu{\small{$B$}}}
\end{pspicture}\hfill
\begin{pspicture}(5,5)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\rput{0}(0.8,2.5){\multido{\n=0+2,\i=1+2}{3}{\dotnode(\n,1.732){S\i}}
\multido{\n=0+2,\i=2+2}{3}{\dotnode(\n,-1.732){S\i}}
}
 \ncline{S1}{S2} \ncline{S1}{S4} \ncline{S1}{S6}  \ncline{S2}{S3} \ncline{S2}{S5} \ncline{S3}{S4} \ncline{S3}{S6} \ncline{S4}{S5} \ncline{S5}{S6}
 \uput[dr](0,1.5){\bleu{\small{$C$}}}
\end{pspicture}

Les trois graphes ont le même ordre $(6)$, le même nombre d'arêtes $(9)$ et les sommets des trois graphes sont tous de degré 3. 

Or dans $B$ il y a deux sous graphes complets d'ordre 3 ce qui n'est pas le cas pour les graphes $A$ et $C$. Donc $B$ n'est pas isomorphe à $A$ et $C$.

Montrons que les graphes $A$ et $C$ sont isomorphes.

\begin{center}
\psset{unit=1cm}
\begin{pspicture}(0,.5)(5,5)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\rput{0}(2.5,2.5){\multido{\n=0+60,\i=1+1}{6}{\dotnode(2;\n){S\i}\rput(2.4;\n){\prune{\footnotesize{$a_\i$}}}}} 
 \ncline{S1}{S2} \ncline{S1}{S4} \ncline{S1}{S6}  \ncline{S2}{S3} \ncline{S2}{S5} \ncline{S3}{S4} \ncline{S3}{S6} \ncline{S4}{S5} \ncline{S5}{S6}
 \uput[dr](0,1.5){\bleu{\small{$A$}}}
\end{pspicture}\hspace{3cm}
\psset{unit=1cm}
\begin{pspicture}(0,.5)(5,5)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=0.75pt, linecolor=bleu}
\rput{0}(0.8,2.5){\multido{\n=0+2,\i=1+2}{3}{\dotnode(\n,1.732){S\i}\uput[u](\n,1.732){\prune{\footnotesize{$c_\i$}}}}
\multido{\n=0+2,\i=2+2}{3}{\dotnode(\n,-1.732){S\i}\uput[d](\n,-1.732){\prune{\footnotesize{$c_\i$}}}}
}
 \ncline{S1}{S2} \ncline{S1}{S4} \ncline{S1}{S6}  \ncline{S2}{S3} \ncline{S2}{S5} \ncline{S3}{S4} \ncline{S3}{S6} \ncline{S4}{S5} \ncline{S5}{S6}
 \uput[dr](0,1.5){\bleu{\small{$C$}}}
\end{pspicture}
\end{center}

Les sommets étant numérotés comme indiqué ci-dessus les deux graphes ont la même matrice d'adjacence :
\[M_A = M_C = \begin{pmatrix}
0 &1 &0 & 1 & 0 & 1\\
1 &0 &1 & 0& 1 & 0\\
0 &1 &0 & 1 & 0 & 1\\
1 &0 &1 & 0& 1 & 0\\
0 &1 &0 & 1 & 0 & 1\\
1 &0 &1 & 0& 1 & 0\\
\end{pmatrix}\]

Donc $A$ et $C$ sont isomorphes.

 \medskip

\textsf {\textsc{\small{remarques}}}

\medskip

\begin{itemize}
	\item Le graphe $B$ est \emph{planaire} : on peut le dessiner sans que ses arêtes se croisent.

	\item Le graphe $C$ (ou $A$) est un graphe \emph{biparti} : il existe une partition de son ensemble $S$ de sommets en deux sous-ensembles $X$ et $Y$ telle que chaque arête du graphe a une extrémité dans $X$ et l'autre dans $Y$. 
	
	Ce n'est pas un graphe planaire, il est impossible de le dessiner sans que ses arêtes se croisent.
\end{itemize}

\pagebreak

\act

\medskip

Voici le plan de trois étages d'un musée. \`A chaque étage, un visiteur se rend compte qu'il peut choisir un itinéraire passant une seule fois par chaque pièce.

Pour chacun des étages :

 Est-il possible de faire le tour de l'étage en passant exactement une seule fois par chacune des portes ?
	
Dans ce cas, où faut-il placer les portes d'entrée et de sortie de l'étage pour que ce parcours reste possible ?
	

\begin{center}
\psset{unit=1cm}
\begin{pspicture}(9,5)
\newrgbcolor{bleu}{0.1 0.05 .5}
\def \porte{\psframe[fillstyle=solid,fillcolor=white,linecolor=white](-.2,-.1)(.2,.1)
\psline[linewidth=1.25pt,linecolor=bleu](-.2,-.1)(-.2,.1)
\psline[linewidth=1.25pt,linecolor=bleu](.2,-.1)(.2,.1)
}
\rput(4.5,4.5){\footnotesize{\textsf{1\textsuperscript{er} étage}}}
\psset{linewidth=.75pt,linecolor=bleu} 
\psframe(0,0)(9,4.2)
\psline(3,0)(3,4.2)
\psline(6,0)(6,4.2)
\psline(0,2.1)(3,2.1)
\rput(1,2.1){\porte}
\rput(2,2.1){\porte}
\rput{90}(3,.7){\porte}
\rput{90}(3,3.5){\porte}
\psline(3,1.4)(6,1.4)
\psline(3,2.8)(6,2.8)
\rput(4,1.4){\porte}
\rput(5,1.4){\porte}
\rput(4.5,2.8){\porte}
\rput{90}(6,.7){\porte}
\rput{90}(6,3.5){\porte}
\psline(6,2.1)(9,2.1)
\rput(7,2.1){\porte}
\rput(8,2.1){\porte}
\end{pspicture}

\psset{unit=1cm}
\begin{pspicture}(9,5)
\newrgbcolor{bleu}{0.1 0.05 .5}
\def \porte{\psframe[fillstyle=solid,fillcolor=white,linecolor=white](-.2,-.1)(.2,.1)
\psline[linewidth=1.25pt,linecolor=bleu](-.2,-.1)(-.2,.1)
\psline[linewidth=1.25pt,linecolor=bleu](.2,-.1)(.2,.1)
}
\rput(4.5,4.5){\footnotesize{\textsf{2\textsuperscript{e} étage}}}
\psset{linewidth=.75pt,linecolor=bleu} 
\psframe(0,0)(9,4.2)
\psline(3,0)(3,4.2)
\psline(6,0)(6,4.2)
\psline(0,1.4)(3,1.4)
\rput(1,1.4){\porte}
\rput(2,1.4){\porte}
\rput{90}(3,.7){\porte}
\psline(0,2.8)(3,2.8)
\rput(1,2.8){\porte}
\rput(2,2.8){\porte}
\rput{90}(3,3.5){\porte}
\psline(3,2.1)(6,2.1)
\rput(4,2.1){\porte}
\rput(5,2.1){\porte}
\rput{90}(6,.7){\porte}
\rput{90}(6,3.5){\porte}
\psline(6,2.1)(9,2.1)
\rput(7.5,2.1){\porte}
\end{pspicture}

\psset{unit=1cm}
\begin{pspicture}(9,5)
\newrgbcolor{bleu}{0.1 0.05 .5}
\def \porte{\psframe[fillstyle=solid,fillcolor=white,linecolor=white](-.2,-.1)(.2,.1)
\psline[linewidth=1.25pt,linecolor=bleu](-.2,-.1)(-.2,.1)
\psline[linewidth=1.25pt,linecolor=bleu](.2,-.1)(.2,.1)
}
\rput(4.5,4.5){\footnotesize{\textsf{3\textsuperscript{e} étage}}}
\psset{linewidth=.75pt,linecolor=bleu} 
\psframe(0,0)(9,4.2)
\psline(3,0)(3,4.2)
\psline(6,0)(6,4.2)
\psline(0,1.4)(3,1.4)
\rput(1,1.4){\porte}
\rput(2,1.4){\porte}
\rput{90}(3,2.1){\porte}
\rput{90}(3,3.5){\porte}
\psline(3,2.8)(6,2.8)
\rput(4,2.8){\porte}
\rput(5,2.8){\porte}
\rput{90}(6,.7){\porte}
\rput{90}(6,3.5){\porte}
\psline(6,1.4)(9,1.4)
\rput(7.5,1.4){\porte}
\psline(6,2.8)(9,2.8)
\rput(7.5,2.8){\porte}
\end{pspicture}
\end{center}

\act

\medskip

Voici un plan de la ville de K\"onigsberg :

\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 ?

\pagebreak

\section{chaînes, cycles ; connexité}

Les graphes sont souvent utilisés pour modéliser des problèmes associés à des parcours ou à des successions d'actions. Pour cela, on introduit la notion de chaîne.

\subsection{définitions}


\cadreR{Soit $G = (S,A)$ un graphe non orienté. Une chaîne est une liste finie et alternée de sommets et d'arêtes, débutant et finissant par des sommets, telle que chaque arête est incidente avec les sommets qui l'encadrent dans la liste.

Le premier et le dernier élément de la liste sont les extrémités initiale et finale de la chaîne.}

\medskip

Si le graphe est simple, on peut définir une chaîne par la liste de ses sommets ou de ses arêtes.

\begin{enumerate}
	\item La \emph{longueur d'une chaîne} est égale au nombre d'arêtes qui la composent.
	\item Une chaîne dont toutes les arêtes sont distinctes  est une \emph{chaîne simple}. 
	\item Une chaîne dont tous les sommets (sauf  peut-être  les extrémités) sont distincts  est une \emph{chaîne élémentaire}. 
	\item Une \emph{chaîne est fermée} si l'origine et l'extrémité finale de la chaîne sont confondues.
	\item Une chaîne fermée est un \emph{cycle} si elle est composées d'arêtes toutes distinctes.
\end{enumerate}

 \medskip

\textsf {\textsc{\small{remarque}}}

\medskip

Les définitions précédentes, peuvent être transposées au cas des graphes orientés. 

On parlera de \emph{chaîne orientée} ou \emph{chemin} et de \emph{cycle orienté} ou \emph{circuit}.

\medskip

\textsf {\textsc{\small{exemple}}}

\begin{tabularx}{\linewidth}{@{}m{13cm} >{\raggedleft \arraybackslash}X@{}}

Dans le graphe ci-contre :
\begin{itemize}
	\item La chaîne $\left\{ s_0\, ; \,s_1\, ; \,s_0\, ; \,s_2\, ; \,s_0\, ; \,s_3\, ; \,s_0\, ; \,s_4\, ; \,s_0\, ; \,s_5\, ; \,s_0\right\}$ est une chaîne fermée de longueur 10.
	\item La chaîne $\left\{s_1\, ; \, s_2\, ; \,s_3\, ; \,s_0\, ; \,s_4\, ; \,s_5\right\}$ est une chaîne élémentaire de longueur 5.
		\item La chaîne $\left\{s_1\, ; \,s_2\, ; \,s_0\, ; \,s_3\, ; \,s_4\, ; \,s_0\, ; \,s_5\, ; \,s_1\right\}$  est un cycle de longueur 7.
\end{itemize}
&
\psset{unit=1cm}
\begin{pspicture}(3,3)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.2,linewidth=0.75pt, linecolor=bleu}
\rput{0}(1.5,1.5){\multido{\n=18+72,\i=1+1}{5}{\dotnode(1.5;\n){S\i} \rput(1.8;\n){\footnotesize{\prune{$s_\i$}}}}}
\dotnode(1.5,1.5){S0} \uput[d](1.5,1.5){\footnotesize{\prune{$s_0$}}}
\ncline{S1}{S2}  \ncline{S2}{S3}  \ncline{S3}{S4}  \ncline{S4}{S5} \ncline{S5}{S1}  
\multido{\n=1+1}{5}{\ncline{S0}{S\n}}
\end{pspicture} 
 \end{tabularx}
 
\subsection{chaînes de longueur donnée}

\subsubsection{nombre de chaînes}

\cadreR{Soit $G$ un graphe et $M$ sa matrice d'adjacence. 

Le nombre de chaînes de longueur $n$ joignant le sommet $i$ au sommet $j$ est donné par le terme d'indice $i,j$ de la matrice $M^n$.}

\subsubsection{distance}

\cadreB{
Soit $G$ un graphe ; si $x$ et $y$ sont deux sommets de $G$, la distance de $x$ à $y$ notée $d(x,y)$, est la longueur d'une plus courte chaîne de $G$  reliant $x$ à $y$.
}

\medskip

\textsf {\textsc{\small{remarques}}}
\begin{itemize}
	\item La distance d'un sommet à lui même est nulle.
	\item S'il n'existe pas de chaînes joignant deux sommets $x$ et $y$, la distance de $x$ à $y$ est infinie.
\end{itemize}

\subsubsection{diamètre}

\cadreB{
On appelle diamètre d'un graphe la plus grande des distances entre deux sommets du graphe.
}

\medskip

\textsf {\textsc{\small{exemple}}}

\medskip

\begin{tabularx}{\linewidth}{@{}m{13cm} >{\raggedleft \arraybackslash}X@{}}
Soit $M = \begin{pmatrix}
0	&1	&0	&0	&0	&0 \\
1	&0	&1	&0	&0	&0 \\
0	&1	&0	&1	&1	&0 \\
0	&0	&1	&0	&1	&1 \\
0	&0	&1	&1	&0	&1 \\
0	&0	&0	&1	&1	&0 \\
\end{pmatrix}$ la matrice d'adjacence du graphe $G$ ci-contre &
\psset{unit=1cm}
\begin{pspicture}(3,3)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.2,linewidth=0.75pt, linecolor=bleu}
\rput{0}(1.5,1.5){\multido{\n=90+72,\i=2+1}{5}{\dotnode(1.5;\n){S\i} \rput(1.8;\n){\footnotesize{\prune{$s_\i$}}}}}
\dotnode(1.5,2){S1} \uput[d](1.5,2){\footnotesize{\prune{$s_1$}}}
\ncline{S1}{S2}  \ncline{S2}{S3}  \ncline{S3}{S4} \ncline{S3}{S5} \ncline{S4}{S5} \ncline{S4}{S6} \ncline{S5}{S6}  
\end{pspicture} \\
 \end{tabularx}

\medskip

Déterminons la matrice des distances $D$ du graphe, dont le coefficient $d_{i,j}$ est égal à la distance entre les sommets $i$ et $j$.

La distance d'un sommet à lui même est nulle et, on utilise le symbole $\infty$ pour indiquer que la distance entre deux sommets n'est pas encore fixée. \[D = \begin{pmatrix}
0	&\infty	&\infty	&\infty	&\infty	&\infty \\
\infty	&0	&\infty	&\infty	&\infty	&\infty \\
\infty	&\infty	&0	&\infty	&\infty	&\infty \\
\infty	&\infty	&\infty	&0	&\infty	&\infty \\
\infty	&\infty	&\infty	&\infty	&0	&\infty \\
\infty	&\infty	&\infty	&\infty	&\infty	&0 \\
\end{pmatrix}
\]


La matrice $M = \begin{pmatrix}
0	&1	&0	&0	&0	&0 \\
1	&0	&1	&0	&0	&0 \\
0	&1	&0	&1	&1	&0 \\
0	&0	&1	&0	&1	&1 \\
0	&0	&1	&1	&0	&1 \\
0	&0	&0	&1	&1	&0 \\
\end{pmatrix}$ donne les distances égales à 1 :\hfill  $D = \begin{pmatrix}
0	&\red{1}	&\infty	&\infty	&\infty	&\infty \\
\red{1}	&0	&\red{1}	&\infty	&\infty	&\infty \\
\infty	&\red{1}	&0	&\red{1}	&\red{1}	&\infty \\
\infty	&\infty	&\red{1}	&0	&\red{1}	&\red{1} \\
\infty	&\infty	&\red{1}	&\red{1}	&0	&\red{1} \\
\infty	&\infty	&\infty	&\red{1}	&\red{1}	&0 \\
\end{pmatrix}
$


La matrice $M^2 = \begin{pmatrix}
1	&0	&1	&0	&0	&0 \\
0	&2	&0	&1	&1	&0 \\
1	&0	&3	&1	&1	&2 \\
0	&1	&1	&3	&2	&1 \\
0	&1	&1	&2	&3	&1 \\
0	&0	&2	&1	&1	&2 \\
\end{pmatrix}$ donne les distances égales à 2 : \hfill  $D = \begin{pmatrix}
0	&1	&\red{2}	&\infty	&\infty	&\infty \\
1	&0	&1	&\red{2}	&\red{2}	&\infty \\
\red{2}	&1	&0	&1	&1	&\red{2} \\
\infty	&\red{2}	&1	&0	&1	&1 \\
\infty	&\red{2}	&1	&1	&0	&1 \\
\infty	&\infty	&\red{2}	&1	&1	&0 \\
\end{pmatrix}
$


La matrice $M^3 = \begin{pmatrix}
0	&2	&0	&1	&1	&0 \\
2	&0	&4	&1	&1	&2 \\
0	&4	&2	&6	&6	&2 \\
1	&1	&6	&4	&5	&5 \\
1	&1	&6	&5	&4	&5 \\
0	&2	&2	&5	&5	&2 \\
\end{pmatrix}$  donne les distances égales à 3 : \hfill  $D = \begin{pmatrix}
0	&1	&2	&\red{3}&\red{3}	&\infty \\
1	&0	&1	&2	&2	&\red{3}\\
2	&1	&0	&1	&1	&2 \\
\red{3}	&2	&1	&0	&1	&1 \\
\red{3}	&2	&1	&1	&0	&1 \\
\infty	&\red{3}	&2	&1	&1	&0 \\
\end{pmatrix}
$


La matrice $M^4 =  \begin{pmatrix*}[r]
2	&0	&4	&1	&1	&2 \\
0	&6	&2	&7	&7	&2 \\
4	&2	&16	&10	&10	&12 \\
1	&7	&10	&16	&15	&9 \\
1	&7	&10	&15	&16	&9 \\
2	&2	&12	&9	&9	&10 \\
\end{pmatrix*}$ donne les distances égales à 4 : \hfill  $D = \begin{pmatrix}
0	&1	&2	&3 &3	&\red{4} \\
1	&0	&1	&2	&2	&3\\
2	&1	&0	&1	&1	&2 \\
3	&2	&1	&0	&1	&1 \\
3	&2	&1	&1	&0	&1 \\
\red{4}	&3	&2	&1	&1	&0 \\
\end{pmatrix}
$

\medskip

La plus grande des distances entre deux sommets du graphe est 4 donc le diamètre du graphe est 4.


 \subsection{connexité}
 
 \cadreR{Un graphe $G$ est connexe s'il existe au moins une chaîne entre deux sommets quelconques $G$.}
 
 \medskip
 
 Autrement dit :  Un graphe est connexe si on peut atteindre n'importe quel sommet à partir d'un sommet quelconque en parcourant différentes arêtes
 
 \subsubsection{algorithme}
 
 L'algorithme suivant permet de déterminer tous les sommets qui peuvent être atteints à partir d'un sommet.
  

\begin{center}
\psframebox[linecolor=black,linewidth=0.25pt,framesep=1em]{
\begin{minipage}{.8\linewidth}

Marquer provisoirement (\emph{au crayon}) le sommet $x$ ; 

\textsf{\textbf{Tant que}} des sommets sont provisoirement marqués

\begin{itemize}
\item[] choisir un sommet $y$  provisoirement marqué ;
\item[] marquer provisoirement les sommets adjacents non marqués ;
\item[] marquer définitivement (\emph{à l'encre}) $y$ ;  
\end{itemize}

\textsf{\textbf{Fin Tant que}}
\end{minipage}
}
\end{center}
Si tous les sommets sont définitivement marqués alors le graphe est connexe, sinon on a obtenu \emph{la classe de connexité} du sommet $x$.

\medskip

La figure suivante illustre cet algorithme sur un graphe

\begin{center}
 \psset{unit=.5cm}
\begin{pspicture}(6,6)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=Bo,dotscale=1.25,linewidth=0.75pt, linecolor=bleu}
\rput{0}(3.5,3){\multido{\n=90+40,\i=1+1}{9}{\dotnode(3;\n){S\i} \rput(3.5;\n){\scriptsize{\bleu{$s_\i$}}}}}
\ncline{S1}{S3} \ncline{S1}{S5}   \ncline{S2}{S4} \ncline{S2}{S7} \ncline{S3}{S5} \ncline{S3}{S9} \ncline{S4}{S6} \ncline{S4}{S7} \ncline{S5}{S8} \ncline{S6}{S7}\ncline{S8}{S9}
\psdots[dotstyle=*,dotscale=1.5,linecolor=prune](S1)
\psdots[dotstyle=*,dotscale=1, linecolor=gray](S3)(S5)
\end{pspicture}\hfill 
\begin{pspicture}(6,6)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=Bo,dotscale=1.25,linewidth=0.75pt, linecolor=bleu}
\rput{0}(3.5,3){\multido{\n=90+40,\i=1+1}{9}{\dotnode(3;\n){S\i} \rput(3.5;\n){\scriptsize{\bleu{$s_\i$}}}}}
\ncline{S1}{S3} \ncline{S1}{S5}   \ncline{S2}{S4} \ncline{S2}{S7} \ncline{S3}{S5} \ncline{S3}{S9} \ncline{S4}{S6} \ncline{S4}{S7} \ncline{S5}{S8} \ncline{S6}{S7}\ncline{S8}{S9}
\psdots[dotstyle=*,dotscale=1.5,linecolor=prune](S1)(S3)
\psdots[dotstyle=*,dotscale=1, linecolor=gray](S5)(S9)
\end{pspicture}
\hfill 
\begin{pspicture}(6,6)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=Bo,dotscale=1.25,linewidth=0.75pt, linecolor=bleu}
\rput{0}(3.5,3){\multido{\n=90+40,\i=1+1}{9}{\dotnode(3;\n){S\i} \rput(3.5;\n){\scriptsize{\bleu{$s_\i$}}}}}
\ncline{S1}{S3} \ncline{S1}{S5}   \ncline{S2}{S4} \ncline{S2}{S7} \ncline{S3}{S5} \ncline{S3}{S9} \ncline{S4}{S6} \ncline{S4}{S7} \ncline{S5}{S8} \ncline{S6}{S7}\ncline{S8}{S9}
\psdots[dotstyle=*,dotscale=1.5,linecolor=prune](S1)(S3)(S5)
\psdots[dotstyle=*,dotscale=1, linecolor=gray](S8)(S9)
\end{pspicture}\hfill
\begin{pspicture}(6,6)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=Bo,dotscale=1.25,linewidth=0.75pt, linecolor=bleu}
\rput{0}(3.5,3){\multido{\n=90+40,\i=1+1}{9}{\dotnode(3;\n){S\i} \rput(3.5;\n){\scriptsize{\bleu{$s_\i$}}}}}
\ncline{S1}{S3} \ncline{S1}{S5}   \ncline{S2}{S4} \ncline{S2}{S7} \ncline{S3}{S5} \ncline{S3}{S9} \ncline{S4}{S6} \ncline{S4}{S7} \ncline{S5}{S8} \ncline{S6}{S7}\ncline{S8}{S9}
\psdots[dotstyle=*,dotscale=1.5,linecolor=prune](S1)(S3)(S5)(S8)(S9)
\end{pspicture}
\end{center}

Le graphe n'est pas connexe, il n'existe pas de chaîne entre les sommets $s_1$ et $s_2$.

 \subsection{cycle eulérien}
 
 \subsubsection{définition}
 
\cadreB{
Un cycle eulérien (\emph{respectivement une chaîne eulérienne}) dans un graphe $G$ est un cycle (\emph{respectivement une chaîne}) contenant chaque arête de $G$ une et une seule fois.
} 
 
 \subsubsection{théorème 1}
 
 \cadreR{Un graphe connexe admet un cycle eulérien si, et seulement si, tous ses sommets ont un degré pair.}
 
\medskip
 
\dem
 
 \medskip
 
Si le graphe possède 0 ou 1 sommet, la preuve est triviale, on suppose donc que l'ordre du graphe est supérieur ou égal à 2. 

Si le graphe connexe admet un cycle eulérien alors en chaque sommet le cycle eulérien \og entrant \fg{} dans le sommet doit \og ressortir \fg{} et comme les arêtes du cycle ne peuvent être utilisées qu'une fois, chaque sommet est de degré pair.
	
	Réciproquement :
	
Soit $G$ un graphe  connexe dont tous les sommets sont de degré pair. 

Comme $G$ possède au moins deux sommets, tous les sommets de $G$ sont de degré supérieur ou égal à 2. Ceci implique qu'il existe au moins un cycle dans $G$. 

Formons un cycle $C_1$ dans $G$ ( chaîne fermée dont toutes les arêtes sont distinctes ).

\begin{itemize}
	\item Si $C_1$ contient toutes les arêtes du graphe alors $G$ admet un cycle eulérien et le théorème est démontré.
	\item Dans le cas contraire, le sous graphe $H$ de $G$ défini par les arêtes non utilisées par $C_1$  a tous ses sommets de degré pair, le cycle contenant un nombre pair d'arêtes incidentes pour chaque sommet.
	
Comme $G$ est connexe, $H$ possède au moins un sommet commun avec le cycle $C_1$.  Soit $x_i$ un tel sommet. Construisons alors, de la même manière que
précédemment, un cycle  $C_2$ dans $H$ à partir de  $x_i$.

En insérant dans le cycle $C_1$ à partir du sommet $x_i$ le cycle $C_2$,on obtient un cycle  $C'_1$. Si ce cycle contient toutes les arêtes de $G$, $C'_1$ est le cycle eulérien cherché.

Sinon, on continue ce processus, qui se terminera car les sommets du graphe $G$ sont en nombre fini.
 
\end{itemize}
 
\subsubsection{théorème 2}
 
 \cadreR{Un graphe connexe possède une chaîne eulérienne si, et seulement si, le nombre de sommets de degré impair est égal à 0 ou 2.
 
 Si le nombre de sommets de degré impair est égal à 2, alors les deux sommets de degré impair sont les extrémités de la chaîne eulérienne}
 
\medskip
 
\dem
 
 \medskip
 
 Soit $G$ un graphe connexe. Si le nombre de sommets de degré impair est nul, alors le graphe $G$ admet un cycle eulérien.
 
 Si le nombre de sommets de degré impair est égal à 2. Soit $s_i$ et $s_ j$ les deux sommets de degré impair. 
 
 Le graphe $G'$ obtenu en ajoutant l'arête $s_i\,s_ j$ au graphe $G$ est connexe et  tous ses sommets sont de degré pair. $G'$ admet un cycle eulérien dont l'origine est le sommet $s_i$.
 
 Par conséquent $G$ contient une chaîne eulérienne qui commence en $s_i$ et se termine en $s_j$. 

  \subsubsection{algorithme}
  
Les démonstrations précédentes permettent de construire une chaîne eulérienne dans un graphe connexe dont le nombre de sommets de degré impair est 0 ou 2.
  

\begin{center}
\psframebox[linecolor=black,linewidth=0.25pt,framesep=1em]{
\begin{minipage}{.8\linewidth}
\textsf{\textbf{SI}} deux sommets sont de degré impair \textsf{ALORS}

\hspace{1em} construire une chaîne simple $C$ ayant pour extrémités ces deux sommets ;

\textsf{\textbf{Fin SI}}

\textsf{\textbf{SI}} tous les sommets sont de degré pair \textsf{ALORS}

\hspace{1em} construire un cycle $C$ à partir d'un sommet quelconque ;

\textsf{\textbf{Fin SI}}

marquer les arêtes de $C$ ;

\textsf{\textbf{Tant que}} il reste des arêtes non marquées

\begin{itemize}
\item[] choisir un sommet $x$ de $C$ ;
\item[] \textsf{SI} il existe un cycle d'origine $x$ ne contenant aucune des arêtes marquées \textsf{ALORS}

\hspace{1em} marquer les arêtes du cycle d'origine $x$ ;

\hspace{1em} remplacer dans  $C$ le sommet $x$ par le cycle d'origine $x$ ;

\textsf{\textbf{Fin SI} }
\end{itemize}
\textsf{\textbf{Fin Tant que}}
\end{minipage}
}
\end{center}

\pagebreak

\textsf {\textsc{\small{exemple}}}

\medskip

\begin{tabularx}{\linewidth}{@{}m{11.5cm} >{\raggedleft \arraybackslash}X@{}}

Le cycle $\left\{ s_1\, ; \,s_6\, ; \,s_5\, ; \,s_7\, ; \,s_3\, ; \,s_4\, ; \,s_2\, ; \,s_1 \right\}$ contient tous les sommets du graphe $G$ ci-contre.

Donc $G$ est connexe.

Il n'y a que deux sommets de degré impair $s_1$ et $s_5$.

Il existe une chaîne eulérienne d'extrémités $s_1$ et $s_5$.

&
 \psset{unit=.5cm}
\begin{pspicture}(9,7)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=Bo,dotscale=1.25,linewidth=0.5pt, linecolor=bleu}
\rput{0}(3,3){\multido{\n=180+60,\i=1+1}{6}{\dotnode(3;\n){S\i} \rput(3.5;\n){\scriptsize{\bleu{$s_\i$}}}}}
 \rput(8.5,3){\scriptsize{\bleu{$s_7$}}}
\dotnode(8,3){S7}
\ncline{S1}{S2} \ncline{S1}{S4}   \ncline{S1}{S6} \ncline{S2}{S5} \ncline{S2}{S4} \ncline{S2}{S6} \ncline{S3}{S4} \ncline{S3}{S5}  \ncline{S3}{S6} \ncline{S3}{S7} \ncline{S4}{S5} \ncline{S5}{S6} \ncline{S5}{S7}
\end{pspicture} \\
\textsc{\textsf{\small{étape 1}}}

Les deux sommets de degré impair sont $s_1$ et $s_5$	

On construit une chaîne simple joignant ces deux sommets ;

\[C=\left\{ s_1\, ; \,s_2\, ; \,s_6\, ; \,s_3\, ; \,s_4\, ; \,s_5 \right\}\]
&
\psset{unit=.5cm}
\begin{pspicture}(9,7)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=Bo,dotscale=1.25,linewidth=0.5pt, linecolor=bleu}
\rput{0}(3,3){\multido{\n=180+60,\i=1+1}{6}{\dotnode(3;\n){S\i} \rput(3.5;\n){\scriptsize{\bleu{$s_\i$}}}}}
\dotnode(8,3){S7} \rput(8.5,3){\scriptsize{\bleu{$s_7$}}}
 \ncline{S1}{S4}   \ncline{S1}{S6} \ncline{S2}{S5} \ncline{S2}{S4}   \ncline{S3}{S5}  \ncline{S3}{S7}  \ncline{S5}{S6} \ncline{S5}{S7}
\psset{linewidth=1.5pt, linecolor=prune}
 \ncline{S1}{S2}\ncline{S2}{S6}\ncline{S6}{S3}\ncline{S3}{S4}\ncline{S4}{S5}
\end{pspicture}\\
\textsc{\textsf{\small{étape 2}}}

Le cycle simple $c_1=\left\{ s_2\, ; \,s_4\, ; \,s_1\, ; \,s_6\, ; \,s_5\, ; \,s_2 \right\}$	ne contient aucune des arêtes de la chaîne $C$.

On fusionne la chaîne $C$ avec le cycle $c_1$ en remplaçant le sommet $s_2$ dans la chaîne $C$ par le cycle $c_1$.

\[C=\left\{ s_1\, ; \,s_2\, ; \,s_4\, ; \,s_1\, ; \,s_6\, ; \,s_5\, ; \,s_2\, ; \,s_6\, ; \,s_3\, ; \,s_4\, ; \,s_5 \right\}\]

Il reste encore des arêtes non marquées, on recommence l'étape 2
&
\psset{unit=.5cm}
\begin{pspicture}(9,7)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=Bo,dotscale=1.25,linewidth=0.5pt, linecolor=bleu}
\rput{0}(3,3){\multido{\n=180+60,\i=1+1}{6}{\dotnode(3;\n){S\i} \rput(3.5;\n){\scriptsize{\bleu{$s_\i$}}}}}
\dotnode(8,3){S7} \rput(8.5,3){\scriptsize{\bleu{$s_7$}}}
   \ncline{S3}{S5}  \ncline{S3}{S7} \ncline{S5}{S7}
 \psset{linewidth=1pt, linecolor=bleu}
 \ncline{S2}{S4} \ncline{S4}{S1}  \ncline{S1}{S6}  \ncline{S6}{S5}  \ncline{S5}{S2}  
\psset{linewidth=1.5pt, linecolor=prune}
 \ncline{S1}{S2}\ncline{S2}{S6}\ncline{S6}{S3}\ncline{S3}{S4}\ncline{S4}{S5}
\end{pspicture}\\

Le cycle  $c_2=\left\{ s_3\, ; \,s_7\, ; \,s_5\, ; \,s_3 \right\}$	ne contient aucune des arêtes de la chaîne $C$.

On fusionne la chaîne $C$ avec le cycle $c_2$ en remplaçant le sommet $s_3$ dans la chaîne $C$ par le cycle $c_2$.

\[C=\left\{ s_1\, ; \,s_2\, ; \,s_4\, ; \,s_1\, ; \,s_6\, ; \,s_5\, ; \,s_2\, ; \,s_6\, ; \,s_3\, ; \,s_7\, ; \,s_5\, ; \,s_3\, ; \,s_4\, ; \,s_5 \right\}\]

Toutes les arêtes sont marquées $C$ est une chaîne eulérienne.
&
\psset{unit=.5cm}
\begin{pspicture}(9,7)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=Bo,dotscale=1.25,linewidth=1pt, linecolor=bleu}
\rput{0}(3,3){\multido{\n=180+60,\i=1+1}{6}{\dotnode(3;\n){S\i} \rput(3.5;\n){\scriptsize{\bleu{$s_\i$}}}}}
\dotnode(8,3){S7} \rput(8.5,3){\scriptsize{\bleu{$s_7$}}}
   \ncline{S3}{S5}  \ncline{S3}{S7} \ncline{S5}{S7}

\psset{linewidth=1.5pt, linecolor=prune}
 \ncline{S1}{S2} \ncline{S2}{S4} \ncline{S4}{S1}  \ncline{S1}{S6}  \ncline{S6}{S5}  \ncline{S5}{S2} \ncline{S2}{S6}\ncline{S6}{S3}\ncline{S3}{S4}\ncline{S4}{S5}
\end{pspicture}\\

 \end{tabularx}
 
 
\newpage

\addcontentsline{toc}{section}{Exercices}

\exo

\medskip


Monsieur et madame X assistent à une réunion. Il y a trois autres couples dans l'assistance et plusieurs poignées de mains ont été é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. X constate que les autres personnes ont échangé des poignées de mains en nombres tous distincts.

Combien de poignées de mains M. X a-t-il échangé avec les autres membres de la réunion ?

\bigskip

\exo

\medskip

Lors d'une soirée, certaines personnes se serrent la main.

\begin{enumerate}
\item Montrer que le nombre de personnes ayant serré un nombre impair de mains est pair.
\item La conjecture :  \og Au cours de la soirée, deux personnes ont serré le même nombre de mains\fg{} est-elle vraie ou fausse ?
\end{enumerate}



\bigskip

\exo

\medskip

Est-il possible de tracer cinq segments sur une feuille, de telle manière que chaque segment en coupe exactement trois autres ?


\bigskip


\exo

\medskip

Pour chacune des listes suivantes, déterminer s'il existe un graphe simple admettant cette liste pour liste des degrés des sommets. S'il existe un tel graphe, le dessiner, sinon expliquer pourquoi.

\medskip

\begin{enumerate}
 \begin{tabularx}{\linewidth}{*{5}{@{}X@{}}}
\item $\left( 0,1, 2, 3 ,4, 5\right)$&\item $\left( 2,3,3,4,4,5\right)$ & \item $\left( 1,1,1,3\right)$ & \item $\left( 1,1,2,4,4\right)$ &  \item $\left( 2, 3, 3, 4 , 5, 6, 7\right)$\\
\end{tabularx}
\end{enumerate}

\bigskip

\exo

\medskip

\begin{enumerate}
	\item Quel est le nombre d'arêtes du graphe simple $G$ si la liste des degrés des sommets est $\left( 2,2,3,3,4 \right)$ ?
\item Dans un graphe simple d'ordre $n$, quel est le nombre maximal d'arêtes ?
\end{enumerate}

\bigskip

\exo

\medskip

Trouver deux graphes d'ordre 5 qui ne sont pas isomorphes et dont les degrés des sommets sont donnés par la liste  $\left(1,2,2,2,3\right)$. 

\bigskip

\exo

\medskip

Un graphe est \og \emph{planaire} \fg{} si on peut le dessiner dans le plan sans que deux arêtes se croisent.

Les graphes suivants sont-ils planaires ?

\medskip

\begin{center}
\psset{unit=1cm}
\begin{pspicture}(0,-.5)(3,4)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=1pt, linecolor=bleu}
\rput{0}(1.4,1.4){\multido{\n=45+90,\i=1+1}{4}{\dotnode(2;\n){S\i}}}
\ncline{S1}{S2}  \ncline{S1}{S3}  \ncline{S1}{S4}  \ncline{S2}{S3}  \ncline{S2}{S4}  \ncline{S3}{S4} 
\uput[d](1.5,0){\small{\bleu{$G_1$}}}
\end{pspicture}\hfill
\psset{unit=1cm}
\begin{pspicture}(0,-.5)(4,4)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=1pt, linecolor=bleu}
\rput{0}(1.9,1.62){\multido{\n=18+72,\i=1+1}{5}{\dotnode(2;\n){S\i}}}
\ncline{S1}{S2}  \ncline{S1}{S3}  \ncline{S1}{S4}  \ncline{S1}{S5} \ncline{S2}{S3}  \ncline{S2}{S4}  \ncline{S2}{S5}  \ncline{S3}{S4}  \ncline{S3}{S5} \ncline{S4}{S5}
\uput[d](2,0){\small{\bleu{$G_2$}}}
\end{pspicture}\hfill
\psset{unit=1cm}
\begin{pspicture}(0,-.5)(3.8,4)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=1pt, linecolor=bleu}
\rput{0}(1.4,1.4){\multido{\n=45+90,\i=1+1}{4}{\dotnode(2;\n){S\i}}}
\rput{0}(2.2,2.2){\multido{\n=45+90,\i=5+1}{4}{\dotnode(2;\n){S\i}}}
\ncline{S1}{S2}  \ncline{S2}{S3}  \ncline{S3}{S4}  \ncline{S4}{S1} 
\ncline{S5}{S6}  \ncline{S6}{S7}  \ncline{S7}{S8}  \ncline{S8}{S5}
\ncline{S1}{S5}  \ncline{S2}{S6}  \ncline{S3}{S7}  \ncline{S4}{S8}
\uput[d](1.9,0){\small{\bleu{$G_3$}}}
\end{pspicture}\hfill
\psset{unit=1cm}
\begin{pspicture}(0,-.5)(3.5,4)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{dotstyle=*,dotscale=1.5,linewidth=1pt, linecolor=bleu}
\rput{0}(1.75,2){\multido{\n=90+60,\i=1+1}{6}{\dotnode(2;\n){S\i}}}
\ncline{S1}{S2}  \ncline{S2}{S3}  \ncline{S3}{S4}  \ncline{S4}{S5} \ncline{S5}{S6}  \ncline{S6}{S1}  \ncline{S1}{S3}  \ncline{S3}{S5}
\ncline{S5}{S1}  \ncline{S2}{S4}  \ncline{S4}{S6}  \ncline{S6}{S2}
\uput[d](1.75,0){\small{\bleu{$G_4$}}}
\end{pspicture}
\end{center}

 \pagebreak
 
\exo

 \medskip 

\begin{enumerate}
	\item Dessiner le graphe simple d'ordre 8 dont l'ensemble des arêtes est :\[A =\{(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 ?

Si oui donner un parcours possible.
\item Existe-il un cycle passant une fois et une seule par toutes les arêtes du graphe ?
\end{enumerate}

 \bigskip 
 
 \exo

\medskip

\begin{enumerate}
\item Dessiner un graphe simple dont la liste des degrés des sommets est $(6,6,2,2,2,2,2,1,1)$
\begin{enumerate}
	\item qui possède une chaîne eulérienne ;
		\item qui ne possède pas de chaîne eulérienne.
\end{enumerate}
	\item Est-il possible d'avoir un graphe qui possède un cycle eulérien si la liste des degrés des sommets est $(6,6,4,2,2,2,2)$ ?
\end{enumerate}
\bigskip

\exo

\medskip

Pour chacun des graphes suivants, existe-t-il un cycle eulérien ? une chaîne eulérienne ?
 
\medskip

\psset{unit=.5cm}
\begin{pspicture}(0,-2)(9,11)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\uput[d](4.5,-1){\small{\textsf{Graphe } $G$}}
\psset{dotstyle=Bo,dotscale=1.2,linewidth=1.5pt, linecolor=bleu}
\dotnode(3,10){S1}\dotnode(1,8){S2}\dotnode(5,7){S3}\dotnode(7,8){S4}\dotnode(2,5){S5}\dotnode(4,5){S6}\dotnode(6,5){S7}\dotnode(9.2,4){S8}\dotnode(0,3){S9}\dotnode(1,1){S10}\dotnode(4,0){S11}\dotnode(7,1){S12}
\psset{linewidth=0.75pt, linecolor=bleu}
\nccurve[angleA=180,angleB=90]{S1}{S2}\nccurve[angleA=-80,angleB=90]{S1}{S3}\nccurve[angleA=240,angleB=90]{S1}{S6}\nccurve[angleA=20,angleB=90]{S1}{S4}\nccurve[angleA=60,angleB=40]{S1}{S8}\nccurve[angleB=60]{S1}{S12}
\nccurve[angleA=40,angleB=140]{S2}{S4}\nccurve[angleA=240,angleB=170]{S2}{S6}\nccurve[angleA=180,angleB=90]{S2}{S10}
   \nccurve[angleA=110,angleB=80]{S3}{S5}\nccurve[angleA=240,angleB=160]{S3}{S7}\nccurve[angleA=10,angleB=30]{S3}{S11}
  \nccurve[angleA=10,angleB=30]{S4}{S12}\nccurve[angleA=-30,angleB=10]{S4}{S10}
 \nccurve[angleA=270,angleB=-90]{S5}{S7}\nccurve[angleA=180,angleB=100]{S5}{S9}
  \nccurve[angleA=-40,angleB=210]{S6}{S8}
   \nccurve[angleA=240,angleB=-20]{S8}{S10}
   \nccurve[angleA=-20,angleB=160]{S9}{S11}
    \nccurve[angleA=270,angleB=-90]{S10}{S12}
     \nccurve[angleA=180,angleB=-90]{S12}{S6}
\end{pspicture}\hfill
\psset{unit=.5cm}
\begin{pspicture}(0,-2)(9,11)
\newrgbcolor{bleu}{0.1 0.05 .5}
\uput[d](4.5,-1){\small{\textsf{Graphe } $H$}}
\psset{dotstyle=Bo,dotscale=1.2,linewidth=1.5pt, linecolor=bleu}
\dotnode(2,10){S1}\dotnode(1,7){S2}\dotnode(5,8){S3}\dotnode(7,8){S4}\dotnode(2,5){S5}\dotnode(5,4.5){S6}\dotnode(7.5,4){S7}\dotnode(9,4){S8}\dotnode(0,3){S9}\dotnode(1,1){S10}\dotnode(4,0){S11}\dotnode(7,1){S12}
\psset{linewidth=0.75pt}
\nccurve[angleA=10,angleB=90]{S1}{S3}\nccurve[angleA=180,angleB=170]{S1}{S5}\nccurve[angleA=-90,angleB=120]{S1}{S7}\nccurve[angleA=250,angleB=60]{S1}{S11}
\nccurve[angleA=120,angleB=90]{S2}{S4}\nccurve[angleA=90,angleB=90]{S2}{S6}\nccurve[angleA=-90,angleB=90]{S2}{S8}\nccurve[angleA=180,angleB=90]{S2}{S10}
\nccurve[angleA=10,angleB=90]{S3}{S7}\nccurve[angleA=200,angleB=-10]{S3}{S9}\nccurve[angleA=-20,angleB=30]{S3}{S11}
  \nccurve[angleA=-90,angleB=30]{S4}{S6}\nccurve[angleA=-30,angleB=10]{S4}{S8}\nccurve[angleA=-30,angleB=10]{S4}{S10}
	\nccurve[angleA=-90,angleB=-90]{S5}{S7}\nccurve[angleA=180,angleB=90]{S5}{S9}\nccurve[angleA=200,angleB=180]{S5}{S11}
  	\nccurve[angleA=200,angleB=-20]{S7}{S9}\nccurve[angleA=-60,angleB=90]{S9}{S11}
  	\nccurve[angleA=240,angleB=-20]{S8}{S10}\nccurve[angleA=-60,angleB=90]{S8}{S12}\nccurve[angleA=-60,angleB=-90]{S10}{S12}
\end{pspicture}\hfill
\psset{unit=.5cm}
\begin{pspicture}(0,-2)(9,11)
\newrgbcolor{bleu}{0.1 0.05 .5}
\uput[d](4.5,-1){\small{\textsf{Graphe } $I$}}
\psset{dotstyle=Bo,dotscale=1.2,linewidth=1.5pt, linecolor=bleu}
\dotnode(3,10){S1}\dotnode(1,8){S2}\dotnode(0,4){S3}\dotnode(7,8){S4}\dotnode(6,6){S5}\dotnode(4,5.5){S6}\dotnode(2,5.2){S7}\dotnode(9,4){S8}\dotnode(2,3){S9}\dotnode(1,1){S10}\dotnode(4,0){S11}\dotnode(7,1){S12}
\psset{linewidth=0.75pt}
\nccurve[angleA=180,angleB=90]{S1}{S2}\nccurve[angleA=140,angleB=180]{S1}{S3}\nccurve[angleA=240,angleB=90]{S1}{S6}\nccurve[angleA=20,angleB=90]{S1}{S4}\nccurve[angleA=60,angleB=40]{S1}{S8}\nccurve[angleB=60]{S1}{S12}
\nccurve[angleA=40,angleB=140]{S2}{S4}\nccurve[angleA=240,angleB=170]{S2}{S6}\nccurve[angleA=180,angleB=90]{S2}{S10}
   \nccurve[angleA=110,angleB=80]{S3}{S5}\nccurve[angleA=30,angleB=160]{S3}{S7}\nccurve[angleA=-40,angleB=180]{S3}{S11}
  \nccurve[angleA=10,angleB=30]{S4}{S12}\nccurve[angleA=-30,angleB=10]{S4}{S10}
 \nccurve[angleA=270,angleB=-90]{S5}{S7}\nccurve[angleA=120,angleB=100]{S5}{S9}  \nccurve[angleA=-10,angleB=30]{S5}{S11}
  \nccurve[angleA=-40,angleB=210]{S6}{S8}
   \nccurve[angleA=240,angleB=-20]{S8}{S10}\nccurve[angleA=-60,angleB=-20]{S8}{S11}
   \nccurve[angleA=-20,angleB=160]{S9}{S11}
    \nccurve[angleA=270,angleB=-90]{S10}{S12}
     \nccurve[angleA=180,angleB=-90]{S12}{S6}
     \end{pspicture}
     
     
  \bigskip

\exo

 \medskip 

 On considère le graphe suivant :

 \begin{center}
\psset{xunit=2cm, yunit=1.5cm}
\begin{pspicture*}(-.25,-.5)(4.25,2.5)
\newrgbcolor{bleu}{0.1 0.05 .5}
\psset{linewidth=1pt,linecolor=bleu}
\psset{linewidth=1pt,linecolor=bleu,dotstyle=Bo,dotsize=5pt}
\dotnode(0,1){A} \dotnode(1,2){B} \dotnode(2,2){C} \dotnode(3,2){D} \dotnode(4,1){E} \dotnode(3,0){F} \dotnode(2,0){G}  \dotnode(1,0){H} 
\ncline{B}{A} \ncline{A}{H}\ncline{H}{G}\ncline{G}{F}\ncline{F}{E} \ncline{E}{D}\ncline{D}{C} \ncline{C}{B}\ncline{B}{G} \ncline{G}{D}\ncline{D}{A} \ncline{A}{E} \ncline{E}{H}\ncline{H}{C}\ncline{C}{F}
\uput[l](0,1){\small {\bleu {A}}} \uput[u](1,2){\small {\bleu {B}}} \uput[u](2,2){\small {\bleu {C}}} \uput[u](3,2){\small {\bleu {D}}} \uput[r](4,1){\small {\bleu {E}}} \uput[d](3,0){\small {\bleu {F}}} \uput[d](2,0){\small {\bleu {G}}} \uput[d](1,0){\small {\bleu {H}}} 
\end{pspicture*}
\end{center}

\begin{enumerate}
\item Le graphe est-il connexe ? 
\item  Le graphe admet-il des chaînes eulériennes ? Si oui,  en préciser une. 
\item Justifier la non-existence d'un cycle eulérien pour le graphe . Quelle arête peut-on alors ajouter à ce graphe pour obtenir un graphe contenant un cycle eulérien ?
\item  Soit $M$ la matrice  associée à ce graphe (les sommets sont pris dans l'ordre alphabétique).  

On donne 
\renewcommand{\arraystretch}{1}$M^3 = \begin{pmatrix*}[r]
4 & 10 & 3 & 12 & 7 & 8 & 3 & 12 \\ 
10 & 0 & 11 & 1 & 8 & 1 & 11 & 1 \\ 
3 & 11 & 0 & 14 & 3 & 11 & 0 & 14 \\ 
12 & 1 & 14 & 2 & 12 & 1 & 14 & 2 \\ 
7 & 8 & 3 & 12 & 4 & 10 & 3 & 12 \\ 
8 & 1 & 11 & 1 & 10 & 0 & 11 & 1 \\ 
3 & 11 & 0 & 14 & 3 & 11 & 0 & 14 \\ 
12 & 1 & 14 & 2 & 12 & 1 & 14 & 2 \\ 
\end{pmatrix*}$
 
\medskip

Déterminer le nombre de chaînes de longueur 3 partant du sommet G et aboutissant au sommet E. 

Citer alors  toutes ces chaînes.  
\end{enumerate}


\bigskip 

\exo 

 \medskip 


\textsf{\textbf{\textsc{partie a}}}

\medskip
  
Le graphe suivant modélise le plan d'une zone résidentielle. Les arêtes du graphe représentent les rues et les sommets du graphe les carrefours.

\medskip

\begin{minipage}{10cm} 
\begin{enumerate}
\item Donner l'ordre du graphe puis le degré de chacun des sommets. 
\item Un piéton peut-il parcourir toutes ces rues sans emprunter plusieurs fois la même rue : 
	\begin{enumerate}
		\item en partant d'un carrefour et en revenant à son point de départ ? Justifier la réponse.
		\item en partant d'un carrefour et en arrivant à un carrefour différent ? Justifier la réponse.
	\end{enumerate}
\end{enumerate}\end{minipage}\hfill \begin{minipage}{6.5cm}\psset{unit=1cm}
\begin{pspicture}(-.5,-.5)(6,3.5)
\newrgbcolor{bleu}{0.1 0.05 .5}
\psset{linewidth=1pt,linecolor=bleu}
\dotnode(4,3){A}\uput[u](4,3){\sf \bleu{\small A}}
\dotnode(1.5,3){B}\uput[u](1.5,3){\sf \bleu{\small B}}
\dotnode(0,1.5){C}\uput[l](0,1.5){\sf \bleu{\small C}} 
\dotnode(1.5,0){D}\uput[d](1.5,0){\sf \bleu{\small D}} 
\dotnode(4,0){E}\uput[d](4,0){\sf \bleu{\small E}} 
\dotnode(5.5,1.5){F}\uput[r](5.5,1.5){\sf \bleu{\small F}} 
\ncline{B}{A}\ncline{A}{F}\ncline{F}{E}\ncline{E}{A}\ncline{A}{D}\ncline{D}{C}\ncline{C}{B}\ncline{B}{D}\ncline{D}{E}
\end{pspicture}\end{minipage}

\medskip

\textsf{\textbf{\textsc{partie b}}}

\medskip
 
Dans le graphe ci-contre, on a indiqué, pour cette même zone résidentielle, le sens de circulation pour les véhicules sur les différentes rues. 

\medskip

\begin{minipage}{10cm} 
\begin{enumerate}
\item Expliquer pourquoi le sommet F représente une impasse. 
\item Écrire la matrice $M$ associée à ce graphe (on rangera les sommets dans l'ordre alphabétique)
\item En partant du carrefour C quel est le nombre minimal de rues qu'il faut emprunter pour arriver en E ?
\item Combien y-a-t-il de chemins de longueur 3 qui arrivent en F ? 
\end{enumerate}\end{minipage}\hfill \begin{minipage}{6.5cm}\psset{unit=1cm,arrowsize=2pt 3}
\begin{pspicture}(-.5,-.5)(6,3.5)
\newrgbcolor{bleu}{0.1 0.05 .5}
\psset{linewidth=1pt,linecolor=bleu}
\dotnode(4,3){A}\uput[u](4,3){\sf \bleu{\small A}}
\dotnode(1.5,3){B}\uput[u](1.5,3){\sf \bleu{\small B}}
\dotnode(0,1.5){C}\uput[l](0,1.5){\sf \bleu{\small C}} 
\dotnode(1.5,0){D}\uput[d](1.5,0){\sf \bleu{\small D}} 
\dotnode(4,0){E}\uput[d](4,0){\sf \bleu{\small E}} 
\dotnode(5.5,1.5){F}\uput[r](5.5,1.5){\sf \bleu{\small F}} 
\ncline[ArrowInside=->]{B}{A}\ncline[ArrowInside=->]{A}{F}\ncline[ArrowInside=-<]{F}{E}\ncline[ArrowInside=-<]{E}{A}\ncarc[arcangle=20,ArrowInside=->]{A}{D}\ncline[ArrowInside=-<]{D}{C}\ncline[ArrowInside=-<]{C}{B}\ncline[ArrowInside=-<]{B}{D}\ncline[ArrowInside=-<]{D}{E}\ncarc[arcangle=20,ArrowInside=->]{D}{A}
\end{pspicture}\end{minipage}

 \bigskip

\exo

 \medskip 

On considère le graphe $\mathcal{G}$ ci-dessous :

\begin{center}
\psset{xunit=.75cm,yunit=.5cm}
\begin{pspicture}(13,6)
\newrgbcolor{bleu}{0.1 0.05 .5}
\newrgbcolor{prune}{.6 0 .48}
\psset{linewidth=1pt,linecolor=bleu}
\cnodeput(0,3){A}{\bleu{\footnotesize{\sf{A}}}}
\cnodeput(2.5,6){B}{\bleu{\footnotesize{\sf{B}}}}
\cnodeput(6.5,6){C}{\bleu{\footnotesize{\sf{C}}}}
\cnodeput(2,0){D}{\bleu{\footnotesize{\sf{D}}}}
\cnodeput(4,3){E}{\bleu{\footnotesize{\sf{E}}}}
\cnodeput(13,3){F}{\bleu{\footnotesize{\sf{F}}}}
\cnodeput(9.4,3){G}{\bleu{\footnotesize{\sf{G}}}}
\cnodeput(7.6,0){H}{\bleu{\footnotesize{\sf{H}}}}
\ncline{D}{H}\ncline{H}{C}\ncline{C}{G}\ncline{G}{H}\ncline{H}{F}\ncline{F}{G}
\ncline{G}{E}\ncline{E}{D}\ncline{D}{A}\ncline{A}{B}\ncline{B}{C}\ncline{C}{E}\ncline{E}{B}
\end{pspicture}
\end{center}

\begin{enumerate}
\item Donner l'ordre du graphe puis le degré de chacun des sommets. 
\item Déterminer en justifiant si ce graphe est : complet ? connexe ?
\item Déterminer en justifiant si le graphe $\mathcal{G}$ admet un cycle eulérien ou une chaîne eulérienne. 
\item On range les sommets par ordre alphabétique. Donner la matrice d'adjacence $M$ associée au graphe. 
\item Une des trois matrices $R$, $S$ ou $T$ est la matrice $M^3$.

	\begin{center}
	\scriptsize{
	 $R = \begin{pmatrix}
0 &5 &3 &5 &2 &2 &4 &2\\ 
5 &2 &7 &2 &8 &3 &3 &5\\ 
3 &7 &6 &4 &9 &3 &9 &20\\ 
5 &2 &4 &0 &9 &2 &3 &8\\ 
2 &8 &9 &9 &4 &4 &20 &4\\ 
2 &3 &3 &2 &4 &2 &6 &6\\ 
4 &3 &9 &3 &20 &6 &6 &9 \\
2 &5 &20 &8 &4 &6 &9 &4\\
\end{pmatrix}$
 \hfill
 $S =\begin{pmatrix}
0 &5 &3 &5 &1 &1 &4 &1\\ 
5 &2 &7 &2 &8 &3 &3 &5\\ 
3 &7 &6 &4 &9 &3 &9 &10\\ 
5 &2 &4 &0 &9 &2 &3 &8\\ 
1 &8 &9 &9 &4 &4 &10 &4\\ 
1 &3 &3 &2 &4 &2 &6 &6\\ 
4 &3 &9 &3 &10 &6 &6 &9 \\
1 &5 &10 &8 &4 &6 &9 &4\\
\end{pmatrix}$
 \hfill
$T =\begin{pmatrix}
0 &5 &3 &5 &1 &2 &4 &5\\ 
5 &2 &7 &2 &8 &3 &3 &5\\ 
3 &7 &6 &4 &9 &3 &9 &10\\ 
5 &2 &4 &0 &9 &2 &3 &8\\ 
1 &8 &9 &9 &4 &4 &10 &4\\ 
1 &3 &3 &2 &4 &2 &6 &6\\ 
4 &3 &9 &3 &10 &6 &6 &9 \\
5 &1 &10 &8 &4 &6 &9 &4\\
\end{pmatrix}$}
	\end{center}
\begin{enumerate}
\item Sans calculer la matrice $M^3$, indiquer quelle est la matrice $M^3$ en justifiant votre choix.
\item Donner, en justifiant, le nombre de chemins de longueur 3 reliant E à F. Les citer tous. 
\end{enumerate}
\end{enumerate}
    
 \bigskip
  
\exo \hfill (\emph{D'après sujet bac France métropolitaine, La Réunion septembre 2016})

 \medskip 


Un parc de loisirs décide d'ouvrir une nouvelle attraction pour les jeunes enfants : un parcours pédestre où chaque enfant doit recueillir, sur différents lieux, des indices pour résoudre une énigme. Le parcours est représenté par le graphe ci-dessous. Les sommets représentent des lieux où sont placés les indices ; les arêtes représentent des chemins pédestres qui les relient. 
\begin{center}
\psset{xunit=.5cm,yunit=.5cm}
\begin{pspicture}(14,8)
\newrgbcolor{bleu}{0.1 0.05 .5}
\psset{linecolor=bleu,linewidth=1pt}
\begin{footnotesize}
\rput(2,5){\cnode*{2pt}{A}{\uput[u](0,0){\sf{\bleu A}}}}\rput(6,6){\cnode*{2pt}{B}{\uput[u](0,0){\sf{\bleu B}}}}\rput(10,5){\cnode*{2pt}{C}{\uput[r](0,0){\sf{\bleu C}}}} \rput(5,3){\cnode*{2pt}{D}{\uput[d](0,0){\sf{\bleu D}}}} \rput(0,1){\cnode*{2pt}{E}{\uput[d](0,0){\sf{\bleu E}}}} \rput(11,8){\cnode*{2pt}{F}{\uput[u](0,0){\sf{\bleu F}}}} \rput(14,4){\cnode*{2pt}{G}{\uput[r](0,0){\sf{\bleu G}}}}  \rput(12,0){\cnode*{2pt}{H}{\uput[d](0,0){\sf{\bleu H}}}}
\ncline{A}{E} \ncline{E}{D} \ncline{D}{A}\ncline{A}{B} \ncline{B}{D} \ncline{D}{C} \ncline{C}{B} \ncline{B}{F} \ncline{F}{C} \ncline{C}{H} \ncline{H}{G} \ncline{G}{F}
\end{footnotesize}
\end{pspicture}
\end{center}

 \textsf{\textbf{\textsc{partie a}}}

\medskip 
 
\begin{enumerate}
\item Un enfant pourra-t-il parcourir chaque chemin pédestre du circuit une fois et une seule ? Si oui, indiquer un circuit possible et sinon expliquer pourquoi.
\item On note $M$ la matrice d'adjacence associée à ce graphe (les sommets sont pris dans l'ordre alphabétique).
 
On donne la matrice $M^4=\begin{pmatrix}
20 & 18 & 20 & 21 & 11 & 13 & 5 & 5\\
18 & 32 & 25 & 25 & 17 & 16 & 10 & 10\\
20 & 25 & 31 & 19 & 13 & 13 & 14 & 5\\
21 & 25 & 19 & 31 & 13 & 21 & 4 & 12\\
11 & 17 & 13 & 13 & 11 & 6 & 4 & 3 \\
13 & 16 & 13 & 21 & 6 & 20 & 3 & 13\\
5 & 10 & 14 & 4 & 4 & 3 & 9 & 1\\
5 & 10 & 5 & 12 & 3 & 13 & 1 & 10\end{pmatrix}$.
 
Déterminer le nombre de parcours allant de E à H en 4 chemins pédestres. Les citer tous. 
\end{enumerate}

\medskip

 \textsf{\textbf{\textsc{partie b}}}

\medskip 
 
Afin d'améliorer la qualité de ses services, une étude statistique a relevé la durée moyenne d'attente en minutes à la billetterie du parc en fonction de l'heure. Ce relevé a eu lieu chaque heure de 9h à 16h. On obtient le relevé suivant : 

\begin{center}
\psset{unit=.5cm}
\begin{pspicture}(-1,-1)(19,12)
\def\pshlabel#1{\scriptsize #1}
\def\psvlabel#1{\scriptsize #1}
\newrgbcolor{bleu}{0.1 0.05 .5}
\psgrid[gridwidth=0.25pt,gridcolor=darkgray,subgriddiv=0,gridlabels=0](0,0)(-1,-1)(19,12)
\psset{xunit=.5cm,yunit=.25cm}
\psaxes[labelsep=.8mm,linewidth=.75pt,ticksize=-2pt 2pt,Dy=2]{->}(0,0)(-1,-2)(19,24)
\uput[dl](19,0){\footnotesize{$x$}} \uput[dl](0,24){\footnotesize{$y$}}
\uput[dl](0,0){\scriptsize{0}}
\psdots[linewidth=1pt, linecolor=bleu,dotscale=.8](9,9)(10,14)(11,20)(12,22)(13,21)(14,20)(15,12)(16,2)
\end{pspicture}
\end{center}

Ainsi, à 10~h, il y avait 14 minutes d'attente à la billetterie.
 
On souhaite modéliser cette durée d'attente par une fonction qui à l'heure associe la durée d'attente en minutes. Ainsi, il sera possible d'avoir une estimation de la durée d'attente. 

On choisit de modéliser cette situation à l'aide de la fonction $f$ définie par $f(x)=ax^2+bx+c$ avec $a$, $b$, $c$ des réels et $a$ non nul telle que les trois points $(9 ; 9)$, $(11 ; 20)$ et $(16 ; 2)$ appartiennent à la représentation graphique de $f$. 
 
\begin{enumerate}
\item Calculer les trois réels $a$, $b$ et  $c$.
\item En utilisant ce modèle, déterminer sur quelle(s) plage(s) horaire(s) l'attente peut être inférieure à dix minutes. 
\end{enumerate} 

 \bigskip 
  
\exo

 \medskip 

On considère le graphe $\Gamma$ ci-dessous. 

\begin{center}
\psset{xunit=1.5cm,yunit=1cm}
\begin{pspicture}(0,-.2)(5,5.2)
\newrgbcolor{bleu}{0.1 0.05 .5}
\psset{linewidth=1pt,linecolor=bleu}
\newrgbcolor{prune}{.6 0 .48}
\cnodeput(1,4){A} {\small{\bleu\sf{A}}}\cnodeput(0,0){B}{\small{\bleu\sf{B}}} 
\cnodeput(1.8,1){C}{\small{\bleu\sf{C}}} \cnodeput(3.2,1){D}{\small{\bleu\sf{D}}}\cnodeput(5,0){E}{\small{\bleu\sf{E}}} \cnodeput(2.5,3){F}{\small{\bleu\sf{F}}} \cnodeput(2.5,5){G}{\small{\bleu\sf{G}}} \cnodeput(4,4){H}{\small{\bleu\sf{H}}} 
\ncline{A}{B} \ncline{B}{E}\ncline{E}{D}\ncline{D}{C}\ncline{C}{B} \ncline{B}{F}\ncline{F}{E}\ncline{E}{H}\ncline{H}{F}
\ncline{F}{A}\ncline{A}{G}\ncline{G}{H}
\end{pspicture}
\end{center}
 
\textsf {\textbf{\textsc{partie a}}}

\medskip

\begin{enumerate}

	\item Donner la matrice $M$ associée au graphe $\Gamma$ (les sommets seront rangés dans l'ordre alphabétique).
	\item On donne : $M^2 = \begin{pmatrix}  
3 & 1 & 1 & 0 & 2 & 1 & 0 & 2\\
1 & 4 & 0 & 2 & 1 & 2 & 1 & 2\\
1 & 0 & 2 & 0 & 2 & 1 & 0 & 0\\
0 & 2 & 0 & 2 & 0 & 1 & 0 & 1\\
2 & 1 & 2 & 0 & 4 & 2 & 1 & 1\\
1 & 2 & 1 & 1 & 2 & 4 & 2 & 1\\
0 & 1 & 0 & 0 & 1 & 2 & 2 & 0\\
2 & 2 & 0 & 1 & 1 & 1 & 0 & 3\\
\end{pmatrix}$  et  $M^3 = \begin{pmatrix*}[r]  
2 & 7 & 1 & 3 & 4 & 8 & 5 & 3\\
7 & 4 & 6 & 1 & 10 & 8 & 3 & 4\\
1 & 6 & 0 & 4 & 1 & 3 & 1 & 3\\
3 & 1 & 4 & 0 & 6 & 3 & 1 & 1\\
4 & 10 & 1 & 6 & 4 & 8 & 3 & 7\\
8 & 8 & 3 & 3 & 8 & 6 & 2 & 8\\
5 & 3 & 1 & 1 & 3 & 2 & 0 & 5\\
3 & 4 & 3 & 1 & 7 & 8 & 5 & 2\\
\end{pmatrix*}$.
 
	\begin{enumerate}		
		\item Déterminer, en justifiant, le nombre de chaînes de longueur 3 reliant B à H. Les citer toutes. 
\item Quelle est la distance entre les sommets B et G ?
	\end{enumerate}
	\item 
	\begin{enumerate}
		\item Déterminer en justifiant si le graphe $\Gamma$ est complet.		
		\item Déterminer en justifiant si le graphe $\Gamma$ est connexe.
	\end{enumerate}
	\end{enumerate}
	
\medskip
 
\textsf {\textbf{\textsc{partie b}}}

\medskip	
	
Le graphe $\Gamma$ modélise le plan d'un parc. Les arêtes du graphe représentent les allées du parc et les sommets du graphe sont les intersections. 

En fin de journée, un agent du service d'entretien fait le tour du parc pour nettoyer les allées.
\begin{enumerate}
\item Est-il possible de planifier un parcours pour que cet agent passe par toutes les allées sans emprunter plusieurs fois la même allée ? Justifier la réponse. Si oui proposer un  parcours.
\item Pour rationaliser le nettoyage des allées, on souhaite établir un circuit commençant et finissant par l'entrée du parc G et qui passe par toutes les allées une et une seule fois.

Quel est le nombre minimal d'allées qu'il faudrait tracer pour obtenir un tel circuit. 
\end{enumerate}

\medskip
 
\textsf {\textbf{\textsc{partie c}}}

\medskip

La buvette du parc vend des crêpes ( 3,50~\euro{}), des glaces ( 3~\euro{}) et des bouteilles d'eau minérale (2,50~\euro{}).

À la fin d'une journée, la recette est de \np{1120}~\euro{}. 

Le responsable de la buvette constate qu'il a vendu deux fois plus de bouteilles d'eau minérale que de crêpes et que le nombre de glaces vendues est égal à la somme   du nombre de bouteilles d'eau minérale et de crêpes vendues.

On note $a$ le nombre de glaces, $b$ le nombre de bouteilles d'eau minérale et $c$ le nombre de crêpes qui ont été vendues ce jour là.

\begin{enumerate}
\item Justifier que $a$, $b$ et $c$ sont solutions du système : $\begin{cases}3a + 2,5b + 3,5c = 1120\\b -2c = 0\\a -b - c = 0\end{cases}$.
\item Déterminer les matrices $A$, $X$ et $B$ pour que le système précédent soit équivalent à $AX=B$.
\item Déterminer $a$, $b$ et $c$. Interpréter le résultat.
\end{enumerate}

\end{document}