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

Теоретическая часть

Рассмотрим чертеж вида

Обозначения и определения

V - множество точек - вершины;

X - множество линий - ребра;

Графом называется совокупность множеств вершин и ребер.

v - номер вершины;

{v, w} - обозначение ребра;

{v, v} - петли;

Одинаковые пары - параллельные или кратные ребра;

Кратностью ребер называют количество одинаковых пар.

Пример: кратность = 3.

Если в графе есть петли и / или кратные ребра, то такой граф называют псевдографом.

Псевдограф без петель называется мультиграфом.

Мультиграф в котором ни одна пара не встречается более одного раза называется графом.

Если пары (v, w) являются упорядоченными, граф называется ориентированным (орграфом).

Ребра ориентированного графа называются дугами.

В неориентированном графе ребра обозначаются неупорядоченной парой - {v, w}.

В ориентированном графе дуги обозначаются упорядоченной парой - (v, w).

G, G₀ - неориентированный граф, D, D₀ - ориентированный.

Обозначают v, w - вершины, x, y, z - дуги и ребра.

Пример

1) V={v₁, v₂, v₃, v₄},

X={x₁=(v₁, v₂), x₂=(v₁, v₂), x₃=(v₂, v₂), x₄=(v₂, v₃)}.

2) V={v₁, v₂, v₃, v₄, v₅},

X={x₁={v₁, v₂}, x₂={v₂, v₃}, x₃={v₂, v₄}, x₄={v₃, v₄}}.

Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. (Для орграфа то же).

Подграф наз. собственным, если он отличен от самого графа.

Говорят, что вершина w орграфа D (графа G) достижима из верш. v, если либо w=v, либо существует путь (маршрут) из v в w.

Граф (орграф) наз связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v и w.

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

Псевдографом, ассоциированным с ориентированным псевдографом D=(V, X) наз. псевдограф G=(V, X₀), в котором X₀ получается из X заменой всех упорядоченных пар (v, w) на неупорядоченные {v, w}.

Орграф наз слабо связным, если связным является ассоциированный с ним псевдограф.

Если граф (орграф) не является связным (слабо связным), то он наз. несвязным.

Компонентой связности графа G (сильной связности орграфа D) наз. его связный (сильно связный) подграф, не являющийся собственным подграфом никакого другого связного (сильно связного) подграфа графа G (орграфа D).

Примеры

опр || назовем орграф D=(V, X) нагруженным, если на множестве дуг X определена некоторая функция , которую называют весовой функцией

Числа - вес дуги, (цена дуги).

Для любого пути П нагруженного орграфа D обозначим через l(П) сумму длин дуг, входящих в путь П. (Каждая дуга считается столько раз, сколько она входит в путь П).

Величина l называется длиной пути. Если выбрать веса равными 1, то придем к ненагруженному графу.

Деревья и циклы

Граф G называется деревом, если он является связным и не имеет циклов. Граф G называется лесом, если все его компоненты связности - деревья.

Деревья обладают следующими свойствами:

1) Граф G есть дерево.

2) Граф G является связным и не имеет простых циклов.

3) Граф G является связным и число его ребер ровно на 1 меньше числа вершин.

4) две различные вершины графа G можно соединить единственной (и при этом простой) цепью.

5) Граф G не содержит циклов, но, добавляя к нему любое новое ребро, получаем ровно один и притом простой цикл.

Если у дерева G имеется, по крайней мере, 1 ребро, то у него найдется висячая вершина.

Предположим, что в графе G нет висячей вершины, тогда найдется цикл (в начале лекции это было доказано), тогда граф - не дерево.

Пусть G связный граф, а висячая вершина в G, граф получается из G в результате удаления вершины и инцидентного ей ребра. Тогда тоже является связным.

Пусть G - дерево с n-вершинами и m-ребрами. Тогда m(G)=n(G) - 1.

Если m<n-1 то граф не связный.

Если m>n-1, и висячих вершин в графе нет, то можно выделить цикл, а следовательно, это - не дерево. В противном случае удалим висячую вершину вместе с инцидентным ей ребром. Повторяя эту операцию n-2 раза, придем к графу с двумя вершинами и более чем одним ребром это не дерево.

Пусть G - дерево. Тогда любая цепь в G будет простой.

Если цепь - не простая, то в G есть циклы G - не дерево.

Цепь единственна по той же причине.

Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

Пусть G - связный граф. Тогда остовное дерево графа G должно содержать n(G) - 1 ребер. Значит, для получения остовного дерева из графа G нужно удалить ребер. Число называется цикломатическим числом графа G.

Алгоритм выделения остовного дерева

1) Выберем в G произвольную вершину , которая образует подграф, являющийся деревом. Положим i=1.

2) Если i=n(G), то задача решена и G_i - искомое остовное дерево графа G. Иначе переходим к п. 3.

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

Присваиваем i:=i+1 и переходим к шагу 2).

Замечание. Остовное дерево может быть выделено, вообще говоря, не единственным способом.

Если граф - нагруженный, то можно выделить остовное дерево с минимальной суммой длин содержащихся в нем ребер.

Алгоритм выделения минимального остовного дерева нагруженного графа

Существует 2 алгоритма для выделения минимального остовного дерева в нагруженном графе: алгоритм Прима и алгоритм Краскала.

Алгоритм Краскала

Идея алгоритма. Искомые ребра соединяют вершины. Поэтому возможны две стратегии построения. Можно идти от вершин и для каждой из них искать минимальное ребро (как это сделано в алгоритме Прима) а можно для каждого ребра выяснять можно ли его включить в строящееся дерево. Алгоритм Краскала предлагает делать это следующим образом. Во-первых, ребра графа пронумеровываем в порядке возрастания весов. Затем для каждого ребра начиная с первого проверяем соединяет или нет оно две несвязные вершины, если да, то его можно включить в остовное дерево. Ясно, что если мы имеем V вершин, то работа алгоритма начинается с V несвязных компонент графа (пока из графа все ребра исключаем). Для того, чтобы их связать необходимо найти V-1 ребро.

Другими словами, алгоритм организует процесс роста компонент связности в процессе которого он объединяются друг с другом до тех пор пока не останется одна являющаяся конечным результатом.

1) Входящие данные:

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

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

Результат:

2) Входящие данные:

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

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

Результат: