Concept

Lemme de König

Résumé
vignette|Tout arbre infini à branchement fini a une branche infinie. En mathématiques, 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 en 1927. Il énonce que : : « Tout arbre infini à branchement fini a une branche infinie. » Il a des applications en logique. Historique Définitions vignette|La publication de Kőnig en 1927 Un arbre est un ensemble de nœuds, muni d'une relation binaire de succession immédiate qui vérifie les conditions suivantes :
  • On distingue la racine R, qui n'est le successeur immédiat d'aucun nœud ;
  • Tout nœud sauf R est le successeur immédiat (ou fils) d'un unique nœud ;
  • Tous les nœuds sont des descendants de la racine R.
Un nœud D est un descendant d'un nœud A s'il existe un chemin de A à D. Un arbre est à branchement fini lorsque tous les nœuds n'ont qu'un nombre fini de fils. Un arbre est infini lorsqu'il a un nombre infini de nœuds. Une branche d'un arbre est une sui
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement