\documentclass[12pt]{article}

\usepackage[fleqn]{amsmath}
\usepackage[cp1252]{inputenc} 
\usepackage[T1]{fontenc} 
\usepackage[french]{babel}
\usepackage{graphicx,caption,subfig}
\usepackage{color}
\usepackage{amssymb}
\usepackage[colorlinks=true,linkcolor=blue,bookmarksnumbered]{hyperref}
\usepackage[table]{xcolor}
\usepackage[left=1.5cm, right=1.5cm, top=1.5cm, bottom=1.5cm]{geometry}
\usepackage{eurosym}

%\setlength\textwidth{15cm} 
%\setlength\oddsidemargin{-0.54cm} 
%\setlength\topmargin{-1.04cm} 
%\setlength\textheight{22.7cm} 
\setlength\headheight{0.55cm} 
%\setlength\headsep{0.5cm} 

\usepackage{fancyhdr}
\renewcommand{\footrulewidth}{0.4pt}

\newenvironment{encadrer}[1]{\noindent \textbf{#1 :} \par \begin{center} \begin{tabular}{|p{13cm}|} \hline}{\\ \hline \end{tabular} \bigskip \end{center}}
\newenvironment{sanscadre}[1]{\noindent \textbf{#1 :}\par  \noindent}{\bigskip\par}
\newenvironment{sanscadresansflush}[1]{\noindent \textbf{#1 :}\par \noindent}{\bigskip\par}
\newenvironment{paragraphe}[1]{\noindent \textbf{#1 :}\par \noindent}{\bigskip\par}


\newcommand{\defref}[2]{\hypertarget{#1}{\emph{\color{red}{#2}}}}
\newcommand{\faireref}[2]{\hyperlink{#1}{#2}}
\newcommand{\nouvitem}{\item[$\bullet$]}
\newcommand{\emphref}[1]{\emph{\color{red}{#1}}}

\newcommand{\pdfrowcolors}[1]{\rowcolors{1}{#1}{#1}}

\title{Graphes, terminale ES spécialité}


\author{F.Gaudon}



\begin{document}

\pagestyle{fancy}
\fancyhead[L]{}
\fancyhead[R]{\textit{Graphes, terminale ES spécialité}}
\fancyfoot[R]{\includegraphics[width=2cm]{88x31.png}}
\fancyfoot[C]{\thepage}
\fancyfoot[L]{\footnotesize \textit{\color{black}\url{http://mathsfg.net.free.fr}}}



\maketitle

\tableofcontents

\newpage

\section{Généralités}

\begin{encadrer}{Définition}
\begin{itemize}
\nouvitem Un \emphref{graphe} est un ensemble de \emphref{sommets} pouvant être reliés par des \emphref{arêtes}.
\nouvitem Deux sommets reliés par une arête sont dits \emphref{adjacents}.
\nouvitem \emphref{L'ordre} d'un graphe est le nombre de sommets.
\nouvitem Une \emphref{boucle} est une arête reliant un sommet à lui-même.
\nouvitem \emphref{Le degré} d'un sommet est le nombre d'arêtes dont le sommet est une extrémité.
\nouvitem Un graphe est dit \emphref{simple} s'il ne comporte pas de boucle et tel qu'entre deux sommets, il y ait au plus une arête.
\end{itemize}
\end{encadrer}

\begin{sanscadre}{Exemple}
\begin{figure}[h]\centering
\includegraphics[width=5cm]{graphesgeneralitescoursimg1.pdf}
\caption*{Graphe simple}
\end{figure}
\end{sanscadre}



\begin{encadrer}{Propriété}
Dans un graphe la somme des degrés des sommets est égale au double du nombre d'arêtes.
\end{encadrer}

\begin{encadrer}{Définitions}
\begin{itemize}
\nouvitem Un graphe est dit \emphref{complet} si tous ses sommets sont adjacents.
\nouvitem Un sous-graphe est un graphe composé de certains de ces sommets ainsi que de toutes les aretes qui les relient.
\nouvitem Un graphe est dit \emphref{orienté} si ses arêtes ont un sens de parcours. On parle alors \emphref{d'origine} et \emphref{d'extrémité} d'une arête.
\end{itemize}
\end{encadrer}

\newpage


\begin{sanscadre}{Exemples}
\begin{figure}[h]\centering
\subfloat[Graphe complet]{\includegraphics[width=5cm]{graphesgeneralitescoursimg2.pdf}}
\subfloat[Graphe orienté]{\includegraphics[width=5cm]{graphesgeneralitescoursimg3.pdf}}
\end{figure}
\end{sanscadre}


\section{Chaînes et cycles}

\begin{encadrer}{Définitions}
\begin{itemize}
\nouvitem Une \emphref{chaîne} est une liste ordonnée de sommets telle que chaque sommet soit adjacent au suivant.
\nouvitem Un graphe est dit \emphref{connexe} si toute paire de sommets peut être reliée par une chaîne.
\nouvitem Une \emphref{chaîne eulérienne} est une chaîne contenant toutes les arêtes du graphe, chacune prise une seule fois.
\nouvitem Un \emphref{cycle} est une chaîne dont l'origine et l'extrémité sont les mêmes et dont les arêtes n'apparaissent qu'une seule fois.
\nouvitem Un cycle est dit \emphref{cycle eulérien} si il est formé de toutes les arêtes du graphe, chacune prise une seule fois.
\end{itemize}
\end{encadrer}

\begin{encadrer}{Théorème d'Euler}
Soit $G$ un graphe connexe.
\begin{itemize}
\nouvitem $G$ admet une chaîne eulérienne si et seulement si $G$ admet exactement deux sommets de degrés impairs.
\nouvitem $G$ admet un cycle eulérien si et seulement si $G$ ne possède que des sommets de degrés pairs.
\end{itemize}
\end{encadrer}

\begin{encadrer}{Définition}
\begin{itemize}
\nouvitem La \emphref{longueur} d'une chaîne est le nombre d'arêtes qui la constituent.
\nouvitem Dans un graphe connexe, 
	\begin{itemize}
		\nouvitem la distance entre deux sommets est la longueur de la plus courte chaîne qui relie ces deux sommets.
		\nouvitem le diamètre du graphe est la plus grande distance entre deux sommets.
	\end{itemize}
\end{itemize}
\end{encadrer}

\section{Matrice d'adjacence d'un graphe}

\begin{encadrer}{Définition}
Soit $G$ un graphe dont les sommets sont numérotés de 1 à $n$ avec $n\in\mathbb{N}^{*}$. La \emphref{matrice d'adjacence} de $G$ est une matrice carrée d'ordre $n$, remplie de sorte que le coefficient $a_{i,j}$ situé à l'intersection de la ligne $i$ et de la colonne $j$ soit le nombre d'arêtes partant du sommet numéro $i$ au sommet numéro $j$.
\end{encadrer}

\begin{encadrer}{Propriétés}
\begin{itemize}
\nouvitem La matrice d'adjacence d'un graphe simple ne comporte que des 0 et des 1.
\nouvitem La matrice d'adjacence d'un graphe non orienté est symétrique.
\end{itemize}
\end{encadrer}

\begin{sanscadre}{Remarques}
\begin{itemize}
\nouvitem Dans un graphe non orienté, la somme des termes d'une ligne (ou d'une colonne) donne le degré du sommet correspondant.
\nouvitem La matrice dont tous les coefficients (sauf éventuellement ceux de la diagonale) sont égaux à 1 est la matrice d'adjacence d'un graphe complet.
\end{itemize}
\end{sanscadre}


\begin{encadrer}{Théorème}
Soit $M$ la matrice d'adjacence d'une graphe $G$ et $p$ un entier naturel non nul. Dans la matrice $M^p$, le coefficient situé à l'intersection de la ligne $i$ et de la colonne $j$ est égal au nombre de chai\^nes de longueur $p$ d'origine le sommet $i$ et d'extrémité le sommet $j$.
\end{encadrer}

\section{Graphes étiquetés et graphes pondérés}

\begin{encadrer}{Définition}
Un graphe \emphref{étiqueté} est un graphe orienté dont chaque arête est affectée d'une étiquette pouvant être des nombres, des lettres ou des symboles. Ils peuvent en outre comporter un sommet de début et un sommet de fin.
\end{encadrer}




\begin{encadrer}{Définition}
Un graphe \emphref{pondéré} est un graphe étiqueté dont les arêtes sont affectées de nombres positifs appelés \emphref{poids}.
\end{encadrer}

\begin{encadrer}{Définitions}
\begin{itemize}
\nouvitem Dans un graphe pondéré, le poids d'une chaîne est la somme des poids des arêtes constituant la chaîne.
\nouvitem Une plus courte chaîne entre deux sommets est, parmi les chaînes qui les relient, une chaîne de poids minimal.
\end{itemize}
\end{encadrer}

\section{Graphes probabilistes}
\begin{encadrer}{Définitions}
Un \emphref{graphe probabiliste} est un graphe orienté et pondéré tel que :
\begin{itemize}
\nouvitem pour chaque sommet, la somme des poids des arêtes issues de ce sommet est égale à 1 ;
\nouvitem le poids de l'arête allant du sommet I au sommet J est la probabilité conditionnelle d'obtenir J à l'étape $n+1$ sachant que l'on a obtenu $I$ à l'étape $n$.
\end{itemize}
\end{encadrer}

\begin{sanscadre}{Exemple}
\begin{figure}[h]\centering
\includegraphics[width=5cm]{graphesgeneralitescoursimg10.pdf}
\caption*{Exemple de graphe probabiliste}
\end{figure}
\end{sanscadre}

\begin{encadrer}{Définitions}
\begin{itemize}
\nouvitem \emphref{L'état probabiliste} d'un système est une loi de probabilité sur l'ensemble des états possibles. Cette loi est représentée par une matrice ligne dont la somme des termes vaut 1.
\nouvitem La matrice de transition d'un graphe probabiliste d'ordre $n$ dont les sommets sont numérotés de 1 à $n$ est la matrice carrée d'ordre $n$ où le terme figurant en ligne $i$ et colonne $j$ est égal au poids de l'arête allant de $i$ vers $j$ si cette arête existe ou à 0 sinon.
\end{itemize}
\end{encadrer}

\begin{sanscadre}{Exemple}
Pour le graphe ci-dessus, soit $(p_0;q_0)$ est l'état probabiliste initial. Alors, après une étape, on peut déterminer l'état probabiliste en utilisant l'arbre suivant :
\begin{center}
\includegraphics[width=5cm]{graphesgeneralitescoursimg11.pdf}
\end{center}
On obtient $P_1=(p_1;q_1)=(0,2p_0+0,6q_0;0,8p_0+0,4q_0)$.\par 
\noindent La matrice de transition est :
$$\begin{pmatrix} 0,2 & 0,8 \\ 0,6 & 0,4 \end{pmatrix} $$
\end{sanscadre}


\begin{encadrer}{Propriété}
Soit $M$ est la matrice de transition d'un graphe probabiliste, $P_0$ la matrice décrivant l'état initial  et $P_n$ l'état probabiliste à l'étape $n$, alors $P_n=P_0\times M^n$.
\end{encadrer}

\begin{encadrer}{Propriété et définition}
Pour tout graphe probabiliste d'ordre 2 dont la matrice de transition $M$ ne comporte pas de 0, l'état probabiliste $P_n$ à l'étape $n$ converge vers un état $P$ indépendant de l'état initial $P_0$. De plus, $P$ vérifie $P=P\times M$. On dit que $P$ est \emphref{l'état stable} du graphe probabiliste.
\end{encadrer}



\end{document}
