Фундаментальна множина циклів графа
Припустимо, нам потрібно за допомогою закону Кірхгофа скласти систему лінійних рівнянь для електричного кола. Ланцюг має складну структуру і містить велику кількість циклів. Запишемо закон Кірхгофа для кожного циклу та почнемо вирішувати отриману систему рівнянь. Відразу виявиться, частина рівнянь є лінійно залежними, тобто. виходять із інших. Значить, якісь цикли були непотрібні?
У цьому розділі буде доведено, що БУДЬ-ЯКИЙ ЦИКЛ графа можна однозначно розкласти за ФУНДАМЕНТАЛЬНИМИ ЦИКЛАМИ цього графа так само, як будь-який вектор тривимірного простору однозначно представляється лінійною комбінацією базисних векторівi,j,k. Також буде показано, як побудувати для даного графа це фундаментальне безліч.
Надалі під графом розумітимемо зв'язковий неорієнтований граф, під циклом — ЕЛЕМЕНТАРНИЙ ЦИКЛ.
Спочатку для довільних множин А і В введемо операцію взяття Симметричної різниці А В = (А B) / (А В).
Побудуємо симетричну різницю трьох множин. Виберемо порядок дій, що відповідає наступному розміщенню дужок: (A B) C.
У силу симетрії при будь-якій розстановці дужок буде виходити те ж безліч A B C. Можна встановити закономірність: у симетричну різницю входять елементи, що містяться одночасно або в одному, або в трьох множинах, а ті, що належать двом, видаляються. Узагальним цей результат на довільне число множин.
Симетрична різниця множин А1, А2, …, Аk містить у точності ті елементи, які належать НЕЧЕТНОМУ числу множин.
Довести це можна індукцією за кількістю множин.
Повернемося до фундаментальних циклів. Ця множина визначається через каркас графа.
Нехай вже збудовано каркас D = графа G = . Якщо до каркасудодати довільну хорду e (E\T), то граф (D e), що вийшов, міститиме рівно один цикл. Назвемо цей цикл Се.
Додаючи до каркасу почергово всі хорди, отримаємо фундаментальну безліч циклів Ф щодо каркаса D Ф =е : e (E \ T) & gt;.
?Питання 1. Вкажіть фундаментальну множину циклів графа G щодо каркаса D на малюнку 8.18.
Симетрична різниця будь-якого числа циклів графа G є циклом графа G.
?Питання 2. У графі G (рисунок 8.18) знайти C1 C2, якщо C1 = (1-2-3), C2 = (2-3-4).
Сформулюємо без підтвердження.
Довільний цикл C графа G можна однозначно подати як симетричну різницю деякого числа фундаментальних циклів.
Іншими словами, будь-який цикл розкладається за базисом фундаментальних циклів.
Як мовилося раніше, знання фундаментальних циклів має важливе значення під час аналізу ЕЛЕКТРИЧНИХ ЛАНЦЮГІВ.
Для кожного фундаментального циклу даного ланцюга можна записати закон КІРХГОФА: сума падінь напруги вздовж циклу дорівнює 0. Всі ці рівняння незалежні, рівняння для інших циклів будуть випливати з них.
Аналізоване алгоритмом ребро (v-u) замикатиме цикл, якщо (v-u) - хорда.
КРИТЕРІЙ ХОРДИ наступний:
(v-u) буде хордою, якщо u - знайдена сусідка v - вже зустрічалася раніше при пошуку в глибину. У цьому випадку вона знаходиться в стек і її номерGLN(u) менше відповідного номераGLN(v). Але це ще не все. Якщо з u ми потрапили у вершину v, тобто є батьком v, тоGLN(u)
Дані: Граф G= , поданий списками ЗАПИС[V], v V.
Результати: Безліч фундаментальних циклів Ф графа G.
Змінні: d, num, СТЕК, ЗАПИС, GLN – глобальні.
1 procedure ЦИКЛ(v);
4num:=num+1; GLN [v]: = num;
5 for u ЗАПИС[v] do
6 if GLN[u]=0 then ЦИКЛ(u)
7 else if (u<>СТЕК[d-1]) AND (GLN[u] називається точкою з'єднання, якщо видалення цієї вершини і всіх, що виходять з неї ребер, веде до збільшення компонент зв'язності графа.
Якщо у зв'язному (що складається з 1 компоненти зв'язності) графі немає точок зчленування, він - двозв'язний.
Будь-який МАКСИМАЛЬНИЙ двозв'язковий підграф графа G називається КОМПОНЕНТОЮ ДВОЗВ'ЯЗНОСТІ або БЛОКОМ цього графа.
?Питання 1. Що буде перетином двох різних блоків графа?
?Питання 2. Що станеться з блоком, якщо до нього приєднати ребро графа, що має з блоком загальну точку і не належить блоку?
Двозв'язність графа – дуже корисна властивість для деяких прикладних завдань.
Уявімо, що вершини графа - телеграфні станції; ребра – лінії передач. Нехай одна зі станцій вийшла з ладу. Якщо граф двозв'язний, то між будь-якими двома станціями залишиться зв'язок.
Багатьом завдань важливо знати блоки графа. Наприклад, знаходити всі елементарні цикли графа G можна окремо для кожного блоку графа G.
Знаходження точок зчленування та блоків графа – класичне завдання. Шукатимемо точки зчленування, обходячи всі вершини графа методом пошуку в глибину. Будемо не лише обходити вершини графа, а й будуватимемо його КАРКАС.
При побудові каркаса пошуком у глибину для двох вершин w і v, пов'язаних рубом, завжди достеменно відомо: або w — нащадок v, або навпаки. Як розпізнати точку зчленування s, якщо вже збудовано каркас D графа G?
Ось КРИТЕРІЙ ТОЧКИ СПОЛУЧЕННЯ::
або це корінь, що має не менше двох синів D;
або у вершини s є хоча б один син і такий, що ні він, ні його нащадки непов'язані хордами з предками s.
Розглянемо рисунок 8.21. Номери вершин — номери, які одержують вершини графа під час побудови каркасу. Покажемо, що вершина s задовольняє другу умову критерію.
За побудовою каркаса s має сина: 3 та нащадка 4. Предок s — вершина k. Син 3 та його нащадок 4 не пов'язані хордами з k. Отже, s - точка зчленування і граф G має блок 1 =.
?Питання 3. З якою вершиною потрібно з'єднати вершину 4, щоб граф G став двозв'язковим?
Вершина k — точка зчленування, оскільки вона корінь, що має двох синів: s та 5. Тому граф G має блок 2 = та блок 3 = .
Знаючи критерій точки зчленування, опишемо Алгоритм знаходження цих точок.
Нехай алгоритм пошуку в глибину будує каркас D графа G. Для кожної вершини v обчислюватимемо два значення:GLN[v] таMIN[v].
GLN[v] — просто номер, який отримує вершина під час побудови каркаса. Наприклад, для кореняGLN[k]=1.
Нехай вершина v з'єднана ХОРДАМИ (згадайте, що таке хорди для каркасу D!) з якимись вершинами X1, …, Xk. Виберемо мінімальний номер цих вершин:
?Питання 4. Які вершини графа малюнку 8.21 з'єднані хордами з вершиною s?
Нехай w - будь-який нащадок вершини v. Він може бути пов'язаний хордами з якимись вершинами Y1, …, Yр.
І, нарешті, підрахуємо Y[w] для КОЖНОГО w — нащадка v і виберемо їх мінімальний.
Мінімальний із трьох номерів GLN[v], X[v], Y[v]> назвемоMIN[v]:
MIN[v] легко обчислити за індукцією.
Нехай всім синів U1, …, Uk вершини vMIN[U1], …,MIN[Uk] вже обчислені.
Згадаймо критерій. Точка зчленування або корінь із двома синами, або предки цієї точки і нащадки хоча б одного сина нез'єднані хордами.
Запишемо цей критерій через GLN та MIN.
МIN[u] - мінімальний з номерів вершин, з якими з'єднаний син u та його нащадки. Якщо серед цих вершин не буде предків v, то критерій виконається. Номери предків строго менші за GLN[v], тому MIN[u] ³ GLN [v] для деякого сина u вершини v.
?Питання 5. Обчисліть MIN[3] для сина 3 вершини s. Чи виконається для критеріїв?
Дані: Граф G = без ізольованих вершин, поданий списками інцидентності ЗАПИС[v], v Î V.
Результати: Безліч ребер всіх компонентів двозв'язності. Змінні MIN, GLN, CTEK,num- глобальні.
1 procedure BLOC(v,p);
3 num:=num+1; GLN[v]:=num;
5 for u Є ЗАПИС[v] do
6 if GLN[u]=0 then
8 СТЕК = GLN[v] then
стек останніми до (v-u) включно - блок, що зв'язує u всіх його нащадків.
14 e p) and (GLN[u] 1) блоків, а алгоритм справно працює для будь-якого графа, що містить блоків без вершин непарного ступеня, представлений списками інцидентності ЗАПИС[v], v Î V.
Результати: Ейлерів цикл, що зберігається в стеку EC.
2 СТЕК: = NIL; EC:=NIL;
3 k := довільна вершина G;
8 if ЗАПИС[v]<>0 then виходить з v>
10 u:= перша вершина списку ЗАПИС[v];