summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--notes-mitro206.tex70
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)})
\]