Loading AI tools
Теоре́ма Фа́рі — теоретико-графове твердження про можливість випрямити ребра будь-якого планарного графа. Іншими словами, дозвіл малювати ребра не у вигляді відрізків, а у вигляді кривих, не розширює класу планарних графів.
Названа на честь угорського математика Іштвана Фарі[de][1], хоча довели її незалежно Клаус Вагнер[ru] 1936[2] і Штайн 1951 року[3].
Формулювання:
- будь-який простий планарний граф має плоске подання, в якому всі ребра зображено відрізками прямих.
Один з способів доведення теореми Фарі — застосування математичної індукції[4]. Нехай G — простий планарний граф із n вершинами. Ми можемо вважати граф максимальним планарним, за необхідності можна додати ребра в початковий граф G. Всі грані графа G в цьому випадку мають бути трикутниками, оскільки в будь-яку грань з більшим числом сторін можна додати ребро, не порушуючи планарності графа, що суперечить домовленості про максимальність графа. Виберемо деякі три вершини a, b, c, що утворюють трикутну грань графа G. Доведемо за індукцією за n, що існує комбінаторно ізоморфне інше вкладення з прямими ребрами графа G, в якому трикутник abc є зовнішньою гранню вкладення. (Комбінаторна ізоморфність означає, що вершини, ребра і грані нового малюнка можна зробити відповідними елементами старого малюнка і при цьому зберігаються всі відношення інцидентності між ребрами, вершинами і гранями, а не тільки між вершинами і ребрами.) База індукції тривіальна, коли a, b і c є єдиними вершинами в G (n=3).
За формулою Ейлера для планарних графів граф G має 3n − 6 ребер. Еквівалентно, якщо визначити дефіцит вершини v у графі G як 6 − deg(v), сума дефіцитів дорівнює12. Кожна вершина у графі G може мати дефіцит не більший від трьох, так що є щонайменше чотири вершини з додатним дефіцитом. Зокрема, ми можемо вибрати вершину v з не більше ніж п'ятьма сусідами, відмінну від a, b і c. Нехай G утворюється видаленням вершини v з графа G і тріангуляцією грані f, отриманої після видалення вершини v. За індукцією, граф G' має комбінаторно-ізоморфне вкладення з прямолінійними ребрами, в якому abc є зовнішньою гранню. Оскільки отримане вкладення G було комбінаторно ізоморфним G', видалення з нього ребер, доданих для отримання графа G', залишає грань f, яка тепер є многокутником P з не більше ніж п'ятьма сторонами. Для отримання малюнка G з комбінаторно-ізоморфним вкладенням із прямими ребрами, вершину v слід додати до многокутника і з'єднати відрізками з його вершинами. За теоремою галереї мистецтв всередині P існує точка, куди можна помістити вершину v, так що ребра, які з'єднують вершину v з вершинами многокутника P, не перетнуть інших ребер многокутника, що завершує доведення.
Крок індукції доведення проілюстровано праворуч.
Де Фрейсікс, Пах і Полак показали, як знайти за лінійний час малюнок із прямолінійними ребрами на ґратці з розмірами, що лінійно залежать від розміру графа, даючи універсальну множину точок із квадратичними розмірами. Схожий метод використав Шнайдер для доведення покращених меж та характеристики планарності, де він ґрунтувався на частковому порядку інцидентності. Його робота наголошує на існуванні певного розбиття ребер максимального планарного графа на три дерева, які відомі як ліс Шнайдера.
Теорема Татта «про гумове укладання» стверджує, що будь-який тризв'язний планарний граф можна намалювати на площині без перетинів так, що його ребра будуть відрізками прямих і зовнішня грань буде опуклим многокутником[5]. Назва відбиває той факт, що таке вкладення можна знайти як точку рівноваги системи пружин, які подають ребра графа.
Теорема Штайніца стверджує, що будь-який 3-зв'язний планарний граф можна подати як ребра опуклого многогранника в тривимірному просторі. Вкладення з прямими ребрами графа можна отримати як проєкцію такого многогранника на площину.
Теорема про упаковку кіл стверджує, що будь-який планарний граф можна подати як граф перетинів набору кіл, що не перетинаються, на площині. Якщо розмістити кожну вершину графа в центрі відповідного кола, отримаємо подання графа з прямолінійними ребрами.
Чи існує для будь-якого планарного графа подання з прямими ребрами, в якому довжини всіх ребер є цілими числами?
Гайко Гарборт[en] порушив питання, чи існує для будь-якого планарного графа подання з прямими ребрами, в якому всі довжини ребер є цілими числами[6]. Питання, чи істинна гіпотеза Гарборта[en], залишається відкритим (Станом на 2014). Однак відомо, що вкладення з цілими прямими ребрами існує для кубічних графів[7].
Сакс[8] порушив питання, чи має будь-який граф із незачепленим вкладенням у тривимірному евклідовому просторі незачеплене вкладення, в якому всі ребра подано відрізками за аналогією з теоремою Фарі для двовимірних вкладень.
- Мінімізація зламів
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
