diff options
| -rw-r--r-- | notes-mitro206.tex | 69 |
1 files changed, 34 insertions, 35 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index ca284a0..7c1f585 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -773,10 +773,10 @@ de $G$ s'appelle \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 -source $x$, ou encore que $y$ est un \textbf{voisin sortant} de $x$, et on -notera $\outnb(x) = \{y : (x,y) \in E\}$ l'ensemble des voisins sortants -de $x$. Un sommet qui n'a pas de voisin sortant est dit \textbf{terminal} -dans $G$. +source $x$, ou encore que $y$ est un \textbf{voisin sortant} de $x$, +et on notera $\outnb(x) = \{y : (x,y) \in E\}$ l'ensemble des voisins +sortants de $x$. Un sommet qui n'a pas de voisin sortant est +appelé \textbf{puits} dans $G$. Un tel graphe est dit \textbf{fini} lorsque $G$ est fini (il est clair que $E$ l'est alors aussi). Il est dit \textbf{acyclique} lorsqu'il @@ -835,7 +835,7 @@ Pour un graphe orienté $G$, les affirmations suivantes sont \begin{itemize} \item[(*)]$G$ est bien-fondé. \item[(\dag)]Tout ensemble \emph{non vide} $N$ de sommets de $G$ - contient un sommet $x \in N$ qui est terminal pour $N$, + contient un sommet $x \in N$ qui est un puits pour $N$, c'est-à-dire qu'il n'existe aucune arête $(x,y)$ de $G$ avec $y \in N$ (i.e., aucun voisin sortant de $x$ n'appartient à $N$). \item[(\ddag)]Si une partie $P\subseteq G$ vérifie la propriété @@ -851,21 +851,21 @@ 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 terminal - pour $N$ »). +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 qu'il y ait une arête de $x_i$ à $x_{i+1}$. Pour montrer que (*) implique (\dag), on suppose que $N$ est un -ensemble non-vide de sommets sans sommet terminal : comme $N$ est -non-vide, on choisit $x_0 \in N$, et comme $x_0$ n'est pas terminal on -peut choisir $x_1 \in N$ atteignable à partir de $x_0$ par une arête, -puis $x_2 \in N$ atteignable à partir de $x_1$ et ainsi de suite — par -récurrence (et par l'axiome du choix [dépendants]), on construit ainsi -une suite $(x_i)$ de sommets telle qu'il y ait une arête de $x_i$ -à $x_{i+1}$. +ensemble non-vide de sommets sans puits [i.e., puits pour $N$] : comme +$N$ est non-vide, on choisit $x_0 \in N$, et comme $x_0$ n'est pas un +puits on peut choisir $x_1 \in N$ atteignable à partir de $x_0$ par +une arête, puis $x_2 \in N$ atteignable à partir de $x_1$ et ainsi de +suite — par récurrence (et par l'axiome du choix [dépendants]), on +construit ainsi une suite $(x_i)$ de sommets telle qu'il y ait une +arête de $x_i$ à $x_{i+1}$. \end{proof} La définition (*) choisie pour un graphe bien-fondé est la plus @@ -940,18 +940,18 @@ 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$ ; 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 terminal -dans $G$) 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 rang} sur $G$, on dit que $\rho(x)$ est le rang (ou -rang bien-fondé) d'un sommet $x$. +y\in\outnb(x)\} + 1$ où on 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 +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 + rang} sur $G$, on dit que $\rho(x)$ est le rang (ou rang bien-fondé) +d'un sommet $x$. \end{defn} -\thingy Autrement dit, un sommet de rang $0$ est un sommet terminal, -un sommet de rang $1$ est un sommet non-terminal dont tous les +\thingy Autrement dit, un sommet de rang $0$ est un puits, +un sommet de rang $1$ est un sommet non-puits dont tous les voisins sortants sont terminaux, un sommet de rang $2$ est un sommet dont tous les voisins sortants sont de rang $\leq 1$ mais et au moins un est de rang exactement $1$, et ainsi de suite. @@ -985,10 +985,10 @@ valeur de Grundy d'un sommet $x$. \end{defn} \thingy En particulier, un sommet de valeur de Grundy $0$ est un -sommet qui n'a que des sommets de valeur de Grundy $>0$ comme -voisins sortants (ceci inclut le cas particulier d'un sommet terminal), -tandis qu'un sommet de valeur de Grundy $>0$ est un sommet ayant au -moins un sommet de valeur de Grundy $0$ comme voisin sortant. +sommet qui n'a que des sommets de valeur de Grundy $>0$ comme voisins +sortants (ceci inclut le cas particulier d'un puits), tandis qu'un +sommet de valeur de Grundy $>0$ est un sommet ayant au moins un sommet +de valeur de Grundy $0$ comme voisin sortant. On verra que la notion de fonction de Grundy, et particulièrement le fait que la valeur soit nulle ou pas, a énormément d'importance dans @@ -1006,13 +1006,12 @@ autre que l'écrasement transitif de l'aval de $x$ vu comme un graphe orienté) s'appelle l'écasement transitif du sommet $x$. \end{defn} -\thingy En particulier, un sommet terminal a pour -écrasement $\varnothing$, un sommet qui n'a pour voisins sortants que des -sommets terminaux a pour écrasement $\{\varnothing\}$, un sommet qui -n'a pour voisins sortants que de tels sommets a pour écrasement -$\{\{\varnothing\}\}$ tandis que s'il a aussi des sommets terminaux -pour voisins sortants ce sera $\{\varnothing,\penalty0 \{\varnothing\}\}$, -et ainsi de suite. +\thingy En particulier, un puits a pour écrasement $\varnothing$, un +sommet qui n'a pour voisins sortants que des sommets terminaux a pour +écrasement $\{\varnothing\}$, un sommet qui n'a pour voisins sortants +que de tels sommets a pour écrasement $\{\{\varnothing\}\}$ tandis que +s'il a aussi des sommets terminaux pour voisins sortants ce sera +$\{\varnothing,\penalty0 \{\varnothing\}\}$, et ainsi de suite. Il y a une subtilité ensembliste dans la définition ci-dessus, c'est qu'on ne peut pas donner \textit{a priori} un ensemble $Z$ dans lequel |