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

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

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

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

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

Доведення  

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

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

Твердження

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

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

Посилання

• А. Б. Скопенков, Вокруг критерия Куратовского планарности графов, 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.]