Lemme de König

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.

À 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.

Concepts associés (3)

Cours associés (1)

Séances de cours associées (7)

Constructive set theory

Axiomatic constructive set theory is an approach to mathematical constructivism following the program of axiomatic set theory. The same first-order language with "" and "" of classical set theory is usually used, so this is not to be confused with a constructive types approach. On the other hand, some constructive theories are indeed motivated by their interpretability in type theories. In addition to rejecting the principle of excluded middle (), constructive set theories often require some logical quantifiers in their axioms to be set bounded, motivated by results tied to impredicativity.

Lemme de König

Théorie de la calculabilité

La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est un domaine de la logique mathématique et de l'informatique théorique. La calculabilité (parfois appelée « computationnalité », de l'anglais computability) cherche d'une part à identifier la classe des fonctions qui peuvent être calculées à l'aide d'un algorithme et d'autre part à appliquer ces concepts à des questions fondamentales des mathématiques. Une bonne appréhension de ce qui est calculable et de ce qui ne l'est pas permet de voir les limites des problèmes que peuvent résoudre les ordinateurs.

MATH-410: Riemann surfaces

This course is an introduction to the theory of Riemann surfaces. Riemann surfaces naturally appear is mathematics in many different ways: as a result of analytic continuation, as quotients of complex

Réseaux neuronaux : apprentissage multicouche

Couvre les fondamentaux des réseaux neuronaux multicouches et de l'apprentissage profond, y compris la propagation arrière et les architectures réseau comme LeNet, AlexNet et VGG-16.

Groupes fondamentaux

Explore les groupes fondamentaux, les classes d'homotopie et les revêtements dans les variétés connectées.

Analyse numérique: systèmes implicites

Couvre les schémas implicites dans l'analyse numérique pour résoudre les équations différentielles partielles.