Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/07173.jsonl.gz/334

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.HistoriqueDé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
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.