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

Last updated
Save as PDF

Page ID: 64467

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Template:MathJaxLevin

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

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

Коли можна намалювати графік так, щоб жодна з країв не перетиналася? Якщо це можливо, ми говоримо, що графік плоский (так як ви можете намалювати його на площині).

Зверніть увагу, що визначення плоского включає в себе словосполучення «можна». Це означає, що навіть якщо графік не виглядає так, як він плоский, він все одно може бути. Можливо, ви можете перемалювати його таким чином, щоб жодні краї не перетинаються. Наприклад, це плоский граф:

$image-101.svg$

Це тому, що ми можемо перемалювати його так:

$image-102.svg$

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

Коли плоский граф малюється без перетину ребер, ребра і вершини графа ділять площину на області. Ми будемо називати кожен регіон обличчям. Графік вище має 3 грані (так, ми включаємо область «зовні» як обличчя). Кількість граней не змінюється незалежно від того, як ви малюєте графік (якщо ви робите це без перетину ребер), тому має сенс призначити кількість граней як властивість плоского графа.

УВАГА: ви можете підраховувати грані лише тоді, коли графік намальований плоскою схемою. Для прикладу розглянемо ці два зображення одного і того ж графіка:

$image-103.svg$ $image-104.svg$

Якщо ви спробуєте підрахувати обличчя за допомогою графіка зліва, ви можете сказати, що є 5 осіб (включаючи зовнішню сторону). Але креслення графіка з плоским зображенням показує, що насправді існує всього 4 грані.

Існує зв'язок між кількістю вершин ($v$), кількістю ребер () і кількістю граней ($e$$f$) у будь-якому пов'язаному планарному графі. Цей зв'язок називається формулою Ейлера.

Визначення: Формула Ейлера для планарних графів

Для будь-якого (зв'язаного) плоского графа з$v$ вершинами,$e$ ребрами та$f$ гранями ми маємо

\ begin {рівняння*} v-e + f = 2\ end {рівняння*}

Чому формула Ейлера вірна? Один із способів переконати себе в його обґрунтованості - крок за кроком намалювати планарний графік. Почніть з графіка$P_2\text{:}$

$image-105.svg$

Будь-який зв'язаний граф (окрім однієї ізольованої вершини) повинен містити цей підграф. Тепер створіть свій графік, додаючи ребра та вершини. Кожен крок буде складатися або з додавання нової вершини, з'єднаної новим ребром до частини вашого графіка (таким чином, створення нового «шипа») або з'єднання двох вершин, які вже є на графіку, з новим ребром (завершення схеми).

$image-106.svg$ $image-107.svg$

Що роблять ці «ходи»? При додаванні шипа кількість ребер збільшується на 1, кількість вершин збільшується на одиницю, а кількість граней залишається колишнім. Але це означає, що$v - e + f$ не змінюється. Завершення схеми додає одне ребро, додає одну грань і зберігає кількість вершин однаковою. Так знову ж таки,$v - e + f$ не змінюється.

Оскільки ми можемо побудувати будь-який графік, використовуючи комбінацію цих двох ходів, і це ніколи не змінює кількість$v - e + f\text{,}$, що кількість буде однаковою для всіх графіків. Але зверніть увагу, що наш початковий графік$P_2$ має$v = 2\text{,}$$e = 1$ і$f = 1\text{,}$ так$v - e + f = 2\text{.}$ Цей аргумент по суті є доказом індукції. Хорошою вправою було б переписати його як офіційний індукційний доказ.

Неплощинні графіки

Для повних графіків$K_n\text{,}$ ми хотіли б мати можливість сказати щось про кількість вершин, ребер і (якщо граф плоский) граней. Давайте спочатку розглянемо$K_3\text{:}$

Скільки вершин$K_3$ має? Скільки ребер?
Якщо$K_3$ плоска, скільки граней вона повинна мати?

Повторіть частини (1) і (2) для$K_4\text{,}$$K_5\text{,}$ і$K_{23}\text{.}$

А як щодо повних двосторонніх графіків? Скільки вершин, ребер та граней (якби вони були плоскими)$K_{7,4}$ має? Для яких значень$m$ і$n$ є$K_n$ і$K_{m,n}$ плоских?

Не всі графіки площинні. Якщо ребер занадто багато і занадто мало вершин, то частина ребер потрібно буде перетинати. Перший раз це відбувається в$K_5\text{.}$

$image-108.svg$

Якщо ви спробуєте перемалювати це без перетину країв, ви швидко потрапите в неприємності. Здається, один край занадто багато. Насправді, ми можемо довести, що незалежно від того, як ви його малюєте, завжди$K_5$ буде перетинатися краю.

Теорема$\PageIndex{1}$

$K_5$не площинний.

Доказ

Доказ - протиріччя. Тому припустимо, що$K_5$ це плоска. Тоді графік повинен задовольняти формулі Ейлера для планарних графів. $K_5$має 5 вершин і 10 ребер, тому ми отримуємо

\ begin {рівняння*} 5 - 10 + f = 2\ кінець {рівняння*}

який говорить про те, що якщо графік намальований без перетину країв, були б$f = 7$ грані.

Тепер розглянемо, скільки країв оточують кожну грань. Кожна грань повинна бути оточена як мінімум 3 ребрами. $B$Дозволяти загальна кількість меж навколо всіх граней на графіку. Таким чином, ми маємо що$B \ge 3f\text{.}$ Але також,$B = 2e\text{,}$ оскільки кожен край використовується як межа рівно двічі. Збираючи це воєдино, ми отримуємо

\ begin {рівняння*} 3f\ le 2e\ end {рівняння*}

Але це неможливо, так як ми вже визначили, що$f = 7$$e = 10\text{,}$ і$21 \not\le 20\text{.}$ це протиріччя так насправді$K_5$ не планарне.

$\square$

Інший найпростіший граф, який не є площинним, є$K_{3,3}$

$image-109.svg$

Доведення того,$K_{3,3}$ що не планарно відповідає будинкам і комунікаціям головоломка: неможливо підключити кожен з трьох будинків до кожного з трьох інженерних комунікацій без перетину ліній.

Теорема$\PageIndex{2}$

$K_{3,3}$не площинний.

Доказ

Знову ж таки, протікаємо протиріччям. Припустимо,$K_{3,3}$ були плоскими. Тоді за формулою Ейлера буде 5 граней, так як$v = 6\text{,}$$e = 9\text{,}$ і$6 - 9 + f = 2\text{.}$

Скільки меж оточують ці 5 граней? $B$Дозволяти це число. Оскільки кожне ребро використовується як межа двічі, ми маємо$B = 2e\text{.}$ також,$B \ge 4f$ оскільки кожна грань оточена 4 або більше кордонами. Ми знаємо, що це правда, тому що$K_{3,3}$ є двостороннім, тому не містить жодних циклів 3-краю. Таким чином

\ begin {рівняння*} 4f\ le 2e. \ end {рівняння*}

Але це б говорило про те,$20 \le 18\text{,}$ що явно помилково. При цьому$K_{3,3}$ не площинний.

$\square$

Зверніть увагу на схожість і відмінності цих доказів. Обидва є доказами протиріччя, і обидва починаються з використання формули Ейлера для отримання (передбачуваної) кількості граней на графіку. Потім ми знаходимо залежність між кількістю граней та кількістю ребер на основі того, скільки ребер оточує кожну грань. Це єдина відмінність. У доказ, бо$K_5\text{,}$ ми отримали$3f \le 2e$ і для$K_{3,3}$ нас йдемо$4f \le 2e\text{.}$ Коефіцієнт$f$ є ключовим. Це найменша кількість країв, які можуть оточувати будь-яке обличчя. Якщо певну кількість ребер оточує грань, то ці ребра утворюють цикл. Так що число - це розмір найменшого циклу в графіку.

Загалом, якщо ми дозволимо$g$ бути розмір найменшого циклу в графіку ($g$розшифровується як обхват, який є технічним терміном для цього), то для будь-якого планарного графіка ми маємо$gf \le 2e\text{.}$ Коли це не погоджується з формулою Ейлера, ми точно знаємо, що графік не може бути планарним.

Багатогранники

Досліджуйте!

Куб - приклад опуклого багатогранника. Він містить 6 однакових квадратів для його граней, 8 вершин та 12 ребер. Куб - це правильний багатогранник (також відомий як платонічне тіло), оскільки кожна грань є ідентичним правильним багатокутником, і кожна вершина з'єднує рівну кількість граней.

Є рівно чотири інших правильних багатогранника: тетраедр, октаедр, додекаедр і ікосаедр з 4, 8, 12 і 20 гранями відповідно. Скільки вершин і ребер має кожна з них?

Ще одна область математики, де ви, можливо, чули терміни «вершина», «край» та «обличчя» - це геометрія. Багатогранник - це геометричне тверде тіло, що складається з плоских багатокутних граней, з'єднаних по краях і вершинам. Нас особливо цікавлять опуклі багатогранники, а це означає, що будь-який відрізок лінії, що з'єднує дві точки на внутрішній стороні багатогранника, повинен цілком міститися всередині багатогранника. ²

Альтернативним визначенням опуклих є те, що внутрішній кут, утворений будь-якими двома гранями, повинен бути менше$180 ^o$.

Зверніть увагу, що оскільки$8 - 12 + 6 = 2\text{,}$ вершини, ребра та грані куба задовольняють формулі Ейлера для плоских графів. Це не випадковість.

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

$image-110.svg$

Фактично, кожен опуклий багатогранник може проектуватися на площину без перетину країв. Подумайте про розміщення багатогранника всередині сфери, зі світлом у центрі сфери. Краї і вершини багатогранника відкидають тінь на внутрішню частину сфери. Потім можна вирізати отвір у сфері посередині однієї з проектованих граней і «розтягнути» сферу, щоб лягти рівно на площині. Обличчя, яке було проколото, стає «зовнішнім» обличчям планарного графа.

Справа в тому, що ми можемо застосувати те, що ми знаємо про графіки (зокрема плоскі графіки) до опуклих багатогранників. Оскільки кожен опуклий багатогранник може бути представлений у вигляді плоского графа, ми бачимо, що формула Ейлера для плоских графів також має місце для всіх опуклих багатогранників. Ми також можемо застосувати ті самі міркування, які ми використовуємо для графіків в інших контекстах до опуклих багатогранників. Наприклад, ми знаємо, що немає опуклих багатогранників з 11 вершинами все ступеня 3, оскільки це зробило б 33/2 ребра.

Приклад$\PageIndex{3}$

Чи існує опуклий багатогранник, що складається з трьох трикутників і шести п'ятикутників? А як щодо трьох трикутників, шести п'ятикутників і п'яти гептагонів (7-сторонніх багатокутників)?

Рішення

Скільки ребер мали б такі багатогранники? Для першого запропонованого багатогранника трикутники сприяли б загалом 9 ребер, а п'ятикутники сприятимуть 30. Однак це підраховує кожне ребро двічі (оскільки кожне ребро межує рівно з двома гранями), даючи 39/2 ребра, неможливість. Такого багатогранника немає.

Другий багатогранник не має цієї перешкоди. Додаткові 35 ребер, спричинені гептагонами, дають загалом 74/2 = 37 ребер. Поки що добре. Тепер скільки вершин має цей передбачуваний багатогранник? Ми можемо використовувати формулу Ейлера. Є 14 облич, тому ми маємо$v - 37 + 14 = 2$ or equivalently $v = 25\text{.}$ But now use the vertices to count the edges again. Each vertex must have degree at least three (that is, each vertex joins at least three faces since the interior angle of all the polygons must be less that $180^\circ$), so the sum of the degrees of vertices is at least 75. Since the sum of the degrees must be exactly twice the number of edges, this says that there are strictly more than 37 edges. Again, there is no such polyhedron.

Щоб завершити це застосування плоских графів, розглянемо правильні багатогранники. Вище ми стверджували, що їх всього п'ять. Звідки ми знаємо, що це правда? Ми можемо довести це за допомогою теорії графів.

Теорема$\PageIndex{3}$: regular polyhedra

Правильних багатогранників рівно п'ять.

Доказ

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

Випадок 1: Кожна грань - це трикутник. $f$Дозволяти кількість граней. Є потім$3f/2$ краю. Використовуючи формулу Ейлера, ми маємо$v - 3f/2 + f = 2$ так$v = 2 + f/2\text{.}$ Тепер кожна вершина має однаковий ступінь, скажімо,$k\text{.}$ так що кількість ребер також$kv/2\text{.}$ Покладання це разом дає

\ begin {рівняння*} e =\ frac {3f} {2} =\ frac {k (2+f/2)} {2}\ кінець {рівняння*}

який говорить

\ begin {рівняння*} k =\ frac {6f} {4+f}\ кінець {рівняння*}

Нам потрібно$k$ і обидва$f$ бути додатними цілими числами. Зауважте, що$\frac{6f}{4+f}$ є зростаючою функцією для позитивних$f\text{,}$ і має горизонтальну асимптоту на 6. Таким чином, єдино можливі значення для$k$ 3, 4 і 5. Кожен з них можливий. Для отримання$k = 3\text{,}$ нам потрібно$f = 4$ (це і є тетраедр). Для$k = 4$ беремо$f = 8$ (восьмигранник). Для$k = 5$ беремо$f = 20$ (ікосаедр). Таким чином, існує рівно три правильних багатогранника з трикутниками для граней.

Випадок 2: Кожне обличчя - квадрат. Тепер ми маємо$e = 4f/2 = 2f\text{.}$ Використовуючи формулу Ейлера, ми отримуємо$v = 2 + f\text{,}$ і підрахунок ребер, використовуючи$k$ ступінь кожної вершини, дає нам

\ begin {рівняння*} e = 2f =\ frac {k (2+f)} {2}\ end {рівняння*}

Рішення для$k$ дарує

\ begin {рівняння*} k =\ frac {4f} {2+f} =\ frac {8f} {4+2f}\ кінець {рівняння*}

Це знову зростаюча функція, але на цей раз горизонтальна асимптота знаходиться в$k = 4\text{,}$ тому єдине можливе значення, яке$k$ може прийняти 3. Це дає 6 граней, і у нас є куб. Існує тільки один правильний багатогранник з квадратними гранями.

Випадок 3: Кожне обличчя - це п'ятикутник. Виконуємо той же розрахунок, що і вище, на цей раз отримуючи$e = 5f/2$ так$v = 2 + 3f/2\text{.}$

\ begin {рівняння*} e =\ frac {5f} {2} =\ frac {k (2+3f/2)} {2}\ кінець {рівняння*}

тому

\ begin {рівняння*} k =\ frac {10f} {4+3f}\ кінець {рівняння*}

Тепер горизонтальна асимптота знаходиться на$\frac{10}{3}\text{.}$ Це менше 4, так що ми можемо тільки сподіватися зробити$k = 3\text{.}$ Ми можемо зробити це, використовуючи 12 п'ятикутників, отримуючи додекаедр. Це єдиний правильний багатогранник з п'ятикутниками в якості граней.

Випадок 4: Кожна грань - це$n$ -кутник з$n \ge 6\text{.}$ Дотримуючись тієї ж процедури, що і вище, ми виводимо, що

\ begin {рівняння*} k =\ frac {2nf} {4+ (n-2) f}\ кінець {рівняння*}

який буде збільшуватися до горизонтальної асимптоти$\frac{2n}{n-2}\text{.}$ Коли$n = 6\text{,}$ ця асимптота знаходиться в$k = 3\text{.}$ будь-якому більшому значенні$n$ дасть ще меншу асимптоту. Тому не існує правильних багатогранників з гранями, більшими за п'ятикутники. ³ Зверніть увагу, що ви можете обробити площину шестигранниками. Це нескінченний планарний граф; кожна вершина має ступінь 3. Ці нескінченно багато шестикутників відповідають межі як$f \to \infty$ to make $k = 3\text{.}$

$\square$