summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--notes-mitro206.tex5
1 files changed, 5 insertions, 0 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 2ccd9ff..d5a07cf 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -823,6 +823,11 @@ 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
+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é.}
+
\begin{prop}[induction bien-fondée]\label{well-founded-induction}
Pour un graphe orienté $G$, les affirmations suivantes sont
équivalentes :