НОУ ІНТУЇТ | лекція | Уявлення про планарном графі
гомеоморфні графи
Теорема (Куратовський, 1930) Граф планарії тоді і тільки тоді, якщо не містить подграфов, гомеоморфних або .
Оскільки доказ теореми Куратовского досить довге і складне, тут воно не наводиться (див. Ф.Харарі. Теорія графів. М .: "Світ". 1973). Проте, скористаємося теоремою Куратовского для отримання іншого критерію планарності. Розглянемо ще два визначення. Елементарним шляхом стягування називається така процедура: беремо ребро (Разом з інцидентними йому вершинами, наприклад, і ) І "стягуємо" його, тобто видаляємо і ототожнюємо і . Отримана при цьому вершина инцидентна тим ребрах (відмінним від ), Яким спочатку були інцидентні або .
Приклад.
Граф називається стягують до графу , якщо можна отримати з за допомогою деякої послідовності елементарних стягування.
Граф планарії тоді і тільки тоді, якщо він не містить подграфов, які стягуються до або до .
Формула Ейлера
Для будь-якого плоского уявлення зв'язкового плоского графа без перегородок число вершин ( ), Число ребер ( ) І число граней з урахуванням нескінченної ( ) Пов'язані співвідношенням .
нехай граф - зв'язний, плоский граф без перегородок. Визначимо значення алгебраїчної суми для його довільного плоского уявлення.
Перетворимо даний граф в дерево, що містить всі його вершини. Для цього видалимо деякі ребра графа , Розриваючи по черзі всі його прості цикли, причому так, щоб граф залишався зв'язковим і без перегородок.
Зауважимо, що при такій відстані одного ребра число граней зменшується на , Так як при цьому або пропаде один простий цикл, або два простих циклу перетворюються в один. Отже, значення різниці при цьому залишається незмінним.
На малюнку ребра, які ми видаляємо, зображені кривими. В отриманому дереві позначимо число вершин - , Число ребер - , Число граней - . Справедлива рівність .
У дереві одна грань, тобто . Операція видалення ребер з графа не змінює число його вершин, тобто . По теоремі 2.1 (див. "Деякі визначення теорії графів" ), В дереві . Звідси , тобто , а тому або .
Отже, доведено, що якщо в плоскому поданні зв'язкового графа без перегородок вершин, ребер і граней, то . Отримана формула називається формулою Ейлера.
Приклад.