diff options
| -rw-r--r-- | notes-mitro206.tex | 133 |
1 files changed, 113 insertions, 20 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index 92db678..409e706 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -2457,7 +2457,7 @@ Un bonus au théorème \ref{positional-determinacy-of-perfect-information-games} est l'affirmation suivante : -\begin{prop} +\begin{prop}\label{p-d-n-vertices-of-perfect-information-games} Dans le contexte du théorème \ref{positional-determinacy-of-perfect-information-games}, si $N^*,P^*,D^*$ est une partition de $G$ en trois parties vérifiant les @@ -2520,7 +2520,7 @@ s'agit notamment de la théorie de l'induction bien-fondée (cf. \ref{scholion-well-founded-induction} et \ref{scholion-well-founded-definition}). -\subsection{Graphes orientés bien-fondés} +\subsection{Graphes orientés bien-fondés}\label{subsection-well-founded-graphs} \begin{defn}\label{definitions-graphs} Un \textbf{graphe orienté [simple]} est la donnée d'un ensemble $G$ et @@ -2549,7 +2549,8 @@ arête pour tout $i\in\mathbb{N}$ (i.e., aucun cycle ni chemin infini, cf. ci-dessous). \end{defn} -\thingy Il est évident que tout graphe bien-fondé est acyclique (s'il +\thingy\label{finite-graph-is-well-founded-iff-acyclic} 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 @@ -2750,19 +2751,21 @@ voisin sortant de $x$, dans la définition de $f(x)$. Voici un exemple d'application de la définition par induction bien-fondée : -\begin{defn} +\begin{defn}\label{definition-well-founded-rank} Soit $G$ un graphe orienté bien-fondé dans lequel chaque sommet n'a -qu'un nombre fini de voisins sortants. 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\outnb(x)\} + 1$ où il est convenu que $\max\varnothing = -1$ ; -formellement, c'est-à-dire qu'on pose $\Phi(x, r) = \max\{r(y) : -y\in\outnb(x)\} + 1$ avec $\Phi(x, r) = 0$ si $x$ est un puits, et -qu'on appelle $\rho$ la fonction telle que $\rho(x) = \Phi(x, -\rho|_{\outnb(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 $x$. +qu'un nombre fini de voisins sortants (par exemple, un graphe fini +acyclique). 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\outnb(x)\} + 1$ où il est convenu que +$\max\varnothing = -1$ ; formellement, c'est-à-dire qu'on pose +$\Phi(x, r) = \max\{r(y) : y\in\outnb(x)\} + 1$ avec $\Phi(x, r) = 0$ +si $x$ est un puits, et qu'on appelle $\rho$ la fonction telle que +$\rho(x) = \Phi(x, \rho|_{\outnb(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 $x$. (Voir +aussi \ref{ordinal-valued-rank-and-grundy-function} pour une +généralisation.) \end{defn} \thingy Autrement dit, un sommet de rang $0$ est un puits, @@ -2793,7 +2796,9 @@ $\gamma$ la fonction telle que $\gamma(x) = \Phi(x, \gamma|_{\outnb(x)})$ dont l'existence et l'unicité sont garanties par le théorème. Cette fonction $\gamma$ s'appelle la \textbf{fonction de Grundy} sur $G$, on dit que $\gamma(x)$ est la -valeur de Grundy d'un sommet $x$. +valeur de Grundy d'un sommet $x$. (Voir +aussi \ref{ordinal-valued-rank-and-grundy-function} pour une +généralisation.) \end{defn} \thingy En particulier, un sommet de valeur de Grundy $0$ est un @@ -2806,9 +2811,10 @@ On verra que la notion de fonction de Grundy, et particulièrement le fait que la valeur soit nulle ou pas, a énormément d'importance dans l'étude de la théorie des jeux impartiaux. On verra aussi comment la définir sans l'hypothèse que chaque sommet n'a qu'un nombre fini de -voisins sortants (mais ce ne sera pas forcément un entier naturel). -En attendant, peut se passer de cette hypothèse pour définir isolément -l'ensemble des sommets de valeur de Grundy $0$ : +voisins sortants (mais ce ne sera pas forcément un entier naturel : +cf. \ref{ordinal-valued-rank-and-grundy-function}). En attendant, +peut se passer de cette hypothèse pour définir isolément l'ensemble +des sommets de valeur de Grundy $0$ : \begin{defn}\label{definition-grundy-kernel} Soit $G$ un graphe orienté bien-fondé. En utilisant le @@ -2836,6 +2842,53 @@ que les N-sommets sont celles à partir desquelles le joueur suivant (`N' comme « Next ») a une stratégie gagnante (consistant, justement, à jouer vers un P-sommet). +\thingy\label{ordinal-valued-rank-and-grundy-function} En anticipant +sur la notion d'ordinaux introduite dans la +section \ref{section-ordinals}, la fonction rang peut se généraliser à +n'importe quel graphe bien-fondé (sans hypothèse de nombre fini de +voisins sortants), à condition d'autoriser des valeurs ordinales +quelconques : précisément, on définit $\rho(x) = \sup\{\rho(y)+1 : +y\in\outnb(x)\}$ (avec cette fois $\sup\varnothing = 0$ pour garder +$\rho(x) = 0$ si $x$ est un puits) c'est-à-dire que $\rho(x)$ est le +plus petit ordinal strictement supérieur à $\rho(y)$ pour tout +$y\in\outnb(x)$. + +De même, la fonction de Grundy peut se généraliser à n'importe quel +graphe bien-fondé en définissant $\gamma(x) = \mex\{\gamma(y) : +y\in\outnb(x)\}$ où $\mex S$ désigne le plus petit ordinal +\emph{n'appartenant pas} à $S$. Il reste vrai que $\gamma(x)$ est nul +si et seulement si $x$ est un N-sommet. + +\thingy\label{well-founded-induction-algorithm} Lorsque $G$ est +\emph{fini} et bien-fondé, i.e., est un graphe fini acyclique +(cf. \ref{finite-graph-is-well-founded-iff-acyclic}), la fonction $f$ +définie par le théorème \ref{well-founded-definition} peut se calculer +algorithmiquement de la façon suivante : +\begin{itemize} +\item utiliser un algorithme de \textbf{tri topologique} (en ayant + inversé le sens des arêtes pour se ramener à la convention usuelle) + pour trouver une numérotation des sommets de $G$ telle que pour + toute arête $(x,y)$ de $G$ le sommet $y$ précède $x$ dans la + numérotation ; +\item parcourir tous les éléments $x\in G$ dans l'ordre de cette + numérotation, et définir $f(x) = \Phi(x, f|_{\outnb(x)})$, qui aura + toujours un sens car tous les éléments de $\outnb(x)$ auront été + parcourus avant $x$. +\end{itemize} +Si le tri topologique a été effectué par parcours en largeur, il est +compatible avec la fonction rang (et inversement, tout tri raffinant +la fonction rang est un tri topologique et peut s'obtenir par parcours +en largeur). La notion de rang ordinal +(cf. \ref{ordinal-valued-rank-and-grundy-function}) est donc une forme +de généralisation transfinie du tri topologique. + +Un algorithme évitant le tri topologique, au prix d'une plus grande +complexité, mais ayant le bénéfice de fonctionner dans une situation +plus générale (graphes non nécessairement bien-fondés/acycliques), +sera exposé dans la section suivante +(cf. \ref{non-well-founded-induction-algorithm}). + + \subsection{Généralisations aux graphes non nécessairement bien-fondés} @@ -3061,6 +3114,46 @@ $f_\alpha \subseteq h$ alors $f_{\alpha+1} = \Psi(f_\alpha) \subseteq est bien le plus petit $f$ tel que $\Psi(f) = f$. \end{proof} +\thingy\label{non-well-founded-induction-algorithm} Lorsque $G$ est +\emph{fini}, la fonction $f$ définie par le +théorème \ref{non-well-founded-definition} (et \textit{a fortiori} par +le théorème \ref{well-founded-definition}) peut se calculer +algorithmiquement de la façon suivante : +\begin{itemize} +\item initialement, poser $f(x) = \mathtt{undefined}$ pour tout $x\in + G$ ; +\item parcourir tous les éléments $x\in G$ et, si $f(y)$ est défini + pour suffisamment de voisins sortants $y$ de $x$ pour imposer + $f(x)$, autrement dit, si $\Phi(x, f|_{\outnb(x)})$ est défini, + alors définir $f(x)$ à cette valeur (noter qu'elle ne changera + jamais ensuite du fait de la cohérence de $\Phi$) ; et +\item répéter l'opération précédente jusqu'à ce que $f$ ne change + plus. +\end{itemize} +La démonstration donnée avec les ordinaux correspond exactement à cet +algorithme, à ceci près que « répéter l'opération » devra peut-être se +faire de façon transfinie. + +\thingy Les différentes définitions par induction bien-fondée +proposées en exemple dans la +section \ref{subsection-well-founded-graphs}, c'est-à-dire la notion +de rang bien-fondé (cf. \ref{definition-well-founded-rank}), de +fonction de Grundy (cf. \ref{definition-grundy-function}) et de +P-sommets et N-sommets (cf. \ref{definition-grundy-kernel}), et même +la généralisation ordinale des deux premiers +(cf. \ref{ordinal-valued-rank-and-grundy-function}), peuvent se +généraliser à des graphes non nécessairement bien-fondés en utilisant +le théorème \ref{non-well-founded-definition} : il faudra juste +admettre que ce soient des fonctions \emph{partielles}, non définies +sur certains sommets (voire, tous les sommets) qui ne sont pas dans la +partie bien-fondée du graphe (cf. \ref{definition-wfpart}). +Néanmoins, ces définitions ne présentent qu'un intérêt limité : le +rang bien-fondé, par exemple, s'avère être défini exactement sur la +partie bien-fondée de $G$ (vérification facile) et coïncider avec le +rang bien-fondé sur ce sous-graphe, et pour ce qui est des P-sommets +et N-sommets, on obtient exactement la fonction évoquée +en \ref{p-d-n-vertices-of-perfect-information-games}. + \subsection{Écrasement transitif} @@ -3180,7 +3273,7 @@ $G/\equiv$, on a bien $f(x) = f(x')$ ssi $x\equiv x'$). % % -\section{Introduction aux ordinaux} +\section{Introduction aux ordinaux}\label{section-ordinals} \subsection{Présentation informelle} |