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

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

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

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

Граф планарний тоді і тільки тоді, коли він не містить підграфів, гомеоморфних повному графу з п'яти вершин (K5) або графу «будинки і колодязі» (K3,3).

Доведення  

Властивість 'граф ${\displaystyle G}$ містить підграф, гомеоморфний графу ${\displaystyle H}$' будемо скорочено записувати у вигляді '${\displaystyle G\supset H}$'. Видалення ребра '${\displaystyle G-e}$', стягування ребра '${\displaystyle G/e}$' і видалення вершини '${\displaystyle G-x}$'.

${\displaystyle G-e\supset K_{5}}$ або ${\displaystyle G-e\supset K_{3,3}}$ або ${\displaystyle G/e\supset K_{5}}$ або ${\displaystyle G/e\supset K_{3,3}}$ для деякого ребра e графу ${\displaystyle G}$, то ${\displaystyle G\supset K_{5}}$ або ${\displaystyle G\supset K_{3,3}}$. ‘Для ${\displaystyle G-e}$’ твердження очевидне. Якщо ${\displaystyle G/xy\supset K_{3,3}}$, то ${\displaystyle G\supset K_{3,3}}$, а якщо ${\displaystyle G/xy\supset K_{5}}$, то ${\displaystyle G\supset K_{5}}$ або ${\displaystyle G\supset K_{3,3}}$.

Твердження

Якщо зв'язний граф ${\displaystyle G}$ не ізоморфний ні ${\displaystyle K_{5}}$, ні ${\displaystyle K_{3,3}}$, і для будь-якого ребра ${\displaystyle e}$ графу ${\displaystyle G}$ обидва графи ${\displaystyle G-e}$ і ${\displaystyle G/e}$ планарні, то ${\displaystyle G}$ — планарний.

Лема про графи Куратовського

Для довільного графу ${\displaystyle K}$ рівносильними є три такі умови:

1. Для будь-якого ребра ${\displaystyle xy}$ графу ${\displaystyle K}$ граф ${\displaystyle K-x-y}$ не містить θ-графу, і з кожної вершини графу ${\displaystyle K-x-y}$ виходить не менше двох ребер.
2. Для будь-якого ребра ${\displaystyle xy}$ графу ${\displaystyle K}$ граф ${\displaystyle K-x-y}$ є циклом (що містить ${\displaystyle n\geq 3}$ вершин).
3. ${\displaystyle K}$ ізоморфний ${\displaystyle K_{5}}$ або ${\displaystyle K_{3,3}}$.

Доведення твердження

Оскільки ${\displaystyle G}$ не ізоморфний ні ${\displaystyle K_{5}}$, ні ${\displaystyle K_{3,3}}$, то за лемою про графи Куратовського існує ребро ${\displaystyle e=(xy)}$ графу ${\displaystyle G}$, для якого в графі ${\displaystyle G-x-y}$ знайдеться або вершина степеня менше 2 (у ${\displaystyle G-x-y}$), або θ-підграф.

Якщо в графі ${\displaystyle G}$ з деякої вершини виходить одне або два його ребра, то при стягуванні одного з них виходить планарний граф, отже, і граф ${\displaystyle G}$ планарний. Тому далі будемо вважати, що з кожної вершини графу ${\displaystyle G}$ виходить не менше трьох його ребер.

Тому в графі ${\displaystyle G-x-y}$ немає ізольованих вершин, і якщо є висяча вершина ${\displaystyle p}$, то вона з'єднана і з ${\displaystyle x}$, і з ${\displaystyle y}$ у графі ${\displaystyle G}$. Намалюємо граф ${\displaystyle G-(xy)}$ на площині без самоперетинів. Оскільки в графі ${\displaystyle G}$ з ${\displaystyle p}$ виходить три ребра, то 'з одного боку' від шляху ${\displaystyle xpy}$ з ${\displaystyle p}$ не виходить ребер. 'Підмалюємо' ребро ${\displaystyle xy}$ уздовж шляху ${\displaystyle xpy}$ 'з цього боку' від нього. Отримаємо зображення графу ${\displaystyle G}$ на площині без самоперетинів.

Розглянемо тепер випадок, коли в графі ${\displaystyle G-x-y}$ знайдеться θ-підграф.

З теореми Жордана випливає, що будь-який плоский граф розбиває площину на скінченне число зв'язних частин. Ці частини називаються гранями плоского графу.

Намалюємо без самоперетинів на площині граф ${\displaystyle G/xy}$. Зображення графу ${\displaystyle G-x-y=G/xy-xy}$ на площині отримуємо стиранням ребер графу ${\displaystyle G/xy}$, що виходять з вершини ${\displaystyle xy}$. Позначимо через ${\displaystyle {\bar {C}}}$ межу тієї грані (зображення) графу ${\displaystyle G/xy-xy}$, яка містить вершину графу ${\displaystyle xy}$ ${\displaystyle G/xy}$.

Зауважимо, що межа грані не може містити θ-підграфу.

(Це твердження можна вивести з теорема Жордана. Інше доведення виходить від супротивного: якщо межа грані містить θ-підграф, то візьмемо точку всередині цієї межі і з'єднаємо її трьома ребрами з трьома точками на трьох 'дугах' θ-підграфу. Отримаємо зображення графу ${\displaystyle K_{3,3}}$ на площині без самоперетинів. Суперечність.)

Тому ${\displaystyle G-x-y\neq {\bar {C}}}$. Тоді ребра графу ${\displaystyle G-x-y-{\bar {C}}}$ містяться в грані (зображення) графу ${\displaystyle G-x-y=G/xy-xy}$, що не містить вершини ${\displaystyle xy}$. Отже, граф ${\displaystyle {\bar {C}}}$ розбиває площину. Тому знайдеться цикл ${\displaystyle C\subset {\bar {C}}}$ відносно якого вершина ${\displaystyle xy}$ лежить (не зменшуючи загальності) всередині, а деяке ребро графу ${\displaystyle C\subset {\bar {C}}}$ — поза.

Позначимо через ${\displaystyle R}$ об'єднання всіх ребер графу ${\displaystyle G/xy}$, що лежать поза циклом ${\displaystyle C}$. (Можливо,${\displaystyle G-x-y-{\bar {C}}\neq R}$.) Можна вважати, що ${\displaystyle R}$ — підграф в ${\displaystyle G}$ (а не тільки в ${\displaystyle G-x-y}$).

Граф ${\displaystyle G-R}$ можна намалювати на площині без самоперетинів. Можна вважати, що ребра графу ${\displaystyle G}$, що виходять з ${\displaystyle x}$ або ${\displaystyle y}$, на зображенні графу ${\displaystyle G-R}$ лежать всередині циклу ${\displaystyle C}$.

Кожна компонента зв'язності графу ${\displaystyle G-x-y-R-C}$ перетинається з ${\displaystyle C}$ не більше ніж по одній точці.

(Якщо це не так, то в ${\displaystyle G-x-y-R-C}$ є шлях, що з'єднує дві точки на ${\displaystyle C}$. На зображенні графу ${\displaystyle G/xy}$ відповідний шлях лежить усередині циклу ${\displaystyle C}$. Отже, цей шлях розбиває внутрішню частину циклу ${\displaystyle C}$ на дві частини, одна з яких містить ${\displaystyle xy}$, a інша не лежить у грані, обмеженій ${\displaystyle {\bar {C}}}$. Тому ${\displaystyle C\nsubseteq {\bar {C}}}$ — протиріччя.)

Тому можна перекинути всередину циклу ${\displaystyle C}$ кожну компоненту зв'язності графу ${\displaystyle G-x-y-R-C}$. Отже, граф ${\displaystyle G-R-C}$ можна намалювати всередині циклу ${\displaystyle C}$. Намалюємо ${\displaystyle R}$ поза ${\displaystyle C}$ для зображення графу ${\displaystyle G/xy}$. Отримаємо зображення графу ${\displaystyle G}$ на площині без самоперетинів.

Див. також

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

Примітки

1. Kuratowski, Kazimierz (1930), (PDF), Fund. Math. (French) , 15: 271—283, архів оригіналу (PDF) за 23 липня 2018, процитовано 5 грудня 2016

Посилання

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