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