From 08010a79383ce8b007171e275eb3bc29b968a81e Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Fri, 4 Dec 2015 16:42:43 +0100 Subject: Well-founded graphs and well-founded induction. --- notes-mitro206.tex | 206 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 206 insertions(+) diff --git a/notes-mitro206.tex b/notes-mitro206.tex index 183307a..18cfddc 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -29,6 +29,7 @@ \newtheorem{lem}[comcnt]{Lemme} \newtheorem{thm}[comcnt]{Théorème} \newtheorem{cor}[comcnt]{Corollaire} +\newtheorem{scho}[comcnt]{Scholie} \renewcommand{\qedsymbol}{\smiley} % \DeclareUnicodeCharacter{00A0}{~} @@ -751,6 +752,211 @@ Avec les hypothèses et notations du corollaire, l'ensemble des $x$ tels que $u(x,y)\geq 0$ pour tout $y\in C$ est un convexe compact $C_0 \neq \varnothing$ inclus dans $C$. + +% +% +% + +\section{Théorie combinatoire des jeux impartiaux} + +\subsection{Graphes orientés bien-fondés} + +\begin{defn} +Un \textbf{graphe orienté [simple]} est la donnée d'un ensemble $G$ et +d'une partie $E$ de $G^2$ ne rencontrant pas la diagonale (i.e., un +ensemble de couples $(x,y)$ avec $x\neq y$) : si on préfère, il s'agit +d'un ensemble $G$ muni d'une relation $E$ irreflexive. Les éléments +de $G$ s'appelle \textbf{sommets} et les éléments de $E$ +\textbf{arêtes} de $G$, et si $(x,y) \in E$, on dit qu'il y a une +arête allant du sommet $x$ au sommet $y$, ou arête de source $x$ et de +cible $y$, ou encore que $y$ est \textbf{atteint} par une arête de +source $x$, ou encore que $y$ est un \textbf{successeur} de $x$. Un +sommet qui n'a pas de successeur est dit \textbf{terminal} dans $G$. + +Un tel graphe est dit \textbf{fini} lorsque $G$ est fini (il est clair +que $E$ l'est alors aussi). Il est dit \textbf{acyclique} lorsqu'il +n'existe pas de suite finie (« cycle ») $x_0,\ldots,x_{n-1}$ de +sommets telle que $(x_i,x_{i+1})$ soit une arête pour chaque $0\leq +i\leq n-1$, où on convient que $x_n = x_0$. + +Un graphe orienté (possiblement infini) est dit \textbf{bien-fondé} +lorsqu'il n'existe pas de suite $x_0,x_1,x_2,\ldots$ de sommets telle +que $(x_i,x_{i+1})$ soit une arête pour tout $i\in\mathbb{N}$. +\end{defn} + +\thingy Il est évident que tout graphe bien-fondé est acyclique (s'il +existe un cycle $x_0,\ldots,x_{n-1}$, on en déduit une suite infinie +en posant $x_i = x_{i\mod n}$) ; pour un graphe \emph{fini}, la +réciproque est vraie : en effet, s'il existe une suite infinie +$x_0,x_1,x_2,\ldots$ avec une arête de $x_i$ à $x_{i+1}$ pour +chaque $i$, il doit exister $n$ tel que $x_n = x_0$, et on obtient +alors un cycle $x_0,\ldots,x_{n-1}$. En général, cependant, les +notions sont distinctes, l'exemple le plus évident étant sans doute +celui de $\mathbb{N}$ dans lequel on fait pointer une arête de $i$ +à $i+1$ pour chaque $i$. + +\begin{defn} +Si $G$ est un graphe orienté on appelle \textbf{relation + d'accessibilité} la clôture réflexive-transitive de la relation +donnée par les arêtes de $G$ : autrement dit, on dit que $y$ est +accessible à partir de $x$ lorsqu'il existe $x = +x_0,x_1,\ldots,x_{n-1},x_n = y$ tels que pour chaque $i$ le sommet +$x_{i+1}$ soit atteint par une arête de source $x_i$ (on autorise +$n=0$, c'est-à-dire que chaque sommet est toujours accessible à partir +de lui-même). + +L'ensemble des sommets accessibles à partir d'un sommet $x$ +s'appellera aussi l'\textbf{aval} de $x$. On peut considérer l'aval +de $x$ comme un sous-graphe induit de $G$ (c'est-à-dire, considérer le +graphe dont l'ensemble des sommets est l'aval de $x$ et dont les +arêtes sont celles qui partent d'un tel sommet). + +L'ensemble des sommets d'un graphe orienté dont l'aval est bien-fondé, +autrement dit, l'ensemble des sommets $x$ tels qu'il n'existe pas de +suite $x_0,x_1,x_2,\ldots$ de sommets où $x_0 = x$ et où pour +chaque $i$ le sommet $x_{i+1}$ est atteint par une arête de +source $x_i$, est appelé la \textbf{partie bien-fondée} du graphe. +\end{defn} + +\begin{prop}[induction bien-fondée]\label{well-founded-induction} +Pour un graphe orienté $G$, les affirmations suivantes sont +équivalentes : + +\begin{itemize} +\item[(*)]$G$ est bien-fondé. +\item[(\dag)]Tout ensemble \emph{non vide} $N$ de sommets de $G$ + contient un sommet $x \in N$ qui est terminal pour $N$, + c'est-à-dire qu'il n'existe aucune arête $(x,y)$ de $G$ avec $y \in + N$ (i.e., aucun successeur de $x$ n'appartient à $N$). +\item[(\ddag)]Si une partie $P\subseteq G$ vérifie la propriété + suivante « lorsque $x \in G$ est tel que tout successeur de $x$ + appartient à $P$, alors $x$ lui-même appartient à $P$ », alors $P + = G$. +\end{itemize} +\end{prop} +\begin{proof} +L'équivalence entre (\dag) et (\ddag) est complètement formelle : elle +s'obtient en posant $P = G\setminus N$ ou réciproquement $N = +G\setminus P$, en passant à la contraposée, et en passant aussi à la +contraposée à l'intérieur de la propriété entre guillemets +dans (\ddag), et encore une fois dans la prémisse de cette propriété +(« tout successeur de $x$ appartient à $P$ » équivaut à « aucun + successeur de $x$ n'appartient à $N$ », i.e., « $x$ est terminal + pour $N$ »). + +Pour montrer que (\dag) implique (*), il suffit d'appliquer (\dag) à +l'ensemble $N := \{x_0,x_1,x_2,\ldots\}$ des sommets d'une suite telle +qu'il y ait une arête de $x_i$ à $x_{i+1}$. + +Pour montrer que (*) implique (\dag), on suppose que $N$ est un +ensemble non-vide de sommets sans sommet terminal : comme $N$ est +non-vide, on choisit $x_0 \in N$, et comme $x_0$ n'est pas terminal on +peut choisir $x_1 \in N$ atteignable à partir de $x_0$ par une arête, +puis $x_2 \in N$ atteignable à partir de $x_1$ et ainsi de suite — par +récurrence (et par l'axiome du choix [dépendants]), on construit ainsi +une suite $(x_i)$ de sommets telle qu'il y ait une arête de $x_i$ +à $x_{i+1}$. +\end{proof} + +La définition (*) choisie pour un graphe bien-fondé est la plus +compréhensible, mais en un certain sens la définition (\ddag) est « la + bonne » (en l'absence de l'axiome du choix, il faut utiliser (\dag) +ou (\ddag), et en mathématiques constructives il faut +utiliser (\ddag)). + +\begin{prop} +Si $G$ est un graphe orienté non supposé bien-fondé, la partie +bien-fondée de $G$ est la plus petite (pour l'inclusion) partie $P$ +vérifiant la propriété « lorsque $x \in G$ est tel que tout successeur + de $x$ appartient à $P$, alors $x$ lui-même appartient à $P$ » +(i.e., la propriété entre guillemets dans (\ddag) +de \ref{well-founded-induction}). +\end{prop} +\begin{proof} +Il est clair que la partie bien-fondée $Q$ de $G$ vérifie cette +propriété. Maintenant, si $P$ vérifie la propriété en question, alors +$P \cap Q$ la vérifie aussi, ce qui montre bien que $Q$ est la plus +petite. +\end{proof} + +\begin{thm}[définition par induction bien-fondée]\label{well-founded-definition} +Soit $G$ un graphe orienté bien-fondé et $Z$ un ensemble quelconque. +Notons $\mathrm{succ}(x) = \{y : (x,y) \in E\}$ l'ensemble des +successeurs d'un sommet $x$ de $G$ (i.e., des $y$ atteints par une +arête de source $x$). + +Appelons $\mathscr{F}$ l'ensemble des couples $(x,f)$ où $x\in G$ et +$f$ une fonction de l'ensemble des successeurs de $x$ vers $Z$ +(autrement dit, $\mathscr{F}$ est $\bigcup_{x \in G} \big(\{x\}\times +Z^{\mathrm{succ}(x)}\big)$). Soit enfin $\Phi\colon \mathscr{F} \to Z$ +une fonction quelconque. Alors il existe une unique fonction $f\colon +G \to Z$ telle que pour tout $x \in G$ on ait +\[ +f(x) = \Phi(x,\, f|_{\mathrm{succ}(x)}) +\] +\end{thm} +\begin{proof} +Montrons d'abord l'unicité : si $f$ et $f'$ vérifient toutes les deux +la propriété anoncée, soit $P$ l'ensemble des sommets $x$ de $G$ tels +que $f(x) = f'(x)$. Si $x \in G$ est tel que $\mathrm{succ}(x) +\subseteq P$, c'est-à-dire que $f|_{\mathrm{succ}(x)} = +f'|_{\mathrm{succ}(x)}$, alors $f(x) = \Phi(x,\, +f|_{\mathrm{succ}(x)}) = \Phi(x,\, f'|_{\mathrm{succ}(x)}) = f'(x)$, +autrement dit, $x\in P$. La phrase précédente affirme précisément que +$P$ vérifie la propriété entre guillemets dans (\ddag) +de \ref{well-founded-induction}, et d'après la proposition en +question, on a donc $P = G$, c'est-à-dire $f = f'$. Ceci montre +l'unicité. + +\textcolor{red}{Existence...} +\end{proof} + +Ce théorème est difficile à lire. En voici une traduction +informelle : + +\begin{scho} +Pour définir une fonction $f$ sur un graphe bien-fondé, on peut +supposer, lorsqu'on définit $f(x)$, que $f$ est déjà défini (i.e., +connu) sur tous les sommets successeurs de $x$ : autrement dit, on +peut librement utiliser la valeur de $f(y)$ sur chaque sommet $y$ +successeur de $x$, dans la définition de $f(x)$. +\end{scho} + +Voici un exemple d'application de la définition par induction +bien-fondée. + +\begin{defn} +Soit $G$ un graphe orienté bien-fondé dans lequel chaque sommet n'a +qu'un nombre fini de successeurs. En utilisant le +théorème \ref{well-founded-definition}, on définit alors une fonction +$\rho\colon G \to \mathbb{N}$ par $\rho(x) = \max\{\rho(y) : +y\in\mathrm{succ}(x)\} + 1$ où $\mathrm{succ}(x)$ désigne l'ensemble +des successeurs de $x$ et où on est convenu que $\max\varnothing = +-1$ ; formellement, c'est-à-dire qu'on pose $\Phi(x, r) = \max\{r(y) : +y\in\mathrm{succ}(x)\} + 1$ (avec $\Phi(x, r) = 0$ si $x$ est terminal +dans $G$) et qu'on appelle $\rho$ la fonction telle que $\rho(x) = +\Phi(x, \rho|_{\mathrm{succ}(x)})$ dont l'existence et l'unicité sont +garanties par le théorème. Cette fonction $\rho$ s'appelle la +\textbf{fonction rang} sur $G$, on dit que $\rho(x)$ est le rang (ou +rang bien-fondé) d'un sommet $G$. +\end{defn} + +\thingy Autrement dit, un sommet de rang $0$ est un sommet terminal, +un sommet de rang $1$ est un sommet non-terminal dont tous les +successeurs sont terminaux, un sommet de rang $2$ est un sommet dont +tous les successeurs sont de rang $\leq 1$ mais et au moins un est de +rang exactement $1$, et ainsi de suite. + +Il revient au même de définir le rang de la manière suivante : le rang +$\rho(x)$ d'un sommet $x$ d'un graphe orienté bien-fondé est le plus +grand $n$ tel qu'il existe une suite $x_0,x_1,\ldots,x_n$ telle que +$x_0 = x$ et que pour chaque $i$ le sommet $x_{i+1}$ soit atteint par +une arête de source $x_i$. + +Pour un graphe non supposé bien-fondé, on peut définir son rang comme +on vient de le dire sur sa partie bien-fondée, et poser $\rho(x) = +\infty$ lorsque $x$ n'appartient pas à la partie bien-fondée. + % % % -- cgit v1.2.3