Фундаментальные циклы ориентированного и неориентированного графа

Размещено на http://www.allbest.ru/

Содержание

Введение

1.Описание графа

1.1Основные понятия о графе

1.2Матрица смежности вершин

1.3Матрица инциденций вершин

1.4Список смежности вершин

1.5Массив ребер

2.Фундаментальные циклы графа

2.1Теоретическое введение

2.2Блок-схема алгоритма определения Фундаментальных циклов графа

Введение

1. Описание графа

1.1 Основные понятия о графе

Графом G=(X,U) называется совокупность двух конечных множеств: множество вершин X={x₁,…,x_n} и множество ребер (дуг) U={u₁,…,u_n}, состоящего из некоторых пар элементов (x_i,x_j) множества X.

Если пары вершин (x_i,x_j) в множестве U являются неупорядоченными, то граф называется неориентированным (неографом), а пары (x_i,x_j) - ребрами этого графа. Если пары вершин (x_i,x_j) в множестве U являются упорядоченными, то граф называется ориентированным (орграфом), а пары (x_i,x_j) - дугами, при этом дуги обозначаются <x_i,x_j>.

1.. Матрица смежности вершин

граф ребро вершина матрица

Матрицей смежности неориентированного графа G=(X,U) с n вершинами называется квадратная матрица А порядка n, элементы которой определяются следующим образом:

(1.2.1)

Для ориентированного графа:

(1.2.2)

Для неориентированного графа матрица смежности вершин симметрическая.

1.3 Матрица инциденций вершин

Матрицей инциденций неориентированного графа G=(X,U) с n вершинами и m ребрами называется матрица B размера nЧm, элементы которой определяются следующим образом:

(1.3.1)

Для неориентированного графа:

(1.3.2)

Таким образом, матрица инциденций вершин для графа, поставленного в задаче и представленного на рисунке 1.1, рассчитанная по формуле 1.3.1, будет выглядеть следующим образом:

Рисунок 1.1. Матрица инциденций вершин для графа

1.4 Список смежности вершин

1.5 Массив ребер

2. Фундаментальные циклы графа

2.1 Теоретическое введение

Зафиксируем некоторое множество и рассмотрим множество всех графов с множеством вершин . Буквой будем обозначать пустой граф из этого множества: .

Для графов и из определим их сумму по модулю (в дальнейшем в этом разделе будем называть ее просто суммой) как граф , где обозначает симметрическую разность множеств и . Иначе говоря, ребро принадлежит графу тогда и только тогда, когда оно принадлежит в точности одному из графов и . Пример показан на рис. 2.1.

Рис. 2.1. Определение суммы по модулю

Следующие свойства введенной операции очевидны или легко проверяются.

Коммутативность: для любых и .

Ассоциативность: для любых .

.

.

Отсюда следует, что множество относительно операции образует абелеву группу. Нейтральным элементом ("нулем") этой группы служит граф , а противоположным к каждому графу является сам этот граф. Уравнение с неизвестным и заданными графами и имеет единственное решение . Благодаря свойству ассоциативности мы можем образовывать выражения вида , не используя скобок для указания порядка действий. Легко понять, что ребро принадлежит графу тогда и только тогда, когда оно принадлежит нечетному количеству из графов .

Рассмотрим множество из двух элементов . Оно является полем относительно операций умножения и сложения по модулю 2. Определим операцию умножения элементов этого поля на графы: , для любого графа . Множество с введенными операциями сложения графов и умножения на элементы поля является линейным векторным пространством.

Зафиксируем некоторый граф и рассмотрим множество всех его остовных подграфов, которое будем обозначать . Это множество состоит из элементов, среди них сам граф и граф . Оно замкнуто относительно сложения графов и умножения на элементы поля, следовательно, является подпространством пространства . Его называют пространством подграфов графа .

Любой граф из может быть выражен как сумма однореберных подграфов. Всего у графа имеется однореберных подграфов и они, очевидно, линейно независимы. Следовательно, однореберные подграфы образуют базис пространства , а размерность этого пространства равна .

В пространстве можно очень естественным способом ввести координаты. Занумеруем ребра графа : . Теперь остовному подграфу можно поставить в соответствие характеристический вектор его множества ребер:

Получаем взаимно однозначное соответствие между множеством и множеством всех двоичных векторов с координатами. Сумме графов соответствует векторная (покоординатная) сумма по модулю 2 их характеристических векторов.

Компактное представление пространства дает его базис. Если выписать все простые циклы графа , то это в большинстве случаев не будет его базисом, так как некоторые из этих циклов могут быть суммами других. Построить базис пространства , состоящий из простых циклов, можно следующим образом. Выберем в графе какой-нибудь каркас . Пусть - все ребра графа , не принадлежащие . Если добавить к ребро , то в полученном графе образуется единственный (простой) цикл . Таким образом, получаем семейство из циклов, они называются фундаментальными циклами относительно каркаса .

Теорема. Множество всех фундаментальных циклов относительно любого каркаса графа образует базис пространства циклов этого графа.

Доказательство. Зафиксируем некоторый каркас и рассмотрим фундаментальные циклы относительно этого каркаса. В каждом из этих циклов имеется ребро , принадлежащее данному циклу и не принадлежащее никакому из остальных. Поэтому при сложении этого цикла с другими фундаментальными циклами данное ребро не "уничтожится" - оно будет присутствовать в суммарном графе. Следовательно, сумма различных фундаментальных циклов никогда не будет пустым графом, то есть фундаментальные циклы линейно независимы.

Покажем теперь, что любой квазицикл графа является суммой фундаментальных циклов. Действительно, пусть - такой квазицикл. Пусть - все ребра , не принадлежащие . Рассмотрим граф . Каждое из ребер , , входит ровно в два слагаемых этой суммы - в и в . Следовательно, при сложении все эти ребра уничтожатся. Все остальные ребра, присутствующие в графах-слагаемых, принадлежат . Значит, - подграф графа . Так как все слагаемые являются квазициклами, значит, - тоже квазицикл. Но в нет циклов, поэтому имеется единственная возможность: , откуда получаем .

Из этой теоремы следует, что размерность пространства циклов графа равна числу ребер, не входящих в его каркас. Так как каркас содержит ребер, где - число компонент связности графа, то эта размерность равна . Это число называют цикломатическим числом графа.

Построение базы циклов

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

Поиск в глубину особенно удобен благодаря основному свойству DFS-дерева - каждое обратное ребро относительно этого дерева является продольным. Это означает, что из двух вершин такого ребра одна является предком другой в DFS-дереве. Каждое такое ребро в процессе поиска в глубину встретится дважды - один раз, когда активной вершиной будет предок, другой раз, когда ею будет потомок. В этом последнем случае искомый фундаментальный цикл состоит из рассматриваемого обратного ребра и участка пути в DFS-дереве, соединяющего эти две вершины. Но этот путь так или иначе запоминается в процессе обхода в глубину, так как он необходим для последующего возвращения. Если, например, для хранения открытых вершин используется стек, то вершины этого пути находятся в верхней части стека. В любом случае этот путь легко доступен и цикл находится без труда. Запишем процедуру построения фундаментальных циклов на базе алгоритма поиска в глубину с построением DFS-дерева. Переменная - счетчик циклов, - последовательность (список) вершин, составляющих цикл с номером .

Алгоритм 1. Построение базы циклов.

пометить все вершины как новые

for do if новая then

Procedure

открыть вершину

while открытая do

if имеется неисследованное ребро

then пометить ребро как исследованное

if вершина новая

then открыть вершину

else

else закрыть вершину

Procedure

Создать список из одного элемента

repeat

добавить к списку

until

Хотя сам поиск в глубину выполняется за линейное от числа вершин и ребер время, решающее влияние на трудоемкость этого алгоритма оказывает необходимость запоминать встречающиеся циклы. Подсчитаем суммарную длину этих циклов для полного графа с вершинами. DFS-дерево в этом случае является простым путем, относительно него будет цикла длины , цикла длины цикл длины . Сумма длин всех фундаментальных циклов будет равна:

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

Рационализация

Приведенный алгоритм нетрудно модифицировать так, что он будет строить базу циклов с суммарной длиной, ограниченной сверху величиной порядка (и такой же будет оценка трудоемкости алгоритма). Рассмотрим в графе произвольную вершину и пусть - все ее предки в DFS-дереве, соединенные с обратными ребрами. Положим также . Обозначим через для путь в DFS-дереве, соединяющий и . Описанный выше алгоритм выдает циклы вида , . Рассмотрим циклы , . Так как , то совокупность всех таких циклов также образует базу циклов графа. Назовем эту систему циклов сокращенной. Алгоритм легко модифицировать так, чтобы вместо циклов выдавались циклы - нужно только после обнаружения обратного ребра, ведущего от предка к потомку (строка 11), выписать вершины, содержащиеся в стеке, начиная с и заканчивая следующей вершиной, смежной с . Для эффективной проверки этой смежности удобно использовать матрицу смежности.

Оценим суммарную длину циклов сокращенной системы. Предположим, что граф имеет вершин и ребер. Каждое обратное ребро принадлежит не более чем двум циклам сокращенной системы. Значит, суммарный вклад обратных ребер в не превосходит .

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

2.2. Блок-схема алгоритма фундаментальных циклов графа

Процедура Tsikl

Заключение

В ходе проделанной работы были закреплена теоретическая часть в области описания и расчетов графов.

Литература

1. Бондарев В.М., Рублинецкий В.И., Качко Е.Г. «Основы программирования» -- Харьков: Фолио; Ростов н/Д: Феникс, 1997.

2. Емеличев Р.И., Мельников О.И., Сарванов В.И., Тышкевич Р.И. «Лекции по теории графов» -- М.: Наука, 1990.

3. Липский В. «Комбинаторика для программистов» : Пер. с польск. - М.: Мир, 1988. - 213 с.

Размещено на Allbest.ru