diff options
Diffstat (limited to 'notes-mitro206.tex')
| -rw-r--r-- | notes-mitro206.tex | 102 |
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 |