\documentclass[french]{article}
\usepackage[T1]{fontenc}
\usepackage{babel}
\usepackage{lmodern}
\usepackage[table]{xcolor}
\usepackage{emerald}
\usepackage{eso-pic}
\usepackage[urlcolor=blue,colorlinks=true]{hyperref}
\usepackage[margin=1cm,bottom=2.5cm]{geometry}
\usepackage{titlesec}
\usepackage{fancyhdr}
\usepackage{tikz}
	\usetikzlibrary {decorations.pathmorphing , shapes.geometric}
\usepackage{pas-math}
\usepackage{multicol}
\usepackage{tkz-graph}

% Couleurs

\definecolor{bleuciel}{HTML}{45b5f4}
\definecolor{bleu}{HTML}{0e3e59}
\definecolor{orangesanguine}{HTML}{b43f0b}
\definecolor{vert}{HTML}{287f13}

% styles des titres

%%% Titre de la fiche

\renewcommand{\title}[1]{%
\begin{center}
\begin{tikzpicture}
\node[fill=bleuciel,ellipse,decorate,decoration={random steps,segment length=3pt,amplitude=2pt}, align=center,inner ysep=5mm, inner xsep=0pt,ball color=bleuciel] (titre) {\ECFJD\Huge #1};
\node[below] (auteur) at (titre.south) {\ECFJD Une fiche de cours de Stéphane Pasquet - Mise à jour : \today};
\node[below] at (auteur.south) {(\url{https://courspasquet.fr})\qquad\qquad(\url{https://mathweb.fr})};
\end{tikzpicture}
\end{center}
}

%%% section

\titleformat{\section}[block]
{\ECFJD\fontsize{16}{14}\selectfont\color{bleu}}
{\thesection}
{1em}
{\ECFJD}
\setlength{\parindent}{0pt}

%%% subsection

\titleformat{\subsection}[block]
{\ECFJD\fontsize{12}{12}\selectfont\color{orangesanguine}}
{\thesubsection}
{1em}
{\ECFJD}
\setlength{\parindent}{0pt}

%%% paragraph

\titleformat{\paragraph}[runin]
{\ECFJD\color{vert}}{\theparagraph}{1em}{}

%%% pied et tête de page

\renewcommand{\headrulewidth}{0pt}
\lhead{}
\cfoot{\ECFJD\Large\color{white}\fcolorbox{bleu}{bleu}{\thepage}}
\renewcommand{\headrulewidth}{0pt}

\begin{document}

\pagestyle{fancy}

\AddToShipoutPictureBG
{%
	\put(\LenToUnit{5mm},\LenToUnit{5mm})
	{%
		\begin{tikzpicture}
		\draw[fill=yellow!10,draw,thick,decorate,decoration = {random steps}] (0,0) rectangle +(\dimexpr\paperwidth-10mm,\dimexpr\paperheight-10mm);
		\end{tikzpicture}
	}
}

\title{Graphes \& matrices}

\section*{Graphes}

\subsection*{Définition}

Un \textit{graphe} $\mathcal{G}$ est la donnée de deux ensembles: l'un est constitué de points, appelés \textit{sommets}, l'autre est constitué de couples de points, appelés \textit{arêtes}.

\subsection*{Vocabulaire}

\begin{itemize}
\item[$\bullet$] Deux sommets sont \textit{adjacents} s'il existe une arête entre eux.

\item[$\bullet$] Une graphe est \textit{complet} si tous les sommets sont adjacents deux à deux.

\vspace*{-1ex}

\paragraph*{Propriété:} un graphe complet à $n$ sommets compte $\dfrac{n(n-1)}{2}$ arêtes.

\medskip


\item[$\bullet$] L'\textit{ordre} d'un graphe est le nombre de sommets de ce graphe.

\item[$\bullet$] Une \textit{chaîne} d'un graphe est une liste ordonnée de sommets adjacents deux à deux.

Le nombre de sommets de cette liste est appelé la \textit{longueur} de la chaîne.

\item[$\bullet$] Un graphe est \textit{connexe} si deux sommets quelconques de ce graphe peuvent être reliés par au moins une chaîne.
\end{itemize}

\subsection*{Types de graphes}

\begin{minipage}{0.45\textwidth}
\subsubsection*{Graphes non orientés}

$\mathcal{G}=( \mathcal{S}; \mathcal{A} )$  est \textit{non orienté} si les couples de $\mathcal{A}$ peuvent être inversés.

\bigskip

Une représentation sagittale d'un tel graphe peut-être celle ci-contre: les arêtes ne comportent pas de flèches.
\end{minipage}
\begin{minipage}{0.45\textwidth}
\begin{center}
\begin{tikzpicture}
%\SetUpEdge[style={->}]
\GraphInit[vstyle=Shade]
\Vertex[L=D]{D}
\Vertex[x=3,y=2]{S}
\Vertex[x=6,y=1]{L}
\Vertex[x=2,y=-1]{A}
\Edge(D)(S)\Edge(D)(A)\Edge(L)(D)\Edge(A)(S)\Edge(A)(L)
\Edge(S)(L)\Edge[style={bend right}](S)(D)
\end{tikzpicture}
\end{center}
\end{minipage}

\vspace*{3em}

\begin{minipage}{0.45\textwidth}
\subsubsection*{Graphes orientés}

$\mathcal{G}=( \mathcal{S}; \mathcal{A} )$  est \textit{orienté} si les couples de $\mathcal{A}$ ne peuvent pas être inversés.

\bigskip

Une représentation sagittale d'un tel graphe peut-être celle ci-contre: les arêtes ont un \og sens \fg, représenté par une flèche.
\end{minipage}
\begin{minipage}{0.45\textwidth}
\begin{center}
\begin{tikzpicture}
\SetUpEdge[style={->}]
\GraphInit[vstyle=Shade]
\Vertex[L=D]{D}
\Vertex[x=3,y=2]{S}
\Vertex[x=6,y=1]{L}
\Vertex[x=2,y=-1]{A}
\Edge(D)(S)\Edge(D)(A)\Edge(L)(D)\Edge(A)(S)\Edge(A)(L)
\Edge(S)(L)\Edge[style={bend right,->}](S)(D)
\end{tikzpicture}
\end{center}
\end{minipage}

\newpage

\begin{minipage}{0.45\textwidth}
\subsubsection*{Graphes pondérés}

Un graphe est dit \textit{pondéré} si ses arêtes sont munies de nombres positifs, appelés \textit{étiquettes} ou \textit{pondérations}.

\bigskip

Une représentation sagittale d'un tel graphe peut-être celle ci-contre: chaque arêtes est étiquetée d'un nombre (représentant ce que l'on veut).
\end{minipage}
\begin{minipage}{0.45\textwidth}
\begin{center}
\begin{tikzpicture}
\GraphInit[vstyle=Shade]
\Vertex[L=D]{D}
\Vertex[x=3,y=2]{S}
\Vertex[x=6,y=1]{L}
\Vertex[x=2,y=-2]{A}
\Edge[label=7,labelstyle={draw=brown,text=brown}](D)(S)
\Edge[label=3,labelstyle={draw=brown,text=brown}](D)(A)
\Edge[label=10,labelstyle={draw=brown,text=brown}](D)(L)
\Edge[label=5,labelstyle={draw=brown,text=brown}](A)(S)
\Edge[label=8,labelstyle={draw=brown,text=brown}](A)(L)
\Edge[label=3,labelstyle={draw=brown,text=brown}](L)(S)
\end{tikzpicture}
\end{center}
\end{minipage}

\vspace*{1em}

\begin{minipage}{0.45\textwidth}
\subsubsection*{Graphes probabilistes}

Un graphe probabiliste est un graphe orienté où la somme des pondérations des arêtes issues d'un même sommet est égale à 1.

\bigskip

Une représentation sagittale d'un tel graphe peut-être celle ci-contre.
\end{minipage}
\begin{minipage}{0.45\textwidth}
\begin{center}
\begin{tikzpicture}[scale=0.7]
\GraphInit[vstyle=Shade]
\tikzset{LabelStyle/.style = {draw=brown,text=brown,fill=white,outer sep=-3mm}}
\grProb[Ldist=0.1cm,LposA=0,LposB=180]%
{Chambre}{Cuisine}%
{{0,3}}{{0,6}}%
{{0,7}}{{0,4}}%
\end{tikzpicture}
\end{center}
\end{minipage}

\section*{Matrices}

\subsection*{Matrice d'adjacence d'un graphe}

\begin{minipage}{0.45\textwidth}
\subsubsection*{Graphe non orienté}

\begin{tikzpicture}
\GraphInit[vstyle=Shade]
\Vertex[L=$S_1$]{D}
\Vertex[x=3,y=2,L=$S_2$]{S}
\Vertex[x=7,y=1,L=$S_4$]{L}
\Vertex[x=1,y=-1,L=$S_3$]{A}
\Edge(D)(S)
\Edge(D)(L)
\Edge(A)(L)
\Edge(L)(S)
\end{tikzpicture}
\end{minipage}
\begin{minipage}{0.45\textwidth}
\[
A=
\begin{pmatrix}
0 & 1 & 0 & 1\\
1 & 0 & 0 & 1\\
0 & 0 & 0 & 1\\
1 & 1 & 1 & 0
\end{pmatrix}
\]
\end{minipage}

\vspace*{3em}

\begin{minipage}{0.45\textwidth}
\subsubsection*{Graphe orienté}

\begin{tikzpicture}
\SetUpEdge[style={->}]
\GraphInit[vstyle=Shade]
\Vertex[L=D]{D}
\Vertex[x=3,y=2]{S}
\Vertex[x=7,y=1]{L}
\Vertex[x=2,y=-1]{A}
\Edge(D)(S)\Edge(D)(A)\Edge(L)(D)\Edge(A)(S)\Edge(A)(L)
\Edge(S)(L)\Edge[style={bend right,->}](S)(D)
\end{tikzpicture}
\end{minipage}
\begin{minipage}{0.45\textwidth}
En convenant de classer les sommets dans cet ordre:
\begin{center}
D -- S -- A -- L
\end{center}
\[
A=
\begin{pmatrix}
0 & 1 & 1 & 0\\
1 & 0 & 0 & 1\\
0 & 1 & 0 & 1\\
1 & 0 & 0 & 0
\end{pmatrix}
\]
\end{minipage}

\paragraph*{Nombre de chaînes d'un graphe non pondéré:} le nombre de chaînes de longueur $k$ reliant deux sommets $S_i$ et $S_j$ est le coefficient $c_{i,j}$ de la matrice $A^k$.

\newpage

\begin{minipage}{0.45\textwidth}
\subsubsection*{Graphe pondéré}
\begin{tikzpicture}
\GraphInit[vstyle=Shade]
\Vertex[L=D]{D}
\Vertex[x=3,y=2]{S}
\Vertex[x=6,y=1]{L}
\Vertex[x=2,y=-2]{A}
\Edge[label=7,labelstyle={draw=brown,text=brown}](D)(S)
\Edge[label=3,labelstyle={draw=brown,text=brown}](D)(A)
\Edge[label=10,labelstyle={draw=brown,text=brown}](D)(L)
\Edge[label=5,labelstyle={draw=brown,text=brown}](A)(S)
\Edge[label=8,labelstyle={draw=brown,text=brown}](A)(L)
\Edge[label=3,labelstyle={draw=brown,text=brown}](L)(S)
\end{tikzpicture}
\end{minipage}
\begin{minipage}{0.45\textwidth}
En convenant d'ordonner les sommets de la manière suivante:
\begin{center}
D -- S -- A -- L
\end{center}
la matrice d'adjacence du graphe ci-contre est:
\[
A=
\begin{pmatrix}
0 & 7 & 3 & 10\\
7 & 0 & 5 & 3\\
3 & 5 & 0 & 8\\
10 & 3 & 8 & 0
\end{pmatrix}
\]
\end{minipage}

\vspace*{3em}

\begin{minipage}{0.45\textwidth}
\subsubsection*{Graphe probabiliste}

\begin{tikzpicture}[scale=0.7]
\GraphInit[vstyle=Shade]
\tikzset{LabelStyle/.style = {draw=brown,text=brown,fill=white,outer sep=-3mm}}
\grProb[Ldist=0.1cm,LposA=0,LposB=180]%
{Chambre}{Cuisine}%
{{0,3}}{{0,6}}%
{{0,7}}{{0,4}}%
\end{tikzpicture}
\end{minipage}
\begin{minipage}{0.45\textwidth}
En convenant d'ordonner les sommets du graphe ci-contre comme ceci:
\begin{center}
Chambre -- Cuisine
\end{center}
la matrice du graphe ci-contre est:
\[
A=
\begin{pmatrix}
0,7&  0,3\\
0,6 & 0,4
\end{pmatrix}
\]
\end{minipage}

\subsection*{Chaîne de Markov}

Une chaîne de Markov est une suite d'événements $\suite{X}{n}{n\in\N}$ où chaque $X_n$ ne dépend que de $X_{n-1}$, pour $n>0$.

La représentation sagittale précédente du graphe probabiliste représente uen chaine de Markov à 2 états.

\subsubsection*{État stable}

Soit $\mathcal{G}$ un graphe probabiliste de matrice $M$.

L'\textit{état stable} du graphe est la matrice ligne $P=\begin{pmatrix}
x_1 & x_2 & \cdots & x_n\end{pmatrix}$ telle que $P = PM$, avec $\displaystyle\sum_{k=1}^n x_k=1$.

\paragraph*{Exemple:} si on considère le graphe probabiliste précédent, l'état stable de ce graphe est la matrice $P=\begin{pmatrix}a & b\end{pmatrix}$ telle que: 
\begin{align*}
P=PM & \iff PI_2=PM\\
& \iff P(M-I_2) = 0\\
& \iff \begin{pmatrix}a & b\end{pmatrix}\begin{pmatrix}0,7-1 & 0,3\\0,6 & 0,4-1\end{pmatrix}=0\qquad,\qquad a+b=1\\
& \iff \begin{cases}
-0,3a +0,6b = 0\\
a+b=1
\end{cases}\\
& \iff \begin{cases}
a = \frac{2}{3}\\
b = \frac{1}{3}
\end{cases}
\end{align*}

L'état stable du graphe est donc $P = \begin{pmatrix}\frac{2}{3} & \frac{1}{3}\end{pmatrix}$.

\medskip

Cela signifie qu'à très termes, la probabilité que Louis soit dans sa chambre est égale à $\dfrac{2}{3}$.

\end{document}