6(23) Алгоритм Беллмана-Мура (алгоритм корректировки меток)

Пусть G=(V,A) – сеть, s – вершиной начала пути, t – конец пути.

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

Всем вершинам приписываются метки, но нет деления на временные и постоянные. Корректировка меток идет по правилу [1]

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

Алгоритм состоит из двух этапов:

1. Нахождение длины кратчайшего пути от s до остальных вершин.

Шаг 1: присвоение начальных значений.

; ; ;

(множество вершин в очереди)

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

Шаг 2: Корректировка меток в очереди.

Удаляем из Q вершину, находящуюся в самом начале очереди. Для любой вершины , достижимой из , корректируем метку по формуле [1]. Если при этом , то корректируем очередь вершин. Иначе продолжаем перебор вершин и корректировку очереди:

Если не была раньше в очереди, и не находится в ней в данный момент, то ставим ее в конец очереди. Иначе переставляем ее в начало очереди.

Шаг 3: проверка на завершение 1 этапа.

Если , то возвращаемся на Шаг 2. Если , то первый этап закончен.

2. Строим сам путь от s к t.

Проводится аналогично второму этапу в алгоритме Дейкстры:

Шаг 4: последовательный поиск дуг кратчайшего пути. Среди вершин, непосредственно предшествующих с постоянными метками, находим , удовлетворяющую соотношению . Если это так, что включаем в искомый путь, и полагаем, что

Шаг 5: проверка на завершение второго этапа. Если , то кратчайший путь найден. В противном случае возвращаемся на Шаг 4

7(24). Деревья и их свойства. Лес.

Опр. Граф без циклов называется ациклическим или лесом.

Опр. Связный неориентированный ациклический граф называется деревом, т.е. деревья являются компонентами леса

Свойства деревьев:

Теорема1

Пусть G=(V,E) |V|=n (Граф порядка n) |E|=m

1. G - дерево

2. G – связный граф, m = n – 1

3. G – ациклический граф, m = n – 1

4. Любые две несовпадающие вершины графа соединяет единственная простая цепь

5. G – ациклический граф, обладающий тем свойством, что если какую-либо пару его несмежных вершин соединить в ребро, то его граф будет содержать ровно один цикл

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

1. существует ровно одна вершина ( V), называемая корнем. Которая не имеет предшествующих вершин P( )=0, P( ) – степень вершины

2. Любой вершине ≠ в графе непосредственно предшествует ровно одна вершина P( )=1

Опр. Вершины, отличные от корня называются узлами дерева

Опр. Висячая вершина ордерева называется листом

Опр. Путь из корня дерева в лист называется ветвью

Опр. Набольшая из длин всех ветвей ордерева называется его высотой

Опр. Расстояние от корня до некоторой вершины называется уровнем вершины.

Сам корень имеет уровень равный нулю.

Вершина одного уровня образует ярус ордерева.

Неориентированное дерево можно сделать ориентированным, выбрав в качестве корня произвольную вершину.

Если в качестве корня взять вершину , то получим ордерево:

- корень

- узлы

- листы

Высота = 4

Уровень = 0

Уровень = 3

Уровень = 2

Уровень = 3

Уровень = 4

Уровень = 4

Уровень = 1

Уровень = 2

Уровень = 2

1 ярус:

2 ярус: ,

3 ярус: ,

4 ярус:

(24)Опр. Подграф G’ = (V’,E’) неориентированного графа G = (V,E)называется остовным подграфом, если V’=V и G’ – это лес, который на любой компоненте графа G образует деревом.

Опр. Подграфом G’ = (,E’) графа G = (V,E) называется остовным поддеревом (каркасом), если V’=V и G’ – дерево.

Теорема2 (теорема Кэли)

Число различных деревьев, которые можно построить на n-различных вершинах, равно = n

В этой формулировке подсчитывается число всех деревьев с данными n)вершинами. Многие из этих деревьев изоморфны и возникает вопрос о числе неизоморфных деревьев среди них.

Это более сложная задача. И она решается для каждого конкретного случая по алгоритму Пойа.

Для подсчета числа остовов в графе используется матрица Кирхгофа.

Теорема 3 (Теорема Кирхгофа).

Число остовных деревьев в связном графе G (порядка ≥ 2) равно алгебраическому дополнению для любого элемента матрицы Кирхгофа. , где - элемент матрицы B; = P , если i=j и это степень вершины

Замечание: из определения =>сумма элементов в каждой строке и в каждом столбце матрицы Кирхгофа равна нулю => все алгебраические дополнения всех элементов матрицы B равны между собой.

Теорема 4

Число ребер произвольного неориентированного графа G, которые необходимо удалить для получения остова не зависит от последовательности их удаления и равно m – n + k,

где m – число ребер, n – число вершин, k – число компонент связности графа G

Доказательство: Дан граф G = (V,E), где |V| = m, |E| = n, k – число компонент связности графа G.

Рассмотрим i-ую компоненту связности графа G => это подграф . Пусть этот подграф содержит вершин. Обозначим за остов графа . Тогда – это дерево и содержит ( ) ребер.

=>для получения остова из компоненты нужно удалить ребер, где – число ребер в графе . Просуммируем удаляемые ребра по всем компонентам связности

Опр. Число (G)= m – n + k называется цикломатическим числом или циклическим рангом графа G

Опр. Число *(G)= n – k называется коциклическим рангом (корангом) графа G

Заметим, что *(G) равно числу ребер, входящих в любой остов графа G

(G) + *(G)=m

Из теоремы 4 => два следствия:

1. Неориентированный граф G является лесом <=>

2. Неориентированный граф имеет единственный цикл <=> Ѵ(G)=1