summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex102
1 files changed, 83 insertions, 19 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 7c1f585..b0b9779 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -33,6 +33,7 @@
\renewcommand{\qedsymbol}{\smiley}
%
\newcommand{\outnb}{\operatorname{outnb}}
+\newcommand{\downstr}{\operatorname{downstr}}
\newcommand{\mex}{\operatorname{mex}}
%
\DeclareUnicodeCharacter{00A0}{~}
@@ -823,10 +824,36 @@ chaque $i$ le sommet $x_{i+1}$ est atteint par une arête de
source $x_i$, est appelé la \textbf{partie bien-fondée} du graphe.
\end{defn}
-On peut remarquer que la relation d'accessibilité sur $G$ est
+\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. \textcolor{red}{Détailler + discuter
- si $G$ est bien-fondé.}
+seulement si $G$ est acyclique. Lorsque $G$ est bien-fondé, la
+relation d'accessibilité est elle-même bien-fondée.
+
+\begin{defn}
+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$ »
+(i.e. « 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 :
+« lorsque $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$ »).
+\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
+réunion d'avals.
+
+Pour ce qui est des ensembles aval-inductifs, il est clair qu'une
+intersection quelconque d'ensembles aval-inductifs est aval-inductive.
+Leur nature, au moins dans un graphe bien-fondé, va être précisée dans
+ce qui suit.
\begin{prop}[induction bien-fondée]\label{well-founded-induction}
Pour un graphe orienté $G$, les affirmations suivantes sont
@@ -840,19 +867,19 @@ Pour un graphe orienté $G$, les affirmations suivantes sont
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 voisin sortant de $x$
- appartient à $P$, alors $x$ lui-même appartient à $P$ », alors $P
- = G$.
+ appartient à $P$, alors $x$ lui-même appartient à $P$ » (i.e.,
+ « $P$ est aval-inductif »), alors $P = G$.
\end{itemize}
\end{prop}
\begin{proof}
L'équivalence entre (\dag) et (\ddag) est complètement formelle : elle
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 voisin sortant de $x$ appartient à $P$ » équivaut à « aucun
-voisin sortant de $x$ n'appartient à $N$ », i.e., « $x$ est un puits
-pour $N$ »).
+contraposée à l'intérieur de la propriété d'être aval-inductif (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 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
@@ -872,21 +899,43 @@ La définition (*) choisie pour un graphe bien-fondé est la plus
compréhensible, mais en un certain sens la définition (\ddag) est « la
bonne » (en l'absence de l'axiome du choix, il faut utiliser (\dag)
ou (\ddag), et en mathématiques constructives il faut
-utiliser (\ddag)).
+utiliser (\ddag)). En voici une traduction informelle :
+
+\begin{scho}
+Pour montrer une propriété $P$ sur les sommets d'un graphe bien-fondé,
+on peut supposer (comme « hypothèse d'induction »), lorsqu'il s'agit
+de montrer que $x$ a la propriété $P$, que cette propriété est déjà
+connue de tous les voisins sortants de $x$.
+\end{scho}
\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 voisin sortant
- de $x$ appartient à $P$, alors $x$ lui-même appartient à $P$ »
-(i.e., la propriété entre guillemets dans (\ddag)
+aval-inductive de $P$ (i.e., 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$ » entre guillemets dans (\ddag)
de \ref{well-founded-induction}).
\end{prop}
\begin{proof}
-Il est clair que la partie bien-fondée $Q$ de $G$ vérifie cette
-propriété. Maintenant, si $P$ vérifie la propriété en question, alors
-$P \cap Q$ la vérifie aussi, ce qui montre bien que $Q$ est la plus
-petite.
+La plus petite partie aval-inductive de $G$ a bien un sens, car
+l'intersection de toutes les parties aval-inductives est encore
+aval-inductive (cf. \ref{trivial-remark-downstream}).
+
+Si $x$ est un sommet de $G$ et $\downstr(x)$ désigne son aval
+(considéré comme sous-graphe induit de $G$), il est clair que pour
+toute partie $P$ aval-inductive de $G$, la partie $P \cap \downstr(x)$
+de $\downstr(x)$ est aval-inductive dans ce dernier (le point
+important étant que les voisins sortants d'un sommet de $\downstr(x)$
+dans ce dernier sont les mêmes que ceux dans $G$). En particulier, si
+$\downstr(x)$ est bien-fondé (c'est-à-dire, si $x$ appartient à la
+partie bien-fondée de $G$), alors $x$ appartient à toute partie
+aval-inductive de $G$.
+
+Mais réciproquement, la partie bien-fondée de $G$ est elle-même
+aval-inductive (car si $\downstr(y)$ est bien-fondé pour tout voisin
+sortant de $x$, il est clair que $\downstr(x)$ est aussi bien-fondé),
+donc un sommet qui appartient à toute partie aval-inductive de $G$
+est, en particulier, dans la partie bien-fondée de $G$.
\end{proof}
\begin{thm}[définition par induction bien-fondée]\label{well-founded-definition}
@@ -918,7 +967,22 @@ de \ref{well-founded-induction}, et d'après la proposition en
question, on a donc $P = G$, c'est-à-dire $f = f'$. Ceci montre
l'unicité.
-\textcolor{red}{Existence...}
+Pour montrer l'existence, on considère l'ensemble $\mathfrak{E}$ des
+fonctions $e\colon H\to Z$ définies sur une partie aval-close $H
+\subseteq G$ et telles que pour tout $e(x) = \Phi(x, e|_{\outnb(x)})$
+pour tout $x\in H$. Si $e,e' \in \mathfrak{E}$ alors $e$ et $e'$
+coïncident là où toutes deux sont définies, comme le montre l'unicité
+qu'on a montrée (appliquée à $e$ et $e'$ sur l'ensemble aval-clos $H
+\cap H'$ de définition commun de $e$ et $e'$). En particulier, la
+réunion [des graphes] de tous les $e\in\mathfrak{E}$ définit encore un
+élément $f$ de $\mathfrak{E}$, maximal pour le prolongement. Soit $P$
+l'ensemble des $x \in G$ où $f$ est définie. Si $P$ contient (i.e.,
+$f$ est définie sur) tous les voisins sortants d'un certain $x\in G$,
+alors $f$ est nécessairement définie aussi en $x$, sans quoi on
+pourrait l'y prolonger par $f(x) = \Phi(x,\, f|_{\outnb(x)})$, ce qui
+contredirait la maximalité de $f$. Par induction bien-fondée, on en
+conclut $P = G$, c'est-à-dire que $f$ est définie sur $G$ tout entier.
+C'est ce qu'on voulait.
\end{proof}
Ce théorème est difficile à lire. En voici une traduction