Лекции по дискретной математике. Глава 4 Часть 1 - файл n1.doc

Лекции по дискретной математике. Глава 4 Часть 1
скачать (588.5 kb.)
Доступные файлы (1):
n1.doc589kb.01.06.2012 12:07скачать

n1.doc

Глава 4. ВЗВЕШЕННЫЕ ГРАФЫ И ОРГРАФЫ




3

Определения

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




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

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

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


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



Замечание






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

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


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






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


[A]=

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

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

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

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

Пример









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

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

г

Определение

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




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

Пример








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

дерево графа


Определение






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

Пример






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


Определения







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

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




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

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

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

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

  1. До тех пор, пока в дереве не появится (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.



Замечания







Если размерность взвешенного графа растет, то возникает очевидная трудность определения цикла, возникающего при добавлении из очереди ребра.

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



Шаг 1. Из приоритетной очереди выбираем ребро {g,h}, которое создает первое нетривиальное дерево. Красный цвет выбран описателем этого дерева. Число ребер дерева равно 1.

Шаг 2. Ребро {c,i}из приоритетной очереди создает второе нетривиальное дерево. Синий цвет выбран описателем этого дерева. Число ребер каркасного дерева равно 2.




Шаг 3. Ребро {f,g} вошло в первое нетривиальное дерево, т.к. вершина g – красная, а f – белая. Красный цвет остался описателем этого дерева. Число ребер каркасного дерева - 3.




Шаг 4. Ребро {a,b}создает третье нетривиальное дерево. Зеленый цвет становится описателем этого дерева. Число ребер каркасного дерева равно 4.



Шаг 5. Добавляем ребро {c,f}. Вершина c – синяя, вершина f – красная. Ребро {c,f} яет первое и второе деревья. Красный цвет выбран в качестве описателя этого объединенного дерева. Число ребер каркасного дерева равно 5.



Шаг 6. Ребро {g,i} имеет одинаковые красные описатели вершин, следовательно, оно создает цикл. Отбрасываем его.



Шаг 7. Ребро {c,d}: вершина с имеет красный цвет, вершина d – белая. Добавляем ее к дереву. Описатели дерева – красные. Число ребер каркасного дерева равно 6.


Шаг 8. Вершины h и i ребра {h,i} – красные. Ребро создает цикл, отбрасываем его.




Шаг 9. Ребро{a,h} – вершина a – зеленая, вершина h – красная. Добавляем ребро {c,d}к дереву. Красный цвет остается описателем этого дерева. Число ребер каркасного дерева равно 7.




Шаг 10. Вершины b и c ребра {b,c}- красные. Добавление этого ребра приведет к созданию цикла. Отбрасываем его.



Шаг 11. Ребро {d,e}: вершина d – красная, а вершина e – белая. Добавляем это ребро к дереву. Вершины дерева – красные. Число ребер каркасного дерева равно 8, алгоритм стоп.



Вес минимального каркасного дерева = 38

Замечание






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

3.2.2. Алгоритм Прима (Prim)


Определения






Алгоритм Прима характеризуется следующим:





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

  1. Выбрать любую вершину графа (корень дерева).

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

  1. До тех пор, пока в дереве не появится n-1 ребер, выполнить:

    1. Создать очередь находящихся вне дерева и инцидентных вершине. Очередь организовать в порядке возрастания весов ребер.

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

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

Псевдокод



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


Пример






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

Начальная вершина (корень дерева) – вершина а.

В дереве n-1=5-1=4 ребра



Замечания







Как и для алгоритма Краскала, в алгоритме Прима для определения циклов можно воспользоваться описателями вершин, при этом понадобятся определители двух типов – для вершин дерева (красный цвет) и для всех остальных вершин (белый цвет).

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


Пример












3.2.3. Минимальное каркасное дерево для точек на евклидовой плоскости



Определение







Евклидовым минимальным каркасным деревом (Euclidean minimum spanning tree – EMST) является минимальное каркасное дерево множества точек на плоскости (или в более общем случае во многомерном пространстве), где веса ребер между каждой парой точек будет расстоянием между этими двумя точками.

Первый алгоритм решения задачи






  1. Строится полносвязный граф, связывающий заданные n точек.

  2. Рассчитываются расстояния между всеми вершинами графа по формуле

((xi –xj)2 +(yi – yj)2)1/2. Эти расстояния принимаются в качестве весов ребер графа.

  1. Алгоритмом Крускала или Прима строится минимальное каркасное дерево полученного взвешенного графа.

Пример






Координаты точек (x,y):

  1. (5,80);

  2. (34,93);

  3. (25,65);

  4. (50,65);

  5. (5,51);

  6. (33,41);

  7. (66,51);

  8. (15,10);

  9. (50,20);

  10. (75,30);

  11. (95,39);

  12. (84,9).






Минимальное каркасное дерево,

общая длина 280,75


Определения






Триангуляцией1 называется планарный граф, получающийся при соединении n вершин ребрами, такой, что нельзя добавить ни одного нового ребра без нарушения планарности (т.е. без пересечения ребрами друг друга где бы то ни было, кроме вершин).

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

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

Второй алгоритм решения







  1. По заданному множеству точек на плоскости (каждая точка является вершиной графа) построить триангуляцию Делоне.

  2. В качестве весов ребер взять их длину.

  3. Использовать алгоритм Прима или Краскала для нахождения минимального каркасного дерева.


Замечания






  1. Борис Николаевич Делоне предложил этот метод триангуляции в 1934 году в работах по вычислительной геометрии.

  2. Существуют эффективные алгоритмы построения триангуляции Делоне.



3.3. Минимальные каркасные деревья

с

Определения
ограничениями



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

В литературе можно найти свыше 30 вариантов двухкритериальных минимальных каркасных проблем, а также несколько многокритериальных проблем.

3.3.1. Минимальное каркасное дерево

с заданной степенью


Определения


Если потребовать, чтобы степень минимального каркасного дерева не превышала заданного числа, т.е. deg(Т)=k, k2, то возникает проблема нахождения минимального каркасного дерева с заданной степенью. Далее для краткости эта проблема будет называться k-MST проблемой (k-Minimum Spanning Tree problem).

2-MSP проблема является проблемой нахождения гамильтонова пути минимальной длины.

Класс сложности






k-MST проблема относится к NP-тяжелым при любом k.

Алгоритмы для k-MST проблемы на евклидовой плоскости






При задании графа G на евклидовой плоскости вес его ребер есть расстояние между смежными вершинами. Для данного случая было доказано, что существует минимальное каркасное дерево со степенью не более 5. Однако при k=3 проблема NP-тяжела, при k=4 доказательства нет.

Для решения k-MST проблемы на евклидовой плоскости существуют эвристические алгоритмы полиномиального времени (в частности, модифицированный алгоритм Прима (k-Prim algorithm)).

Весьма успешно применяются различные версии генетических и эволюционных алгоритмов.


3.3.2. Минимальное каркасное дерево с максимальным числом листьев


Определение






Для заданного взвешенного ненаправленного графа G=(V,E) найти минимальное каркасное дерево Т с максимальным числом листьев.

Класс сложности






П
Алгоритмы
роблема относится к NP-тяжелым.



Известны достаточно хорошие аппроксимационные алгоритмы, лучший из имеет сложность почти линейную в размерах графа. Аппроксимационное отношение алгоритмов – 2,5 – 3,0.

3.3.3. Каркасное дерево с кратчайшей

о

Определение
бщей длиной пути



Задан взвешенный ненаправленный граф G=(V,E) и положительное целое число B. Имеется ли каркасное дерево T=(V,F), FE, такое, что сумма всех путей между всеми возможными парами вершин u и v в этом дереве не превышала величину B?

Класс сложности






П
Алгоритмы
роблема относится к NP-тяжелым.



Имеются эвристические алгоритмы, позволяющие получить аппроксимационные отношения 2,15/8 и 3/2 за время О(n2+f(G)), O(n3) и O(n4) соответственно, где f(G) – время вычисления кратчайших путей между всеми парами вершин графа G, а n – число вершин графа G.

3.3.4. Каркасное дерево с ограничением диаметра


Определение


Для заданного взвешенного связного графа найти минимальное каркасное дерево с заданной нижней границей диаметра D2.

Класс сложности






Проблема относится к NP-тяжелой для 4Dn-1, где n – число вершин графа.

Алгоритмы






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

3

Определение
.3.5. Каркасное дерево оптимальной связи




Задан связный ненаправленный граф G=(V,E). На ребрах графа заданы:

  1. Запросы связи или передачи. Задаются матрицей запросов R=[rij], где rij – количество нагрузки, необходимое передать между вершинами vi и vj.

  2. Расстояния между вершинами vi и vj. Задаются матрицей расстояния w[vi,vj].

Найти минимальное каркасное дерево Т=(V,F),FE, с минимальным весом

W(T)= f(wij,rij).

Во многих случаях рассматриваются функции f вида f=wij*rij, где * - операция умножения.

Класс сложности






Проблема является NP-тяжелой.

Алгоритмы




За последние 10-15 лет для решения проблемы было предложено большое количество эволюционных и генетических алгоритмов.

3.3.6. Проблема многоцелевого минимального каркасного дерева


Определения






Для заданного связного ненаправленного графа G=(V,E) с n вершинами для каждого ребра задается K>1 неотрицательных целых числа. Эти числа определяют K атрибутов на ребрах графа wij=(wij1,wij2,…,wijK). Тогда проблема нахождения многоцелевого каркасного дерева формулируется следующим образом:

на каркасном дереве Т графа G минимизировать W=(W1,W2,…,WK), где Wk=wi,jk, k1…K.

Данная минимизация может и не дать минимум по всем компонентам W. В этом случае требуется найти множество каркасных деревьев S*S (это множество называется оптимальным множеством Парето (Pareto)).

3

Определение
.3.7. Проблема многоцелевого минимального каркасного дерева с заданной степенью



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

Класс сложности






Данная проблема NP-тяжелая.

3

Определения
.3.8. Обобщенное минимальное каркасное дерево



Кластерами разбиения вершин графа на несколько групп по определенному признаку. Примером такого разбиения могут служить клики графа.

Проблема обобщенного минимального каркасного дерева (The Generalized Minimum Spanning Tree Problem – GMSTP) формулируется следующим образом.

Задан ненаправленный связный граф G=(V,E) и V является объединением K кластеров Vk , k=1,2,K, кластеров вершин графа. Неотрицательная матрица стоимости C=[cij] ассоциируется с ребрами E.

GMSTP требует построения минимального по стоимости каркасного дерева, содержащего по крайней мере одну вершину из каждого кластера (проблема L-GMSTP).

Существует иная формулировка проблемы:

Найти минимальное по стоимости каркасное дерево, содержащее точно одну вершину из каждого кластера (проблема E-GMSTP).



Класс сложности





В обеих формулировках проблема является NP-тяжелой.

Замечание







Впервые проблема E-GMSTP была исследована в 1995 году, а проблема L-GMSTP – в 2000-2001 гг.

Алгоритмы





Различные точные алгоритмы решения применимы для графов с числом вершин от 100 до 200.

Имеется ряд эвристических и генетических алгоритмов алгоритмов, позволившие решить проблему с числом вершин графа около 500.

    1. Д

      Определения

      еревья Штейнера (Steiner)



Пусть G=(V,E) будет графом, в котором каждое ребро имеет положительный действительный вес. В графе G задается множество N терминальных вершин, VN. Оставшиеся вершины (V\N) называются нетерминальными вершинами или вершинами Штейнера.

Дерево Т, построенное на графе G, является минимальным деревом Штейнера или просто деревом Штейнера, если это дерево содержит все терминальные вершины N (заметим, что в дереве Штейнера могут содержаться нетерминальные вершины или вершины Штейнера).

Пример









Терминальные вершины:

N={1,3,6}


Рис.3.4.1. Дерево Штейнера (выделено жирным)

с точками Штейнера {2,4,5}

Класс сложности







Проблема нахождения минимального дерева Штейнера относится к NP-тяжелым.

Точные алгоритмы






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

Эвристические алгоритмы






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

В решении проблемы Штейнера имеется два крайних случая, когда они решаются в полиномиальное время:

- N=V, когда проблема сводится к поиску минимального каркасного дерева;

- N=2, когда проблема сводится к поиску минимального пути между двумя вершинами.

Эвристический алгоритм слияния кратчайших путей

(The Merged Shortest Paths Heuristic - SPATH)







Задан граф G=(V,E), |V|=n, |E|=m, неотрицательные целочисленные веса ребер и терминальные вершины FV.

Описание алгоритма:

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

Если кратчайший путь выбирается с помощью алгоритма Дейкстры, то сложность алгоритма равна O(zn2), где n – число вершин графа, z- число терминальных вершин.



Дерево Штейнера с евклидовой метрикой





Огромный практический интерес представляет решение проблемы дерева Штейнера на плоскости. Для любых двух пар вершин графа u=(ux,uy) и v=(vx,vy), заданных координатами на плоскости, расстояние задается в Lp-метрике (1 p ):

||uv||p=(|ux – vx|p + |uy – uy|p)1/p.

Для двух специальных случаев:





Алгоритм построения дерева Штейнера с евклидовой метрикой





На плоскости задано N точек, из F - терминальные.

Алгоритм приблизительного построения дерева Штейнера:

  1. Построить полносвязный граф G’=(N,E’) на вершинах N. Расстоянием между двумя вершинами этого графа будет кратчайшее расстояние между этими вершинами. Взять эти расстояния в качестве весов.

  2. Найти минимальное каркасное дерево Т’ полносвязного графа G’.

  3. Подставить минимальное каркасное дерево T’ в исходный граф G. Заменить каждое ребро дерева T’ минимальным путем исходного графа G. В результате получится новый граф T’’ (не всегда T’’ будет деревом).

  4. Найти каркасное дерево графа T’’, которое будет приблизительным деревом Штейнера.

Аппроксимационное отношение этого алгоритма равно 2.

Пример









G=(V,E)

N={A,B,C,D}

G’=(N,E’)




Рис.3.4.4. Построение дерева Штейнера (выделено жирным)

Замечание






Е

Пример

сли допускается введение на плоскости дополнительных «искусственных» вершин (они становятся вершинами Штейнера), то вес минимального дерева Штейнера можно уменьшить соответствующим подбором вершин Штейнера.









Исходная задача

Дерево Штейнера

(длина=9)

Дерево Штейнера с дополнительными вершинами Штейнера

(длина=7)


Рис.3.4.5. Решение задачи Штейнера в прямоугольных координатах

    1. Деревья Штейнера с ограничениями

      1. Д

        Определение
        ерево Штейнера с ограничением степеней



Задан простой связной ненаправленный G=(V,E) c n вершинами, неотрицательными весами ребер cij , подмножеством терминальных вершин ZV и ограничениями степеней вершин ki2.

Проблемой Штейнера с ограничениями на степени вершин (The Degree-constrained Steiner Problem – DCSP) является нахождение на графе дерева Т такого, что степень каждой вершины дерева deg(i)ki, а сумма весов ребер этого дерева минимальна среди всех возможных деревьев с ограничениями на степени вершин.

Класс сложности





Класс сложности DCSP – NP-тяжелая.

Алгоритмы





Точные алгоритмы решения DCSP (алгоритм перечисления каркасных деревьев и динамический программный алгоритм) имеют сложность O(p22(n-p) + n3) и O(n3p +n22p + n) соответственно. Получить решения в приемлимое время для графа с десятком вершин проблематично.

Существует достаточно большое число эвристических алгоритмов, ряд из них дает расхождение решения на 10% от точного решения.

      1. Д

        Определение
        ерево Штейнера с ограничением запаздывания



Задан простой связный ненаправленный граф G=(V,E) и две весовые функции на ребрах графа: функция стоимости сij и функция запаздывания Dij. Обе функции являются целыми положительными числами. Кроме того, задана вершина-исток s и терминальные вершины SV.

Проблема нахождения дерева Штейнера с ограничением запаздывания:

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

Класс сложности





Класс сложности данной проблемы – NP-тяжелый.

Алгоритмы







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



      1. О

        Определение

        бобщенное дерево Штейнера





Задан граф G=(V,E), вершины которого разбиты на кластеры, а ребра имеют неотрицательные целые веса cij.

Проблема обобщенного дерева (The Generalized Steiner Tree Problem – GSTP) формулируется двумя способами:

Класс сложности





Проблемы L-GSTP и E-GSTP относятся к NP-тяжелым.

1 Термин «триангуляция» по-разному трактуется в вычислительной геометрии, геодезии, теории графов и других областях.


Глава 4. ВЗВЕШЕННЫЕ ГРАФЫ И ОРГРАФЫ
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации