Скільки дерев у графі

Графи та їхні остовні дерева

Ріс. 1

Розглянемо план шести щоденних рейсів деякої авіакомпанії між деякими парами з аеропортів a, b, c і d, показаний на малюнку 1. Для формалізації такої та багатьох інших ситуацій у математиці використовується поняття граф.

Граф — це кінцевий і не порожній набір вершин і кінцевий набір ребер, кожне з яких з’єднує пару вершин. У нашому прикладі вершина графа — це аеропорт, а ребро — це рейс авіакомпанії. Пара вершин графа може бути з’єднана кількома ребрами (це може означати, що авіакомпанія здійснює кілька рейсів на день). Також ребро може з’єднувати вершину з самою собою; в цьому випадку воно називається петлею (про таке ребро можна думати, як про прогулянковий рейс авіакомпанії).

Інакше кажучи, з математичної точки зору, на малюнку 1 ми бачимо граф з чотирма вершинами a, b, c і d, шістьма ребрами, з них одне ребро — петля при вершині c і пара ребер з’єднує b з d. Число ребер, що виходять з даної вершини, називається її ступенем, при цьому петлі вважаються двічі; ступені вершин a, b, c і d — 1, 4, 4 і 3 відповідно.

Зображений граф є зв’язковим, тобто з будь-якої його вершини можна пройти в будь-яку іншу, пройшовши по декількох його ребрах.

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

Цикл — це маршрут, складений з різних ребер, що обходить кілька вершин без повторень і повертається у вихідну вершину. Число ребер у циклі називається довжиною циклу. Наприклад, у нашому графі є два цикли довжини три з вершинами b, c і d, один цикл довжини два з вершинами b і d, а також петля при вершині c утворює цикл довжини один.

Дійсно, якщо з будь-якого циклу зв’язкового графа викинути будь-яке ребро, то граф залишиться зв’язковим. Більш того, якщо після видалення деякого ребра граф залишився зв’язковим, то це ребро належало деякому циклу — цей цикл утворений самим руба і найкоротшим шляхом між його кінцями в графі, що залишився.

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

Взагалі кажучи, зв’язковий граф без циклів називається деревом. У таких графах немає петель і з будь-якої їхньої вершини в будь-яку іншу є єдиний шлях за ребрами без повторень вершин.

На малюнку 2 ви бачите всі п’ять різних остовних дерев нашого вихідного графа.

Ріс. 2

Кількість залишкових дерев у даному графі. Ми будемо позначати. Наприклад, якщо Стер — це граф, який буде розглянуто вище, то — 5.

Щоб перевірити розуміння даних визначень, ми радимо вирішити наступні дві стандартні вправи про дерева:

Вправи

1. Доведіть, що якщо дерево має хоча б дві вершини, то в ньому знайдеться вершина ступеня 1.

2. Доведіть, що число ребер в будь-якому дереві на одиницю менше числа його вершин. Скористайтеся індукцією за кількістю вершин і попередньою вправою.

Ріс. 3

Зокрема, з вправи 2 випливає, що незалежно від вибору ребер число віддалених ребер в процедурі отримання остовного дерева з графа, описаної вище, — одне і те ж. (Для зв’язкового графа. Це число називають його першим числом Бетті; воно зазвичай позначається _{^ 1} (^).)

Ребро зв’язкового графа називається мостом, якщо видалення цього ребра з графа робить граф незв’язним; такий граф розбивається на два зв’язкових графа, звані його островами (рис. 3).

Вправа 3. Нехай граф ^ містить міст між островами Δ₁ і Δ₂. Будь ласка, доведіть, що порожній ( ) =  .

Видалення-плюс-стягування

Ріс. 4

Нехай   є ребро в графі. Позначимо через     граф, отриманий з. Вилученням ребра  , і через ^/   — граф, отриманий з. Стягуванням ребра   в точку (рис. 4).

Якщо ребро   не є петлею, тоді виконується наступне співвідношення:

τ(Γ) = τ(Γρ) + τ(Γ/ρ), (*)

яке ми будемо називати видалення-плюс-стягування.

Дійсно, остовні дерева в ^ можна розділити на дві категорії — ті, що містять ребро  , і ті, що його не містять. Для дерев з першої категорії стягування ребра   в точку дає остовне дерево в ^/  , а дерева другої категорії є також остовними деревами в графі ^  . Більше того, обидві ці відповідності взаємно однозначні. Звідси витікає формула (*).

Наприклад, якщо Лад — це перший приклад і   є ребро між вершинами b і c, тоді перші два остовних дерева на малюнку 2 відповідають дереву в ^  , а останні два відповідають дереву в ^/  .

Формулу (*) зручно записувати схематично, як показано на малюнку 4. На графі ^ ребро  , для якого застосовується формула, перекреслено.

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

τ(Γ) = τ(Γρ).

З формули видалення-плюс-стягування можна вивести кілька інших корисних співвідношень. Наприклад, якщо у графі ^ є кінцева вершина w (тобто вершина ступеня 1), то w і єдине ребро при w можна видалити і в отриманому графі ^w число його остовних графів не зміниться, тобто

τ(Γ) = τ(Γw).

Дійсно, позначимо через   єдине ребро при w. Зауважимо, що граф ^   незв’язний, оскільки вершина w не має ребер, і, значить, ^ (^  ) = 0. З іншого боку, ^/   = ^w, звідки і отримуємо нашу рівність.

Ріс. 5

На схемах двостороння стрілка «↔» буде означати, що відповідні графи мають те ж число остовних дерев; Наприклад, з виведених співвідношень можна отримати наступну діаграму (рис. 5), що означає, зокрема, що ^ (^) = 2· ^ (^).

Рівності, описані вище, дають алгоритм обчислення. Дійсно, для будь-якого ребра   обидва графа.   і ./   мають меншу кількість ребер. Таким чином, видалення-плюс-стягування зводить знаходження числа остовних дерев. До знаходження числа остовних дерев більш простих графів.

Дерева у віялах

Графи наступного виду (рис. 6) називаються віялами; віяло з n + 1 вершиною буде позначатися _{^ n}.

Ріс. 6

Застосувавши співвідношення, отримані в попередньому розділі, ми можемо скласти нескінченну схему, показану на малюнку 7. На додаток до віялів(  ) у схемі беруть участь їх варіації(   _), що відрізняються від(  ) додатковим руба. При виникненні петель або кінцевих вершин ми їх тут же видаляємо.

Ріс. 7

Введемо позначення( a_n =. (Θ_n)) і( a. Зі схеми легко вивести два рекуррентних співвідношення:

( a_{n+1} = a^′_n + a_n, )

( a^′_n = a_n + a^′_{n−1} )

Таким чином, у послідовності чисел( a_1, a ­ _ 1, a_2, a ­ _ 2, a_3,…) кожне наступне є сумою двох попередніх.

Нагадаємо, що послідовність чисел Фібоначчі F_n задається тим же співвідношенням F_{n +} 1 = Fn + _Fn ‑ 1 з F1 = F2 = 1. Вона починається так:

1, 1, 2, 3, 5, 8, 13, …

Далі зауважимо, що( Θ_1) — це дві вершини, з’єднані єдиним руба, а( ^ ^ _ 1) — це дві вершини, з’єднані подвійним ребром. Звідси( a_1 = 1 = F_2) і( a ^ _ 1 = 2 = F_3), а отже,

a_n = F_2n

для будь-якого n.

Можна також вивести рекуррентне співвідношення на( a_n) без використання( a.

( a_{n+1} = a^′_n + a_n = 2a_n + a^′_{n−1} = 3a_n − a_{n−1}.)

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

( a_n = frac{1}{sqrt{5}}left(left(frac{3 + sqrt{5}}{2}right)^n − left(frac{3 − sqrt{5}}{2}right)^nright). )

Цей процес докладно описано в книжці [4], яку ми рекомендуємо читачеві. Оскільки( 0 n, цю формулу можна записати коротше:

( a_n = left[frac{1}{sqrt{5}} left(frac{3 + sqrt{5}}{2}right)^nright],)

де [x] позначає цілу частину числа x.

Для закріплення матеріалу радимо розібрати наступні вправи:

Вправи

4. Розгляньмо послідовність графів _{^ n} наступного типу (рис. 8):

Ріс. 8

Будь ласка, доведіть, що   (^ n) =   для будь_{— якого n.}

5. Нехай b_n позначає кількість остовних дерев у сходах _{^ n} з n сходинками в послідовності графів наступного типу (рис. 9):

Ріс. 9

Скористайтеся розробленим методом і доведіть, що послідовність b_n задовольняє співвідношенню

Ріс. 10

b_n+1 = 4b_n − b_n−1.

(Зауважимо, що b₁ = 1 і b₂ = 4; звідси можна швидко порахувати перші члени послідовності:

1, 4, 15, 56, 209, 780, 2911, …)

Вам знадобиться ще кілька послідовностей графів( В’  _ n) і( В  . _ n), показаних на малюнку 10.

Просунута вправа 6. Коліщатками називаються графи _{^ n} такого типу (рис. 11):

Ріс. 11

Будь ласка, доведіть, що послідовність c_n =   n задовольняє таку рекуррентну формулу:

c_n+1 = 4c_n − 4c_n−1 + c_n−2.

Зауваження. Простіше вивести співвідношення

c_n+1 − a_n+1 = c_n + a_n.

Знаючи, що c₁ = 1, c₂ = 5, останній рівність дозволяє отримати вираз для c_n:

c_n = F_2n+1 + F_2n−1 − 2 = L_2n − 2;

тут L_n = F_{n ‑} 1 + _Fn + 1; ця послідовність називається числами Люка. Як і числа Фібоначчі, числа Люка часто з’являються в різних комбінаторних завданнях.

Заключні зауваження

Підрахунок числа остовних дерев пов’язаний з розрахунком електричних ланцюгів. Припустимо, граф ^ описує електричний ланцюг, в якому кожне ребро — це опір в один ом, джерело живлення підключене до вершин a і b і I є загальний струм в ланцюгу, виміряний в амперах. Нам треба порахувати струм через один з опорів.

Нехай   є ребро ^ з обраним напрямком. Зауважимо, що всі остовні дерева ^ можна розділити на три типи: (1) ті, в яких на шляху з a в b ребро   з’являється з позитивною орієнтацією; (2) ті, в яких на шляху з a в b ребро   з’являється з негативною орієнтацією; (3) ті, в яких на шляху з a в b ребро   не з’являється. Позначимо за допомогою — +, _— і — 0 число дерев у цих трьох категоріях. Вочевидь, порожній ( ) ₌   + +’_’+’0.

Силу струму _I   вздовж   можна обчислити за такою формулою:

( I_ρ = frac{τ_+:−:τ_−}{τ(Γ)} · I)

Доказ виходить прямою перевіркою правил Кірхгофа для значень струмів, отриманих за цією формулою, для всіх ребер в ^.

Є багато інших прикладів використання правил Кірхгофа в теорії графів. Наприклад, у [7] вони використовуються у фізичному доказі формули Ейлера

B ‑ Р + Г = 2,

де В, Р і Г позначають число вершин, ребер і граней багатогранника відповідно.

Формула видалення-плюс-стягування застосовувалася при вирішенні так званої задачі про квадрування квадрата. Історія цього завдання і її чудове рішення обговорюються в книжках [6] і [2]; ідея цього рішення також заснована на оригінальному використанні електричних ланцюгів.

Наведений нами висновок рекуррентних формул для чисел остовних дерев у віялах, сходах і колесах дається в [8]; це завдання також обговорюється в класичній книжці [3].

Суттєво більш складним завданням є знаходження числа остовних дерев у повних графах, тобто таких, в яких будь-яка пара різних вершин з’єднана єдиним ребром. Якщо n позначає число вершин повного графа, то число його остовних дерев дорівнює n^{n ‑ 2}. Іншими словами,

τ(Π_n) = nⁿ⁻², (**)

де _{^ n} позначає повний граф з n вершинами (рис. 12).

Ріс. 12

Рівність (* *) називається формулою Келі. Найбільш відомим доказом є так званий код Прюфера — спосіб однозначного кодування дерева впорядкованою послідовністю з його вершин; кільком іншим доказам присвячено розділ 30 в [1]. У розширеній версії цієї статті [5] наводиться доказ, заснований на формулі видалення-плюс-стягування.

Для числа розмальовок вершин графа виконується аналогічна формула: видалення-мінус-стягування. А саме, нехай   (^, k) означає число розмальовок графа ^ в k кольорів, при яких кінці кожного ребра пофарбовані в різні кольори. Тоді виконується співвідношення

χ(Γ, k) = χ(Γρ, k) − χ(Γ/ρ, k).

Дійсно, допустимі розмальовки графа ^   можна розбити на дві категорії: (1) ті, в яких кінці ребра   пофарбовані в різні кольори, такі залишаються допустимими в графі ^; (2) ті, в яких кінці ребра   пофарбовані в один колір, кожній такій розмальовці відповідає єдина розмальовка ^/  . Звідси — формула.

Вправа 7. Будь ласка, доведіть, що функція   є багаточленою з цілими коефіцієнтами від k; він називається хроматичним багаточленом графа.

Підказка. Скористайтеся індукцією за загальною кількістю ребер і вершин графа і формулою видалення-мінус-стягування.

Література1

. М. Айгнер, Г. Циглер. Докази з Книги. М.:Біном. Лабораторія знань, 2015.2

. М. Гарднер. Математичні головоломки та розваги. М.: Онікс, 1994.3

. Д. Кнут, Р. Грехем, О. Паташник. Конкретна математика. Математичні основи інформатики. М.:Вільямс, 2009.4.

Маркушевич. Повернені послідовності. М.: Держтехвидав, 1950. (Популярні лекції з математики, випуск 1) 5

. А. М. Петрунін. Скільки дерев у графі//arXiv:1803.03749 [math.HO].6.

І. М. Яглом. Як розрізати квадрат? М.:Наука, 1968.7. M

. Levi. An Electrician’s (or a Plumber’s) Proof of Euler’s Polyhedral Formula // SIAM News, vol. 50, no. 4, 2017.8. M

. H. Shirdareh Haghighi, Kh. Bibak. Recursive relations for the number of spanning trees // Applied Mathematical Sciences, vol. 3, no. 46, pp. 2263–2269, 2009.