Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 34

Алгоритм типа развал (обратный алгоритму ДОСТРОЙКА «отстрел кандидатов»)

Сначала все вершины – кандидаты, затем начинаем удалять вершины с максимальной степенью: сначала – 7, корректируем степени, затем в новом графе ищем вершину с максимальной степенью – 3, удаляем

`S ={7,3,1,5}, затем S=V \`S={2,4,6,8}          Ответ.

Задача о минимальном доминирующем множестве.

Построить min количество военных баз, контролирующих все вершины???.

Достройка: выбираем вершины с максимальной степенью и удаляем уже контролируемые вершины. Затем то же делаем в оставшемся графе. Ответ: {7 и 3}.

Задача: развал самостоятельно.

№27. Задача о минимальной раскраске.

Найти минимальное число красок, при котором граф м.б. правильно раскрашен (т.е. любые 2 смежные вершины окрашены в разный цвет), и сам способ окраски.

Имеет место Теорема. Всякий планарный граф можно раскрасить в 4 краски.

Рассмотрим простой алгоритм, раскрашивающий планарный граф в 6 цветов.

Алгоритм: Удаляем вершины с минимальной степенью. В планарном графе число ребер R меньше 3×N, S S_i= 2×R < 6×N Þ минимальная степень < 6.

Теперь идем в обратную сторону и определяем номер краски: нельзя использовать краски, которыми окрашены соседние вершины. Т.к. в момент удаления степень вершин была меньше 3, то нам хватит 3 красок.

Задача о максимальной клике.

Нельзя ли было бы обойтись двумя красками? Двойственной задачей к этой является задача о максимальной клике (клика = полный подграф). Если в графе существует полный подграф на 3 ребрах, то минимальное число красок = 3 (т.к. минимальное число красок для полного подграфа на N вершинах равно N).

В нашем случае есть клика: т.е. чтобы решить задачу о максимальной клике и решить задачу о раскраске, и посмотреть не являются ли вершины с номерами 8, 7, 1 вершинами клики.

Задача о P-медиане на графе. Даны граф G =(V,E), матрица расстояний D ={d_ij} и веса вершин W={w_i}. Найти подмножество С Ì V и |С| = p такое, что         Интерпретация: С – множество складов.

 Минимизируем суммарную длину пути при подвозе товаров со складов.

Решение (аналог argmin алгоритма ДОСТРОЙКА). Пусть C^*= {j^*- новый склад} и  - расстояние до ближайшего склада. Тогда

Трудоемкость: 1. C ^*= C È {j^*},     2. r_i(C ^*)          3.  n = |V|операций.

O(n²) - выбор одного центра. Повторяя выбор p раз, получим трудоемкость O(n²p). Задача на графе NP‑полна, для деревьев существует полиномиальный алгоритм.

Задача о P-центре. В отличие от задачи о p‑медиане функционал будет такой:

Аналог алгоритма ДОСТРОЙКА для этой задачи – наиболее удаленный сосед.

Задача коммивояжера.

Алгоритм 1. Иди в ближайшую непройденную вершину (может не найти цикл).

Алгоритм 2: Если выполнено неравенство треугольника d_ij £d_ik +d_kj, то гарантируется нахождение цикла с длиной, превышающий оптимум не более чем в 2 раза. Сначала построим МОД и выпишем обход: 1,2,7,6,3,6,5,4,5,6,7,2,8,2,1 (вперед и назад). Проредим его, вычеркивая все повторные вхождения вершин, кроме последней. Получим эйлеров цикл: 1,2,7,6,3,5,4,8,1. Оценим погрешность e:

Из неравенства треугольникаD_постр £ 2×D_МОД < 2×D_опт  - длина кратчайшего обхода.

2×D_опт > D_постр Þ D_постр - D_опт < D_опт Þ      e - приближенный алгоритм. Трудоемкость решения O(n²) (построение МОД)

№28. Алгоритм Кристофидеса для ЗКНТ.

1.  Строим МОД и на нем множество V’ вершин с нечетной степенью.

2.  На множестве V’ строим минимальное взвешенное паросочетание (МПС) (вершины разбиваются на пары, соединяемые ребрами с минимальной суммарной длиной): (1,8), (2,3), (6,4). Добавляем эти ребра в дерево.

3.  На этом мультиграфе строится эйлеров обход: 1 2 3 6 4 5 6 7 2 8 1