Основные понятия и определения

Элементы теории графов

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

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

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

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

Граф G задается множеством точек или вершин x(1), x(2),…, x(n) (которое обозначается через x(j)ÎX) и множеством дуг или ребер u(1), u(2),…, u(m) (которое обозначается символом u(i)ÎU), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается и задается парой (X,U), т.е. G(X,U). Граф G(X,U) считается заданным, если каждому элементу множества U соответствуют два элемента множества X.

Рис. 2.4.1. Граф с вершинами и ребрами.

Элементы множества Х называются вершинами, а элементы множества U - дугами или ребрами. Линии, соединяющие любые пары элементов множества Х называются дугами. Дуга графа имеет направление, обозначаемое стрелкой, которая направлена остриём от одного элемента множества X к другому. Дуги обозначается малыми буквами u с индексомu(k)ÎU. Ребром называется линия не имеющая направления (неупорядоченная) между любой парой элементов множества Х.

Граф G(X,U) все элементы множества U которого являются дугами, называется ориентированным (рис. 2.4.2а), если же все элементы множества U являются ребрами, то G(X,U) - неориентированный граф (рис. 2.4.2б). Если множество U содержит дуги и ребра, то G(X,U) - смешанный граф (рис. 2.4.2в).

Рис.2.4.2. Типы графов

Две вершины x(a) и x(b) являются граничными вершинами дуги u, если x(a) – конец дуги, а x(b) – начало дуги (рис. 2.4.3). Две дуги u₁ и u₂ называются смежными, если они различные и имеют общую граничную вершину (независимо от того, является ли эта вершина началом или концом дуги u₁ и u₂ ). Например, на рис. 2.4.3 смежными являются дуги u(a) и u(g), u(ε) и u(j), и т.д.

Две вершины множества X смежные, если они различны и существует дуга, идущая от одной из них к другой. Примерами смежных вершин на рис. 2.4.3 являются вершины x(a) и x(b); x(b) и x(c); x(c) и x(d) и т.д. Вершина называется изолированной, если она не соединена дугами с другими вершинами графа.

Дуга, начальная и конечная вершина которой совпадают, называется петлей. На рис. 2.4.3 дуга u(b) является петлёй.

Говорят, что дуга u исходит из вершины x(b), если x(b) является началом, но не является концом u, и что дуга заходит в x(b), если x(b) является концом, но не является началом u. В обоих случаях дуга u называется инцидентной вершине x(b) а вершина x(b) инцидентной дуге u. Например, на рис. 2.4.3 вершина x(b) инцидентна дуге u(α), а дуга u(a)ÎU инцидентна вершине x(a).

Рис. 2.4.3. Ориентированный граф

Две дуги u(a)ÎU и u(g)ÎU инцидентных друг другу, если обе они инцидентны одной и той же вершине x(b).

Две вершины x(b) и x(c) называются соседними (или смежными), если есть дуга u(g)ÎU, их соединяющая. Степень вершины Р(x(i)) равна числу дуг, инцидентных ей. На рис. 2.4.3. вершине x(c) инцидентны три дуги – u(g), u(s) и u(j), то есть Р(x(c)) = 3.

Для каждой вершины вводится понятие полустепени захода и полустепени исхода. Полустепень захода P⁺(x(i)) вершины x(i) - количество дуг, заходящих в данную вершину, а полустепень исхода Р^-(x(i)) вершины x(i) - количество дуг, исходящих из данной вершины.

Для графа, изображенного на рис. 2.4.3,

P⁺(x(с)) = 1, Р^-(x(с)) = 2, Р(x(c)) = P⁺(x(с)) + Р^-(x(с)) = 1 + 2 = 3.

Вершина называется входом, если P⁺(x(i))=0 (т.е. отсутствуют входящие дуги), а P^-(x(i))¹0 и называется выходом, если P⁺(x(i)) ¹0, P^-(x(i))=0. (т.е. отсутствуют исходящие дуги).

Путем в графе G(X,U) называется такая последовательность дуг (u(1), u(2),…, u(n)), в которой конец каждой предыдущей дуги совпадает с началом следующей дуги. На рис. 2.4.3 путь из x(b) в x(c) состоит из дуг u(e), u(j) и u(g),

Путь называется простым, когда в нем никакая дуга не встречается дважды, и составным, если какая-либо из дуг встречается более одного раза. Так путь из x(a) в x(d) на рис. 2.4.4 является простым путем и состоит из дуг u(a,b), u(b,c) и u(c,d).

Путь, в котором никакая вершина не встречается дважды, — элементарный путь. Примером элементарного пути на рис. 2.4.4 может служить путь u(а, с), u(с, d) или u(а,b), u(b,с), u(с,d).

Путь, проходящий через все вершины и притом толь­ко по одному разу, — называется гамильтонов путь. Путь, со­держащий все дуги графа, притом только по одному разу— эйлеров путь. Для графа, представленного на рис. 2.4.4, эйлерова и гамильтонова пути не существует.

Длина пути — число дуг последовательности m = (u(1), u(2),…, u(k)). Ветвь — путь, в котором начальная и конечная вершины являются узлами. На рис. 2.4.5 представлена ветвь — путь из x(2) в x(4), состоящий u(x(2), x(3)), u(x(3), x(4)).

Рис. 2.4.5. Ориентированный граф.

Дуга u(х(i), x(j)) называется замыкающей, если удаление ее не приводит к аннулированию пути из x(i) в x(j). На рис. 2.4.4 замыкающими являются дуги u(а, с), u(а, d), u(а, е).

Контур — конечный путь, начинающийся и заканчивающий в одной и той же вершине. Контур единичной длины называется петлей. Например, на рис. 2.4.5 петлей является контур, образованный дугой u(х(5), х(5)).

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

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

Разновидность графов. Граф, две вершины которого могут соединяться более чем одним дугой (ребром) называется мультиграфами (рис. 2.4.6).

а) Мультиграф

3

4

б) Подграф

в) двудольный граф

Рис. 2.4.6. Разновидность графов

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

Деревом называется связанные граф с числом вершин не менее двух, не содержащих циклов и петель. На рис. 2.4.7. представлен граф типа дерева.

Вершины, инцидентные только одному ребру дерева называются висячими. Каждое дерево имеет не менее двух висячих вершин. Степень висячей вершины дерева равна 1, т.е. P(x(i)) = 1.

x ₀ x₃

x₁ x₈

x₂ x₇

x₉ x₄ x₅

x₁₁ x ₅

x₁₄

x₁₀ x₁₆ x₁₂ x₁₃

Рис. 2.4.7. Иерархическое дерево

Вершины, инцидентные только одному ребру дерева называются висячими. Каждое дерево имеет не менее двух висячих вершин. Степень висячей вершины дерева равна 1, т.е. P(x(i)) = 1.

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

1. Дерево является связным графом.

2. Дерево не содержит циклов и петель

3. Число ребер дерева на единицу меньше числа вершин.

4. Дерево перестаёт быть связанным после удаления любого его ребра.

5. Каждая пара смежных вершин соединена только одним ребром.

6. Всякая пара несмежных вершин соединена цепью, притом только одной.

7. Удаление любого ребра нарушает связанность графа.

8. Дерево имеет по крайне мере две висячих вершины.

Не связанный граф без петель и циклов называется лесом. На примере рис. 2.4.7 лес получается удалением ребра из графа. Например, если удалить (х(0), х(1)) и (х(0), х(3)), то получим не связанный граф, состоящий из трех деревьев (трех компонент связанности).

Прадеревом называется ориентированное дерево. Корнем прадерева является вершина с полустепенью захода P+(x(i)) = 0, т.е. из корня прадерева дуги только выходят, но ни одна не заходит в корень. Пример прадерева показан на рис. 2.4.8.

x (0)

x (2)

x (5)

x (1) x (4) x (9)

x(7) x (6)

x (3)

x (8)

Рис. 2.4.8.Граф в виде дерева

Корнем прадерева в данном случае является вершина х(0). Уровень расположения вершин прадерева относительно его корня на­зывается рангом вершины. Ранг вершины определяется ее поряд­ковым номером по пути от корня прадерева до данной вершины, не считая самого корня.

Принимая, что корень х(0) имеет нулевой ранг (r(х(0))=0), для рассматриваемого примера получим следующие ранги всех вершин:

r(х(1))= r(х(2))=1;

r(х(3))= r(х(4))= r(х(5))=2;

r(х(6))= r(х(7))= r(х(8))= r(х(9))=3

Ориентированный граф G(X,U) называется подграфом графа G¹ (X¹,U¹), если справедливо: XÍX¹, UÍU¹. Формальное определение подграфа говорит о том, что если выбрана часть вершин X¹ графа, то в подграфе должны находиться все дуги U¹ соединяющие эти вершины. Подграф G (X,U) называется суграфом графа G ¹(X¹,U¹), если справедливо X=X*, UÍU¹.

Вершина x_i считается достижимой из x_j на G(X,U), если на этом графе существует путь из x_j в x_i. Каркасом G(X,U) с корнем в вершине Х_s орграфа G¹(X¹,U¹) называется суграф, для которого выполняются следующие условия:

1) вершины множества Х, достижимые из Х_s на ориентированном графе G ¹(X¹,U¹), достижимы из той же вершины на суграфе G (X,U);

2) = Х-1

На рис. 2.4.9а изображен ориентированный взвешенный граф G’ (X’,U’), а на рис. 2.4.9б - один из его каркасов с корнем в вершине Х₁ .

Весом каркаса P(G) будем называть сумму весов дуг, ему принадлежащих. Так, вес каркаса G(X,U), изображенного на рис. 2.4.9, равен:

P(G)= r(1,3) + r(3,2) + r(3,4) = 15

Задача формулируется следующим образом: на заданном ориентированном графе G ¹(X¹,U¹) требуется определить экстремальные каркасы с корнем в вершине Х₅ ÎX¹ , т.е. такие, сумма весов дуг которых минимальна или максимальна.

Экстремальные каркасы ориентированного графа показаны на рис. рис.2.4.10. Граф на рис. 2.4.10а, является минимальным каркасом, а на рис. 8.4.б - максимальным (с корнем в вершине Х₁).

а) min б) max

3 3

2 5 7

2 3 4 2 4

1 1 1

Рис. 2.4.10. Минимальный и максимальный каркасы исходного графа

Сетью называется конечный граф G (X,U)без циклов и петель, ориентированный в одном общем направлении от вершин V, являющихся входами графа, к вершинам W,являющихся выходами. При этом для каждой вершины Vполустепень захода, а для каждой вершины Wполустепень исхода соответственно равна нулю, т. е.

P⁺(v) = 0 и P^-(w) = 0.

Приведенный на рис. 2.4.11 граф является сетью с двумя входами V={x(1),x(2)} и тремя выходами W={x(6), x(7), x(8)}.

x(1) x(6)

x(3) x(4) x(7)

x(2) x(5) x(8)

Рис. 2.4.11. Граф , представленный в виде сети.

Очевидно, что для входов и выходов графа справедливы также выражения: U⁺ (v)= 0 и U^- (w)= Ø, Ø - знак пусто; где U⁺ (v) — множество дуг, входящих в вершины V;U^- (w)— множество дуг, выходящих из вершины W.

Транспортная сеть — это сеть, характеризуемая тремя признаками:

1) она имеет только один вход;

2) она имеет только один выход

3) каждой дуге такого графа соответствует некоторое целое положительное число с(u)³0,называемое пропускной способность данной дуги.

Граф, отображающий транспортную сеть, обозначается G (X, U, C(u)).

Пример транспортной сети приведен на рис. 2.4.12, где V=x(1) — вход, a W= x(6) — выход.

x(2) x(4)

x(1) x(6)

x(3) x(5)

Рис. 2.4.12. Транспортная сеть.

С транспортной сетью тесно связано понятие потока, под которым понимается некоторая функция j(u), удовлетворяющая сле­дующим условиям:

1. j(u) ³ 0, (uÎU);

2. j(u) ³ c(u);

3. å j(u) - å j(u) =0; (x(i)¹ v, x(i))¹w).

u ÎU^- x(i) u ÎU⁺ x(i)

Это означает, что функция j(u) - поток по дуге u, во-первых, есть целочисленное положительное число, во-вторых, не превы­шает пропускной способности данной дуги, в-третьих, сумма по­токов, входящих в некоторую вершину x(i) (не являющуюся входом или выходом), равна сумме потоков, выходящих из этой вершины.

Действительно, из третьего условия следует:

å j(u) = å j(u) = F(x(i)).

u ÎU^- x(i) u ÎU⁺ x(i)

где F(x(i)) — величина суммарного потока через вершины x(i).

Поток по дуге j(u) можно уподобить количеству протекающего по ней в единицу времени вещества. Тогда условие (3) является, по су­ществу, условием сохранения потока, выражающим положение о том, что в промежуточных вершинах потоки не создаются и не исчезают.

Разрез сети. Все множество вершин X данной транспортной сети всегда можно разбить на такие два взаимно дополнительных под­множества А и В, что

1. А ¹ В, А Î X и В Î X; 2. VÎA; 3. WÎ В.

Следовательно, в подмножестве А содержится вход сети и неко­торые промежуточные вершины, а в подмножестве В содержатся оставшиеся вершины, и в том числе выход сети W.

x(2) x(4) разрез

А

x(1) x(6)

x(3) x(5) В

Рис. 2.4.13.Разрез графа

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

С (U_b) = å с(u).

uÎ U_b

Наибольшая величина потока F_max для заданной транспортной сети определяется минимальной величиной разреза С_min (U_b) этой сети, т.е.

F_max = С_min (U_b)

Ещё одно определение разреза связанно с понятием компоненты связанности графа, т.е. множество ребер, исключение которых из графа увеличивает число его компонент, называется разрезом.

Вершина, которая имеет только выходящие дуги, называется источником, а вершина, в которую входят дуги, называется стоком.

Если каждой дуге (ребру) присвоен вес r(ij), то G(X,U) называется взвешенным графом.