diff options
Diffstat (limited to 'notes-mitro206.tex')
| -rw-r--r-- | notes-mitro206.tex | 30 |
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. + % % % |