5.5: Планарні графіки

Доказ Наш доказ – індукція на \(m\) кількість ребер. Якщо \(m=0\) , то так як \(G\) пов’язаний, наш граф має єдину вершину, і так є одна грань. При цьому \(n−m+f=1−0+1=2\) в міру необхідності. Тепер припустимо, що ми довели формулу Ейлера для всіх графів з менш ніж m ребер і нехай \(G\) мають \(m\) ребра. Підберіть \(e\) край \(G\) . Що станеться, якщо ми сформуємо новий графік \(G′\) , видаливши e з \(G\) ? Якщо \(G′\) пов’язано, застосовується наша індуктивна гіпотеза. Скажімо, що \(G′\) має \(n′\) вершини, \(m′\) ребра та \(f′\) грані. Тоді за допомогою індукції ці числа задовольняють \(n’ – m’ + f’ = 2\) . Так як ми видалили тільки один край, \(n′=n\) і \(m′=m−1\) . Що \(e\) зробило видалення з числа осіб? У \(G′\) є нове обличчя, яке раніше було двома обличчями, розділеними на \(e\) в \(G\) . Таким чином, \(f′=f−1\) . Підставляючи їх в \(n′−m′+f′=2\) , ми маємо \(n-(m-1) + (f-1) = 2 \Longleftrightarrow n-m+f = 2\) . Таким чином, якщо \(G′\) підключено, ми зробили. Однак, якщо \(G′\) відключений, ми не можемо застосувати індуктивне припущення \(G′\) безпосередньо. На щастя, оскільки ми видалили лише одне ребро, \(G′\) має дві складові, які ми можемо розглядати як два з’єднаних графіка \(G_1′\) і \(G_2′\) . Кожен з них має менше \(m\) країв, тому ми можемо застосувати до них індуктивну гіпотезу. Для \(i=1,2\) , \(n_i′\) нехай число вершин \(G_i′, m_i′\) числа ребер від \(G_i′, and f_i′\) числа граней \(G_i′\) . Тоді за допомогою індукції ми маємо \(n_1′ – m_1′ +f_1′ = 2\) і \(n_2′ – m_2′ + f_2′ = 2\) . Додавши їх разом, ми маємо \((n_1′ + n_2′) – (m_1′ + m_2′) + (f_1′ + f_2′) = 4\) . Але зараз \(n=n_1′ + n_2’\) і \(m_1′ + m_2′ = m-1\) , таким чином рівність стає \(n – (m-1) + (f_1′ + f_2′) = 4 \Longleftrightarrow n-m + (f_1′ + f_2′) = 3\) . Єдине, що нам ще належить з’ясувати, це те \(f\) , як \(f_1′+f_2′\) відноситься до, і ми повинні сподіватися, що це дозволить нам збити 3 вниз до 2. Кожна грань \(G_1′\) і \(G_2′\) є обличчям \(G\) , так як той факт, що видалення \(e\) роз’єднує \(G\) означає, що \(e\) повинна бути частиною кордону необмеженої грані. Далі необмежений грань підраховується двічі в сумі \(f_1′+f_2′\) , так \(f=f_1′+f_2′−1\) . Це дає саме те, що нам потрібно для завершення доказу. Взята сама по собі формула Ейлера не здається такою корисною, оскільки вона вимагає підрахунку кількості граней у планарному вбудовуванні. Однак ми можемо використовувати цю формулу, щоб отримати швидкий спосіб визначити, що графік не є планарним. Розглянемо креслення без перетинів ребер графа по \(n\) вершинам і m ребрам, с \(n \geq 3\) . Розглядаємо пари \((e,F)\) , де \(e\) є ребром \(G\) і \(F\) є грань, яка має \(e\) як частину своєї межі. Скільки таких пар? Назвемо кількість пар \(p\) . Кожен край може зв’язати або одну або дві грані, так що у нас є, що \(p \leq 2m\) . Ми також можемо зв’язати, \(p\) підрахувавши кількість пар, в яких \(F\) з’являється обличчя. Кожна грань обмежена як мінімум 3 ребрами, тому вона з’являється як мінімум в 3 пари, і так \(p \geq 3f\) . Таким чином \(3f \leq 2m\) або \(f \leq 2m/3\) . Тепер, використовуючи формулу Ейлера, ми маємо \(m=n+f – 2 \leq n + \frac – 2 \Longleftrightarrow \frac \leq n-2\) . Таким чином, ми довели наступну теорему.

Теорема 5.33

Планарний граф на \(n\) вершині має не більше \(3n−6\) ребер, коли \(n \geq 3\) .

Контрапозитив цієї теореми, а саме те, що \(n\) -вершинний граф з більш ніж \(3n−6\) ребрами не є площинним, зазвичай є найбільш корисним формулюванням цього результату. Наприклад, ми бачили (рис. 5.31), що \(K_4\) є площинним. А як щодо \(K_5\) ? Він має 5 вершин і \(C(5,2)=10>9=3 \cdot 5−6\) ребер, тому він не плоский, і, таким чином \(n \geq 5\) , для, \(K_n\) не плоский, так як містить \(K_5\) . Важливо зазначити, що теорема 5.33 – це не все, кінець визначення того, чи граф є планарним. Щоб переконатися в цьому, повернемося до теми малювання \(K_\) в площині. Цей граф має 6 вершин і 9 ребер, тому він проходить тест теореми 5.33. Однак, якщо ви витратите пару хвилин, намагаючись знайти спосіб малювати \(K_\) в площині без будь-яких перетинання країв, ви досить швидко почнете вірити, що це неможливо зробити – і ви б мали рацію! Щоб зрозуміти, \(K_\) чому не плоска, нам доведеться повернутися до формули Ейлера, і ми знову працюємо з парами края-грань. Бо ми бачимо \(K_\) , що кожне ребро повинно бути частиною кордону двох граней, а грані обмежені циклами. Також, оскільки графік двосторонній, непарних циклів немає. Таким чином, підраховуючи пари края-грань з точки зору краю, ми бачимо, що є \(2m=18\) пари. Якщо ми \(f_k\) дозволимо кількість граней, обмежених циклом довжини \(k\) , то \(f=f_4+f_6\) . Таким чином, підраховуючи пари края-грань з точки зору обличчя, є \(4f_4+6f_6\) пари. З формули Ейлера ми бачимо, що кількість граней \(f\) має бути 5, так що тоді \(4f_4+6f_6 \geq 20\) . Але з нашого підрахунку крайових пар ми маємо \(2m=4f_4+6f_6\) , даючи \(18 \geq 20\) , що явно абсурдно. Таким чином, не \(K_\) є площинним. У цей момент ви, мабуть, запитуєте себе «Так що?» Ми вклали неабияку кількість зусиль, щоб встановити, що \(K_5\) і \(K_\) є неплощинними. Зрозуміло, що будь-який графік, який містить їх також непланарний, але є багато графіків, так що ви можете подумати, що ми могли б бути в цьому назавжди. На щастя, ми не будемо, оскільки за своєю суттю планарність дійсно зводиться до цих двох графіків, як ми скоро побачимо. Якщо \(G=(V,E)\) граф і \(uv \in E\) , то ми можемо сформувати новий граф, \(G′\) який називається , \(G\) додаючи нову вершину \(v′\) і \(uv\) замінивши ребро ребрами \(uv′\) і \(v′v\) . Іншими словами, \(G′\) має набір вершин \(V′=V \cup \\) та набір країв \(E′=(E−\) \cup \\) . Два графіка \(G_1\) і \(G_2\) є , якщо їх можна отримати з одного і того ж графіка шляхом (потенційно тривіальної) послідовності елементарних підрозділів. Мета обговорення гомеоморфних графіків полягає в тому, що два гомеоморфні графіки мають однакові властивості, коли мова йде про малювання в площині. Щоб побачити це, подумайте про те, що станеться, \(K_5\) якщо ми сформуємо елементарний підрозділ його через будь-який з його країв. Ясно, що він залишається неплощинним. Насправді, якщо взяти будь-який неплоский граф і сформувати елементарний підрозділ, використовуючи будь-який з його ребер, отриманий граф буде неплощинним. Наступна дуже глибока теорема була доведена польським математиком Казимежем Куратовським в 1930 році. Його доказ виходить за рамки цього тексту.

Теорема 5.34. Теорема Куратовського

Графік є планарним тоді і лише тоді, коли він не містить підграф гомеоморфний ні \(K_5\) або \(K_<3,3>\) .

Теорема Куратовського дає корисний спосіб перевірки, чи є граф планарним. Хоча знайти підграф гомеоморфний до \(K_5\) або \(K_<3,3>\) вручну не завжди легко, існують ефективні алгоритми для тестування планарності, які використовують цю характеристику. Щоб побачити цю теорему в роботі, розглянемо графік Петерсена, показаний на малюнку 5.17. Граф Петерсена має 10 вершин і 15 ребер, тому він проходить тест теореми 5.33, і наш аргумент, використовуючи формулу Ейлера, щоб довести, що \(K_<3,3>\) це непланарний був досить складним, ми, ймовірно, не хочемо спробувати його для графа Петерсена. Щоб використати теорему Куратовського тут, нам потрібно вирішити, чи вважаємо за краще знайти підграф гомеоморфний до \(K_5\) чи до \(K_<3,3>\) . Хоча графік Петерсена виглядає дуже схожим на \(K_5\) , він насправді одночасно занадто схожий і занадто різний для нас, щоб мати можливість знайти підграф гомеоморфний до \(K_5\) , оскільки кожна вершина має ступінь 3. Таким чином, ми поставили собі за мету знайти підграф графа Петерсена гомеоморфний до \(K_<3,3>\) . Для цього зверніть увагу, що \(K_<3,3>\) містить цикл довжини 6 і три ребра, які знаходяться на місці між вершинами навпроти один одного на циклі. Ми ідентифікуємо шестицикл в графі Петерсена і малюємо його як шестикутник і поміщаємо решту чотири вершини всередині циклу. Такий креслення показаний на малюнку 5.35. Підграф \(K_<3,3>\) гомеоморфний до знайдено шляхом видалення чорної вершини, оскільки тоді білі вершини мають ступінь два, і ми можемо замінити кожну з них та їх два падаючі ребра (показано жирним шрифтом) одним ребром. Малюнок 5.35. Більш наочний малюнок графа Петерсена Ми закриваємо цей розділ проблемою, яка об’єднує поточний розділ разом з темою розфарбовування графіка. У 1852 році Френсіс Гатрі, англієць, який в той час навчався на юриста, але згодом став професором математики в Південній Африці, намагався розфарбувати карту графств Англії так, щоб будь-які два округи, які поділяли межовий сегмент (тобто вони торкнулися більш ніж однієї точки) були пофарбовані різними кольорами. Він помітив, що для цього йому потрібні лише чотири кольори, і він не зміг намалювати жодної карти, яка потребує п’яти кольорів. (Він зміг знайти карту, яка вимагала чотирьох кольорів, приклад якої показаний на малюнку 5.36.) Малюнок 5.36. Карта, яка вимагає чотирьох кольорів Чи може бути правдою, що кожна карта може бути пофарбована лише чотирма кольорами? Він запитав про проблему свого брата Фредеріка Гатрі, який був студентом математики Університетського коледжу в Лондоні, і Фредерік врешті-решт повідомив проблему Августу де Моргану (про славу законів де Моргана), одному зі своїх викладачів. Саме таким чином народилася одна з найвідоміших (або сумнозвісних) проблем, відома протягом століття як Проблема чотирьох кольорів, а тепер теорема про чотири кольори, в теорії графів. Де Морган дуже зацікавився проблемою чотирьох кольорів, і передав її серу Вільяму Роуану Гамільтону, видатному ірландському математику і тому, для кого названі гамільтонові цикли, але Гамільтон не знайшов проблему цікавою. Гамільтон – один з небагатьох людей, які розглядали проблему чотирьох кольорів, але не захопилися нею. Ми продовжимо наше обговорення історії теореми чотирьох кольорів за мить, але спочатку ми повинні розглянути, як ми можемо перетворити проблему розфарбовування карти на питання теорії графів. Що ж, здається природним, що кожному регіону повинна бути присвоєна відповідна вершина. Ми хочемо змусити регіони, які поділяють межу, мати різні кольори, тому це говорить про те, що ми повинні розмістити ребро між двома вершинами, якщо і тільки якщо їх відповідні області мають спільну межу. (Як приклад, карта на рис. 5.36 відповідає графіку \(K_4\) .) Неважко побачити, що це створює плоский графік, оскільки ми можемо провести ребра через загальний межовий відрізок. Крім того, трохи подумавши, ви повинні побачити, що за умови плоского креслення графіка, ви можете створити карту, в якій кожна вершина веде до області, а ребра ведуть до загальних сегментів кордону. Таким чином, проблема чотирьох кольорів може бути зазначена як «Чи кожен планарний графік має хроматичне число не більше чотирьох?» Інтерес до проблеми чотирьох кольорів нудився до 1877 року, коли британський математик Артур Кейлі написав листа Королівському товариству з проханням про те, чи була вирішена проблема. Це принесло проблему до уваги ще багатьох людей, і перше «доказ» теореми чотирьох кольорів, завдяки Альфреду Брею Кемпе, було завершено в 1878 році і опубліковано через рік. Минуло 11 років, перш ніж Персі Джон Хівуд знайшов недолік у доказі, але зміг врятувати його достатньо, щоб показати, що кожен планарний графік має хроматичне число не більше п’яти. У 1880 році Пітер Гатрі Тайт, британський фізик, найвідоміший своєю книгою Трактат про природну філософію з сером Вільямом Томсоном (лорд Кельвін), зробив оголошення, яке припустило, що він мав доказ теореми чотирьох кольорів, що використовують гамільтонівські цикли в певних планарних графіках. Однак, відповідно до того, як Тайт наближався до деяких домислів у математичній теорії вузлів, виявляється, що згодом він зрозумів близько 1883 року, що він не міг довести, що гамільтонівські цикли, які він використовував, насправді існували, і тому Тайт, ймовірно, лише вважав, що він має доказ теореми чотирьох кольорів. на короткий час, якщо взагалі. Однак потрібно було б до 1946 року, щоб знайти контрприклад до здогадки, яку Тайт використовував у своїй спробі довести теорему чотирьох кольорів. У першій половині ХХ століття був досягнутий певний поступовий прогрес у вирішенні проблеми чотирьох кольорів, але мало хто з видатних математиків серйозно зацікавився нею. Останній поштовх для підтвердження теореми чотирьох кольорів прийшов приблизно в той же час, коли перші електронні комп’ютери набули широкого використання в промисловості та дослідженнях. У 1976 році два математики з Університету штату Іллінойс оголосили про своє комп’ютерне доказ теореми чотирьох кольорів. Доказ Кеннета Аппела та Вольфганга Хакена змусив Університет штату Іллінойс додати фразу «ЧОТИРИ КОЛЬОРИ ДОСТАТНЬО» до відбитка свого поштового лічильника.

Теорема 5.37. Теорема про чотири кольори

Кожен планарний граф має хроматичне число не більше чотирьох.

Як визначити чи є граф Планарним

GPL Ghostscript 9.14

2017-01-29T21:09:47+02:00 2017-01-29T21:09:47+02:00 PDF24 Creator endstream endobj 2 0 obj endobj xref 0 156 0000000000 65535 f 0000183466 00000 n 0000327002 00000 n 0000183245 00000 n 0000179491 00000 n 0000000015 00000 n 0000006035 00000 n 0000183532 00000 n 0000189136 00000 n 0000220982 00000 n 0000189796 00000 n 0000247030 00000 n 0000190697 00000 n 0000252903 00000 n 0000191962 00000 n 0000287912 00000 n 0000183573 00000 n 0000183603 00000 n 0000179651 00000 n 0000006055 00000 n 0000013298 00000 n 0000186907 00000 n 0000192470 00000 n 0000188238 00000 n 0000212687 00000 n 0000183666 00000 n 0000183696 00000 n 0000179813 00000 n 0000013319 00000 n 0000022773 00000 n 0000183781 00000 n 0000186538 00000 n 0000186148 00000 n 0000315573 00000 n 0000183860 00000 n 0000183890 00000 n 0000179975 00000 n 0000022794 00000 n 0000030046 00000 n 0000183986 00000 n 0000184016 00000 n 0000180137 00000 n 0000030067 00000 n 0000037553 00000 n 0000184090 00000 n 0000184120 00000 n 0000180299 00000 n 0000037574 00000 n 0000046366 00000 n 0000187503 00000 n 0000197323 00000 n 0000184194 00000 n 0000184224 00000 n 0000180461 00000 n 0000046387 00000 n 0000053302 00000 n 0000184320 00000 n 0000184350 00000 n 0000180623 00000 n 0000053323 00000 n 0000062304 00000 n 0000184435 00000 n 0000184465 00000 n 0000180785 00000 n 0000062325 00000 n 0000071277 00000 n 0000184539 00000 n 0000184569 00000 n 0000180947 00000 n 0000071298 00000 n 0000078747 00000 n 0000184643 00000 n 0000184673 00000 n 0000181109 00000 n 0000078768 00000 n 0000086316 00000 n 0000184747 00000 n 0000184777 00000 n 0000181271 00000 n 0000086337 00000 n 0000094064 00000 n 0000184851 00000 n 0000184881 00000 n 0000181433 00000 n 0000094085 00000 n 0000103847 00000 n 0000184977 00000 n 0000185007 00000 n 0000181595 00000 n 0000103868 00000 n 0000111667 00000 n 0000185081 00000 n 0000185111 00000 n 0000181757 00000 n 0000111688 00000 n 0000117767 00000 n 0000185207 00000 n 0000185237 00000 n 0000181919 00000 n 0000117788 00000 n 0000125030 00000 n 0000185300 00000 n 0000185331 00000 n 0000182083 00000 n 0000125052 00000 n 0000133766 00000 n 0000185406 00000 n 0000185437 00000 n 0000182249 00000 n 0000133788 00000 n 0000141280 00000 n 0000185512 00000 n 0000185543 00000 n 0000182415 00000 n 0000141302 00000 n 0000149204 00000 n 0000185618 00000 n 0000185649 00000 n 0000182581 00000 n 0000149226 00000 n 0000157409 00000 n 0000185735 00000 n 0000185766 00000 n 0000182747 00000 n 0000157431 00000 n 0000165541 00000 n 0000185841 00000 n 0000185872 00000 n 0000182913 00000 n 0000165563 00000 n 0000173569 00000 n 0000185947 00000 n 0000185978 00000 n 0000183079 00000 n 0000173591 00000 n 0000179469 00000 n 0000186053 00000 n 0000186084 00000 n 0000192667 00000 n 0000197545 00000 n 0000212891 00000 n 0000221196 00000 n 0000247232 00000 n 0000253112 00000 n 0000288130 00000 n 0000315792 00000 n 0000186306 00000 n 0000186678 00000 n 0000187055 00000 n 0000187819 00000 n 0000188521 00000 n 0000189568 00000 n 0000189949 00000 n 0000191228 00000 n 0000315477 00000 n 0000325381 00000 n trailer ] >> startxref 327191 %%EOF