\documentclass[french,a4paper]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc} % systématique
\usepackage{babel}
\usepackage[left=2.2cm, right=2.2cm, top=2.2cm, bottom=2.2cm]{geometry} % à revoir (diminuer) en cas de modification du document
%\usepackage{fancybox} % si fbox n'est pas suffisant
\usepackage{color}
%\usepackage{graphics}
%\usepackage{multicol} % pour organiser le document en colonnes si \twocolumn insuffisant
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{stmaryrd} % some fonts / symbols (\llbracket for example)
%\usepackage{array} % étend les options des envts array et tabular
\usepackage{minted} % pour mettre en forme du code
%\usepackage{calrsfs} % lettres calligraphiées avec \mathcal
\usepackage{blkarray} % accolade sur plusieurs lignes de texte (utilisé dans plus courts chemins)

\title{Option informatique MP : L'essentiel des arbres et des graphes}
\author{Louis Alvin}
\date{\today}


\begin{document}


\maketitle



\section{Arbres binaires}

\paragraph{Définition}

Soit \(E\) un ensemble d'éléments appelés \textit{étiquettes}. L'ensemble des arbres binaires étiquetés sur \(E\), noté \( \mathcal{A}_{E} \), est tel que :

\begin{itemize}
	\item[\textbullet] Vide \( \in \mathcal{A}_{E} \)
	\item[\textbullet] \( \forall x \in E, ~ \forall A_{g}, A_{d} \in \mathcal{A}_{E}, ~~~ (A_{g}, x, A_{d}) \in \mathcal{A}_{E} \)
	\item[\textbullet] \( \mathcal{A}_{E} \) est minimal pour l'inclusion.
\end{itemize}

\begin{minted}{ocaml}
type 'a arbre = Vide | Noeud of 'a arbre * 'a * 'a arbre
\end{minted}

\paragraph{Propriété}

\( h(A) + 1 \leq |A| \leq 2^{h(A)+1} - 1 \)

\paragraph{Arbre binaire de recherche}

Il s'agit d'un arbre :

\begin{itemize}
	\item[\textbullet] soit Vide
	\item[\textbullet] soit de la forme \( (A_{g}, x, A_{d}) \) avec :
	\begin{itemize}
		\item tous les nœuds de \(A_{g}\) sont \(< x\)
		\item tous les nœuds de \(A_{d}\) sont \(> x\)
		\item \(A_{g}\) et \(A_{d}\) sont également des arbres binaires de recherche.
	\end{itemize}
\end{itemize}

\paragraph{Tas binaires}

Un tas max (resp. tas min) est un arbre binaire qui vérifie les deux contraintes :

\begin{itemize}
	\item[\textbullet] tout nœud de l'arbre est supérieur (resp. inférieur) à ses fils
	\item[\textbullet] l'arbre est \textbf{parfait} : tous les niveaux sont complets sauf éventuellement le dernier, rempli de gauche à droite.
\end{itemize}

N.B. : on numérote les nœuds en partant de la racine (1), puis de gauche à droite. Si un nœud est numéroté \(i\), alors son fils gauche est numéroté \(2i\), son fils droit \(2i+1\), son père \( \lfloor \frac{i}{2} \rfloor \). On représente le tas par un tableau.

\paragraph{Tri par tas}

Dans un tas max, le plus grand élément du tas est à la racine, son extraction est donc en \(\mathcal{O}(1)\). On l'envoie à la fin du tas ; on utilise \texttt{t.(0)} pour conserver l'indice du premier élément hors du tas (à la création, \texttt{t.(0) = Array.length t}). Pour retrouver un tas, on effectue des échanges avec le plus grand des fils pour descendre le conflit jusqu'à résolution totale.

\begin{minted}{ocaml}
let echange t i j =
	let tmp = t.(i) in
	t.(i) <- t.(j);
	t.(j) <- tmp;;

let plus_grand_fils t i =
	let i_max = ref i in (* si noeud > fils on renvoie i *)
	if 2*i < t.(0) && t.(2*i) > t.(!i_max) then i_max := 2*i; (* test du fils gauche *)
	if 2*i + 1 < t.(0) && t.(2*i + 1) > t.(!i_max) then i_max := 2*i + 1; (* fils droit *)
	!i_max;;

let rec descend t i =
	let i_max = plus_grand_fils t i in
	if i_max <> i then
		(echange t i i_max;
		descend t i_max);;
\end{minted}

Tant qu'il reste un élément dans le tas, on extrait le max. du tas et on descend la racine pour retrouver une structure de tas.

\begin{minted}{ocaml}
let tri_par_tas t =
	t.(0) <- Array.length t;
	while t.(0) > 1 do
		echange t 1 (t.(0) - 1);
		t.(0) <- t.(0) - 1;
		descend t 1
	done;;
\end{minted}



\section{Graphes}

\paragraph{Lemme des poignées de main}

Le degré entrant (resp. sortant) d'un sommet \(u\), noté \(\deg^{-}(u)\) (resp. \(\deg^{+}(u)\)), est défini par
\( \deg^{-}(u) = \text{Card}({v \in V, ~ (v,u) \in E}) \). On énonce alors le lemme :

\[ \sum_{v \in V} \deg^{+}(v) = \sum_{v \in V} \deg^{-}(v) = |E| \]

\paragraph{Modélisation avec listes d'adjacences}

\begin{minted}{ocaml}
type graphe = int list array
\end{minted}

\paragraph{Modélisation avec matrice d'adjacences}

N.B. : Si \(G\) est non orienté, alors la matrice \(A\) est symétrique.

\begin{minted}{ocaml}
type graphe = bool array array
\end{minted}


\subsection{Parcours de graphes}

\paragraph{Parcours en profondeur}

On utilise un tableau de booléens pour mémoriser les sommets visités.

\begin{minted}{ocaml}
let parcours_profondeur g u0 =
	let visite = Array.make (Array.length g) false
	in let rec visiter u =
		if visite.(u) = false then
			begin
			visite.(u) <- true;
			let rec visite_voisins l = match l with
				| [] -> ()
				| v::q -> visiter v;
					  visite_voisins q
			in visite_voisins g.(u)
			end
	in visiter u0;;
\end{minted}

\paragraph{Parcours en largeur}

On a besoin d'une file pour stocker les sommets selon l'ordre croissant de leur distance à \(u_{0}\).

\begin{minted}{ocaml}
let parcours_largeur g u0 =
	let n = Array.length g in
	let q = Queue.create () in
	let visites = Array.make n false in
	Queue.add u0 q;
	visites.(u0) <- true
	while not (Queue.is_empty q) do
		let u = Queue.pop q in
		for v = 0 to (n-1) do
			if visites.(v) = false then
				(Queue.add v q;
				visites.(v) <- true)
		done;
	done;;
\end{minted}


\subsection{Algorithmes de plus courts chemins}

Pour les graphes non pondérés, à partir d'un sommet donné, on utilise un parcours en largeur.

Pour les graphes pondérés, 3 situations : \\

\begin{blockarray}{l\Right{\}}{~Dijkstra}}
	\textbullet ~ D'un sommet vers tous les autres~\\
	\textbullet ~ D'un sommet vers un autre
\end{blockarray}

\begin{blockarray}{l\Right{\}}{~Floyd-Warshall}}
	\textbullet ~ De tous les sommets vers tous les autres~
\end{blockarray}

\subsubsection{Algorithme de Floyd-Warshall}

On suppose que le graphe pondéré n'admet aucun cycle de poids \(< 0\).

\paragraph{Principe}

Il s'agit d'un algorithme de programmation dynamique.

On cherche les \( d(i,j) \) pour tout \(i,j \in V \). Hypothèse : \( V = \{0, ..., n-1\} \).

Sous-problème : contrainte supplémentaire sur les sommets autorisés dans les chemins.

On note : \( d_{ij}^{(k)} \) la longueur d'un plus court chemin de \(i\) à \(j\) passant uniquement par des sommets dans \( \{0, ..., k\} \).

Problème à résoudre : \( k = n-1 \). \\

On procède par récurrence forte sur \(k\).

Cas de base : \(k = -1 \longrightarrow\) aucun sommet intermédiaire dans les chemins :\\
\( d_{ij}^{(-1)} = \left\lbrace
\begin{array}{l}
	0 \text{ si } i = j \\
	\omega (i,j) \text{ si } (i,j) \in E \\
	+\infty \text{ sinon (pas de chemin)}
\end{array} \right. \)

Relation de récurrence : Supposons qu'on ait calculé les \( d_{ij}^{(k)} \) pour \( k \in \llbracket -1 ; n-2 \rrbracket \) fixé, et \( \forall (i,j) \in V^{2} \). On souhaite calculer \( d_{ij}^{(k+1)} \text{ pour } (i,j) \in V^{2} \).

Au final, on obtient :
\( d_{i,j}^{(k+1)} = \min \left( d_{i,j}^{(k)};\text{  } d_{i,k+1}^{(k)} + d_{k+1,j}^{(k)} \right) \).

Le résultat recherché correspond à \( k = n-1 \).

\paragraph{Pseudo-code}

\begin{minted}[escapeinside=||,mathescape=true]{text}
Pour tout |\(\mathtt{ (i,j) \in \llbracket 0; n-1 \rrbracket }\)| faire :
	|\(\mathtt{ d_{ij}^{(-1)} \longleftarrow } \left\lbrace \begin{array}{l} \mathtt{ 0 \texttt{ si } i = j \text{  };\text{ } \omega (i,j) \texttt{ si } i \neq j \texttt{ et } (i,j) \in E } \\ \mathtt{+\infty} \texttt{ sinon} \end{array} \right. \)|
	Pour |\(\mathtt{ k = 0 }\)| à |\(\mathtt{ n - 1 }\)| faire :
		Pour |\(\mathtt{ (i,j) \in \llbracket 0; n-1 \rrbracket }\)| faire :
			|\(\mathtt{ d_{ij}^{(k)} \longleftarrow \texttt{min} \left( d_{ij}^{(k-1)};\text{  } d_{ik}^{(k-1)} + d_{kj}^{(k-1)} \right) }\)|
	Renvoyer |\(\mathtt{ \left( d_{ij}^{(n-1)} \right)_{i,j} }\)|
\end{minted}

\subsubsection{Algorithme de Dijkstra}

On suppose que \( G = (V, E, \omega) \) est un graphe pondéré avec \( \omega : E \rightarrow \mathbb{R}^{+} \).

On cherche les longueurs des plus courts chemins d'un sommet \(s\) appelé source vers tous les autres sommets de \(G\).

\paragraph{Principe}

On adapte l'algorithme de parcours en largeur permettant de trouver les plus courts chemins dans un graphe \textit{non pondéré} \(\rightarrow\) l'utilisation d'une file nous permettait d'explorer les sommets dans l'ordre de leur distance à \(s\) croissante.

Pour Dijkstra, on parcourt également les sommets dans l'ordre de leur distance à \(s\).

À chaque étape, on dispose de surestimations des longueurs des plus courts chemins depuis \(s\), que l'on note \(d(u)\) (pour \(u \in V\)). On notera \( \delta(s,u) \) la longueur d'un plus court chemin de \(s\) à \(u\).

On manipule un ensemble \( S \subseteq V \) de sommets qu'il reste à explorer et dont on ne connaît pas encore la distance à \(s\).

\paragraph{Pseudo-code}

\begin{minted}[escapeinside=||,mathescape=true]{text}
|\(\mathtt{ d(s) \leftarrow 0 \text{ } ; \text{ } d(u) \leftarrow +\infty }\)|
|\(\mathtt{ S \leftarrow V }\)|
Pour |\(\mathtt{ k = 0 \text{ à } \mid S \mid - 1 }\)| faire :
	|\(\mathtt{ u \leftarrow \texttt{Argmin} \{ d(v), \text{ } v \in S \} }\)|
	Enlever u de S
	Pour tout v voisin de u faire :
		Si |\(\mathtt{ d(v) > d(u) + \omega (u,v) }\)| :
			|\(\mathtt{ d(v) \leftarrow d(u) + \omega (u,v) }\)|
Renvoyer d
\end{minted}

















\end{document}