More re-reading.

1 files changed, 39 insertions, 31 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index dc53cfb..41b3176 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -35,6 +35,7 @@
 \newcommand{\outnb}{\operatorname{outnb}}
 \newcommand{\downstr}{\operatorname{downstr}}
 \newcommand{\mex}{\operatorname{mex}}
+\newcommand{\limp}{\Longrightarrow}
 %
 \DeclareUnicodeCharacter{00A0}{~}
 %
@@ -798,7 +799,7 @@ Un \textbf{graphe orienté [simple]} est la donnée d'un ensemble $G$ et
 d'une partie $E$ de $G^2$ ne rencontrant pas la diagonale (i.e., un
 ensemble de couples $(x,y)$ avec $x\neq y$) : si on préfère, il s'agit
 d'un ensemble $G$ muni d'une relation $E$ irreflexive.  Les éléments
-de $G$ s'appelle \textbf{sommets} et les éléments de $E$
+de $G$ s'appellent \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
@@ -815,7 +816,8 @@ i\leq n-1$, où on convient que $x_n = x_0$.
 
 Un graphe orienté (possiblement infini) est dit \textbf{bien-fondé}
 lorsqu'il n'existe pas de suite $x_0,x_1,x_2,\ldots$ de sommets telle
-que $(x_i,x_{i+1})$ soit une arête pour tout $i\in\mathbb{N}$.
+que $(x_i,x_{i+1})$ soit une arête pour tout $i\in\mathbb{N}$ (i.e.,
+aucun cycle ni chemin infini, cf. ci-dessous).
 \end{defn}
 
 \thingy Il est évident que tout graphe bien-fondé est acyclique (s'il
@@ -833,45 +835,51 @@ celui de $\mathbb{N}$ dans lequel on fait pointer une arête de $i$
 Si $G$ est un graphe orienté on appelle \textbf{relation
   d'accessibilité} la clôture réflexive-transitive de la relation
 donnée par les arêtes de $G$ : autrement dit, on dit que $y$ est
-accessible à partir de $x$ lorsqu'il existe $x =
-x_0,x_1,\ldots,x_{n-1},x_n = y$ tels que pour chaque $i$ le sommet
-$x_{i+1}$ soit atteint par une arête de source $x_i$ (on autorise
-$n=0$, c'est-à-dire que chaque sommet est toujours accessible à partir
-de lui-même).
+accessible à partir de $x$ lorsqu'il existe $x {=}
+x_0,x_1,\ldots,x_{n-1},x_n {=} y$ tels que pour chaque $i$ le sommet
+$x_{i+1}$ soit voisin sortant de $x_i$ (on autorise $n=0$,
+c'est-à-dire que chaque sommet est toujours accessible à partir de
+lui-même).
 
 L'ensemble des sommets accessibles à partir d'un sommet $x$
-s'appellera aussi l'\textbf{aval} de $x$.  On peut considérer l'aval
-de $x$ comme un sous-graphe induit de $G$ (c'est-à-dire, considérer le
-graphe dont l'ensemble des sommets est l'aval de $x$ et dont les
-arêtes sont celles qui partent d'un tel sommet).  On remarquera la
-convention faite que $x$ appartient à son propre aval.
+s'appellera aussi l'\textbf{aval} de $x$ et pourra se noter
+$\downstr(x)$ (c'est donc la plus petite partie $P$ de $G$ telle que
+$x\in P$ et $y\in P \limp \outnb(y)\subseteq P$,
+cf. \ref{definition-downstream-closed-inductive}).  On peut considérer
+l'aval de $x$ comme un sous-graphe induit de $G$ (c'est-à-dire,
+considérer le graphe dont l'ensemble des sommets est l'aval de $x$ et
+dont les arêtes sont celles qui partent d'un tel sommet).  On
+remarquera la convention faite que $x$ appartient à son propre aval.
 \end{defn}
 
 \thingy On peut remarquer que la relation d'accessibilité sur $G$ est
 antisymétrique (i.e., est une relation d'ordre partiel) si et
 seulement si $G$ est acyclique.  Lorsque $G$ est bien-fondé, la
-relation d'accessibilité est elle-même bien-fondée (i.e., le graphe
-qu'elle définit est bien-fondé).
+relation d'accessibilité est elle-même bien-fondée (au sens où le
+graphe qu'elle définit est bien-fondé).
 
 \begin{defn}\label{definition-downstream-closed-inductive}
 Si $G$ est un graphe orienté, on dira qu'un ensemble $P$ de sommets de
 $G$ est \textbf{aval-clos} lorsqu'il vérifie la propriété suivante :
 « si $x$ est dans $P$ alors tout voisin sortant de $x$ est dans $P$ »
-(ou de façon équivalente, « tout sommet accessible à partir d'un
-  sommet de $P$ est encore dans $P$ »).
-
-Réciproquement, on dira qu'un ensemble $P$ de sommets de $G$
-est \textbf{aval-inductif} lorsqu'il vérifie la propriété suivante :
-« si $x \in G$ est tel que tout voisin sortant de $x$ appartient
-  à $P$, alors $x$ lui-même appartient à $P$ » (i.e. « $P$ contient
-  tout sommet dont tous les voisins sortants sont dans $P$ »).
+(soit $x\in P \limp \outnb(x)\subseteq P$ ; ou de façon équivalente,
+« tout sommet accessible à partir d'un sommet de $P$ est encore
+  dans $P$ »,).
+
+Réciproquement, on dira qu'un ensemble $P$ de sommets de $G$ est
+\textbf{aval-inductif} lorsqu'il vérifie la propriété suivante : « si
+  $x \in G$ est tel que tout voisin sortant de $x$ appartient à $P$,
+  alors $x$ lui-même appartient à $P$ » (i.e. « $P$ contient tout
+  sommet dont tous les voisins sortants sont dans $P$ »,
+soit $\outnb(x)\subseteq P \limp x\in P$).
 \end{defn}
 
 \thingy\label{trivial-remark-downstream} Il est clair qu'une
 intersection ou réunion quelconque d'ensembles aval-clos est encore
 aval-close.  L'aval de $x$ (ensemble des sommets accessibles
-depuis $x$) est toujours aval-clos, et il est facile de se convaincre
-qu'un ensemble de sommets est aval-clos si et seulement si il est une
+depuis $x$) est toujours aval-clos, c'est même la plus petite partie
+aval-close contenant $x$, et il est facile de se convaincre qu'un
+ensemble de sommets est aval-clos si et seulement si il est une
 réunion d'avals.
 
 Pour ce qui est des ensembles aval-inductifs, il est clair qu'une
@@ -1004,9 +1012,9 @@ 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$ ;
+y\in\outnb(x)\} + 1$ où il 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
+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
@@ -1169,11 +1177,11 @@ Appelons $\mathscr{F}$ l'ensemble des couples $(x,f)$ où $x\in G$ et
 $f$ une fonction \emph{partielle} de l'ensemble des voisins sortants
 de $x$ vers $Z$ (autrement dit, $\mathscr{F}$ est $\bigcup_{x \in G}
 \bigcup_{D \subseteq \outnb(x)} \big(\{x\}\times Z^D\big)$).  Soit
-enfin $\Phi\colon \mathscr{F} \dasharrow Z$ une fonction cohérente en
-la deuxième variable, c'est-à-dire telle que $\Phi(x,f) = \Phi(x,g)$
-dès que $f \supseteq g$.  Alors il existe une plus petite (au sens du
-prolongement) fonction partielle $f\colon G \dasharrow Z$ telle que
-pour tout $x \in G$ on ait
+enfin $\Phi\colon \mathscr{F} \dasharrow Z$ une fonction partielle
+cohérente en la deuxième variable, c'est-à-dire telle que $\Phi(x,f) =
+\Phi(x,g)$ dès que $f \supseteq g$.  Alors il existe une plus petite
+(au sens du prolongement) fonction partielle $f\colon G \dasharrow Z$
+telle que pour tout $x \in G$ on ait
 \[
 f(x) = \Phi(x,\, f|_{\outnb(x)})
 \]