summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2015-12-05 10:36:42 +0100
committerDavid A. Madore <david+git@madore.org>2015-12-05 10:36:42 +0100
commit054c3fa24ea18125e13196544b55737edb87a7af (patch)
treeb28b0b863a6e2a52af9c21c33c0e833ddddd04d2 /notes-mitro206.tex
parent611ffd45dfa0a7da2f81d686071b5c16e6f803c1 (diff)
downloadmitro206-054c3fa24ea18125e13196544b55737edb87a7af.tar.gz
mitro206-054c3fa24ea18125e13196544b55737edb87a7af.tar.bz2
mitro206-054c3fa24ea18125e13196544b55737edb87a7af.zip
Terminology: use "out-neighbor" rather than "successor".
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex80
1 files changed, 40 insertions, 40 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index d5a07cf..ca284a0 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -32,7 +32,7 @@
\newtheorem{scho}[comcnt]{Scholie}
\renewcommand{\qedsymbol}{\smiley}
%
-\newcommand{\succr}{\operatorname{succ}}
+\newcommand{\outnb}{\operatorname{outnb}}
\newcommand{\mex}{\operatorname{mex}}
%
\DeclareUnicodeCharacter{00A0}{~}
@@ -773,9 +773,9 @@ 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$, et on
-notera $\succr(x) = \{y : (x,y) \in E\}$ l'ensemble des successeurs
-de $x$. Un sommet qui n'a pas de successeur est dit \textbf{terminal}
+source $x$, ou encore que $y$ est un \textbf{voisin sortant} de $x$, et on
+notera $\outnb(x) = \{y : (x,y) \in E\}$ l'ensemble des voisins sortants
+de $x$. Un sommet qui n'a pas de voisin sortant est dit \textbf{terminal}
dans $G$.
Un tel graphe est dit \textbf{fini} lorsque $G$ est fini (il est clair
@@ -837,9 +837,9 @@ Pour un graphe orienté $G$, les affirmations suivantes sont
\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$).
+ N$ (i.e., aucun voisin sortant 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$
+ suivante « lorsque $x \in G$ est tel que tout voisin sortant de $x$
appartient à $P$, alors $x$ lui-même appartient à $P$ », alors $P
= G$.
\end{itemize}
@@ -850,8 +850,8 @@ 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
+(« tout voisin sortant de $x$ appartient à $P$ » équivaut à « aucun
+ voisin sortant de $x$ n'appartient à $N$ », i.e., « $x$ est terminal
pour $N$ »).
Pour montrer que (\dag) implique (*), il suffit d'appliquer (\dag) à
@@ -877,7 +877,7 @@ 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
+vérifiant la propriété « lorsque $x \in G$ est tel que tout voisin sortant
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}).
@@ -891,27 +891,27 @@ petite.
\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 $\succr(x) = \{y : (x,y) \in E\}$ l'ensemble des
-successeurs d'un sommet $x$ de $G$ (i.e., des $y$ atteints par une
+Notons $\outnb(x) = \{y : (x,y) \in E\}$ l'ensemble des
+voisins sortants 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$
+$f$ une fonction de l'ensemble des voisins sortants de $x$ vers $Z$
(autrement dit, $\mathscr{F}$ est $\bigcup_{x \in G} \big(\{x\}\times
-Z^{\succr(x)}\big)$). Soit enfin $\Phi\colon \mathscr{F} \to Z$
+Z^{\outnb(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|_{\succr(x)})
+f(x) = \Phi(x,\, f|_{\outnb(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 $\succr(x)
-\subseteq P$, c'est-à-dire que $f|_{\succr(x)} =
-f'|_{\succr(x)}$, alors $f(x) = \Phi(x,\,
-f|_{\succr(x)}) = \Phi(x,\, f'|_{\succr(x)}) = f'(x)$,
+que $f(x) = f'(x)$. Si $x \in G$ est tel que $\outnb(x)
+\subseteq P$, c'est-à-dire que $f|_{\outnb(x)} =
+f'|_{\outnb(x)}$, alors $f(x) = \Phi(x,\,
+f|_{\outnb(x)}) = \Phi(x,\, f'|_{\outnb(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
@@ -927,9 +927,9 @@ 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
+connu) sur tous les voisins sortants 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)$.
+voisin sortant de $x$, dans la définition de $f(x)$.
\end{scho}
Voici un exemple d'application de la définition par induction
@@ -937,14 +937,14 @@ 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
+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\succr(x)\} + 1$ où on est convenu que $\max\varnothing =
+y\in\outnb(x)\} + 1$ où on est convenu que $\max\varnothing =
-1$ ; formellement, c'est-à-dire qu'on pose $\Phi(x, r) = \max\{r(y) :
-y\in\succr(x)\} + 1$ (avec $\Phi(x, r) = 0$ si $x$ est terminal
+y\in\outnb(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|_{\succr(x)})$ dont l'existence et l'unicité sont
+\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$.
@@ -952,8 +952,8 @@ rang bien-fondé) d'un sommet $x$.
\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
+voisins sortants sont terminaux, un sommet de rang $2$ est un sommet dont
+tous les voisins sortants 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
@@ -970,15 +970,15 @@ 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
+qu'un nombre fini de voisins sortants. 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\succr(x)\}$ où, si $S\subseteq\mathbb{N}$, on note $\mex S
+y\in\outnb(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\succr(x)\}$ et qu'on appelle
+$\Phi(x, g) = \mex\{g(y) : y\in\outnb(x)\}$ et qu'on appelle
$\gamma$ la fonction telle que $\gamma(x) = \Phi(x,
-\gamma|_{\succr(x)})$ dont l'existence et l'unicité sont
+\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$.
@@ -986,9 +986,9 @@ valeur de Grundy d'un sommet $x$.
\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),
+voisins sortants (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.
+moins un sommet de valeur de Grundy $0$ comme voisin sortant.
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
@@ -998,7 +998,7 @@ l'étude de la théorie des jeux impartiaux.
Soit $G$ un graphe orienté bien-fondé. En utilisant le
théorème \ref{well-founded-definition} (modulo la remarque qui suit),
on définit alors une fonction $f$ sur $G$ par $f(x) = \{f(y) :
-y\in\succr(x)\}$. L'image de $G$ par la fonction $f$ (c'est-à-dire
+y\in\outnb(x)\}$. L'image de $G$ par la fonction $f$ (c'est-à-dire
l'ensemble des $f(x)$ pour $x\in G$) s'appelle l'\textbf{écrasement
transitif} ou \textbf{écrasement de Mostowski} de $G$, tandis que
$f$ s'appelle la fonction d'écrasement, et la valeur $f(x)$ (qui n'est
@@ -1007,11 +1007,11 @@ orienté) s'appelle l'écasement transitif du sommet $x$.
\end{defn}
\thingy En particulier, un sommet terminal a pour
-écrasement $\varnothing$, un sommet qui n'a pour successeurs que des
+écrasement $\varnothing$, un sommet qui n'a pour voisins sortants que des
sommets terminaux a pour écrasement $\{\varnothing\}$, un sommet qui
-n'a pour successeurs que de tels sommets a pour écrasement
+n'a pour voisins sortants que de tels sommets a pour écrasement
$\{\{\varnothing\}\}$ tandis que s'il a aussi des sommets terminaux
-pour successeurs ce sera $\{\varnothing,\penalty0 \{\varnothing\}\}$,
+pour voisins sortants ce sera $\{\varnothing,\penalty0 \{\varnothing\}\}$,
et ainsi de suite.
Il y a une subtilité ensembliste dans la définition ci-dessus, c'est
@@ -1020,12 +1020,12 @@ $f$ prend sa valeur : il faut en fait appliquer une généralisation
de \ref{well-founded-definition} où $Z$ est remplacé par l'univers de
tous les ensembles : nous ne rentrerons pas dans ces subtilités, et
admettrons qu'il existe bien une unique fonction $f$ sur $G$ qui
-vérifie $f(x) = \{f(y) : y\in\succr(x)\}$ pour chaque $x\in G$.
+vérifie $f(x) = \{f(y) : y\in\outnb(x)\}$ pour chaque $x\in G$.
\begin{defn}
Un graphe orienté $G$ est dit \textbf{extensionnel} lorsque deux
-sommets $x$ et $x'$ ayant le même ensemble de successeurs ($\succr(x)
-= \succr(x')$) sont égaux.
+sommets $x$ et $x'$ ayant le même ensemble de voisins sortants ($\outnb(x)
+= \outnb(x')$) sont égaux.
\end{defn}
\begin{prop}
@@ -1037,7 +1037,7 @@ en \ref{definition-transitive-collapse} est injective.
Supposons $G$ transitif et montrons par induction bien-fondée que $f$
est injective sur l'aval de tout sommet $x$. Soit $P$ l'ensemble des
$y$ tels que $f$ restreinte à l'aval de $y$ soit injective. Soit $x$
-un sommet dont tous les successeurs appartiennent à $P$ :
+un sommet dont tous les voisins sortants appartiennent à $P$ :
\textcolor{red}{à finir.}
\end{proof}