Lemme de könig

Lemme de könig

Lemme de König

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.

Sommaire

Définitions

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 (mathématiques) pour une définition plus générale et plus puissante (arbres non-dénombrables).

Preuve

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

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.

Voir aussi

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Lemme de K%C3%B6nig ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Lemme de könig de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Lemme De König — 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.… …   Wikipédia en Français

  • Lemme de Konig — Lemme de König 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… …   Wikipédia en Français

  • Lemme de König — 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.… …   Wikipédia en Français

  • Konig — König Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • König — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « König », sur le Wiktionnaire (dictionnaire universel) König …   Wikipédia en Français

  • Lemme d'Auerbach — En mathématique, le lemme d Auerbach, qui porte le nom de Herman Auerbach, est un lemme d analyse fonctionnelle qui affirme que certaines propriétés des espaces euclidiens sont valables pour des espaces vectoriels normés généraux de dimension… …   Wikipédia en Français

  • Theoreme de Konig — Théorème de König Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Il existe plusieurs « théorèmes de König » pour la simple raison qu il existe plusieurs scientifiques portant le nom de König… …   Wikipédia en Français

  • Théorème de König — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Il existe plusieurs « Théorèmes de König » pour la simple raison qu il existe plusieurs scientifiques portant le nom de König (écrit aussi… …   Wikipédia en Français

  • Théorème de könig — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Il existe plusieurs « théorèmes de König » pour la simple raison qu il existe plusieurs scientifiques portant le nom de König (que l on… …   Wikipédia en Français

  • Théorèmes de König — Théorème de König Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Il existe plusieurs « théorèmes de König » pour la simple raison qu il existe plusieurs scientifiques portant le nom de König… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”