фундаментальні цикли
Компактне представлення простору дає його базис. Якщо виписати всі прості цикли графа, то це в більшості випадків не буде його базисом, так як деякі з цих циклів можуть бути сумами інших (див. Приклад на рис. 7.1). Побудувати базис простору, що складається з простих циклів, можна наступним чином. Виберемо в графі який-небудь каркас. Нехай - все ребра графа, які не належать. Якщо додати до ребро, то в отриманому графі утворюється єдиний (простий) цикл. Таким чином, отримуємо сімейство з циклів, вони називаються фундаментальними циклами щодо каркаса.
Теорема 2. Безліч всіх фундаментальних циклів щодо будь-якого каркаса графа утворює базис простору циклів цього графа.
Доведення. Зафіксуємо деякий каркас і розглянемо фундаментальні цикли щодо цього каркаса. У кожному з цих циклів є ребро, що належить даному циклу і не належить ніякому з інших. Тому при додаванні цього циклу з іншими фундаментальними циклами дане ребро не «знищиться" - воно буде присутній в сумарному графі. Отже, сума різних фундаментальних циклів ніколи не буде порожнім графом, тобто фундаментальні цикли лінійно незалежні.
Покажемо тепер, що будь-який квазіцікл графа є сумою фундаментальних циклів. Дійсно, нехай - такий квазіцікл. Нехай - все ребра, які не належать. Розглянемо граф. Кожне з ребер,, входить рівно в два доданків цієї суми - в і в. Отже, при додаванні всі ці ребра знищаться. Всі інші ребра, присутні в графах-доданків, належать. Значить, - підграф графа. Так як всі складові є квазіцікламі. значить, - теж квазіцікл. Але в немає циклів, тому є єдина можливість:, звідки отримуємо.
З цієї теореми випливає, що розмірність простору циклів графа дорівнює числу ребер, що не входять в його каркас. Так як каркас містить ребер, де - число компонент зв'язності графа, то ця розмірність дорівнює. Це число називають цикломатическая числом графа.
Побудова бази циклів
Базис простору циклів графа коротко називають базою циклів. На підставі теореми 2 можна запропонувати досить простий спосіб побудови бази циклів графа. Спочатку знаходиться який-небудь каркас, потім для кожного ребра, що не належить каркасу, відшукується той єдиний цикл, який це ребро утворює з ребрами каркаса. Таким чином, будь-який алгоритм побудови каркаса може бути використаний для знаходження бази циклів.
Пошук в глибину особливо зручний завдяки основному властивості DFS-дерева (теорема 1 з "Пошук в глибину") - кожне зворотне ребро щодо цього дерева є поздовжнім. Це означає, що з двох вершин такого ребра одна є предком інший в DFS-дереві. Кожне таке ребро в процесі пошуку в глибину зустрінеться двічі - один раз, коли активної вершиною буде предок, іншим разом, коли нею буде нащадок. В цьому останньому випадку шуканий фундаментальний цикл складається з розглянутого зворотного ребра і ділянки шляху в DFS-дереві. з'єднує ці дві вершини. Але цей шлях так чи інакше запам'ятовується в процесі обходу в глибину. так як він необхідний для подальшого повернення. Якщо, наприклад, для зберігання відкритих вершин використовується стек. то вершини цього шляху знаходяться у верхній частині стека. У будь-якому випадку цей шлях легко доступний і цикл знаходиться без праці. Запишемо процедуру побудови фундаментальних циклів на базі алгоритму пошуку в глибину з побудовою DFS-дерева. Змінна - лічильник циклів, - послідовність (список) вершин, що становлять цикл з номером.
Алгоритм 1. Побудова бази циклів.
- позначити всі вершини як нові
- fordoif нова then
- відкрити вершину
- while відкрита do
- if є недосліджене ребро
- then помітити ребро як досліджене
- if вершина нова
- then відкрити вершину
- else
- else закрити вершину
- Створити список з одного елемента
- repeat
- додати до списку
- until
Хоча сам пошук в глибину виконується за лінійний від числа вершин і ребер час, вирішальний вплив на трудомісткість цього алгоритму надає необхідність запам'ятовувати зустрічаються цикли. Підрахуємо сумарну довжину цих циклів для повного графа з вершинами. DFS-дерево в цьому випадку є простим шляхом, щодо нього буде циклу довжини, циклу довжини цикл довжини. Сума довжин всіх фундаментальних циклів дорівнюватиме
Таким чином, на деяких графах число операцій цього алгоритму буде величиною порядку.