Цикли - дуже важлива частина структури графа, з ними доводиться мати справу при вирішенні багатьох завдань. У графі може бути дуже багато циклів (див. Задачу 5.15), тому корисно мати кошти для компактного опису безлічі всіх циклів даного графа і маніпулювання ними. Одне з найбільш зручних засобів такого роду надає апарат лінійної алгебри.
Далі будемо розглядати графи з фіксованим безліччю вершин V. Буквою O будемо позначати порожній граф:.
Сумою по модулю 2 (надалі в цьому розділі будемо називати її просто сумою) двох графів і називається граф, де позначає симетричну різницю множин.
Наступні властивості введеної операції очевидні або легко перевіряються.
1) Комутативність: для будь-яких і.
2) Асоціативність: для будь-яких.
3) для будь-якого G.
4) для будь-якого G.
Звідси випливає, що безліч всіх графів з безліччю вершин V утворює абелеву групу щодо операції додавання по модулю 2. Нейтральним елементом ( «нулем») цієї групи служить граф O. а протилежним до кожного графу є сам цей граф. Рівняння з невідомим X і заданими графами G і H має єдине рішення. Завдяки властивості асоціативності ми можемо утворювати вирази виду, не використовуючи дужок для вказівки порядку дій. Легко зрозуміти, що ребро належить графу тоді і тільки тоді, коли воно належить непарному кількості з графів.
Розглянемо безліч з двох елементів. Воно є полем щодо операцій множення і додавання по модулю 2. Визначимо операцію множення елементів цього поля на графи:, для будь-якого графа G. Безліч всіх графів з безліччю вершин V при введених операціях складання графів і множення на елементи поля є лінійним векторним простором (т . е. підпорядковується аксіоматиці таких просторів).
Зафіксуємо деякий граф і розглянемо безліч всіх його остовних подграфов. Це безліч складається з елементів, серед них сам граф G і граф. Воно замкнуто щодо складання графів і множення на елементи поля, отже, є подпространством простору всіх графів. Його називають простором подграфов графа G.
У просторі подграфов можна природним способом ввести координати. Занумеруем ребра графа G.. Тепер остовному подграфа можна поставити у відповідність характеристичний вектор його безлічі ребер:
Отримуємо взаємно однозначна відповідність між безліччю подграфов і безліччю -мірних довічних векторів. Сумі графів відповідає векторна (покоординатно) сума по модулю 2 їх характеристичних векторів.
Далі в цьому розділі слово «цикл» будемо розуміти дещо інакше, ніж до сих пор.Іменно, циклом графа G будемназивать його кістяк підграф, у якого одна компонента зв'язності є простим циклом, а решта - ізольованими вершинами. Остовно підграф, у якого ступеня всіх вершин парні, називається квазіціклом. Таким чином, будь-який цикл є квазіціклом і граф Про - квазіцікл.
Теорема про квазіціклах.Множество всіх квазіціклов даного графа замкнуто щодо складання по модулю 2.
З цієї теореми випливає, що безліч всіх квазіціклов графа G є подпространством простору подграфов, воно називається простором циклів графа.
Компактне представлення лінійного векторного простору дає його базис. Базис простору циклів називають просто базисом циклів. Побудувати базис циклів можна наступним чином. Виберемо в графі G який-небудь каркас T. Нехай - все ребра графа G. які не належать T. Якщо додати до T ребро, то в отриманому графі утворюється єдиний цикл. Таким чином, отримуємо сімейство з s циклів, вони називаються фундаментальними циклами щодо каркаса T.
Теорема про фундаментальні ціклах.Множество всіх фундаментальних циклів щодо будь-якого каркаса T графа G утворює базис простору циклів цього графа.
З цієї теореми випливає, що розмірність простору циклів графа дорівнює числу ребер, що не входять в його каркас. Так як каркас містить ребер, де k - число компонент зв'язності графа, то ця розмірність дорівнює. Це число називають цикломатическая числом графа.
Каркас графа можна побудувати багатьма способами. Для побудови базису циклів графа особливо зручний пошук в глибину завдяки основному властивості DFS-дерева - кожне зворотне ребро щодо цього дерева є поздовжнім. Це означає, що з двох вершин такого ребра одна є предком інший в DFS-дереві. Кожне таке ребро в процесі пошуку в глибину зустрінеться двічі - один раз, коли активної вершиною буде предок, іншим разом, коли нею буде нащадок. В цьому останньому випадку шуканий фундаментальний цикл складається з розглянутого зворотного ребра і ділянки шляху в DFS-дереві, що з'єднує ці дві вершини. Але цей шлях так чи інакше запам'ятовується в процесі обходу в глибину, так як він необхідний для подальшого повернення. Якщо, наприклад, для зберігання відкритих вершин використовується стек, то вершини цього шляху знаходяться у верхній частині стека. У будь-якому випадку цей шлях легко доступний і цикл знаходиться без праці.
Хоча сам пошук в глибину виконується за лінійний від числа вершин і ребер час, вирішальний вплив на трудомісткість алгоритму надає необхідність запам'ятовувати зустрічаються цикли. Підрахуємо сумарну довжину фундаментальних циклів, отриманих за допомогою пошуку в глибину для повного графа з n вершинами. DFS-дерево в цьому випадку є простим шляхом, щодо нього буде циклу довжини 3, циклу довжини 4, ..., 1 цикл довжини n. Сума довжин всіх фундаментальних циклів дорівнюватиме
Таким чином, на деяких графах число операцій цього алгоритму буде величиною порядку.
З простором циклів тісно пов'язане простір розрізів графа. Нехай,. Розріз графа G. визначається безліччю А. - це кістяк підграф, ребрами якого є всі ребра графа, що з'єднують вершини з А з вершинами з.
Теорема про разрезах.Множество всіх розрізів даного графа замкнуто щодо складання по модулю 2.
Розріз, який визначається одноелементна безліччю А. називається елементарним. Базис простору розрізів зв'язкового графа можна отримати, якщо взяти всі його елементарні розрізи, крім одного (будь-якого). Для незв'язною графа це потрібно виконати для кожної компоненти зв'язності. Таким чином, розмірність простору розрізів графа з k компонентами дорівнює.
Нехай і - характеристичні вектори двох остовних подграфов графа G. Будемо говорити, що ці підграфи ортогональні. якщо. Це рівнозначно тому, що підграфи мають парне число загальних ребер.
Теорема про циклах і разрезах.Любой цикл даного графа ортогонален будь-якому його розрізу.
Так як сума розмірностей просторів циклів і розрізів дорівнює розмірності простору подграфов, то з цієї теореми випливає, що простору циклів і розрізів є ортогональними доповненнями один одного. Це можна використовувати для побудови базису циклів по матриці інцидентності. Продемонструємо це на прикладі. Нехай потрібно знайти базис циклів для графа, показаного на малюнку 8. Побудуємо його
матрицю інцидентності і видалимо з неї одну (будь-яку) рядок (в разі незв'язною графа видаляється по одному рядку з кожної компоненті зв'язності):
Рядки цієї матриці - характеристичні вектори елементарних розрізів, що утворюють базис розрізів. Так як простір циклів є ортогональним доповненням простору розрізів, то залишається знайти фундаментальну систему рішень системи лінійних однорідних рівнянь з цією матрицею (над полем з двох елементів). Для цього за допомогою операцій над рядками перетворимо матрицю так, щоб в перших шпальтах утворилася одинична подматріца:
Видаляємо перші чотири стовпці, що залишилася матрицю транспоніруем і приписуємо кт ній справа одиничну підматрицю:
Рядки отриманої матриці представляють базис циклів.