Лема Кеніга
лема про існування нескінченного шляху в графі
Лема Кеніга про нескінченний шлях — теорема, яка дає достатню умову існування нескінченного шляху в графі. Ця теорема відіграє важливу роль як приклад у конструктивній математиці і теорії доведень.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/68/Denes_K%C3%B6nig_-_%C3%9Cber_eine_Schlussweise_aus_dem_Endlichen_ins_Unendliche.png/220px-Denes_K%C3%B6nig_-_%C3%9Cber_eine_Schlussweise_aus_dem_Endlichen_ins_Unendliche.png)
Довів Денеш Кеніг 1927 року[1].
Формулювання
ред.Нехай — нескінченний, але локально скінченний (тобто кожна його вершина має скінченний степінь) зв'язний граф. Тоді містить нескінченний простий шлях, тобто шлях без повторюваних вершин, який починається в одній вершині і подовжується нескінченно довго.
Зауваження
ред.Джерела
ред.- Дональд Кнут. Fundamental Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 1. — 650 с. — ISBN 0-201-89683-4.(англ.)
Примітки
ред.- ↑ Kőnig, D. (1927), «Über eine Schlussweise aus dem Endlichen ins Unendliche», Acta Sci. Math. (Szeged) (3(2-3)): 121—130.
Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |
В іншому мовному розділі є повніша стаття Kőnig's lemma(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою перекладу з англійської.
|