%\documentclass{article} \documentclass{tpcaml} \usepackage{fullpage} \usepackage[french]{babel} \usepackage[T1]{fontenc} \usepackage{amsfonts,amsmath,amssymb,amsthm,boxedminipage,color,url,fullpage,bbm,tikz,multicol} \usepackage{array} \usepackage{setspace} \usepackage{fourier-orns} \usepackage{enumerate} \usepackage{vmargin} % red\'efinir les marges \setmarginsrb{1cm}{1cm}{1cm}{1cm}{0.3cm}{0.2cm}{0.5cm}{0.5cm} \usepackage{graphicx} %\usepackage[applemac]{inputenc} %\newcommand{\R}{\mathbb{R}} %\newcommand{\C}{\mathbb{C}} \newtheorem{thm}{Théorème} \newtheorem{de}{Définition} \newtheorem{prop}{Propriété} \newtheorem{lemme}{Lemme} \newcounter{question} %\newcommand{\question}{\vspace{0.25cm}\par\noindent\stepcounter{question} % \hspace{-0.25cm}\fbox{\textbf{\arabic{question}}}\quad} \usepackage{fancyhdr,frame} \pagestyle{fancy} \fancyhf{} %\fancyhead[LE,RO]{Share\LaTeX} %\fancyhead[RE,LO]{Guides and tutorials} \fancyfoot[LE,LO]{Lyc\'ee Faidherbe-MPI-2023/2024} \fancyfoot[CE,CO]{\thepage} \renewcommand{\headrulewidth}{0pt} \renewcommand{\footrulewidth}{1pt} \date{15 octobre} \title{Chapitre 4 : Compl\'ements d'algorithmique des graphes} \begin{document} \maketitle \thispagestyle{fancy} Les figures utilisées dans ce document proviennent de l'ouvrage suivant :\\ https://jeffe.cs.illinois.edu/teaching/algorithms/ \section{CFC-Kosaraju} On rappelle la notion de sous graphe induit : \begin{de} Soit $G=(S,A)$ un graphe et $S' \subset S$ un sous ensemble de sommets de $G$. On appelle $G'=(S',A')$ le sous graphe induit par $S'$ où $A' = \{(x,y) \in A : x \in S' \text{ et } y \in S'\}$. \end{de} On rappelle la définition des composantes fortement connexes dans un graphe orienté : \begin{de} On définit la relation $R$ sur $S$ par $\forall x,y \in S, xRy$ ssi il existe un chemin de $x$ à $y$ et il existe un chemin de $y$ à $x$. Cette relation est une relation d'équivalence et ses classes d'équivalences forment une partition de $S$. Chaque classe d'équivalence $S_i$ induit un graphe $G_i=(S_i,E_i)$ et l'ensemble des graphes $G_i$ est l'ensemble des composantes fortement connexes de $G$. \end{de} Voici un exemple illustrant cette notion : \begin{center} \includegraphics[width=0.3\textwidth]{cfc} \end{center} On a vu en première année qu'on peut identifier les composantes connexes d'un graphe non orienté à l'aide d'un parcours (qu'il soit en profondeur ou en largeur). Calculer les composantes fortement connexes est une tâche a priori plus ardue mais on va voir que cela peut être fait en exploitant le parcours en profondeur et ses propriétés. \subsection{Rappels sur le parcours en profondeur} Commençons par rappeler le principe du parcours en profondeur. On part d'un sommet, on le traite et on appelle récursivement la procédure sur tous ses voisins s'ils n'ont pas encore été découverts. \begin{verbatim} pp_rec(g,s) : if (not(decouvert[s]) : decouvert[s]<-true; pour tous les x voisins de s : pp_rec(g,x); traite[s]<-true; \end{verbatim} Un appel à \verb+pp_rec(g,s)+ va parcourir les sommets accessibles depuis le sommet \verb+s+. Afin de s'assurer de visiter tous les sommets du graphe et non pas seulement ceux accessibles depuis \verb+s+, on appellera successivement cette procédure sur tous les sommets qui n'ont pas encore été découverts lors des appels précédents. \begin{verbatim} pp(g) : pour tous les sommets x de g : traite[x]<-false; decouvert[x]<-false; pour tous les sommets x de g : si non decouvert[x] : pp_rec(g,x); \end{verbatim} La distinction entre les sommets découverts et non découverts est essentielle pour écrire un parcours en profondeur. Elle garantit que chaque sommet n'est traité qu'une seule fois et que l'algorithme s'arrête. Nous avons ici ajouté la notion de sommet traité qui signifie qu'un sommet ainsi que tous les sommets accessibles depuis ce dernier ont été découverts. Cette notion s'est déjà révélée utile pour les applications comme la détection de cycle dans un graphe orienté ou le tri topologique et nous sera aussi utile ici. Un parcours en profondeur induit une forêt du parcours en profondeur. Cette dernière est définie par une relation de parenté : on dit que $v$ est le fils de $u$ si l'appel à \verb+pp_rec(g,v)+ est directement effectué par la fonction \verb+pp_rec(g,u)+. Ainsi, $v$ est descendant de $u$ si l'appel à \verb+pp_rec(g,v)+ est fait au sein de la fonction \verb+pp_rec(g,u)+(par elle même ou par un de ses appels récursifs imbriqués). En d'autre terme : \fbox{$v$ sera un descendant de $u$ dans la forêt ssi lorsque $v$ est découvert alors $u$ est découvert mais pas encore traité} (la fonction \verb+pp_rec(g,u)+ n'est pas encore terminée). C'est pour la caractérisation de cette relation de descendance que l'on a introduit la notion de sommet traité. En plus de la caractérisation de la relation de descendance entre sommets au sein de la forêt de parcours, soulignons une propriété fondamentale :\\ Si au moment de la découverte du sommet \verb+u+ il existe un chemin reliant \verb+u+ à \verb+v+ composé uniquement de sommets non découverts alors \verb+v+ sera un descendant de \verb+u+. \subsection{Graphe miroir} \begin{de} Le graphe miroir de $G$ est le graphe o\`u on a interverti l'orientation des arêtes. Soit $G=(S,A)$ un graphe orienté, le graphe miroir de $G$, noté $\bar{G}$ est définit par $(S,A')$ où $A'=\{(x,y) : (y,x) \in A\}$. \end{de} \begin{prop} Soit $G=(S,A)$ un graphe orienté. Le miroir du miroir de $G$ est $G$ lui-même. \end{prop} \begin{de} Soit $G=(S,A)$ un graphe orienté. On dit qu'un sommet $s \in S$ est un puit ssi $G$ ne contient aucune arête de la forme $(s,\ldots)$. Soit $G=(S,A)$ un graphe orienté. On dit qu'un sommet $s \in S$ est une source ssi ssi $G$ ne contient aucune arête de la forme $(\ldots,s)$. \end{de} \begin{thm} Soit $G=(S,E)$ un graphe orienté. Un sommet $s\in S$ est un puit dans $G$ ssi c'est une source dans $\bar{G}$. \end{thm} \vspace{3cm} \begin{de} Soit $G=(S,E)$ un graphe orienté. Pour tout $s \in S$, on note $\text{reach}_G(s)=\{ x \in S : s \leadsto_G x\}$. \end{de} \begin{de} Soit $G=(S,E)$ un graphe orienté. Pour tout $s \in S$, on note $\text{reach}_G^{-1}(s)=\{ x \in S : x \leadsto_G s\} = \{x \in S : s \in reach(x)\}$. \end{de} \begin{prop} Soit $G=(S,E)$ un graphe orienté. Pour tout $s \in S$, $\text{reach}_G^{-1}(s)=\text{reach}_{\bar{G}}(s)$. \end{prop} \vspace{3cm} \subsection{Calcul d'une composante fortement connexe} Soit $G=(S,E)$ un graphe orienté. Pour tout $s \in S$, $cfc(s)=\{x \in s : x \leadsto_G s \text{ et } s \leadsto_G x\} = \text{reach}_G(s) \cap \text{reach}_{\bar{G}}(S)$. Ainsi, à l'aide de n'importe quel type de parcours d'origine \verb+s+ on peut déterminer ces ensembles en parcourant une fois $G$ et une fois $\bar{G}$. On peut donc calculer une CFC en $O(|S|+|A|)$ et toutes les CFC en $O(|S|.|A|)$. \subsection{Algorithme de Kosaraju : calcul de l'ensemble des composantes fortement connexes en temps linéaire} %\begin{lemme} %Soit $G=(S,E)$ un graphe orienté. Chaque composante fortement connexe $C$ de $G$ contient un unique sommet n'ayant pas de père de la forêt d'un parcours en profondeur dans $C$ (soit il n'a pas de père, soit il en a un dans une autre composante fortement connexe). %Ce sommet est appelé racine de la composante $C$ et tous les autres sommets de $C$ sont des descendants de celui-ci dans la forêt du parcours en profondeur. %\end{lemme} %Illustrons ce phénomène sur l'exemple suivant : \begin{center} \includegraphics[width=0.6\textwidth]{cfc_ex} \end{center} Faisons un pp en suivant l'ordre alphabétique puis en suivant l'inverse de l'ordre alphabétique. Que remarque-t-on ? Nous venons de mettre en évidence l'idée principale de l'algorithme de Kosaraju : on fait un parcours en profondeur du graphe en prenant un ordre bien choisi sur les sommets pour garantir que chaque appel par la fonction \verb+pp+ à la fonction \verb+pp_rec+ détermine une composante connexe puisque les sommets accessibles depuis le sommet qui fait le premier appel sont exactement toute sa composante fortement connexe (\textbf{et rien de plus}). Il suffit donc de choisir à chaque fois un sommet dont la composante fortement connexe est un puit c'est-à-dire dont aucune arête ne sort. On obtient alors l'algorithme suivant : \begin{verbatim} CFC(g): num=0; tant que g n'est pas vide : C initialisée à vide choisir un sommet s dans une composante puit appeler pp_rec(g,s) en l'adaptant pour que les sommets visités soient considérés dans la CFC num et insérés dans C num++ supprimer dans G tous les sommets de C et leurs arêtes \end{verbatim} Une chose reste très floue ici : comment déterminer un sommet dans une composante fortement connexe puit ? Ce n'est pas si simple. \begin{lemme} Soit $G=(S,A)$ un graphe orienté. Le sommet qui est traité en dernier par un parcours en profondeur est dans une composante fortement connexe source (cad dans laquelle aucune arête ne rentre). \end{lemme} \vspace{6,5cm} \begin{lemme} Soit $G=(S,A)$ un graphe orienté. Un sommet est dans une CFC source de $\bar{G}$ ssi il est dans une CFC puit de $G$. \end{lemme} On en déduit que \textbf{trouver un sommet dans une CFC puit est équivalent à considérer le dernier sommet traité dans un parcours en profondeur de $\bar{G}$}. \bigskip Ainsi, l'ordre sur les sommets que l'on va utiliser pour parcourir $G$ à la recherche des CFC est l'ordre inverse de la fin de traitement des sommets associée à un parcours en profondeur de $\bar{G}$. L'algorithme final a donc la forme suivante : \begin{enumerate} \item on calcule $\bar{G}$ et on fait un parcours en profondeur afin de calculer les dates de fin de traitement. \item on fait un parcours en profondeur de $G$ en suivant l'ordre inverse des dates de fin de traitement obtenues à l'étape précédente pour sélectionner un nouveau sommet pour lancer \verb+pp_rec+. \end{enumerate} \bigskip On remarque que plutôt que de calculer explicitement les dates de fin de traitement, il suffit de les empiler dans une pile quand on a finit de les traiter afin d'obtenir une pile qui contient les sommets dans l'ordre souhaité. \subsection{Graphe des CFC} Soit $G=(S,A)$ un graphe orienté. On peut définir son graphe des composantes connexes comme le graphe dont les sommets correspondent à chaque composante connexe de $G$ et on met une arête de $C$ vers $C'$ ssi il existe une arête $x \rightarrow y$ avec $x \in C$ et $y \in C'$. On remarque que ce graphe est acyclique (DAG) et que trouver l'ordre dans lequel déterminer les composantes est équivalent à faire un tri topologique sur ce DAG. On a d'ailleurs vu l'année dernière en TP qu'un graphe orienté était acyclique ssi on pouvait toujours trouver des sommets puits (de degré entrant nul), les éliminer avec leurs arêtes jusqu'à obtenir le graphe vide. Cette dernière remarque permet de garantir que l'algorithme de Kosaraju est bien correct car il existe à chaque étape une composante puit dans le graphe (un sommet puit dans le graphe des composantes fortement connexes) et celle-ci peut alors être reconstruite à partir de n'importe lequel de ses sommets, par exemple celui dont la date de fin de traitement est la plus grande. \subsection{Application au problème 2SAT} Considérons le problème 2SAT défini de la manière suivante : on prend en entrée $\varphi$ une formule sous forme normale conjonctive avec toutes ses clauses de taille 2 et on veut décider si elle est satisfiable ou non. On va montrer qu'il existe un algorithme linéaire qui permet de répondre à cette question. \begin{de} Soit $\varphi$ une formule en $2$-FNC sur l’ensemble de variables $\mathcal{V} = \{v_1, \ldots , v_n\}$. On définit le graphe d’implication de $\varphi$, noté $G_{\varphi}$, par $G_{\varphi} = (S,A)$ où : $S = \mathcal{V} \cup \{ \neg v : v \in \mathcal{V}\}$ : les sommets sont les littéraux. Si $\ell_1 \vee \ell_2$ est une clause de la formule alors on met une arête de $\neg \ell_1$ vers $\ell_2$ et une autre arête de $\neg \ell_2$ vers $\ell_1$. \end{de} Construire les graphes d’implication des formules : \begin{itemize} \item$ \Phi = (\neg y \vee \neg z) \wedge (\neg x \vee z) \wedge z \wedge (y \vee x) \wedge (\neg y \vee z)$ \item $\Psi = (\neg x \vee t) \wedge (x \vee \neg z) \wedge (y \vee \neg z) \wedge (x \vee z) \wedge (\neg y \vee \neg x) \wedge (\neg t \vee z)$. \end{itemize} \begin{thm} Si $G_{\varphi}$ admet un chemin de $\ell_1$ vers $\ell_2$ alors $\ell_1 \Rightarrow \ell2$ est conséquence syntaxique de $\varphi$. \end{thm} %\vspace{5cm} \begin{thm} $\varphi$ est satisfiable si et seulement si aucune composante fortement connexe de $G_{\varphi}$ ne contient à la fois une variable et sa négation. \end{thm} %\vspace{10cm} \section{Couplages dans un graphe biparti} \subsection{Le cas général} \begin{de} Soit $G = (S,A)$ un graphe non orienté. On appelle couplage de $G$ un sous-ensemble $C \subset A$ tel que pour tous $(a, b) \in C^2, a \cap b = \emptyset$, c’est-à-dire un sous-ensemble d’arêtes qui n’ont pas de sommets en commun. Un couplage $C$ est dit maximal si pour toute arête $a \notin C, C \cup \{a\}$ n’est pas un couplage. Un couplage $C$ est dit maximum si son cardinal est le maximum parmi tous les couplages de $G$. Si un sommet $s \in S$ apparaît dans l'une des arêtes de $C$, il est dit apparié pour $C$. Sinon, il est dit libre pour $C$. Un couplage $C$ est dit parfait s’il n’existe aucun sommet libre pour $C$. \end{de} Considérons l'exemple suivant : \begin{center} \includegraphics[width=0.3\textwidth]{ex_couplage.pdf} \end{center} \begin{thm} Un couplage maximum est un couplage maximal. \end{thm} \vspace{3cm} \newpage \begin{de} Soit $G=(S,A)$ un graphe non orienté et $C \subset A$ un couplage de $G$. On appelle : \begin{itemize} \item chemin alternant un chemin simple (élémentaire?) dont les arêtes sont alternativement dans $C$ et $A \setminus C$. \item chemin augmentant un chemin alternant qui commence et termine par des sommets libres. \end{itemize} \end{de} \vspace{2cm} \begin{thm} Soit $G=(S,A)$ un graphe non orienté et $C$ un couplage de $G$ alors $C$ est un couplage maximum de $G$ si et seulement s'il n'existe pas de chemin augmentant pour $C$. \end{thm} \vspace{10 cm} On en déduit l'algorithme suivant :\\ $C \leftarrow \emptyset$\\ tant qu'il existe un chemin augmentant pour $C$ : trouver $ca$ un chemin augmentant pour $C$. $C\leftarrow C \Delta ca$\\ Cet algorithme est incomplet puisque trouver un chemin augmentant n'a aucune raison d'être facile. \subsection{Graphes bipartis} \begin{de} Un graphe $G=(S,A)$ est dit biparti s'il existe une partition de ses sommets en deux ensembles $S_1$ et $S_2$ telle que les arêtes de $G$ ne sont qu'entre un sommet de $S_1$ et un sommet de $S_2$. \end{de} \begin{de} Soit $G=(S,A)$ un graphe biparti avec $S=S_1 \cup S_2$. Soit $C$ un couplage de $G$. On définit le graphe orienté associé à $C$ par $G_C=(S',A')$ où : \begin{itemize} \item $S'=S \cup \{s,t\}$ \item pour tout sommet $x \in S_1$ on met l'arête $(s,x)$ ssi $x$ est libre dans $C$. \item pour tout sommet $x \in S_2$ on met l'arête $(x,t)$ ssi $x$ est libre dans $C$. \item on oriente les arêtes de $A$ de la façon suivante : de $S_1$ vers $S_2$ pour les arêtes qui ne sont pas dans $C$ et de $S_2$ vers $S_1$ pour celles qui y sont. \end{itemize} \end{de} %Exemple : %\vspace{8cm} \begin{thm} Soit $G=(S,A)$ un graphe biparti, $C$ un couplage et $G_C$ le graphe orienté associé à $C$. $G$ possède un chemin augmentant pour $C$ ssi il existe un chemin de $s$ à $t$ dans $G_C$. S'il existe un tel chemin noté $(s,s_1,\ldots,s_k,t)$ alors $(s_1,\ldots,s_k)$ est un chemin augmentant pour $C$. \end{thm} \vspace{5cm} Conclusion : on peut trouver un chemin augmentant de $G$ en cherchant un chemin de $s$ à $t$ dans $G_C$ ce que l'on peut faire par exemple avec un parcours en largeur. On obtient alors un algorithme de recherche de couplage maximum de complexité $O(|A|.|S|)$. \section{Algorithme A*} Principe de l'algorithme : \begin{enumerate} \item Pour tout sommet x, on pose $dist(s,x)=+\infty$. \item On pose $dist(s,s)=0$. \item On insère tous les sommets $x$ dans la file de priorité avec $dist(s,x)$ comme priorité. \item Tant que la file n'est pas vide : \begin{enumerate} \item on défile le sommet de priorité minimale noté x. Si $x=t$ alors on renvoie $dist(s,t)$. \item Sinon, pour chacun de ses voisins y : si $dist(s,x)+p(x,y) \leq dist(s,y)$ alors $dist(s,y) \leftarrow dist(s,x)+p(x,y)$ et si $y$ est dans la file : on met à jour la priorité de $y$ dans la file par $dist(s,y)+h(y) $ sinon on insère $y$ dans la file avec priorité $dist(s,y)+h(y) $. \end{enumerate} \item Renvoyer $t$ non accessible. \end{enumerate} \bigskip Notations : on note $s$ le sommet d'origine de la recherche et $t$ la destination. Pour tout sommet $x$, on pose $d(s,x)$ le poids d'un chemin de poids minimal de $s$ à $x$ dans le graphe et $dist(s,x)$ la valeur estimée par l'algorithme à un moment donné. On note $h(x)$ la valeur de l'heuristique qui est une estimation à la baisse de $d(x,t)$. \bigskip Preuve de la correction de l'algorithme A* quand l'heuristique est admissible. \bigskip On commence par remarquer quelques propriétés immédiatement liées à l'algorithme. Les trois invariants suivants sont vérifiés : \begin{enumerate} \item $\forall x \in S, d(s,x) \leq dist(s,x)$. \item Tous les sommets qui sont dans la file de priorité ont une priorité qui vaut $dist(s,x) + h(x)$. \item Un sommet qui n'est plus dans la file de priorité a été défilé avec une priorité $dist(s,x)+h(x)$ car si sa distance est amenée à diminuer alors on le remet dans la file. \end{enumerate} \bigskip Montrons maintenant que l'algorithme A* calcule bien le poids d'un chemin de poids minimal $s$ à $t$ lorsque $h$ est admissible. \bigskip Notons $d$ la valeur renvoyée par l'algorithme. On a donc défilé $t$ avec une priorité qui vaut $d+h(t)=d$ ($h(t)=0$ car $h$ est admissible et $d(t,t)=0$). Supposons qu'il existe un chemin de poids minimal $ c : s \rightarrow v_1 \rightarrow \ldots \rightarrow v_n \rightarrow t$ de poids $d'