Цикломатичне число графа

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

Цикломатическая числом графа # 957; (G) - називається число базисних циклів, через які можна виразити будь-який інший цикл.

# 957; (G) = m-n + 1, де m - сигнатура; n - безліч вершин.

Для наведеного вище графа # 957; (G) = 5-4 + 1 = 2, тобто є 2 незалежних циклу і що можна прибрати 2 ребра так, щоб вийшов пов'язаний граф без циклів.

Теорема Ейлера: число елементів базисної системи циклів графа постійно і дорівнює його Цикломатичне число.

(12) Топологічне сортування графа.

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

1) всі вершини нумеруються від 1 до n

2) Рівень n0 утворює безліч вершин x, для яких S ^ - (x) = 0 т.е.вершіни в яких в соот. стлбцах вектора n1 стоять нулі

3) З матриці видаляються сторокой відповід. вершин нульового рівня. Якщо після видалення рядка нульових елементів не утворилося, то в вих. графі є цикли і граф сортуванні не піддається. Ця процедура має max число кроків, яка дорівнює кількості вершин n

(11) Дерева. Кістяк мінімальної ваги.

Дерево - це зв'язний ациклічний граф. Можливості підключення означає наявність шляхів між будь-якою парою вершин, ациклічності - відсутність циклів і те, що між парами вершин є тільки по одному шляху. Якщо з графа видалити # 957; ребер (ню - цикломатичне число) і при цьому граф залишається зв'язковим, то отримуємо остов графа (кістяк).

Теорема Келі. На позначеному повному графі з n вершинами можна побудувати n n-2 остов дерев.

Орієнтоване (спрямоване) дерево - ациклічності орграф (орієнтований граф, що не містить циклів), в якому тільки одна вершина має нульову ступінь заходу (в неї не ведуть дуги), а всі інші вершини мають ступінь заходу 1 (в них веде рівно по одній дузі ). Вершина з нульовим ступенем заходу називається коренем дерева, вершини з нульовим ступенем результату (з яких не виходить жодна дуга) називаються кінцевими вершинами або листям Теорема. У зв'язкового графі (M, N, T) знайдеться частковий зв'язний граф (M, N, T) В якому | M | - 1 = | N '| = K і можна перенумерувати вершини з M числами від Про до k, a дуги з N 'числами від l до k таким чином, що для будь-якої дуги u € N' викон.

Завдання про найкоротший остовном дереві: Нехай кожній дузі J графа (M, N, T) зіставлено невід'ємне число l [j] іменоване довжиною цієї дуги Потрібно побудувати таке кістяк (M, N, T) У якого сума Длин дуг була б мінімальна.

Алгоритм починає роботу з включення в поддерево початкової вершини. Оскільки остов дерево включає всі вершини графа G. то вибір початкової вершини не має принципового значення. Будемо кожної чергової вершині привласнювати позначку # 61538; (xi) = 1. якщо вершина xi належить Піддерево Xp. і # 61538; (xj) = 0 - в іншому випадку.

Алгоритм має вигляд:

Операції над графами.

1) Доповнення графа G = (x, U).

Це граф. у якого носій збігається з вихідним графом і безліч дуг є доповнення для безлічі дуг U.

2) Об'єднання графів

За умови, що не перетинаються

G = (x, U) у якого безліч вершин об'єднані з і дуги утворені с.

Граф G = (x, U) утворений шляхом об'єднання графів і побудови повного двудольного графа, у якого одна частка представляє собою безліч. а 2 частка

4) Видалення вершини x з графа G = (x, U)

5) Видалення ребра з графа