Компоненти зв'язності лісу - дерева.
Граф G - дерево, якщо він зв'язний і число ребер на одиницю мкньше числа вершин.
Якщо G - дерево, тоді будь-яка ланцюг буде простою.
Будь-які дві вершини дерева можна з'єднати ланцюгом, притому простий.
Нехай G - дерево. Якщо додати одне ребро, то отримаємо рівно один простий цикл.
Поняття дерева має в теорії нрафов важливе значення, так це простий тип графів, і тому часто спочатку на ньому вивчаються теоретичні питання, поставлені для кінцевих графів. З іншого боку поняття дерева використовується для вирішення різних технічних завдань. Тобто має прикладне значення.
Рассмотрм одну з таких задач. Для цього введемо ще одне визначення.
Кістяком (що покриває деревом) графа називається його підграф, що є деревом і містить всі вершини графа.
Нехай потрібно n міст з'єднати мережею доріг. Вартість будівництва кожної дороги між двома містами відома. Побудуємо граф, в якому вершшіни - міста, ребра - дороги. Кожному ребру пріпішем вага, рівний вартості будівництва дороги. визначимо вагу остова, як суму ваг складових його ребер.
Проектування мережі доріг зводиться до побудови кістяка ГАРФ, що має мінімальну вагу. В силу зв'язності дерева виконається умова з'єднати кожне місто з кожної дорогою.
Розглянемо спочатку завдання побудови кістяка без урахування ваг його ребер. Ідея алгоритму полягає в тому, що проглядаються в довільному порядку ребра графа і св відповідно до правила приймається рішення про включення чергового ребра в остов.
Дане правило полягає в перевірці умови, при виконанні якого розглядається ребро утворює цикл з побудованим подграфом. Якщо умова виконується, то ребро не включають в остов і забарвлюють в червоний колір, якщо не виконується, то включають в остов і забарвлюють в зелений колір.
Робота алгоритму закінчується після того, як ациклический підграф виявиться зв'язковим і буде містити всі вершини графа.
Алгоритм побудови кістяка
Крок 1. Вибрати будь-який ребро і забарвити в зелений колір. Утворити підграф G1 з цього ребра. Виконати крок 2.
Варіант а. Пофарбувати ребро в зелений колір і сформувати підграф Gi + 1. додавши до компонентів подграфа Gi нову компоненту зв'язності - розглядається ребро. Виконати крок 2.
Варіант б. Пофарбувати ребро в зелений колір і сформувати підграф Gi + 1. об'єднавши дві компоненти зв'язності в одну. Виконати крок 2.
Варіант в. Пофарбувати ребро в зелений колір і сформувати підграф Gi + 1. додавши до однієї компоненті подграфа Gi розглядається ребро. Виконати крок 2.
Варіант р Пофарбувати ребро в червоний колір, якщо воно образут в побудованим підграфі цикл.
Побудуємо остов для графа, заданого діаграмою, не враховуючи вагу ребер.
Забарвимо ребро 1. v2> в зелений колір.
Забарвимо ребро 4. v5> в зелений колір, т.к має місце варіант а.
Забарвимо ребро 4. v1> в зелений колір, т.к має місце варіант б.
Забарвимо ребро 2. v5> в червоний колір, т.к має місце варіант р
Забарвимо ребро 4. v3> в зелений колір, т.к має місце варіант в.
Ациклический підграф містить всі вершини графа, значить остов побудований:
5. Цикловий ранг графа. Цикломатичне число
Якщо G (V, X) не є ациклічним графом, то в ньому можна виділити цикл.
Незалежними називаються цикли графа G, якщо вони відрізняються хоча б одним ребром.
Безліч всіх незалежних простих циклів, які можна виділити в мультиграфом складають циклової базис графа.
Кількість простих циклів в базисі називається цикломатическая числом або циклічним рангом графа G.
Обзначім цикломатичне число через n (G).
Якщо G (V, X) - зв'язний граф, то n (G) = m (G) - n (G) + p (G), де m (G) - кількість ребер в графі, n (G) - кількість вершин в графі, p (G) - кількість компонент зв'язності в графі.
Так, наприклад, для дерева не існує циклової базис, тому що в дереві m = n - 1, р = 1 (дерево - зв'язний граф). Тоді цикломатичне число дорівнює n (G) = n - 1 - n +1 = 0. Отже в базисі немає жодного циклу.
Розглянемо алгоритм знаходження циклового базису зв'язкового мультиграфом.
Якщо n (G) = 0, то граф ациклический, циклового базису не існує.
Нехай n (G)> 0. Виділимо в G будь кістяк Т. Нехай число вершин в графі G одно n, а число ребер - m. x1. x2, ..., xn-1 - ребра в Т (кістяк містить всі вершини графа, а по властивості дерева число ребер на 1 менше числа вершин), xn. xn + 1, ..., xm - інші ребра графа G (зауважимо, що n ³ 2, m ³ n). Число останніх ребер m - (n - 1) = m - n + 1, і збігається з цикломатическая числом зв'язного графа. Додаючи будь-яке з ребер xi (i = n, ..., m). до дерева Т, отримуємо деякий підграф графа G, з якого виділяємо простий цикл mi- (n-1). проходить через ребро xi. Діючи таким чином, знаходимо сукупність простих циклів 1. mm-n + 1>. Оскільки в кожному з циклів цієї системи є ребро, що не міститься в інших циклах, то отримана система незалежна, отже, є циклових базисом графа G.
Використовуючи даний алгоритм, визначимо циклової базис мультиграфом, представленого на малюнку:
Обчислимо цикломатичне число: n = 4, m = 8, p = 1, отже, n (G) = 8 - 4 + 1 = 5. Значить, циклової базис містить 5 незалежних циклів. Побудуємо кістяк:
Додамо по одному видалені з графа ребра і будемо, таким чином, отримувати прості цикли:
Отримали п'ять циклів, що становлять циклової базис графа.