Теорема Фарі про розпрямлення графа
Теоре́ма Фа́рі — теоретико-графове твердження про можливість випрямити ребра будь-якого планарного графа. Іншими словами, дозвіл малювати ребра не у вигляді відрізків, а у вигляді кривих, не розширює класу планарних графів.
Названа на честь угорського математика Шаблон:НпШаблон:Sfn, хоча довели її незалежно Шаблон:Нп 1936Шаблон:Sfn і Штайн 1951 рокуШаблон:Sfn.
Формулювання:
- будь-який простий планарний граф має плоске подання, в якому всі ребра зображено відрізками прямих.
Доведення
Один з способів доведення теореми Фарі — застосування математичної індукції[1]. Нехай Шаблон:Mvar — простий планарний граф із Шаблон:Mvar вершинами. Ми можемо вважати граф максимальним планарним, за необхідності можна додати ребра в початковий граф Шаблон:Mvar. Всі грані графа Шаблон:Mvar в цьому випадку мають бути трикутниками, оскільки в будь-яку грань з більшим числом сторін можна додати ребро, не порушуючи планарності графа, що суперечить домовленості про максимальність графа. Виберемо деякі три вершини Шаблон:Math, що утворюють трикутну грань графа Шаблон:Mvar. Доведемо за індукцією за Шаблон:Mvar, що існує комбінаторно ізоморфне інше вкладення з прямими ребрами графа Шаблон:Mvar, в якому трикутник Шаблон:Math є зовнішньою гранню вкладення. (Комбінаторна ізоморфність означає, що вершини, ребра і грані нового малюнка можна зробити відповідними елементами старого малюнка і при цьому зберігаються всі відношення інцидентності між ребрами, вершинами і гранями, а не тільки між вершинами і ребрами.) База індукції тривіальна, коли Шаблон:Mvar, Шаблон:Mvar і Шаблон:Mvar є єдиними вершинами в Шаблон:Mvar (Шаблон:Math).
За формулою Ейлера для планарних графів граф Шаблон:Mvar має Шаблон:Math ребер. Еквівалентно, якщо визначити дефіцит вершини Шаблон:Mvar у графі Шаблон:Mvar як Шаблон:Math, сума дефіцитів дорівнюєШаблон:Math. Кожна вершина у графі Шаблон:Mvar може мати дефіцит не більший від трьох, так що є щонайменше чотири вершини з додатним дефіцитом. Зокрема, ми можемо вибрати вершину Шаблон:Mvar з не більше ніж п'ятьма сусідами, відмінну від Шаблон:Mvar, Шаблон:Mvar і Шаблон:Mvar. Нехай Шаблон:Math утворюється видаленням вершини Шаблон:Mvar з графа Шаблон:Mvar і тріангуляцією грані Шаблон:Mvar, отриманої після видалення вершини Шаблон:Mvar. За індукцією, граф Шаблон:Mvar має комбінаторно-ізоморфне вкладення з прямолінійними ребрами, в якому Шаблон:Mvar є зовнішньою гранню. Оскільки отримане вкладення Шаблон:Mvar було комбінаторно ізоморфним Шаблон:Mvar, видалення з нього ребер, доданих для отримання графа Шаблон:Mvar, залишає грань Шаблон:Mvar, яка тепер є многокутником Шаблон:Mvar з не більше ніж п'ятьма сторонами. Для отримання малюнка Шаблон:Mvar з комбінаторно-ізоморфним вкладенням із прямими ребрами, вершину Шаблон:Mvar слід додати до многокутника і з'єднати відрізками з його вершинами. За теоремою галереї мистецтв всередині Шаблон:Mvar існує точка, куди можна помістити вершину Шаблон:Mvar, так що ребра, які з'єднують вершину Шаблон:Mvar з вершинами многокутника Шаблон:Mvar, не перетнуть інших ребер многокутника, що завершує доведення.
Крок індукції доведення проілюстровано праворуч.Шаблон:Clear
Пов'язані результати
Де Фрейсікс, Пах і Полак показали, як знайти за лінійний час малюнок із прямолінійними ребрами на ґратці з розмірами, що лінійно залежать від розміру графа, даючи універсальну множину точок із квадратичними розмірами. Схожий метод використав Шнайдер для доведення покращених меж та характеристики планарності, де він ґрунтувався на частковому порядку інцидентності. Його робота наголошує на існуванні певного розбиття ребер максимального планарного графа на три дерева, які відомі як ліс Шнайдера.
Теорема Татта «про гумове укладання» стверджує, що будь-який тризв'язний планарний граф можна намалювати на площині без перетинів так, що його ребра будуть відрізками прямих і зовнішня грань буде опуклим многокутникомШаблон:Sfn. Назва відбиває той факт, що таке вкладення можна знайти як точку рівноваги системи пружин, які подають ребра графа.
Теорема Штайніца стверджує, що будь-який 3-зв'язний планарний граф можна подати як ребра опуклого многогранника в тривимірному просторі. Вкладення з прямими ребрами графа можна отримати як проєкцію такого многогранника на площину.
Теорема про упаковку кіл стверджує, що будь-який планарний граф можна подати як граф перетинів набору кіл, що не перетинаються, на площині. Якщо розмістити кожну вершину графа в центрі відповідного кола, отримаємо подання графа з прямолінійними ребрами.Шаблон:ВставкаШаблон:Не перекладено порушив питання, чи існує для будь-якого планарного графа подання з прямими ребрами, в якому всі довжини ребер є цілими числами[2]. Питання, чи істинна Шаблон:Не перекладено, залишається відкритим (Шаблон:Станом на). Однак відомо, що вкладення з цілими прямими ребрами існує для кубічних графівШаблон:Sfn.
СаксШаблон:Sfn порушив питання, чи має будь-який граф із незачепленим вкладенням у тривимірному евклідовому просторі незачеплене вкладення, в якому всі ребра подано відрізками за аналогією з теоремою Фарі для двовимірних вкладень.
Див. також
Примітки
Література
- Шаблон:Стаття
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Стаття
- Шаблон:Стаття
- Шаблон:Стаття
- Шаблон:Стаття
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Стаття
- Шаблон:Стаття
- Шаблон:Стаття
- Шаблон:Стаття
- ↑ Приведённое доказательство можно найти в книге В. В. Прасолов. Элементы комбинаторной и дифференциальной топологии. М.: МЦНМО, 2004.
- ↑ Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb.