summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--notes-mitro206.tex21
1 files changed, 14 insertions, 7 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index b0b9779..25279c8 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -815,7 +815,8 @@ 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).
+arêtes sont celles qui partent d'un tel sommet). On remarquera la
+convention faite que $x$ appartient à son propre aval.
L'ensemble des sommets d'un graphe orienté dont l'aval est bien-fondé,
autrement dit, l'ensemble des sommets $x$ tels qu'il n'existe pas de
@@ -827,14 +828,15 @@ source $x_i$, est appelé la \textbf{partie bien-fondée} du graphe.
\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.
+relation d'accessibilité est elle-même bien-fondée (i.e., le graphe
+qu'elle définit est bien-fondé).
\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$ »).
+(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 :
@@ -853,7 +855,7 @@ 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.
+ce qui suit, et ceci justifiera le terme d'« aval-inductif ».
\begin{prop}[induction bien-fondée]\label{well-founded-induction}
Pour un graphe orienté $G$, les affirmations suivantes sont
@@ -1097,9 +1099,14 @@ fonction d'écrasement $f$ définie
en \ref{definition-transitive-collapse} est injective.
\end{prop}
\begin{proof}
-Supposons $G$ transitif et montrons par induction bien-fondée que $f$
+Si $f$ est injective et si $\outnb(x) = \outnb(x')$ alors en
+particulier $f(x) = f(x')$ (puisque $f(x)$ est définie comme l'image
+par $f$ de $\outnb(x)$), donc $x = x'$. Ceci montre que $G$ est
+extensionnel.
+
+Réciproquement, $G$ extensionnel 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$
+$x$ tels que $f$ restreinte à l'aval de $x$ soit injective. Soit $x$
un sommet dont tous les voisins sortants appartiennent à $P$ :
\textcolor{red}{à finir.}
\end{proof}