Grundy function on a graph.

1 files changed, 28 insertions, 2 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 18cfddc..fede523 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -32,6 +32,8 @@
 \newtheorem{scho}[comcnt]{Scholie}
 \renewcommand{\qedsymbol}{\smiley}
 %
+\newcommand{\mex}{\operatorname{mex}}
+%
 \DeclareUnicodeCharacter{00A0}{~}
 %
 \DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
@@ -923,7 +925,7 @@ 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.
+bien-fondée :
 
 \begin{defn}
 Soit $G$ un graphe orienté bien-fondé dans lequel chaque sommet n'a
@@ -938,7 +940,7 @@ 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$.
+rang bien-fondé) d'un sommet $x$.
 \end{defn}
 
 \thingy Autrement dit, un sommet de rang $0$ est un sommet terminal,
@@ -957,6 +959,30 @@ 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.
 
+Voici un autre exemple de 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
+$\gamma\colon G \to \mathbb{N}$ par $\gamma(x) = \mex\{\gamma(y) :
+y\in\mathrm{succ}(x)\}$ où, si $S\subseteq\mathbb{N}$, on note $\mex S
+:= \mathbb{N}\setminus S$ pour le plus petit entier naturel
+\emph{n'appartenant pas} à $S$ ; formellement, c'est-à-dire qu'on pose
+$\Phi(x, g) = \mex\{g(y) : y\in\mathrm{succ}(x)\}$ et qu'on appelle
+$\gamma$ la fonction telle que $\gamma(x) = \Phi(x,
+\gamma|_{\mathrm{succ}(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$.
+\end{defn}
+
+\thingy En particulier, un sommet de valeur de Grundy $0$ est un
+sommet qui n'a que des sommets de valeur de Grundy $>0$ comme
+successeurs (ceci inclut le cas particulier d'un sommet terminal),
+tandis qu'un sommet de valeur de Grundy $>0$ est un sommet ayant au
+moins un sommet de valeur de Grundy $0$ comme successeur.
+
 %
 %
 %