Теорема Понтрягіна — Куратовського

Теорема Понтрягіна — Куратовського — теорема теорії графів, що дає необхідну й достатню умову планарності графу. Доведена в 1930 році польським математиком Казимиром Куратовським і незалежно від нього радянським математиком Понтрягіним. Однак останній не опублікував свого доведення, тому часто літературі теорема називається просто теоремою Куратовського.

Формулювання

Граф називається планарним, якщо його можна зобразити на двовимірній площині так, щоб його ребра попарно не перетиналися. Класичними прикладами непланарних графів є K₅ (повний граф на 5 вершинах) і K_3,3 (званий ще «будинки та колодязі» або «вода, газ та електрика» — повний двочастковий граф, що має по 3 вершини в кожній частці). Очевидно, що якщо граф G містить підграф, гомеоморфний K₅ або K_3,3, то він непланарний. Теорема Понтрягіна — Куратовського стверджує, що істинне й обернене, тобто:Шаблон:Теорема

Див. також

• Критерій планарності Вітні

Посилання

• А. Б. Скопенков, Вокруг критерия Куратовского планарности графов, 2012. Шаблон:Webarchive
• А. Б. Скопенков, Вокруг критерия Куратовского планарности графов, Математическое просвещение, сер. 3, вып. 9, 2005(116—128). Шаблон:Webarchive
• Yu. Makarychev, A short proof of Kuratowski's graph planarity criterion, J. of Graph Theory, 25 (1997) 129—131. Шаблон:Webarchive