Terminology: use "sink" rather than "terminal (vertex)".

1 files changed, 34 insertions, 35 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index ca284a0..7c1f585 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -773,10 +773,10 @@ 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{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$.
+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
+appelé \textbf{puits} dans $G$.
 
 Un tel graphe est dit \textbf{fini} lorsque $G$ est fini (il est clair
 que $E$ l'est alors aussi).  Il est dit \textbf{acyclique} lorsqu'il
@@ -835,7 +835,7 @@ Pour un graphe orienté $G$, les affirmations suivantes sont
 \begin{itemize}
 \item[(*)]$G$ est bien-fondé.
 \item[(\dag)]Tout ensemble \emph{non vide} $N$ de sommets de $G$
-  contient un sommet $x \in N$ qui est terminal pour $N$,
+  contient un sommet $x \in N$ qui est un puits pour $N$,
   c'est-à-dire qu'il n'existe aucune arête $(x,y)$ de $G$ avec $y \in
   N$ (i.e., aucun voisin sortant de $x$ n'appartient à $N$).
 \item[(\ddag)]Si une partie $P\subseteq G$ vérifie la propriété
@@ -851,21 +851,21 @@ 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 voisin sortant de $x$ appartient à $P$ » équivaut à « aucun
-  voisin sortant de $x$ n'appartient à $N$ », i.e., « $x$ est terminal
-  pour $N$ »).
+voisin sortant de $x$ n'appartient à $N$ », i.e., « $x$ est un puits
+pour $N$ »).
 
 Pour montrer que (\dag) implique (*), il suffit d'appliquer (\dag) à
 l'ensemble $N := \{x_0,x_1,x_2,\ldots\}$ des sommets d'une suite telle
 qu'il y ait une arête de $x_i$ à $x_{i+1}$.
 
 Pour montrer que (*) implique (\dag), on suppose que $N$ est un
-ensemble non-vide de sommets sans sommet terminal : comme $N$ est
-non-vide, on choisit $x_0 \in N$, et comme $x_0$ n'est pas terminal on
-peut choisir $x_1 \in N$ atteignable à partir de $x_0$ par une arête,
-puis $x_2 \in N$ atteignable à partir de $x_1$ et ainsi de suite — par
-récurrence (et par l'axiome du choix [dépendants]), on construit ainsi
-une suite $(x_i)$ de sommets telle qu'il y ait une arête de $x_i$
-à $x_{i+1}$.
+ensemble non-vide de sommets sans puits [i.e., puits pour $N$] : comme
+$N$ est non-vide, on choisit $x_0 \in N$, et comme $x_0$ n'est pas un
+puits on peut choisir $x_1 \in N$ atteignable à partir de $x_0$ par
+une arête, puis $x_2 \in N$ atteignable à partir de $x_1$ et ainsi de
+suite — par récurrence (et par l'axiome du choix [dépendants]), on
+construit ainsi une suite $(x_i)$ de sommets telle qu'il y ait une
+arête de $x_i$ à $x_{i+1}$.
 \end{proof}
 
 La définition (*) choisie pour un graphe bien-fondé est la plus
@@ -940,18 +940,18 @@ 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ù on 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 terminal
-dans $G$) 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$.
+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\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$.
 \end{defn}
 
-\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
+\thingy Autrement dit, un sommet de rang $0$ est un puits,
+un sommet de rang $1$ est un sommet non-puits dont tous les
 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.
@@ -985,10 +985,10 @@ 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
-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 voisin sortant.
+sommet qui n'a que des sommets de valeur de Grundy $>0$ comme voisins
+sortants (ceci inclut le cas particulier d'un puits), tandis qu'un
+sommet de valeur de Grundy $>0$ est un sommet ayant au 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
@@ -1006,13 +1006,12 @@ autre que l'écrasement transitif de l'aval de $x$ vu comme un graphe
 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 voisins sortants que des
-sommets terminaux a pour écrasement $\{\varnothing\}$, un sommet qui
-n'a pour voisins sortants que de tels sommets a pour écrasement
-$\{\{\varnothing\}\}$ tandis que s'il a aussi des sommets terminaux
-pour voisins sortants ce sera $\{\varnothing,\penalty0 \{\varnothing\}\}$,
-et ainsi de suite.
+\thingy En particulier, un puits a pour écrasement $\varnothing$, un
+sommet qui n'a pour voisins sortants que des sommets terminaux a pour
+écrasement $\{\varnothing\}$, un sommet qui n'a pour voisins sortants
+que de tels sommets a pour écrasement $\{\{\varnothing\}\}$ tandis que
+s'il a aussi des sommets terminaux 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
 qu'on ne peut pas donner \textit{a priori} un ensemble $Z$ dans lequel