· Граф – пара множеств 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) называется последовательность v1x1v2x2v3...xkvk+1.
· Цепь – незамкнутый маршрут (путь), в котором все рёбра (дуги) попарно различны.
· Простая цепь – цепь, в которой все вершины попарно различны.
· Цикл (контур) - замкнутый маршрут (путь), в котором все рёбра (дуги) попарно различны.
· Простой цикл (контур) - цикл (контур), в котором все вершины попарно различны.
|
|
· Длина пути – число рёбер (дуг) в маршруте (пути).
· Путь в графе называется минимальным, если он состоит из минимального количества рёбер.
· Орграф D называется нагруженным, если на множестве дуг Х определена весовая функция – длина дуги хÎХ.
· Путь называется минимальным в нагруженном графе или орграфе, если он имеет минимальную длину пути.
· Матрица смежности (графа, орграфа): А = [aij], V = {v1,…,vn},
X = {x1,…,xm}
· Матрица инцидентности: B = [bij]
(орграфа D)
(графа G)
· Матрица достижимости T = [tij]
· Матрица связности S = [sij]
(орграфа 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. Начало работы. Все вершины графа считаются новыми (не просмотренными). Берем произвольную вершину v0, записываем ее в стек и помечаем, как просмотренную.
2. Обозначим через v вершину, которая находится на вершине стека. Ищем еще не просмотренную вершину u, такую, что существует ребро (v, u) (дуга <v, u> для ориентированного графа). Если такой вершины нет, то переходим к пункту 3. В противном случае помечаем найденную вершину u как просмотренную и записываем ее в стек. Повторяем текущий пункт 2.
3. Удаляем текущую вершину из стека. Если стек пуст, то все вершины графа просмотрены. Алгоритм заканчивает работу. Иначе переходим к предыдущему пункту 2.
Рисунок 1 – Пример графа
Рассмотрим работу алгоритма на примере графа, представленного на рисунке 1.
Обход графа в глубину. Будем схематично изображать стек развернутым по горизонтали. Считаем, что вершина стека находится слева.
Порядок просмотра вершин следующий:
v1 v2 v4 v6 v5 v8 v9 v7 v3 v13 v12 v10 v11.
· Обход графа в ширину – основывается на замене стека, используемого при обходе в глубину, очередью 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 обозначаем FW1(v). Полагаем k=1;
2. если FWk(v)=Æ или выполняется k=n-1, w Ï FWk(v), то вершина w не достижима из v, и работа алгоритма на этом заканчивается. В противном случае переходим к шагу 3;
3. если wÏFWk(v), то переходим к шагу 4. В противном случае существует путь из v в w длины k, и этот путь является кратчайшим. Последовательность вершин vw1w2…wk-1w, где
4. помечаем индексом k+1 все непомеченные вершины, которые принадлежат образу множества вершин с индексом k. Множество вершин с индексом k+1 обозначаем FWk+1(v). Присваиваем k:=k+1 и переходим к шагу 2.
Замечание: Множество FWk(v) обычно называют фронтом волны k -го уровня.
Замечание: Вершины w1w2…wk-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. , следовательно - длина минимального пути из в . Определяем оптимальное количество ребер в минимальном пути, т.е. найдем , , , т.е. -минимальное число ребер в пути всех минимальных путей из в ;
4. определяем номера вершин минимального пути.
Причем =1, = , =0. Тогда искомый минимальный путь можно записать как … .
· Эйлеровый (Эйлерова) цикл (цепь) – цикл (цепь), который (которая) проходит по одному разу через каждое ребро псевдографа G.
Теорема 1. Конечный граф G Эйлеров тогда и только тогда, когда он связен и степени всех его вершин четны.
· Гамильтоновый (Гамильтонова) цикл (цепь) -цикл (цепь), который (которая) проходит через вершину псевдографа G ровно один раз.