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

вершин и набор E неупорядоченных и упорядоченных пар вершин; обычно

граф обозначают как G(V, E).
Неупорядоченная пара вершин называется ребром, упорядоченная пара — дугой.

— ориентированным (или орграфом).
Пара вершин может быть соединена двумя или

более ребрами (или, соответственно, дугами одного направления), такие ребра (или дуги) называются кратными.
Дуга (или ребро) может начинаться и заканчиваться в одной и той же вершине, в этом случае соотв. дуга (или ребро) называется петлей.
Вершины, соединенные ребром или дугой, называются смежными.
Ребра, имеющие общую вершину, тоже называются смежными.
Ребро (или дуга) и любая из его вершин называются инцидентными.
Принято говорить, что ребро (u, v) соединяет вершины u и v, а дуга (u, v) начинается в вершине u и кончается в вершине v.

вершинам, которые соединены линиями, соответствующими ребрам (или дугам — в

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

мультиграф
д — смешанный граф
е — сеть

полный двудольный граф
г — дерево
д — планарный граф
е — регулярный

граф

если существует взаимно-однозначное соответствие между множествами вершин V, W и

множествами ребер E, I, сохраняющее отношение инцидентности.

вершин V  V и множеством ребер (дуг) E  E,

— такими, что каждое ребро (дуга) из E инцидентно (инцидентна) только вершинам из V.
Последовательность ребер (v0, v1), (v1, v2), ..., (vi-1, vi), (vi, vi+1), ..., (vr-1, vr) называется маршрутом, соединяющим вершины v0 и vr. Маршрут замкнут, если v0 = vr.
Маршрут называется цепью, если все его ребра различны, и простой цепью, если все его вершины различны.
Замкнутая (простая) цепь называется (простым) циклом.

максимальный связный подграф (то есть, не содержащийся в других связных

подграфах) графа G называется компонентой связности. Несвязный граф имеет, по крайней мере, две компоненты связности.
Связный граф с наименьшим числом ребер (или связный граф без циклов) называется деревом.
Граф называется k - связным (k - реберно - связным), если удаление не менее k вершин (ребер) приводит к потере свойства связности.
Маршрут, содержащий все вершины или ребра графа и обладающий определенными свойствами, называется обходом графа.
Длина маршрута (цепи, простой цепи) равна количеству ребер а порядке их прохождения. Длина кратчайшей простой цепи, соединяющей вершины vi и vj в графе G, называется расстоянием d (vi, vj) между vi и vj. В связном неориентированном графе расстояние удовлетворяет аксиомам метрики.

A) – орграф
Путь в D – последовательность вершин и дуг

u1, a1, u2, a2,..., ut, at, ut+1 , где t0, причем каждая вершина ui  V, а каждая дуга ai  A, и ai всегда является дугой (ui, ui+1). Путь обычно записывается последовательностью вершин u1, u2, ..., ut, ut+1.
Полупуть в D – последовательность вершин и дуг u1, a1, u2, a2,..., ut, at, ut+1, где t0, причем каждая вершина ui  V, а каждая дуга ai  A, и ai всегда является либо дугой (ui, ui+1), либо дугой (ui+1, ui). Полупуть также обычно записывается последовательностью вершин u1, u2, ..., ut, ut+1.

Пусть G = (V, E) – граф
Цепь в G – последовательность вершин и ребер u1, e1, u2, e2,..., ut, et, ut+1, где t0, причем каждая вершина ui  V, а каждое ребро ei  E, и ei всегда является ребром (ui, ui+1). Цепь обычно записывается последовательностью вершин u1, u2, ..., ut, ut+1.
Цепь = маршрут без повторений (каждое ребро проходится лишь один раз).
Аналогия — та же цепь (см. выше)
В определении полуцепи нет смысла — полуцепь всегда совпадает с соответствующей цепью.

полупуть, проходящий через все вершины D.
Простым путем или простым полупутем

в D называется путь или полупуть без повторяющихся вершин.
Замкнутым путем или полупутем в D называется путь или полупуть u1, a1, u2, a2,..., ut, at, ut+1, в котором ut+1=u1.
Полный замкнутый путь или полный замкнутый полупуть в D – полный путь или полный полупуть, который замкнут.

Полная цепь или полная полуцепь в G – цепь или полуцепь, проходящая через все вершины G.
Простой цепью в G называется цепь без повторяющихся вершин.

Замкнутой цепью в G называется цепь u1, u2, ..., ut, ut+1, в которой ut+1=u1.

Полная замкнутая цепь в G – полная цепь, которая замкнута.

u1, в котором все вершины различны.
Полуконтуром в D называется замкнутый

полупуть, u1, a1, u2, a2,..., ut, at, u1, в котором все вершины u1, u2, ..., ut и все дуги a1, a2,..., at различны.
Вершина ui достижима из вершины uj, если имеется путь из ui в uj.
Вершины ui и uj соединимы, если имеется путь из вершины ui в вершину uj или из вершины uj в вершину ui.
Длиной пути, полупути, простого пути, простого полупути, контура или полуконтура называется число дуг, содержащихся в них.
Расстояние d(ui, uj) от вершины ui и до вершины uj в D равно длине кратчайшего пути из ui в uj или не определено, если путь из ui в uj отсутствует.
Во взвешенном графе длиной и расстоянием обычно называют  с учетом веса ( весов).

Циклом в G называется замкнутая цепь u1, e1, u2, e2,..., ut, et, u1 , в которой все вершины различны.
Аналогия — тот же цикл(см. выше)
В определении полуцикла нет смысла — полуцикл всегда совпадает с соответствующим циклом.

Вершина ui, достижима из вершины uj, если имеется соединяющая их цепь.
Вершины ui и uj соединимы, если имеется соединяющая их цепь.

Длиной цепи, простой цепи или цикла называется число ребер, содержащихся в них.

Расстояние d(ui, uj) от вершины ui и до вершины uj в G равно длине кратчайшей цепи между ui и uj или не определено, если цепь между ними отсутствует.

сильно связным (сильным, категории связности 3), если для каждой пары

вершин ui и uj в D ui достижима из uj и ui достижима из ui.
Орграф D называется слабо связным (слабым, категории связности 1), если каждая пара вершин ui и uj в D соединима (полупутем).
Орграф D называется односторонне связным (односторонним, категории связности 2), если для каждой пары вершин ui и uj в D либо ui достижима из uj , либо uj достижима из ui.

Граф G называется связным, если каждая пара вершин ui и uj в G связана цепью.



Аналогия — см. выше


Аналогия — см. выше

B  A.
Порожденным подграфом в D называется подграф (W, B), в котором

B содержит все дуги из A, соединяющие вершины в W.

Сильной компонентой в D называется максимальный сильно связный (порожденный) подграф.

Подграфом в G называется граф (W, F), в котором W  V, F  E.
Порожденным подграфом в G называется подграф (W, F), в котором F содержит все ребра из E, соединяющие вершины в W.
Компонентой (связности) в G называется максимальный связный (порожденный) подграф.

G(V, E), а e1, e2, ... em — его ребра

(дуги).
Матрицей смежности вершин графа G называется матрица A=||aij||, i=1,...,n; j = 1, ..., n, у которой элемент aij равен числу ребер (или дуг), соединяющих вершины vi и vj (соответственно, идущих из вершины vi в вершину vj).
Матрицей инцидентности графа G называется матрица B=||bij||, i=1, .., n; j = 1, ..., m, у которой элемент bij равен 1, если вершина vi инцидентна ребру (дуге) ej и равен 0, если не инцидентна.
Наконец, граф можно задать посредством списков. Например,
вариант 1: списком пар вершин, соединенных ребрами (или дугами);
вариант 2: списком списков для каждой вершины множества смежных с ней вершин.

вершин)

aij равен числу ребер, соединяющих вершины vi и vj

(для неориентированного графа). Матрица симметричная.

aij равен числу дуг идущих из вершины vi в вершину vj (для ориентированного графа)

вершины, m – ребра (дуги),
Для неориентированного графа
bij

=1, если вершина vi инцидентна ребру ej
bij =0, если вершина vi не инцидентна ребру ej
Для ориентированного графа
bij =-1, если дуга ej выходит из вершины vi
bij =1, если дуга ej входит в вершины vi
bij =2, если дуга ej является петлей в вершине vi .
bij =0, если вершина vi не инцидентна ребру ej

вершин) на списки смежности для вершин.
Список для каждой вершины

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

X1 a x2 a x3 a x5 a 0
X2 a x2 a x5 a 0
X3 a 0
X4 a x3 a 0
X5 a x4 a 0
X6 a x1 a x5 a x6 a 0

добавление ребра или вершины, стягивание ребра (отождествление пары смежных вершин),

подразбиение ребра (т.е. замена ребра (u, v) на пару (u, w), (w, v), где w — новая вершина) и др.

у которого V=VU и E=E1E2

Соединение G1(V,E1) и G2(U,E2) есть граф

G(V,E), у которого V=VU и E=E1E2 (ребра соединяющие все вершины множеств V1 и V2)

Декартово произведение G1(V,E1)G2(U,E2). Результирующий граф имеет множество вершин W={(ViUj)}. Ребро между вершинами ViUj и VkUl существует если
А) Vi=Vk и существует ребро UjUl в графе G2
В) Uj=Ul и существует ребро ViVk в графе G1

V1

V2

U1

U2

U3

V1

V2

U1

U2

U3

V1U1

V1U2

V1U3

V2U1

V2U2

V2U3

Ребро между вершинами ViUj и VkUl существует если

А) Vi=Vk и существует ребро UjUl в графе G2

В) существует ребро ViVk в графе G1

V1

V2

U1

U2

U3

V1U1

V1U2

V1U3

V2U1

V2U2

V2U3

эффективности компьютерных алгоритмов
Пример. На выполнение алгоритмов А, В, С, D

и Е требуется n, 3n2, 2n2 + 4n, n3 и 2n элементарных операций соответственно.
Посчитаем время, необходимое для работы алгоритмов при n = 1, 10, 100 и 1000, если одна операция совершается за 1 миллисекунду

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

роста функции f(n) не больше, чем у g(n), если найдется такая положительная константы С, что | f(n) | <= | g(n) |. Этот факт обозначают как f(n) = O(g(n))

проходящий через каждое ребро графа в точности один раз, т.е.

путь v1, ..., vm+1, такой что каждое ребро e  E появляется в последовательности v1, ..., vm+1 в точности один раз как e = {vi, vi+1 } для некоторого i.
Если v1 = vm+1, то такой путь называется эйлеровым циклом. Задача существования эйлерова пути в заданном графе была решена Эйлером в 1736 году, и представленное им необходимое и достаточное условие существования такого пути считается первой в истории теоремой теории графов.
Теорема. Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более чем две вершины нечетной степени.

нечетной степени, представленный списками ЗАПИСЬ [v], v  V.
Результаты: Эйлеров

цикл, представленный последовательностью вершин в стеке СЕ.

v:= произвольная вершина графа;
CTEK v;
while CTEK  do

begin v:= top (CTEK); { v = верхний элемент стека }
if ЗАПИСЬ [v]  then
begin u:= первая вершина списка ЗАПИСЬ [v];
CTEK u;
{ удалить ребро {v, u} из графа }
ЗАПИСЬ [v] := ЗАПИСЬ [v] \ {u};
ЗАПИСЬ [u] := ЗАПИСЬ [u] \ {v};
v := u
end
else { ЗАПИСЬ [v] = }
begin v  CTEK ; СЕ  v;
end
end
end

в стек CTEK и удаляет ребро из графа, либо переносит

вершину из стека CTEK в стек CE. Таким образом, число итераций этого цикла — О(m). В свою очередь число шагов в каждой итерации ограничено константой.
Т.о. общая сложность алгоритма есть О(m).

каждый эйлеров путь является циклом, так как концы эйлерова пути,

не являющегося циклом, всегда вершины нечетной степени.
Предположим, что u и v — единственные вершины нечетной степени связного графа G = V, E, и образуем граф G* добавлением дополнительной вершины t и ребер {u, t} и {v, t} (или просто {u, v}, если {u, v} E ). Тогда G* — связный граф без вершин нечетной степени, а эйлеровы пути в G будут в очевидном взаимно однозначном соответствии с эйлеровыми циклами в G*.

один раз через каждую вершину (а не каждое ребро) данного

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

— это блок, содержащий только вершины степени 2 и две

несмежные вершины степени 3.

p  3 вершин. Если для всякого n, 1  n

< (p – 1)/2, число вершин, со степенями, не превосходящими n, меньше чем n, и для нечетного р число вершин степени (p – 1)/2 не превосходит (p – 1)/2, то G — гамильтонов граф.
Следствие (Дирака). Если p  3 и deg v  p/2 для любой вершины v графа G, то G — гамильтонов граф.

(то есть для которых пока не найдено быстрых алгоритмов решения,

но проверка того, является ли данное решение правильным, проходит быстро).
Ни для одной из NP-полных задач не известен полиномиальный алгоритм (т.е. с числом шагов, ограниченным полиномом от размерности задачи), причем существование полиномиального алгоритма для хотя бы одной из них автоматически влекло бы за собой существование полиномиальных алгоритмов для всех этих задач.

перебор всех возможностей: генерируем все n! различных последовательностей вершин и

для каждой из них проверяем, определяет ли она гамильтонов путь. Такие действия требуют по меньшей мере n! n шагов, но функция от n подобного вида растет быстрее, чем произвольный многочлен, и даже быстрее, чем произвольная экспоненциальная функция вида an, a > 1, ибо

v  V.
Результаты: Список всех гамильтоновых циклов графа G.

последовательности X[1], . . ., X[k – 1]: массив

X — глобальный }
begin
for y  ЗАПИСЬ [X[k – 1]] do
if (k = n +1) and (y = v0) then write(X[1], . . ., X[n], v0)
else if DOP[y] then
begin X[k] := y; DOP[y] := ложь;
ГАМИЛЬТ (k +1);
DOP[y] := истина
end
end; { ГАМИЛЬТ }
begin { главная программа }
for v  V do DOP[v] := истина; { инициализация }
X[1] := v0; { v0 = произвольная фиксированная вершина графа }
DOP[v0] := ложь;
ГАМИЛЬТ (2);
end.

и будет меньше, чем в случае полного перебора, однако же

в наихудшем случае растет по экспоненте с возрастанием размерности задачи.

побывав в каждом городе ровно один раз, сведя при этом

затраты на передвижение к минимуму.
Для решения задачи нам необходимо найти гамильтонов цикл минимального общего веса.
Эффективный алгоритм пока не известен. Для сложных сетей число гамильтоновых циклов непомерно велико. Рассмотрим алгоритм поиска субоптимального решения.
Алгоритм ближайшего соседа
Дан нагруженный граф с множеством вершин V. Цикл, полученный в результате работы, будет совпадать с конечным значением переменной маршрут, а его длина — конечное значение переменной w.

0;
v:=v;
Отметить v;
while останутся

неотмеченные вершины do
begin
Выбрать неотмеченную вершину u, ближайшую к v;
Маршрут := маршрут и;
w:= w + вес ребра v u;
v := u;
Отметить v
еnd
Маршрут := маршрут v;
w:= w + вес ребра v v
end

гамильтононовых циклов

связен и ацикличен.
Пусть G = V, E — граф

с n вершинами и m ребрами.
Необходимые и достаточные условия того, что G — дерево:
Любая пара вершин в G соединена единственным путем
G связен и m = n – 1
G связен и удаление хотя бы одного его ребра нарушает связность графа
G ацикличен, но если добавить хотя бы одно ребро, то в G появится цикл.

G, являющийся деревом и включающий в себя все вершины G,

называется остовным деревом.
Построение остовного дерева: Выбираем произвольное ребро и последовательно добавляем другие ребра, не создавая при этом циклов, до тех пор, пока нельзя будет добавить никакого ребра, не получив при этом цикла.
! Всего n -1 ребро!!!

минимального остовного дерева — это одна из немногих задач теории

графов, которую можно считать полностью решенной.
Задача о проведении дорог. Для каждой пары городов А и В известна стоимость С(А,В) строительства городов между ними. Нужно построить самую дешевую из все возможных сеть дорог. Искомый граф должен быть деревом, которое называют экономическим. Таким образом, задача состоит в нахождении алгоритма, определяющего среди nn–2 возможных деревьев, которые соединяют вершины, дерева наименьшей длины, определяемой как сумма его ребер.

Упорядочим ребра графа в порядке их неубывания их весов.
Шаг 2.

Начиная с первого ребра в этом списке, добавлять ребра в графе, соблюдая условие: такое добавление не должно приводить к появлению цикла.
Шаг 3. Повторять Шаг 2 до тех пор, пока число ребер в графе не станет равно n – 1. Получившееся дерево является минимальным остовным деревом графа.
Больше всего времени необходимо для выполнения сортировки — при m ребрах это m log2m операций. Но нужны только n – 1 ребро!
Для полных графов более эффективный алгоритм был предложен Примом и Дейкстрой.

с ближайшим по весу соседом.
Шаг 2. Найдите не присоединенную (еще)

вершину, ближе всего лежащую к одной из присоединенных, и соедините с ней.
Шаг 3. Повторять Шаг 2 до тех пор, пока все вершины не будут присоединены.