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

· Граф – пара множеств V и X - G = (V,X). V – множество вершин, X – множество ребер.

· Петля – ребро вида (v,v).

· Кратные рёбра – одинаковые пары в X.

· Кратность ребра {v,w} – количество одинаковых пар {v,w} в Х.

· Ориентированный граф (орграф D) – граф, для которого пары в Х упорядочены. Ребра в орграфе называются дугами и обозначаются <u,v>.

· Степенью вершины V графа G называется число d(v) рёбер графа, инцидентных вершине v. Если d(v) = 1, тогда v – висячая вершина, если d(v) = 0, тогда v –изолированная вершина.

· Полустепенью исхода (захода) вершины v орграфа D называется d⁺(v) – число дуг, исходящих из v (δ^- (v)- число дуг, заходящих в v).

· Маршрутом для графа G (путём для орграфа D) называется последовательность v₁x₁v₂x₂v₃...x_kv_k_+1.

· Цепь – незамкнутый маршрут (путь), в котором все рёбра (дуги) попарно различны.

· Простая цепь – цепь, в которой все вершины попарно различны.

· Цикл (контур) - замкнутый маршрут (путь), в котором все рёбра (дуги) попарно различны.

· Простой цикл (контур) - цикл (контур), в котором все вершины попарно различны.

· Длина пути – число рёбер (дуг) в маршруте (пути).

· Путь в графе называется минимальным, если он состоит из минимального количества рёбер.

· Орграф D называется нагруженным, если на множестве дуг Х определена весовая функция – длина дуги хÎХ.

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

· Матрица смежности (графа, орграфа): А = [a_ij], V = {v₁,…,v_n},

X = {x₁,…,x_m}

· Матрица инцидентности: B = [b_ij]

(орграфа D)

(графа G)

· Матрица достижимости T = [t_ij]

· Матрица связности S = [s_ij]

(орграфа D)

(графа G)

· Матрица длин дуг

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

· Минимальное остовное дерево (МОД) – остовное дерево нагруженного графа с минимальной суммой длин дуг содержащихся в нём.

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

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

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

Алгоритмы на графах

Алгоритм построения остовного дерева графа:

1. выбираем в графе G произвольную вершину , и строим подграф = {V = { }, X = Ǿ}, полагаем шаг алгоритма i:= 1;

2. если i= n, то - искомое дерево, конец алгоритма, иначе

3. = {V={ ,…, , X = U (, )} где ,…, – вершины . – какая-либо вершина смежная с новой присоединенной вершиной , i:= i+1, переход к пункту 2.

Алгоритм построения минимального остовного дерева графа:

1. выбираем ребро минимальной длины, = {V = { , }, X = (, )}; полагаем шаг алгоритма i:=1

2. если i=n, то - искомое минимальное остовное дерево, конец алгоритма, иначе

· добавляем к какой – либо вершине смежное с ней ребро, но минимальной длины, новая вершина которого не находится среди ранее выбранных. Полагаем i:=i+1 переход к пункту 1.

· Обход графа в глубину -основывается на идее использования стека (другие названия – возвратный ход, бектрекинг, обход графа в глубину). Применение правила LIFO (Last In First Out – последним пришел, первым обслужен) приводит к следующей стратегии: идти «вглубь» графа, пока это возможно (есть непросмотренные вершины), возвращаться и искать другой путь, когда таких вершин нет. Поиск продолжается, пока не просмотрены все вершины, достижимые из исходной.

Алгоритм построения обхода графа в глубину:

1. Начало работы. Все вершины графа считаются новыми (не просмотренными). Берем произвольную вершину v₀, записываем ее в стек и помечаем, как просмотренную.

2. Обозначим через v вершину, которая находится на вершине стека. Ищем еще не просмотренную вершину u, такую, что существует ребро (v, u) (дуга <v, u> для ориентированного графа). Если такой вершины нет, то переходим к пункту 3. В противном случае помечаем найденную вершину u как просмотренную и записываем ее в стек. Повторяем текущий пункт 2.

3. Удаляем текущую вершину из стека. Если стек пуст, то все вершины графа просмотрены. Алгоритм заканчивает работу. Иначе переходим к предыдущему пункту 2.

Рисунок 1 – Пример графа

Рассмотрим работу алгоритма на примере графа, представленного на рисунке 1.

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

Порядок просмотра вершин следующий:

v₁ v₂ v₄ v₆ v₅ v₈ v₉ v₇ v₃ v₁₃ v₁₂ v₁₀ v₁₁.

· Обход графа в ширину – основывается на замене стека, используемого при обходе в глубину, очередью FIFO (First In First Out – первым пришел, первым обслужен). Алгоритм обхода в ширину просматривает все вершины, достижимые из начальной. Происходит движение «вширь» графа, (сначала просматриваются все соседние вершины, затем соседи соседей и т.д.).

· Алгоритм построения обхода в ширину в графе:

1. Все вершины графа считаются новыми (не просмотренными). Берем произвольную вершину v0, записываем ее в очередь и помечаем как просмотренную.

2. Обозначим через v вершину, которая находится на выходе очереди. Ищем еще не просмотренную вершину u, такую, что существует ребро (v, u) (дуга <v, u> для ориентированного графа). Если такой вершины нет, то переходим к пункту 3. В противном случае помечаем найденную вершину u как просмотренную и записываем ее в очередь. Повторяем текущий пункт 2.

3. Удаляем текущую вершину из очереди. Если очередь пуста, то все вершины графа просмотрены. Алгоритм заканчивает работу. Иначе переходим к предыдущему пункту 2.

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

Рассмотрим работу алгоритма на графе из примера 1 (см. рис. 1).

Обход графа в глубину. Будем схематично изображать очередь развернутой по горизонтали. Считаем, что хвост очереди находится слева, а начало – справа.

Порядок просмотра вершин следующий:

v1 v2 v4 v12 v6 v7 v10 v11 v5 v9 v13 v3 v8.

· = - множество вершин, достижимых из .

· = - множество вершин, из которых достигается .

· Алгоритм построения компонент связности графа:

1. выбираем произвольную вершину графа (орграфа) , полагаем шаг k:= 1, ;

2. рассчитываем для нее ;

3. рассчитываем ;

4. рассчитаем компоненту связности ;

5. k: = k+1;

6. если V\ U ≠ Ǿ, тогда выбираем произвольную вершину из V\ U , переход к пункту 2, иначе конец алгоритма.

· Алгоритм Терри – это алгоритм поиска маршрута в связном графе G(V,W), соединяющего заданные вершины v и w ∈ V, где v ≠ w.

Исходя из v, осуществлять последовательный переход от каждой достигнутой вершины к смежной ей вершине, руководствуясь следующими правилами:

1. идя по произвольному ребру, всякий раз отмечать направление, по которому оно было пройдено и первое заходящее в v ребро;

2. исходя из v, всегда следовать только по тому ребру, которое не было пройдено, или было пройдено в противоположном направлении;

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

· Алгоритм фронта волны – это алгоритм поиска минимального пути из заданной вершины v в вершину w в неориентированном или орграфе.

1. помечаем вершину v индексом 0. Затем помечаем вершины, принадлежащие образу вершины v, индексом 1. Множество вершин с индексом 1 обозначаем FW₁(v). Полагаем k=1;

2. если FW_k(v)=Æ или выполняется k=n-1, w Ï FW_k(v), то вершина w не достижима из v, и работа алгоритма на этом заканчивается. В противном случае переходим к шагу 3;

3. если wÏFW_k(v), то переходим к шагу 4. В противном случае существует путь из v в w длины k, и этот путь является кратчайшим. Последовательность вершин vw₁w₂…w_k-1w, где

4. помечаем индексом k+1 все непомеченные вершины, которые принадлежат образу множества вершин с индексом k. Множество вершин с индексом k+1 обозначаем FW_k+1(v). Присваиваем k:=k+1 и переходим к шагу 2.

Замечание: Множество FW_k(v) обычно называют фронтом волны k -го уровня.

Замечание: Вершины w₁w₂…w_k-1вообще говоря, могут быть выделены неоднозначно. Эта неоднозначность соответствует случаям, когда существует несколько различных кратчайших путей из v и w.

· Алгоритм Форда – Беллмана - алгоритм решает задачу о нахождении кратчайших путей из одной вершины во все остальные для случая, когда веса ребер могут быть отрицательными. Кроме того алгоритм контролирует отсутствие циклов отрицательного веса, достижимых из исходной вершины.

Утверждение: для i=2,…,n, k≥0 (1)

для i=1, k≥0 (2)

1. вычислить таблицу значений , i=1 до n, k=0 до (n-1) по формулам (1), (2);

2. если , то - недостижима из в . Конец алгоритма, иначе

3. , следовательно - длина минимального пути из в . Определяем оптимальное количество ребер в минимальном пути, т.е. найдем , , , т.е. -минимальное число ребер в пути всех минимальных путей из в ;