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