diff options
| -rw-r--r-- | notes-mitro206.tex | 21 |
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} |