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

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

Цикломатическая матрица:

Цикломатическим числом графа ν(G) – называется число базисных циклов, через которые можно выразить любой другой цикл.

ν(G)=m-n+1, где m – сигнатура; n – множество вершин.

Для приведенного выше графа ν(G)=5-4+1=2, т.е. имеется 2 независимых цикла и что можно убрать 2 ребра так, чтобы получился связанный граф без циклов.

Теорема Эйлера: число элементов базисной системы циклов графа постоянно и равно его цикломатическому числу.

(12) Топологическая сортировка графа.

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

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

2) Уровень n0 образует множество вершин x, для которых S^- (x)=0 т.е.вершины в которых в соот. стлбцах вектора n1 стоят нули

3)Из матрицы удаляются стороки соот. вершинам нулевого уровня. Если после удаления строки нулевых элементов не образовалось, то в исх. графе имеются циклы и граф сортировке не поддается. Эта процедура имеет max число шагов, равное числу вершин n

(11) Деревья. Остовное дерево минимального веса.

Дерево - это связный ациклический граф. Связность означает наличие путей между любой парой вершин, ацикличность - отсутствие циклов и то, что между парами вершин имеется только по одному пути. Если из графа удалить ν ребер(ню – цикломатическое число) и при этом граф остается связным, то получаем остов графа(остовное дерево).

Теорема Кэли. На помеченном полном графе с 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, то выбор начальной вершины не имеет принципиального значения. Будем каждой очередной вершине присваивать пометку (xi)=1, если вершина xi принадлежит поддереву Xp, и (xj)=0 – в противном случае.

Алгоритм имеет вид:

.

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

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

Это граф , у которого носитель совпадает с исходным графом и множество дуг есть дополнение для множества дуг U.

2) Объединение графов

При условии, что не пересекаются

G = (x, U) у которого множество вершин объединены с и дуги образованы с .

3) Сумма графов

Граф G = (x, U) образован путем объединения графов и построения полного двудольного графа, у которого одна доля представляет собой множество , а 2 доля

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

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