Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
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.
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 suite finie ou infinie de nœuds N(i), qui commence par la racine, et qui est telle que pour tout i, N(i+1) est un fils de N(i).
Considérons un arbre infini à branchement fini. Soit N(0) la racine.
Comme N(0) a un nombre infini de descendants et a un nombre fini de fils, l'un d'entre eux au moins, noté N(1), a un nombre infini de descendants.
Comme N(1) a un nombre infini de descendants et a un nombre fini de fils, l'un d'entre eux au moins, noté N(2), a un nombre infini de descendants.
etc.
On définit ainsi une suite infinie de nœuds N(0), N(1), ... qui forme une branche infinie.
vignette|Etant donné un ensemble de tuiles de Wang, le plan est pavable si, et seulement si tout carré fini est pavable si, et seulement si le quart de plan est pavable.
Le lemme de Kőnig permet de démontrer que : étant donné un ensemble de tuiles de Wang, le plan est pavable si, et seulement si tout carré fini est pavable si, et seulement si le quart de plan est pavable.
Le lemme de Kőnig intervient dans la démonstration du fait que si un langage est décidé par une machine de Turing non-déterministe (qui s'arrête sur toutes les entrées) alors il est décidé par une machine de Turing déterministe.
Source officielle
À 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.