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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Формулювання[ред. | ред. код]

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

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

Доказ[ред. | ред. код]

Властивість 'граф містить підграф, гомеоморфний графу ' будемо скорочено записувати у вигляді ''. Видалення ребра '', стягування ребра '' і видалення вершини ''.

 або  або  або  для деякого ребра e графа , то  або . ‘Для ’ утверждение очевидно. Если  , то , а якщо , то  або .

Твердження[ред. | ред. код]

Якщо зв'язний граф  не ізоморфний ні , ні , і для будь-якого ребра  графа обидва графа  і  планарні, то планарен.

Лема про графах Куратовского[ред. | ред. код]

Для довільного графа три наступні умови рівносильні:

  1. Для будь-якого ребра графа xy граф не містить θ-графа, і з кожної вершини графа виходить не менше двох ребер.
  2. Для будь-якого ребра графа xy граф є циклом (що містить вершин).
  3. ізоморфний або .

Доказ затвердження[ред. | ред. код]

Так як не из ізоморфний ні , ні , то по лемі про графах Куратовского існує ребро графа , для якого в графі знайдеться або вершина ступеня менше 2 (у ), або θ-підграф.

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

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

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

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

Намалюємо без самоперетинів на площині граф . Зображення графа на площині виходить стиранням ребер графа , що виходять з вершини . Позначимо через кордон тієї межі (зображення) графа , яка містить вершину графа .

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

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

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

Позначимо через об'єднання всіх ребер графа , що лежать поза циклу . (Можливо,.) Можна вважати, що — підграф в (а не тільки в ).

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


Кожна компонента зв'язності графа перетинається з не більше ніж по одній точці.


(Якщо це не так, то в є шлях, що з'єднує дві точки на . На зображенні графа відповідний шлях лежить всередині циклу . Значить, цей шлях розбиває внутрішню частину циклу на дві частини, одна з яких містить , a інша не лежить в межі, обмеженою . Тому — протиріччя.)

Тому можна перекинути всередину циклу кожну компоненту зв'язності графа . Отже, граф можна намалювати всередині циклу . Намалюємо поза для зображення графа . Отримаємо зображення графа на площині без самоперетинів.

Примітки[ред. | ред. код]

  1. Kuratowski, Kazimierz (1930). Sur le problème des courbes gauches en topologie. Fund. Math. (French) 15: 271–283. 

Посилання[ред. | ред. код]