diff options
| -rw-r--r-- | notes-mitro206.tex | 140 |
1 files changed, 81 insertions, 59 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index 8cea295..20f6ee3 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -786,6 +786,13 @@ compact $C_0 \neq \varnothing$ inclus dans $C$. \subsection{Graphes orientés bien-fondés} +Le but de cette section est de présenter les outils fondamentaux sur +les graphes orientés bien-fondés (cf. \ref{definitions-graphs}) +permettant utiles à la théorie combinatoire des jeux impartiaux. Il +s'agit notamment de la théorie de l'induction bien-fondée +(cf. \ref{scholion-well-founded-induction} +et \ref{scholion-well-founded-definition}). + \begin{defn}\label{definitions-graphs} 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 @@ -822,7 +829,7 @@ notions sont distinctes, l'exemple le plus évident étant sans doute celui de $\mathbb{N}$ dans lequel on fait pointer une arête de $i$ à $i+1$ pour chaque $i$. -\begin{defn}\label{definition-accessibility-downstream-wfpart} +\begin{defn}\label{definition-accessibility-downstream} 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 @@ -838,12 +845,6 @@ 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. - -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 -suite $x_0,x_1,x_2,\ldots$ de sommets où $x_0 = x$ et où pour -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} \thingy On peut remarquer que la relation d'accessibilité sur $G$ est @@ -852,7 +853,7 @@ 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é). -\begin{defn} +\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$ » @@ -861,7 +862,7 @@ $G$ est \textbf{aval-clos} lorsqu'il vérifie la propriété suivante : 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 +« 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$ »). \end{defn} @@ -878,13 +879,6 @@ 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, et ceci justifiera le terme d'« aval-inductif ». -Il sera utile pour la suite de remarquer que la partie bien-fondée -de $G$ est à la fois aval-close et aval-inductive (car on peut -construire une suite infinie $x_0, x_1, x_2\ldots$, avec $x_{i+1}$ -voisin sortant de $x_i$, commençant par un $x_0$ donné si et seulement -si on peut le faire en commençant pour un certain voisin sortant $x_1$ -de ce $x_0$). - \begin{prop}[induction bien-fondée]\label{well-founded-induction} Pour un graphe orienté $G$, les affirmations suivantes sont équivalentes : @@ -896,9 +890,10 @@ Pour un graphe orienté $G$, les affirmations suivantes sont 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é - suivante « lorsque $x \in G$ est tel que tout voisin sortant de $x$ + 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$ est aval-inductif »), alors $P = G$. + « $P$ est aval-inductif », + cf. \ref{definition-downstream-closed-inductive}), alors $P = G$. \end{itemize} \end{prop} \begin{proof} @@ -931,43 +926,17 @@ compréhensible, mais en un certain sens la définition (\ddag) est « la ou (\ddag), et en mathématiques constructives il faut utiliser (\ddag)). En voici une traduction informelle : -\begin{scho} +\begin{scho}\label{scholion-well-founded-induction} 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}\label{wfpart-is-smallest-inductive} -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$ -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} -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é, -cf. \ref{trivial-remark-downstream}), donc un sommet qui appartient à -toute partie aval-inductive de $G$ est, en particulier, dans la partie -bien-fondée de $G$. -\end{proof} +Exactement comme le principe de récurrence sur les entiers naturels, +le principe d'induction bien-fondée peut servir non seulement à +démontrer des propriétés sur les graphes bien-fondés, mais aussi à +définir des fonctions dessus : \begin{thm}[définition par induction bien-fondée]\label{well-founded-definition} Soit $G$ un graphe orienté bien-fondé et $Z$ un ensemble quelconque. @@ -1019,7 +988,7 @@ C'est ce qu'on voulait. Ce théorème est difficile à lire. En voici une traduction informelle : -\begin{scho} +\begin{scho}\label{scholion-well-founded-definition} Pour définir une fonction $f$ sur un graphe bien-fondé, on peut supposer, lorsqu'on définit $f(x)$, que $f$ est déjà défini (i.e., connu) sur tous les voisins sortants de $x$ : autrement dit, on @@ -1052,14 +1021,11 @@ tous les voisins sortants sont de rang $\leq 1$ mais et au moins un est de rang exactement $1$, et ainsi de suite. Il revient au même de définir le rang de la manière suivante : le rang -$\rho(x)$ d'un sommet $x$ d'un graphe orienté bien-fondé est le plus -grand $n$ tel qu'il existe une suite $x_0,x_1,\ldots,x_n$ telle que -$x_0 = x$ et que pour chaque $i$ le sommet $x_{i+1}$ soit atteint par -une arête de source $x_i$. - -Pour un graphe non supposé bien-fondé, on peut définir son rang comme -on vient de le dire sur sa partie bien-fondée, et poser $\rho(x) = -\infty$ lorsque $x$ n'appartient pas à la partie bien-fondée. +$\rho(x)$ d'un sommet $x$ d'un graphe orienté bien-fondé est la plus +grande longueur possible d'un chemin orienté partant de $x$, +c'est-à-dire, le plus grand $n$ tel qu'il existe une suite +$x_0,x_1,\ldots,x_n$ telle que $x_0 = x$ et que pour chaque $i$ le +sommet $x_{i+1}$ soit atteint par une arête de source $x_i$. Voici un autre exemple de définition par induction bien-fondée : @@ -1112,6 +1078,62 @@ de $G$ : ainsi, \emph{un P-sommet est un sommet dont tous les voisins moins un P-sommet pour voisin sortant}. \end{defn} +On va voir que dans le jeu exposé en \ref{introduction-graph-game}, si +le graphe est bien-fondé, les P-sommets sont les positions du jeu à +partir desquelles le joueur précédent a une stratégie gagnante, tandis +que les N-sommets sont celles à partir desquelles le joueur suivant +(`N' comme « Next ») a une stratégie gagnante (consistant, justement, +à jouer vers un P-sommet). + + +\subsection{Généralisations aux graphes non nécessairement bien-fondés} + +\begin{defn}\label{definition-wfpart} +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 +suite $x_0,x_1,x_2,\ldots$ de sommets où $x_0 = x$ et où pour +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} + +\thingy\label{trivial-remark-wfpart} Il sera utile pour la suite de +remarquer que la partie bien-fondée de $G$ est à la fois aval-close et +aval-inductive (car on peut construire une suite infinie $x_0, x_1, +x_2\ldots$, avec $x_{i+1}$ voisin sortant de $x_i$, commençant par un +$x_0$ donné si et seulement si on peut le faire en commençant pour un +certain voisin sortant $x_1$ de ce $x_0$). + +\begin{prop}\label{wfpart-is-smallest-inductive} +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$ +aval-inductive de $P$ (i.e., vérifiant la propriété « si $x \in + G$ est tel que tout voisin sortant de $x$ appartient à $P$, alors + $x$ lui-même appartient à $P$ », +cf. \ref{definition-downstream-closed-inductive}). +\end{prop} +\begin{proof} +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é, +cf. \ref{trivial-remark-wfpart}), donc un sommet qui appartient à +toute partie aval-inductive de $G$ est, en particulier, dans la partie +bien-fondée de $G$. +\end{proof} + \subsection{Écrasement transitif} @@ -1251,7 +1273,7 @@ auteurs font implicitement une des deux hypothèses « court » étant la conjonction des deux. Ici, on fera le plus souvent l'hypothèse que $G$ est terminant ; on attire l'attention sur le fait que cela signifie que $x_0$ appartient à la partie bien-fondée -(cf. \ref{definition-accessibility-downstream-wfpart}) du graphe $G$. +(cf. \ref{definition-wfpart}) du graphe $G$. \begin{defn} Pour un jeu $G$ comme |