1. гомеоморфні графи Теорема (Куратовський, 1930) Граф планарії тоді і тільки тоді, якщо не містить...

гомеоморфні графи

Теорема (Куратовський, 1930) Граф планарії тоді і тільки тоді, якщо не містить подграфов, гомеоморфних або .

Оскільки доказ теореми Куратовского досить довге і складне, тут воно не наводиться (див. Ф.Харарі. Теорія графів. М .: "Світ". 1973). Проте, скористаємося теоремою Куратовского для отримання іншого критерію планарності. Розглянемо ще два визначення. Елементарним шляхом стягування називається така процедура: беремо ребро (Разом з інцидентними йому вершинами, наприклад, і ) І "стягуємо" його, тобто видаляємо і ототожнюємо і . Отримана при цьому вершина инцидентна тим ребрах (відмінним від ), Яким спочатку були інцидентні або .

Приклад.

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

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

Формула Ейлера

Для будь-якого плоского уявлення зв'язкового плоского графа без перегородок число вершин ( ), Число ребер ( ) І число граней з урахуванням нескінченної ( ) Пов'язані співвідношенням .

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

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

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

На малюнку ребра, які ми видаляємо, зображені кривими. В отриманому дереві позначимо число вершин - , Число ребер - , Число граней - . Справедлива рівність .

У дереві одна грань, тобто . Операція видалення ребер з графа не змінює число його вершин, тобто . По теоремі 2.1 (див. "Деякі визначення теорії графів" ), В дереві . Звідси , тобто , а тому або .

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

Приклад.