Lemme de König

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Théorème de König.

Le lemme de Kőnig est un lemme de la théorie des graphes que l'on doit au mathématicien hongrois Dénes Kőnig. Il énonce que :

« Tout arbre infini à branchement fini a une branche infinie. »

Définitions[modifier | modifier le code]

Un arbre est un ensemble d'objets, appelés nœuds, tels qu'il y ait une relation binaire de succession immédiate et un nœud d'origine O qui satisfont aux conditions suivantes :

  • O n'est le successeur immédiat d'aucun nœud ;
  • Tout nœud sauf O est le successeur immédiat d'un unique nœud ;
  • Tous les nœuds sont des successeurs de O.

Un nœud A est un successeur d'un autre D s'il existe une suite finie de nœuds qui commence par D, qui finit par A, et qui est telle que tout nœud est un successeur immédiat (au sens de la structure de l'arbre) de celui qui le précède dans la suite.

Un arbre est à branchement fini lorsque tous les nœuds n'ont qu'un nombre fini de successeurs immédiats.

Un arbre est infini lorsqu'il a un nombre infini de nœuds.

Une branche d'un arbre est une suite finie ou infinie de nœuds N(i), qui commence par O, et qui est telle que pour tout i, N(i+1) est un successeur immédiat de N(i).

Voir aussi arbre (théorie des ensembles) pour une définition plus générale et plus puissante (arbres non-dénombrables).

Preuve[modifier | modifier le code]

La preuve de Kőnig est brève.

Un nœud est dit infini s'il a un nombre infini de successeurs.

Supposons qu'on ait un arbre infini d'origine O à branchement fini.

O est infini. Comme O n'a qu'un nombre fini de successeurs immédiats, l'un d'entre eux au moins, noté N(1), est infini ; sinon O ne serait pas infini. De même l'un au moins, noté N(2), des successeurs immédiats de N(1) est infini. On définit ainsi un nombre infini de nœuds N(i), pour tout entier positif i, qui ensemble forment une branche infinie.

(Remarque : on utilise ici l'axiome des choix dépendants, forme faible de l'axiome du choix.)

Autre formulation[modifier | modifier le code]

Une relation acyclique à branchement fini est globalement finie si et seulement si tous les éléments sont accessibles.

Une relation \,R sur \,E est à branchement fini si pour tout x\in E l'ensemble \{y \in E\mid x R y\} est fini.

Une relation \,R est globablement finie si pour tout x\in E l'ensemble \{y \in E \mid x R^* y\} est fini, où \,R^* est la fermeture réflexive et transitive de \,R.

Une relation \,R est acyclique si x\,R^*\, y et y\,R^*\,x implique x\,=\,y.

L'ensemble des éléments accessibles par \,R est le plus petit ensemble tel que ((\forall y\in E)~ x R y \Rightarrow Acc_R(y)) \Rightarrow Acc_R(x) .

Cette formulation a l'avantage de ne pas faire référence à l'infini et de ne pas utiliser de négations inutiles.

Généralisations[modifier | modifier le code]

De façon assez surprenante, le lemme de Kőnig ne se généralise pas aux arbres non dénombrables ; voir l'article Arbre d'Aronszajn pour plus de détails.

Voir aussi[modifier | modifier le code]