Як довести що граф ейлерів

0 Comments

15.2: Формула Ейлера

Теорема \(\PageIndex<1>\) Якщо \(G\) планарне вбудовування зв’язаного графа (або мультиграфа, з петлями або без них), то \[|V | − |E| + |F| = 2.\] Доказ 1: Доведемо цю формулу індукцією на кількість граней вбудовування. \(G\) Дозволяти площинне вбудовування зв’язаного графа (або мультиграф, з або без петель). Базовий випадок: Якщо \(|F| = 1\) тоді \(G\) не може мати жодних циклів (інакше внутрішня та зовнішня частина циклу будуть \(2\) окремими гранями). Так \(G\) повинен бути пов’язаний графік, який не має циклів, тобто дерево. За теоремою 12.4.1 ми знаємо, що ми повинні мати \(|E| = |V | − 1\) , так \[|V | − |E| + |F| = |V | − (|V | − 1) + 1 = 2.\] Дерево не може мати жодних петель або декількох ребер, оскільки вони утворюють цикли. Індуктивний крок: Ми починаємо з констатації нашої індуктивної гіпотези. \(k ≥ 1\) Дозволяти бути довільним, і припустити, що для будь-якого планарного вбудовування зв’язаного графа (або мультиграфа, з або без петель) з \(k\) гранями, \(|V | − |E| + |F| = 2\) . \(G\) Дозволяти планарне вбудовування зв’язаного графа з \(k + 1 ≥ 2\) гранями. Так як дерева мають тільки одну грань, \(G\) повинні мати цикл. Виберіть будь-який край \(e\) , який знаходиться в циклі \(G\) , і нехай \(H = G \setminus \\) . Зрозуміло, що ми маємо \[|E(H)| = |E(G)| − 1\] і \(|V (H)| = |V (G)|\) . Крім того, \[|F(H)| = |F(G)| − 1 = k\] так як край \(e\) , що є частиною циклу, повинен розділяти дві грані \(G\) , які об’єднані в одну грань \(H\) . Крім того, оскільки \(e\) був у циклі і \(G\) пов’язаний, Пропозиція 12.3.4, \(H\) пов’язана і \(H\) має планарне вбудовування, індуковане планарним вбудовуванням \(G\) . Тому наша індуктивна гіпотеза відноситься до \(H\) , так \[ \begin \begin 2 &= |V (H)| − |E(H)| + |F(H)| \\ &= |V (G)| − (|E(G) − 1) + (|F(G)| − 1) \\ &= |V (G)| − |E(G)| + |F(G)| \end \end \] На цьому індуктивний крок закінчений. За принципом математичної індукції, \(|V | − |E| + |F| = 2\) для будь-якого планарного вбудовування зв’язаного графа (або мультиграфа, з петлями або без них).

Вищевказане доказ є незвичним для доказу індукцією на графіках, оскільки індукція не на кількість вершин. Якщо ви спробуєте довести формулу Ейлера шляхом індукції на кількість вершин, видалення вершини може відключити граф, що означатиме, що індукційна гіпотеза не застосовується до отриманого графіка. Однак існує інша операція графа, яка зменшує кількість вершин на \(1\) , і зберігає графік зв’язним. На жаль, він може перетворити графік на мультиграф, тому його можна використовувати лише для підтвердження результату, який відповідає дійсності як для мультиграфів, так і для графіків. Ця операція називається скороченням краю.

Визначення: Договірний край \(G\) Дозволяти графу з ребром \(uv\) . Графік, \(G’\) отриманий при скороченні ребра, \(uv\) має вершини. \[V (G’ ) = (V (G) \setminus \) ∪ \,\] \(u’\) де нова вершина. Краї є \[E(G’) = \left( [E(G) \setminus \] \setminus \ \right) ∪ \ vy ∈ E(G)\>\] Якщо ви думаєте про вершини \(u\) і \(v\) як пов’язані дуже короткою пружною, яка була розтягнута в \(G\) , то ви можете думати \(G’\) як графік, який ви отримаєте, якщо ви дозволите пружні стискати, поєднуючи вершини \(u\) і \(v\) в «нову» вершину \(u’\) .

Зверніть увагу, що якщо \(G\) це пов’язано, то графік, отриманий при стисненні будь-якого краю, також \(G\) буде з’єднаний. Однак якщо \(uv\) є ребром, який ми стискаємо, \(u\) і \(v\) маємо взаємного сусіда \(x\) , то в графіку \(uv\) , отриманому шляхом скорочення, буде кратний край між \(u’\) і \(x\) . Також, якщо \(G\) має плоске закладення, то після стягування будь-якого краю все одно буде плоске закладення. Якщо \(u \neq v\) , то скорочення \(uv\) зменшує кількість вершин на одну, зменшує кількість ребер на одиницю, і не змінює кількість граней. Тепер ми можемо використовувати цю операцію для доведення формули Ейлера шляхом індукції на кількість вершин

Теорема \(\PageIndex<1>\) Якщо \(G\) планарне вбудовування зв’язаного графа (або мультиграфа, з петлями або без них), то \[|V | − |E| + |F| = 2.\] Доказ 2: \(G\) Дозволяти площинне вбудовування зв’язаного графа (або мультиграф, з або без петель). Базовий випадок: якщо \(|V | = 1\) тоді \(G\) має одну вершину. Крім того, кожен край – це петля. Кожна петля задіює \(1\) край, і облягає \(1\) лицьовою стороною. Таким чином, цей графік матиме ще одну грань, ніж петлі (оскільки вона має одну грань, навіть якщо петель немає). Таким чином, \[|V | − |E| + |F| = 1 − e + (e + 1) = 2.\] Індуктивний крок: Ми починаємо з констатації нашої індуктивної гіпотези. \(k ≥ 1\) Дозволяти бути довільним, і припустити, що для будь-якого планарного вбудовування зв’язаного графа (або мультиграфа, з або без петель) з \(k\) вершинами, \(|V | − |E| + |F| = 2\) . \(G\) Дозволяти планарне вбудовування зв’язаного графа з \(k + 1 ≥ 2\) вершинами. Так як граф пов’язаний і має як мінімум дві вершини, він має хоча б одне ребро \(uv\) , с \(u \neq v\) . \(G’\) Дозволяти графу, який ми отримуємо шляхом контрактування \(uv\) . Потім \(G’\) відбувається планарне вбудовування зв’язаного графа (або мультиграфа, з петлями або без них) на \(k\) вершині, тому наша індуктивна гіпотеза застосовується до \(G’\) . Тому, \[ \begin \begin 2 &= |V (G’)| − |E(G’)| + |F(G’)| \\ &= (|V (G)| − 1) − (|E(G) − 1) + |F(G)| \\ &= |V (G)| − |E(G) + |F(G)| \end \end \] На цьому індуктивний крок закінчений. За принципом математичної індукції, \(|V | − |E| + |F| = 2\) для будь-якого планарного вбудовування зв’язаного графа (або мультиграфа, з петлями або без них).

Скорочення ребер має деякі інші дуже важливі застосування в теорії графів. Перш ніж розглядати деякі наслідки формули Ейлера, ми пояснимо одну відому теорему, яка включає скорочення країв та плоскі графіки.

Визначення: Неповнолітній \(G\) Дозволяти графу. Тоді \(H\) є незначним, \(G\) якщо ми можемо побудувати \(H\) з \(G\) шляхом видалення або скорочення ребер і видалення вершин.

У 1937 році Вагнер довів теорему, досить схожу на теорему Куратовського.

Теорема \(\PageIndex<2>\) : Wagner’s Theorem Графік є планарним тоді і лише тоді, коли він не має незначних ізоморфних до \(K_5\) або \(K_\) .

Можна довести теорему Вагнера як легкий наслідок теореми Куратовського, оскільки якщо він \(G\) має підграф, який є підрозділом \(K_5\) або \(K_<3,3>\) потім стискається все, крім одного шматочка кожного підрозділеного краю, дає нам незначний, який є ізоморфним до \(K_5\) або \(K_<3,3>\) . Тим не менш, теорема Вагнера важлива сама по собі, як перший приклад набагато більш пізньої та дуже потужної роботи Ніла Робертсона та Пола Сеймура про неповнолітніх графа. Сім’я, як кажуть, є неповнолітньою закритою, якщо дана будь-яка графа в сім’ї, будь-яка неповнолітня частина графіка також є в сім’ї. Планарні графи є прикладом малозамкнутого сімейства, оскільки операції видалення (ребер або вершин) і стиснення ребер зберігають плоске вбудовування. Робертсон і Сеймур довели чудовий результат, що якщо сімейство графів є незначним замкнутим, то сім’я може характеризуватися кінцевим набором «заборонених неповнолітніх». Тобто для будь-якого такого сімейства \(\mathcal\) існує кінцевий набір \(\mathcal\) графіків, таких, що \(\mathcal ∈ \mathcal\) якщо і тільки в тому випадку, якщо не \(\mathcal\) з’являється незначний з \(\mathcal\) . Теорема Вагнера говорить нам, що коли \(\mathcal\) це сімейство плоских графів, \(\mathcal = \\>\) . Формула Ейлера має деякі важливі наслідки.

Слідство \(\PageIndex<1>\) \(G\) Дозволяти бути зв’язаний графік. Тоді кожне планарне вбудовування \(G\) має однакову кількість граней. Доказ У нас є \(|V | − |E| + |F| = 2\) . Оскільки \(|V|\) і \(|E|\) не залежать від вибору вбудовування, ми \(|F| = 2 + |E| − |V|\) не можемо залежати від вибору вбудовування.

Слідство \(\PageIndex<2>\) Якщо \(G\) простий пов’язаний планарний граф і \(|V| ≥ 3\) , то \[|E| ≤ 3|V| − 6\] Якщо крім того, не \(G\) має циклів довжини менше \(4\) , то \(|E| ≤ 2|V| − 4\) . Доказ Виправте площинне вбудовування \(G\) . Пересуваємося по кожній грані, вважаючи кількість країв, з якими стикаємося, і відпрацьовуємо результат двома способами. Спочатку ми дивимося на кожне обличчя по черзі і підраховуємо, скільки країв оточує це обличчя. Оскільки графік простий, кожна грань повинна бути оточена принаймні \(3\) ребрами, якщо не існує лише однієї грані. Якщо є тільки одна грань і при переміщенні навколо цієї грані ми не рахуємо хоча б \(3\) ребер, то граф – це дерево, яке має не більше одного ребра, так що \(|V| ≤ 2\) . Тому наш підрахунок прийде як мінімум \(3|F|\) . Кожен край або розділяє дві грані, або звисає в обличчя. У першому випадку це буде зараховано один раз, коли ми рухаємося навколо одного з двох осіб, що трапляються. В останньому випадку це буде зараховано двічі, коли ми рухаємось навколо обличчя, в яке воно бовтається: один раз, коли ми рухаємось всередину вздовж цієї звисаючої частини, і один раз, коли ми рухаємось назад назовні. Таким чином, кожне ребро зараховується рівно двічі, тому наш підрахунок дійде точно \(2|E|\) . Поєднуючи ці, ми бачимо \(2|E| ≥ 3|F|\) , що, так \(|F| ≤ \dfrac<2|E|>\) . Якщо не \(G\) має циклів довжини менше \(4\) , то кожна грань повинна бути оточена хоча б \(4\) ребрами, тому той же аргумент дає \(2|E| ≥ 4|F|\) , так що \(|F| ≤ \dfrac<|E|><2>\) . За формулою Ейлера \(|V| − |E| + |F| = 2\) , так \[|V| − |E| + \dfrac<2|E|> ≥ 2.\] Множення через \(3\) і переміщення \(|E|\) термінів в праву сторону, дає \[3|V| ≥ |E| + 6,\] які можна легко переставити у форму нашого оригінального твердження. У разі, коли не \(G\) має циклів довжини менше \(4\) , отримуємо замість \[|V| − |E| + \dfrac<|E|> <2>≥ 2,\] Отже \(2|V| ≥ |E| + 4\) , який знову-таки можна легко переставити в форму, наведену в заяві цього слідства.

Слідство \(\PageIndex<3>\) Якщо \(G\) простий пов’язаний планарний граф, то \(δ(G) ≤ 5\) . Доказ До протиріччя, припустимо, що \(G\) це простий пов’язаний планарний граф, і для кожного \(v ∈ V\) , \(d(v) ≥ 6\) . Тоді \[\sum_ d(v) ≥ 6|V|.\] За допомогою леми рукостискання Ейлера, це дає \[\sum_ d(v) = 2|E| ≥ 6|V |.\] Тому, \[|E| ≥ 3|V | > 3|V | − 6,\] але це суперечить Слідству 15.2.2.

Формула Ейлера (і її наслідки) дають нам набагато простіший спосіб довести, що \(K_5\) і не \(K_<3,3>\) є площинними.

Слідство \(\PageIndex<4>\) Графік \(K_5\) не плоский. Доказ У \(K_5\) нас є \(|E| = \binom = 10\) , і \(|V| = 5\) . Отже, \[3|V| − 6 = 15 − 6 = 9 < 10 = |E|\] За наслідком 15.2.2, не \(K_5\) повинен бути площинним.

Слідство \(\PageIndex<5>\) Графік \(K_\) не планарний Доказ У \(K_\) нас є \(|E| = 9\) , і \(|V| = 6\) . Отже, \[2|V | − 4 = 12 − 4 = 8 < 9 = |E|\] Оскільки \(K_\) двосторонній, він не має циклів довжини менше \(4\) , ніж, тому за наслідком 15.2.2, не \(K_\) повинен бути площинним

Вправа \(\PageIndex<1>\) 1) Використовуйте індукцію, щоб довести формулу Ейлера для планарних графіків, які мають рівно дві з’єднані компоненти. 2) Формула Ейлера може бути узагальнена до нероз’єднаних графіків, але має додаткову змінну для кількості зв’язаних компонентів графа. Вгадайте, якою буде ця формула, і використовуйте індукцію, щоб довести свою відповідь. 3) Знайти і довести наслідок формули Ейлера для нероз’єднаних графіків, подібний до Слідство 15.2.2. (Використовуйте свою відповідь на питання \(2\) .) 4) Для графіків, вбудованих на тор, \(|V| − |E| + |F|\) має різне (але постійне) значення, до тих пір, поки всі грані «виглядають як» диски. (Якщо ви знайомі з топологією, грані повинні бути вбудовані в площину, а не виглядати як тор. Отже, розміщення планарного вбудовування графіка вниз на одній стороні тора не враховується.) Що це за величина? 5) Визначення. Ми говоримо, що планарне вбудовування графа є самоподвійним, якщо він ізоморфний до його плоского подвійного. Доведіть, що якщо планарне вбудовування зв’язаного графа \(G\) є самоподвійним, то \(|E| = 2|V| − 2\) . 6) Визначення. Доповненням \(G\) є граф з тими ж вершинами, що і \(G\) , але чиї ребра є саме неребрами \(G\) . ( \(u\) Тобто примикає до \(v\) в доповненні \(G\) якщо і тільки \(u\) не примикає до \(v\) в \(G\) .) Тому, якщо \(G^c\) є доповненням \(G\) , то \(E(K_<|V(G)|>)\) є розмежованим об’єднанням \(E(G)\) і \(E(G^c)\) . Показати, що якщо \(G\) це простий планарний граф з принаймні одинадцятьма вершинами, то доповнення не \(G\) є площинним. 7) Знайдіть планарний граф, \(G\) з доповненням \(|V| = 8\) якого також є планарним. 8) Для кожного з наступних наборів умов або намалюйте зв’язаний простий графік \(G\) у площині, який задовольняє умовам, або поясніть, як ви знаєте, що його немає. (a) Граф має \(15\) вершини та \(12\) ребра. (b) Граф має \(10\) вершини та \(33\) ребра. (c) Граф має \(5\) вершини та \(8\) ребра. (d) Графік має \(6\) вершини та \(9\) ребра, а вбудовування має 6 граней

Recommended articles

  1. Article type Section or Page License CC BY-NC-SA Show Page TOC No on Page
  2. Tags
    1. authorname:jmorris
    2. source[translate]-math-60150

    Пошук Ейлерового циклу в неорієнтованому графі

    Ейлеровим циклом (також відомий як Ейлерів ланцюг) називається замкнутий маршрут, в якому кожне ребро графа зустрічається точно один раз. Для існування такого маршруту в зв’язному неорієнтованому графі необхідно і достатньо, щоб степінь для всіх його вершин була парною. Сьогодні, розглянемо алгоритм, основна ідея якого збігається з алгоритмом обходу графа в глибину, та з його допомогою, для деякого неорієнтований граф , знайдемо Ейлерів цикл. Для цього, припустимо, що вимога зв’язності і парності степенів для нього виконується. Відмітимо, що в такому випадку граф є, принаймі, двозв’язним а отже, містить цикл.

    Графічне представлення алгоритму пошуку Ейлерового циклу

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

    Позначимо знайдений таким чином цикл як . Якщо включає всі ребра графа , то Ейлерів цикл побудовано. В іншому випадку, переходимо до розгляду графа , який отримуємо шляхом видалення з графа всіх ребер, що входять до графу . Цей граф може бути як зв’язним, так і не зв’язним, але будь-яка його компонента в силу зв’язності має хоча б одну загальну вершину з графом . Так як кожна вершина в і має парну степінь, то і в степінь всіх вершин повинна бути парною.

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

    Далі, знову-таки, перевіряємо чи отриманий цикл не являється Ейлеровим. Ящо так, то процес завершено. В іншому випадку слід перейти до розгляду графа (отримуємо шляхом видалення з графа всіх ребер, що входять до графа ), відшукати в ньому цикл , який слід об’єднати з і так далі. Відмітимо, що виходячи з того, що кожен раз кількість не пройдених ребер зменшується, то описаний процес скінченний і повинен закінчитися побудовою Ейлерового циклу.

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

    Ейлерів цикл в неорієнтованому графі – приклад знаходження:

    Побудувати Ейлерів цикл для неорієнтованого графа наступного вигляду.

    Неорієнтований граф задачі

    Проаналізувавши заданий граф бачимо, що кожна з його вершина має парну степінь, тому цей граф Ейлерів, а отже містить Ейлерів цикл. Застосуємо для нього розглянутий вище алгоритм. Для цього, на першому кроці, виберемо в якості початкової вершину номер «1», та скориставшись одним з не пройдених інцидентних їй ребер, наприклад , переходимо у вершину номер «2». Ребро після цього вважається пройденим. Після цього, скориставшись не пройденим інцидентним ребер, але на цей раз для вершини «2», переходимо у вершину «3». Продовжуючи аналогічні дії далі, отримаємо список вершин, послідовний обхід яких і утворюватиме для заданого графа наступний Ейлерів ланцюг: .