summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex30
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.
+
%
%
%