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

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

Базисная система циклов графа – это множество линейно-независимых по модулю два циклов, такое, что любой цикл графа выражается как линейная комбинация по модулю 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 вершинами можно построить nn-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) Удаление ребра из графа

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

Случайные записи:

Остовы полного графа


Похожие статьи:

  • Характеристические числа графов

    Цикломатическое число. Пусть задан граф без петель. Цикломатическим числом графа называют величину V(G)=r-n+P,где n — число вершин графа, r — число его…

  • Глава 5. элементы теории графов

    Основные понятия теории графов. Теория графов представляет собой область дискретной математики, особенностью которой является геометрический подход к…

  • Устойчивость, покрытия, паросочетания в графе

    ОПР. Инвариантом графа G называется число, связанное с этим графом, которое принимает одно и то же значение на любом графе, изоморфном данному. Вершина…

Добавьте постоянную ссылку в закладки. Вы можете следить за комментариями через RSS-ленту этой статьи.
Комментарии и трекбеки сейчас закрыты.