Глава 4. Взвешенные графы и орграфы

3

Определения

.1. Функция веса

Взвешенным графом (орграфом)называется граф (орграф) со взвешенными вершинами и/или ребрами (дугами).

Во вершинно-взвешенном графе (орграфе)вводится дополнительная функцияER,R–вещественные числа, которая ассоциируется с каждой вершиной графа (орграфа). Эту функцию можно рассматривать как функцию, задающую «стоимость» вершины.

3.1.1. Графическое изображение

При графическом изображении взвешенного графа (орграфа) веса вершин ставятся около окружностей, изображающих вершины, а веса ребер - разрывах соответствующих ребер (дуг).

Замечание

Далее будут рассматриваться реберно-взвешенные графы (орграфы), которые кратко будут называться взвешенными графами (орграфами).

3.1.2. Матричное представление

Взвешенная матрица смежности

Для взвешенного графа (орграфа) взвешенная матрица смежности[A] размераnn,n=|V| задается следующим образом:

[A]=

w(v_i,v_j), если есть ребро (дуга) из вершиныv_i в вершинуv_j;

0 в остальных случаях,

где w(v_i,v_j)R– вес («стоимость») ребра (дуги).

Для простых графов взвешенная матрица смежности симметрична относительно главной диагонали.

Пример

Рис.3.1.2. Взвешенная матрица смежности графа и ее графическое представление

3.1.3. Таблица инциденций взвешенного

г

Определение

рафа и орграфа

Строка таблицы инциденцийсодержит вершинуV_iс перечислением всех инцидентных ей ребер (дуг) и их весами.

Пример

3.2. Минимальное каркасное

дерево графа

Определение

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

Пример

3.2.1. Алгоритм Краскала (Kruskal)

Определения

Алгоритм Краскала создает лес деревьев. Вначале лес содержитnпростых деревьев. На каждом шаге добавляется самое минимальное по весу ребро так, чтобы оно соединяло два дерева вместе.

Если выбранное ребро формирует цикл, то оно отбрасывается.

Инициализация алгоритма:

1. Создать лес, содержащий nтривиальных деревьев по одной вершине в каждом дереве (нет ребер);

2. Организовать приоритетную очередь ребер графа, организованную в порядке возрастания весов ребер.

Выполнение алгоритма:

3. До тех пор, пока в дереве не появится (n-1)-ребер,

выполнить:

1. Выбрать из очереди ребро с наименьшим весом;

2. Если ребро формирует цикл, то отбросить его, иначе добавить это ребро в лес.

Псевдокод

Замечания

1. Каждый шаг алгоритма Краскала будет соединять два дерева вместе, поэтому в конце алгоритма получится только одно дерево.

2. Сложность алгоритма O(mlogn),n=|V|,m=|E|.

Пример

Инициализация:

1. Строится лес из 5-ти тривиальных деревьев

2. Приоритетная очередь:

2{a,e}, 4{a,c}, 4{b,d}, 5{d,c}, 6{a,b}, 6{b,e}, 7{d,e}, 8{a,d}, 8{c,e}, 9{c,d}

Шаг 3.Выбор из очереди ребра 4{b,d}. Циклов нет.

Шаг 4. выбор из очереди ребра 5{b,c}. Циклов нет.

Шаг 5.Выбор из очереди ребра 6{a,b}. Появляется цикл (a,b,c). Ребро 6{a,b} отбрасывается.

Шаг 6.Выбор из очереди ребра 6{b,e}. Появляется цикл (a,b,c,e). Ребро 6(b,e) отбрасывается.

Шаг 7.Выбор из очереди ребра 7{d,e}. Появляется цикл (a,b,c,d,e). Ребро 7{d,e} отбрасывается.

Шаг 8.Выбор из очереди ребра 8{a,d}. Появляется цикл (a,c,b,d). Ребро 8{a,d} отбрасывается.

Шаг 9.Выбор из очереди ребра 8{c,e}. Появляется цикл (a,c,e). Ребро 8{c,e} отбрасывается.

Шаг 10.Выбор из очереди ребра 9{c,d}. Появляется цикл (b,c,d). Ребро 9{c,d} отбрасывается.

Алгоритм – стоп. Минимальное каркасное дерево (см.шаг 4) имеет вес 15.