Алгоритмические задачи на графах
 Скачать 1.07 Mb.
|
|
? E, c : E ? N, B > в графе G с длиной ребер c существует цикл длины ? B, включающий все ребра из E 0 } является NP-полной. Указание.Сведите к этой задаче задачу ГАМИЛЬТОНОВ_ЦИКЛ. 88 9 Что делать с полными проблемами? Как мы установили в предыдущем разделе, многие практически важные проблемы теории графов являются полными, те. в общем случае требуют, по-видимому, для своего решения экспоненциального времени. Такими же также являются многие алгоритмические проблемы логики, алгебры, теоретического программирования, искусственного интеллекта и др. областей (см. Как же поступать, обнаружив, что интересующая нас проблема является полной Что можно предпринять для ее практического решения Отметим три основных подхода для ответа на этот вопрос: • уточнение класса входных данных возможно экземпляры задач, которые требуется решать, удовлетворяют каким-либо дополнительным условиям, те. входят в некоторую более просто решаемую подпроблему; • эвристические алгоритмы в ряде случаев позволяют быстро находить решение проблемы, не гарантируя при этом его оптимальности (к ним относятся, в частности, алгоритмы локального поиска и их различные вариации); • аппроксимационные алгоритмы могут обеспечить достаточно эффективное и достаточно точное, в томили ином смысле, решение Разумеется, эти подходы можно объединять, например, для решения уточненной проблемы использовать эвристический или аппроксимационный алгоритм. Кроме того, полезными могут оказаться переборные алгоритмы с интеллектуальными возвратами и стохастические алгоритмы, которые обеспечивают быстрое и достаточное хорошее решение в среднем. Приведем несколько примеров использования указанных подходов. 9.1 Аппроксимация для задачи ВЕРШИННОЕ ПОКРЫТИЕ Оптимизационный вариант задачи ВЕРШИННОЕ ПОКРЫТИЕ состоит в определении минимального множества вершин, в котором каждое ребро имеет хоть один конец. Рассмотрим следующий простой алгоритм для построения вершинного покрытия. Алгоритм Аппр_ВП. Вход:G = (V, E) неориентированный граф. Выход: C вершинное покрытие для G. 1. C := ?; 2. WHILE E 6= ? взять произвольное ребро (u, v) из E; 4. C := C ? {u, v} ; 5. E := E \ {(x, y) | (x ? {u, v}) OR (y ? {u, v})} ; 6. } ; 7. Теорема 9.1. Алгоритм Аппр_ВП по графу G = (V, E) строит его вершинное покрытие которое больше минимального вершинного покрытия не более чем в два раза. Время работы алгоритма Аппр_ВП O(|V | + Доказательство. Действительно, поскольку каждое ребро (x, y) удаляется изв стр. лишь тогда, когда хотя бы один из его концов входит в C, тов конце работы C является вершинныи покрытием. Для каждой пары вершин {u, v}, попадающей в C в стр. 4, хотя бы одна из этих вершин должна принадлежать любому, в том числе и минимальному, вершинному покрытию G. Следовательно, число вершин C превосходит число вершин в минимальном вершинном покрытии не более чем в 2 раза. Оценка сложности очевидна. Казалось бы, естествено попытаться улучшить алгоритм Аппр_ВП, добавляя в C в стр.4 не два конца очередного ребра, а один, те. заменить стр. 4 на = C ? Но полученный с помощью такой оптимизации алгоритм Аппр_ВП1 может привести к существенной потере качества аппроксимации. Рассмотрим для каждого натурального n двудольный граф B n = (X ? Y, E) , где X = {x 1 , . . . , x n } , а другая доля Y состоит из n непересекающихся подмножеств Y = ? n i=1 Y i . Каждая вершина y из Y i связана с i вершинами, причем никакие две вершины из Y i не имеют общих соседей в X. Таким образом, Y i = {y ij | 1 ? j < bn/ic} , E i = {(y ij , x k ) | 1 ? j < bn/ic, i(j ? 1) + j ? k ? ij} , E = ? n i=1 E i , а общее число вершин в Y равно n + bn/2c + bn/3c + . . . + 1 = O(n log Минимальное вершинное покрытие в графе B n , очевидно, образует множество X и его мощность равна n. Алгоритм Аппр_ВП поместит в C (при любом порядке рассмотрения ребер вершин. Если же применить алгоритм Аппр_ВП1 со стр. 4', тов могут попасть все вершины из Y . Таким образом, полученное покрытие будет враз хуже минимального. Все же идею добавления водного конца для каждого расматриваемого ребра можно использовать, если этот конец выбирать случайно. Зафиксируем некоторый порядок ребер графа G = (V, E), E = {e 1 , . . . , e m } . Рассмотрим следующий вероятностный алгоритм. Алгоритм Аппр_ВП_вер. Вход:G = (V, E = {e 1 , . . . , e m }) неориентированный граф. Выход: C вершинное покрытие для G. 1. C := ?; 2. WHILE E 6= ? взять первое по списку ребро e i = (u, из с вероятностью 0.5 выбрать в качестве x одну из вершин u, v; 5. C := C ? {x} ; 6. E := E \ {(z, y) | (z = x) OR (y = x)} ; 7. } ; 8. Теорема 9.2. Алгоритм Аппр_ВП_вер по графу G = (V, E) строит его вершинное покрытие, которое в среднем больше минимального вершинного покрытия не более чем в два раза. Время работы алгоритма Аппр_ВП_вер O(|V | + Доказательство. Поскольку ребро удаляется изв стр. 6 только, когда один из его концов попал в C, а после завершения работы алгоритма E = ?, то C является вершинным покрытием. Зафиксируем некоторое минимальное вершинное покрытие C ? = {x 1 , . . . , x k } ? V . Из каждой пары вершин u, v, рассматривающейся в стр. 3, по крайней мере одна входит в C ? . Вероятность ее успешного выбора в стр. 4 в качестве x равна 0.5. Поэтому среднее число попыток для k таких успешных выборов равно 2k. Но это и есть средний размер C. Еще одна естественная эвристика для поиска минимального вершинного покрытия состоит в поочередном выборе и удалении вершин максимальной (оставшейся) степени. При этом на каждом шаге помещаемая в покрытие вершина будет покрывать максимально возможное число оставшихся ребер. Однако и эта эвристика проваливается на графах B n . Действительно, согласно ей на первом этапе в покрытие попадут вершины из Y n , на втором этапе могут попасть вершины из Y n?1 , на третьем вершины из и т.д. В результате построенное покрытие будет содержать все вершины из Y и окажется враз больше минимального. 9.2 Аппроксимации для задачи коммивояжера В разделе 8.5 мы установили полноту задачи распознавания КОММИВОЯЖЕР. В этом мы рассмотрим ее как задачу оптимизации: найти цикл минимальной длины (стоимости, веса, проходящий через все вершины полного нагруженного неориентированного графа G = (V, E = V Ч V ) с матрицей длин ребер C = (c ij ), 1 ? i, j, ? |V Заметим, что мы всегда можем рассматривать полные графы, положив длину отсутствующих ребер равной ? ( или числу превосходящему сумму длин всех настояших ребер). Обозначим через OP длину кратчайшего гамильтонова пути в графе с матрицей расстояний C, а через A K (C) длину гамильтонова пути, выдаваемого алгоритмом A. Как показывает следующее утверждение, задача коммивояжера не допускает никакой сколь-нибудь эффективной полиномиальной аппроксимации. Теорема 9.3. Если P 6= NP , то для всякой функции f(n) = c n (c - константа) для задачи КОММИВОЯЖЕРа не существует полиномиального аппроксимационного алгоритма A, у которого для всякой матрицы расстояний C меет место неравенство) ? f (n)OP те. любой алгоритм, работающий в полиномиальное время, для некоторых графов выдает результат в экспоненту раз хуже оптимального). Доказательство. Изменим немного сведение задачи ГАМ_ЦИКЛ из доказательства теоремы Пусть G = (V, E) неориентированный граф с n вершинами. Определим по нему полный нагруженный граф G 0 = (V, E 0 = V Ч V со следующей функцией длины ребер, v) если (u, v) ? E nf (если (u, v) 6? Из этого определения непосредственно следует, что если в графе G имеется гамильтонов цикл тов графе имеется гамильтонов цикл длины n, а если в G нет гамильтонова цикла, тов кратчайший путь коммивояжера имеет длину не меньше nf(n)+n?1. Отметим, что для любого ребра (u, v) ? двоичная запись его длины имеет размер |c(u, v)| ? |nf(n)| ? 1 + log 2 (nc n ) = O(n log n) . Поэтому преобразование G в можно выполнить за полиномиальное (от n) время. Если бы для задачи КОММИВОЯЖЕРа существовал полиномиальный аппроксимацион- ный алгоритм A ошибающийся не более чем враз, то по его результату для графа можно было бы судить о наличии или отсутствии гамильтонова цикла в G. А именно, при ответе в G гамильтонов цикл есть, а при A(G 0 ) ? nf (n) + n ? такого цикла нет. Таким образом, мы могли бы решить полную задачу ГАМ_ЦИКЛ за полиномиальное время, из чего следовало бы, что P = NP Заметим, что графы, к которым происходит сведение в этой теореме не удовлетворяют неравенству треугольника, которое выполнялось для графов из доказательства теоремы Если же ограничиться классом графов G = (V, E) с длинами ребер c : E ? R + , для которых выполнено неравенство треугольника, те. для любых трех вершин u, w, v ? V c(u, v) ? c(u, w)+ c(w, v) , то возможны аппроксимации за полиномиальное время, которые дают обходы, которые хуже оптимального в логарифм или даже в константу раз Рассмотрим вначале эвристику ближайшего соседа, которой, по-видимому, пользуется большинство людей при небходимости обойти большое число магазинов. Основанный на этой эвристике алгоритм NN (Nearest Neighbor - ближайший сосед, начав обход с некоторой вершины, далее всякий раз выбирает в качестве следующей вершины обхода ту, из еще не посещенных вершин, которая находится ближе всего к последней посещенной вершине. Таким образом, путь v = v 1 , v 2 , . . . , v k (k < продолжается такой вершиной v k+1 ? V \{v 1 , v 2 , . . . , v что c(v k , v k+1 ) = min{c(v k , v 0 ) | v 0 ? V \ {v 1 , v 2 , . . . , v Сложность построения пути коммивояжера этим алгоритмом, очевидно, оценивается как. В работе [24] были получены логарифмические оценки качества приближения для этого алгоритма. Теорема 9.4. (1) Для любой n Ч матрицы расстояний C, удовлетворяющей неравенству треугольника, выполнено неравенство N (C) ? 1 2 (dlog 2 ne + 1)OP T (C). (2) Для сколь угодно больших n существуют n Ч матрицы C, удовлетворяющие неравенству треугольника, для которых N (C) > 1 3 (log 2 (n + 1) + 4 3 )OP T (Еще одна жадная эвристика для задачи коммивояжера MF, которую иногда называют мульти-фрагментной, аналогична эвристике, использованной в построении минимального остовного дерева алгоритмом Крускала. Вначале в искомый гамильтонов путь помещаем самое короткое ребро, а затем на очередном шаге добавляем к уже выбранному подмножеству ребер самое короткое из оставшихся ребер, которое не нарушает гамильтоновости (те. не приводит к появлению вершин степени 3). Этот алгоритм, очевидно, можно реализовать за время n) . А оценки качества получаемых им решений такие же, как и для алгоритма те. получаемый результат MF (C) может быть хуже оптимального в O(log n) раз. Более точные приближенные алгоритмы были приведены в упомянутой работе Розенкран- ца, Стирнза и Льюиса Один из них основан на нижней оценке длины оптимального пути коммивояжера через размер минимального остовного дерева. Действительно, если из любого гамильтонова цикла удалить одно ребро, то получившийся путь будет содержать все вершины графа и, следовательно, будет одним из его остовных деревьев. Обозначим через MST (C) вес минимального остовного дерева графа с матрицей расстояний C. Тогда из вышесказанного следует, что T (C) ? M ST (Рассмотрим алгоритм МОД, который использует двойной обход минимального остовного дерева. Он работает следующим образом. По матрице длин ребер C исходного графа с n вершинами построить его минимальное остовное дерево T = (V, E) (зметим, что |E| = n ? 1). 2. Заменить в нем каждое неориентированное ребро (u, v) ? E двумя противоположно направленными ориентированными ребрами (u, v) и (v, u). Обозначим получившийся ориентированный граф через T 2. 3. В графе T 2 полустепени захода и исхода каждой вершины равны 1. Поэтому в нем существует Эйлеров цикл, включающий все ребра. Выбрав произвольную вершину в качестве исходной, построить в T 2 Эйлеров цикл. Пусть это путь p e = v 1 , v 2 , . . . , v 2n?1 (= v 1 ) 4. Превратить p в гамильтонов цикл p g = u 1 , u 2 , . . . , u n+1 (= следующим образом) u 1 = v 1 b) Пусть для 1 < i < n уже определен начальный отрезок пути p g , включающий i ? 1 ребро с вершинами u 1 , . . . , u и u i = v j . Тогда в качестве u выберем следующую еще не пройденную вершину из p e , те. u i+1 = v k , где k = min{l | (l > j) ? (v l / ? {u 1 , . . . , u i }) и продолжим p ребром (u i , u i+1 ) = (v j , v k ) c) Завершим путь p ребром изв Теорема 9.5. Для любой n Ч матрицы расстояний C, удовлетворяющей неравенству треугольника, алгоритм МОД строит маршрут коммивояжера не более чем в 2 раза прево- ходящий по длине оптимальный, т.е. 2МОД(C) ? 2 OP T (Время работы алгоритма МОД не превосходит O(n 2 log Доказательство. Действительно, из неравенства треугольника следует, что длина каждого ребра (u i , u i+1 ) , помещаемого в путь p в пунктах 4(b) и 4(c), не превосходит длину соответствующего участка v j , . . . , v пути p e . Поэтому длина всего путине превосходит длину p Отсюда имеем, МОД) = c(p g ) ? c(p e ) = 2 M ST (C) ? 2 OP T (Для построения минимального остовного дерева можно использовать, например, алгоритм Крускала имеющий сложность O(n 2 log см. теорему 4.1). Построение Эйлерова цикла задачи и 2.14), его удвоение и преобразование в гамильтонов цикл в пунктах 2-4 выполняются за время O(|E|) = O(n 2 ) . Заметим, что при использовании для построения минимального остовного дерева наиболее эффективной реализации алгоритма Прима (см. задачу 4.6), время работы алгоритма 2МОД не превосходит O(n 2 ) Кристофидис показал, что, используя минимальные остовные деревья и минимальные паро- сочетания, можно построить более точное приближение к оптимальному пути коммивояжера. Напомним, что совершенным паросочетанием во взешенном графе G = (V, E) с матрицей расстояний называется такое подмножество ребер M ? E, что никакие два из них не имеют общих концов и все вершины из V являются концами ребер из M. Минимальным называется совершенное паросочетание наименьшего веса (см. пункт Алгоритм МОД-МП работает следующим образом. По матрице длин ребер C исходного графа с n вершинами построим его минимальное остовное дерево T = (V, E) (зметим, что |E| = n ? 1). 2. В дереве T = (V, выделим подмножество вершин нечетной степени V 0 Рассмотрим полный подграф графа G на вершинах и построим для него минимальное совершенное паросочетание M. 3. Пусть мультиграф T 1 = (V, E1), где множество ребер E1 включает все ребра из и из M (некоторые ребра могут входить в E1 дважды. Степени всех вершин в T 1 четны. Построим в нем Эйлеров цикл p e 4. Превратим p в гамильтонов цикл p так, как это сделано в п. 4 алгоритма 2МОД. Теорема 9.6. Для любой n Ч матрицы расстояний C, удовлетворяющей неравенству треугольника, алгоритм МОД-МП строит маршрут коммивояжера не более чем в 3/2 раза превоcходящий по длине оптимальный, т.е. МОД-МП(C) ? 3 2 OP T (Время работы алгоритма МОД-МП не превосходит Заметим, что число вершин четно Доказательство. Покажем вначале, что c(M) = P e?M c(e) ? 1 2 OP T (C). Действительно, пусть p min минимальный гамильтонов цикл. Удалим из него вершины из V \ V 0 , превратив таким образом в гамильтонов цикл для подграфа G 0 . Из неравенства треугольника следует, что c(p 0 ) ? c(p min ) . Ребра цикла разбиваются на два совершенных паросочетания. По крайней мере вес одного из них не превосходит 2 c(p 0 ) . Но тогда и вес минимального паросочетания c(M не превосходит 2 c(p 0 ) ? 1 2 c(p min ) = 1 2 OP T (Теперь из этого неравенства и из того, что МОД-МП(C) = c(p g ) ? c(p e ) + c(M и c(p e ) ? OP T (следует утверждение теоремы. Основной вклад в сложность вносит построение минимального совершенного паросочетания в п. 2. Его можно построить за время O(|V | 4 ) , используя алгоритм, предложенный Эдмондсом и Джонсоном (см. например, [5], глава 12, [10], глава Отметим также эвристики локального улучшения маршрута 2-Opt, 3-Opt, . . ., k-Opt. Алгоритм, имея некоторый маршрут коммивояжера, рассматривает всевозможные пары его ребер (a, b) и (c, d) и пытается их перекоммутировать заменить на пару (a, d), (b, c). Алгоритм аналогичным образом пытается улучшить текущий маршрут, рассмтаривая все тройки ребер, а алгоритм k-Opt все подмножества из k ребер текущего маршрута. При этом даже число вариантов, рассматриваемых для проверки локальной оптимальности, имеет порядок k ) , поэтому на практике используют эти эвристики при k = 2, Приведенные выше, а также и многие другие алгоритмы приближенного поиска маршрута коммивояжера подвергались интенсивной экспериментальной проверке на разных классах графов. В частности, оказалось, что на случайных графах с Эвклидовой метрикой и числом вершин порядка 10 алгоритм NN ошибается не более, чем на 25%, алгоритм MF не более, чем на 15%, алгоритм Кристофидеса дает точность порядка 10%, алгоритм 2-Opt 5%, алгоритм (локальные алгоритмы улучшали результаты алгоритма MF). При этом для достижения указанных результатов 2-Opt и 3-Opt для больших графов он тратят в 2-3 раза больше времени, чем более простые эвристики NN и MF, а алгоритм Кристофидеса даже в сотни раз. 9.3 Метод ветвей и границ для задачи коммивояжера Рассмотрим на примере задачи коммивояжера один из методов интеллектуального перебора метод ветвей и границ. Алгоритмы этого типа применяются для поиска оптимальных решений оптимизационных задач. В худшем случае они производят полный перебор вариантов для поиска наилучшего из них и поэтому требуют экспоненциального (от размера входа) времени. Но во многих случаях число рассматриваемых вариантов удается существенно сократить. Предположим, что для некоторой задачи A требуется из большого множества возможных решений SOL выбрать решение s с минимальным весом (длиной, стоимостью) c(s). Предположим также, что SOL естественным образом представляется в виде дерева T , каждой ветви которого соответствует некоторое решение. При этом каждой вершине v дерева T соответствует некоторая подзадача, решение которой определяется путем из корня в v, и имеется легко вычисляемая функция B(v), которая задает нижнюю границу качества решений s, проходящих через v, те. c(s) ? B(v). В переменной ТЕК-МИН будет храниться минимальный вес уже рассмотренных решений. Алгоритм осуществляет обход дерева T в глубину. При этом при достижении листа и построении некоторого полного решения s определяется его веско- торый в случае c(s) < ТЕК-МИН становится новым значением минимума. Перед переходом в новую вершину u вычисляется B(u) и, если B(u) ?ТЕК-МИН, то переход в u (и, следовательно, просмотр решений из поддерева с корнем u) не осуществляется. Ясно, что при этом минимальное решение потеряно не будет. 4 При более эффективной реализации построение минимального паросочетания можно выполнить за время | 4 ) ( (см) . 94 Пусть G = (V, E) неориентированный граф с n вершинами и длинами ребер c. Зафиксируем произвольную вершину a ? V . В качестве T = (V T , рассмотрим дерево всех простых путей, начинающихся в a. Его вершины помечены вершинами из V . Корень имеет метку Пусть в вершину w ? сметкой ведет из корня путь, метки вершин которого образуют подмножество вершин V w ? V . Тогда w соединена исходящими ребрами с вершинами T помеченными {u | (v, u) ? E} ? (V \ Каждая ветвь дерева T длины n, соответствующая га- мильтонову пути s = (a = v 1 , v 2 , . . . , v в G, при наличии ребра (v n , a) ? задает возможный маршрут коммивояжера веса c(s) = P c i=n i=1 (v i , v i+1(modn) ) . Более короткие ветви T соответствуют простым путям G, которые нельзя продолжить до гамильтоновых циклов. Имеются разные способы определения нижней оценки B(w) веса маршрутов коммивояжера, проходящих через вершину w ? Мы рассмотрим один из самых простых. Пусть виз корня ведет путь, соответствующий пути s = (a = v 1 , v 2 , . . . , v k = b), k < в G. Тогда V w = {v 1 , . . . , v и всякий гамильтонов путь s 0 , продолжающий s будет включать все вершины из множества V \ V w . Вес участка этого пути, проходящего по V 0 , не меньше веса MST (минимального остовного дерева подграфа графа G, включающего все вершины из и соединяющие их ребра из E. Поэтому вес любого маршрута коммивояжера, проходящего через w, будет не меньше величины) = B(s) = c(s) + M ST (G 0 ) + min{c(b, u) | u ? V 0 } + min{c(u, a) | u ? Заметим, что на самом деле оценка B(w) однозначно определяется путем s в графе G. Поэтому в приведенном ниже алгоритме вершины w дерева T в явном виде не участвуют, а перебор ведется по путям s в графе Теперь метод ветвей и границ для задачи коммивояжера можно уточнить следующим об- разом. Алгоритм КОМ-ВГ Вход: G = (V, E) (неориентированный граф, представленный списками смежности вида (w 1 , c(v, w 1 )), . . . , (w k(v) , c(v, w k(v) ) , где w 1 , . . . , w k(v) это все вершины, в которые изведут ребра, а c(v, w i ) длина ребра (v, w i ) , и исходная вершина a ? V. 1. Быстро построить некоторый маршрут коммивояжера s, начинающийся в a; 2. ОПТ-ПУТЬ := s; 3. ТЕК-МИН := c(s); 4. v := a; s := ?; 5. ОПТ_ПОИСК(v,s) Procedure ОПТ_ПОИСК(v,s Вход v текущая вершина дерева, s путь из корня в v. 6. W := {w | w входит в путь s}; 7. IF W = V % s гамильтонов путь. THEN 9. { c := c(s) + c(v, a); % c вес текущего маршрута c < ТЕК-МИН 11. THEN { ТЕК-МИН := c; ОПТ-ПУТЬ := s} % новый оптимум. ELSE 14. { L := {u | (v, u) ? E} \ W ; 15. FOR EACH u ? L DO 95 16. { s := s, (v, u) ; 17. V 0 := V \ (W ? {u}); 18. G 0 := подграф G, порожденный V 0 ; 19. B(s) := c(s) + M ST (G 0 ) + min{c(b, u) | u ? V 0 } + min{c(u, a) | u ? V 0 }; 20. IF B(s) <ТЕК-МИН 21. THEN ОПТ_ПОИСК(u,s ) 22. } Заметим, что в качестве исходного маршрута в стр. 1 можно взять произвольную перестановку вершин из V . Но практическая эффективность алгоритма значительно улучшится, если использовать для поиска исходного пути один из быстрых эвристических алгоритмов, рассмотренных в разделе 8.5. Например, алгоритм ближайшего соседа NN за время строит маршрут, который хуже оптимального не более чем в log n раз. Теорема 9.7. Алгоритм КОМ-ВГ всегда находит оптимальное решение задачи коммивоя- жера. Что касается сложности этого алгоритма, то нерекурсивную часть вызова процедуры ОПТ_- ПОИСК(v,s ) можно выполнить за время O(|E| log |E|) (основной вклад вносит время построения минимального остовного дерева при вычислении B(s) в стр. 19). Число вызовов этой процедуры уменьшается за счет ранней проверки условия в стр. 20. Но это в общем случае не гарантирует полиномиальности алгоритма. Пример 25. Продемонстрируем применение алгоритма КОМ-ВГ к поиску оптимального маршрута коммивояжера на графе G, показанном на рис. 43. ( H H H H H H @ @ @ @ @ a a a a a a H H H H H a b c d e f g 3 1 1 6 2 1 10 2 3 2 2 Рис. 43: Граф На рис. 44 представлено дерево путей графа G, которое строит в процессе работы алгоритм КОМ-ВГ. Рядом с каждой вершиной w указано значение нижней оценки B(w) ля этой вершины. Мы считаем, что вершины в списках смежности упорядочены лексикографически. Пусть исходной вершиной является a, а в качестве исходного маршрута в стр. 1 выбран обход в алфавитном порядке s 0 = a, b, c, d, e, f, g, самая левая ветвь дерева. Его вес c(s 0 ) = становится начальным значением ТЕК-МИН. Затем алгоритм обнаруживает путь s 1 = a, b, c, d, e, g, f, a с меньшим весом c(s 1 ) = 15 , который становится следующим значением ТЕК-МИН. Благодаря этой границе обрываются пути a, b, f, e и a, b, f, g (этот путь невозможно продолжить до гамиль- тонова пути. После этого находится путь s 2 = a, f, b, c, d, e, g, a с весом c(s 2 ) = Благодаря этому значению ТЕК-МИН рассмотрение всех остальных путей обрывается на достаточно ранней стадии. Всего в процессе работы алгоритм КОМ-ВГ рассматривает 10 путей при их общем числе в дереве, равном 6! = 720. 96 m a m b 13 k f 12 m g 11 P P P P P P P P P @ @ @ @ @ @ @ @ @ @ m c 14 m f 14 m b 12 m e 18 m g 15 m c 18 m d 21 m e 12 m d 14 m e 19 m g ? m c 12 m e 14 m d 12 m g 15 m e 12 m f 16 m f 15 m g Рис. 44: Дерево обхода алгоритма КОМ-ВГ 9.4 Задачи Задача 9.1. Предложите алгоритм линейной сложности для нахождения максимального независимого множества вершин в неориентированном дереве. Задача 9.2. Постройте "жадный"алгоритм, который находит оптимальное вершинное покрытие для графа, являющегося деревом, за линейное время. Задача 9.3. Предложите алгоритм полиномиальной сложности для нахождения минимального ВЕРШИННОГО ПОКРЫТИЯ в двудольных (бихроматических) графах. Указание. Установите связь между этой задачей и задачей о максимальных паросочетаниях в двудольных графах (см. раздел 7.4). Рссмотрим следующий аппроксимационный алгоритм для построения вершинного покрытия. Используя алгоритм поискав глубину ПОГ построить глубинный лес T G = (V, T графа = (V, E) 2. Поместить в вершинное покрытие C все внутренние вершины из Докажите, что построенное этим алгоритмом множество C является вершинным покрытием для G и превосходит по мощности минимальное вершинное покрытие не более чем в 2 раза. Задача 9.4. Рассмотрим следующую задачу центры : для заданного нагруженного неориентированного графа G = (V, E) с длинами ребер c : E ? R найти подмножество S ? вершин размера |S| = k такое, что каждая вершина из V близка к некоторой вершине из те. S минимизирует функцию max v?V min u?S c(u, Рассмотрите для этой задачи жадный алгоритм, который, начав с произвольной вершины, последовательно добавляет к S наиболее далекие от S вершины. Докажите, что получаемое таким образом решение отличается от оптимального не более, чем в 2 раза. Задача 9.5. Для нагруженного графа G, представленного матрицей C, определите гамиль- тонов путь p N N , используя алгоритм NN (ближайшего соседа) и гамильтонов путь p 2M OD , 97 используя алгоритм 2MOD (с двойным обходом минимального остовного дерева. Сравните полученные результаты с длиной 12 минимального пути = ? ? ? ? ? ? ? ? ? ? 0 3 10 10 10 2 1 3 0 2 12 12 2 10 10 2 0 1 10 12 6 10 12 1 0 2 12 10 10 12 10 2 0 5 3 2 1 12 12 5 0 2 1 10 60 10 3 2 Задача 9.6. Задача поставщиков аналогична предыдущей задаче. В ней дополнительно задано разбиение вершин графа G = (V, E); c : E ?, R на множество поставщиков F ? и множество потребителей D = V \ F . Требуется найти подмножество поставщиков S ? F, |S| = k, котолрое S минимизирует функцию max v?D min u?S c(v, u) Предолжите для этой задачи аппроксимационный полиномиальный алгоритм, который строит решение, отличающееся от оптимального не более, чем в 3 раза. Задача 9.7. Задача МНОЖЕСТВЕННОЕ СЕЧЕНИЕ состоит в том, чтобы по неориентированному графу G = (V, E) и множеству k терминальных вершин v 1 , v 2 , . . . , v найти минимальное множество ребер из E, удаление которых оставит все терминальные вершины в разных связных компонентах. (а) Покажите, что эта задача точно решается за полиномиальное время для k = б) Для случая k = 3 предложите аппроксимационный полиномиальный алгоритм, который строит решение, отличающееся от оптимального не более, чем в 2 раза. (в) Разработайте алгоритм локального поиска множественного сечения для общего слу- чая. Задача 9.8. Рассмотрим следующую задачу МАКСИМАЛЬНОЕ СЕЧЕНИЕ : для заданного нагруженного неориентированного графа G = (V, E) с длинами ребер c : E ? R найти подмножество S ? V вершин такое, что сумма длин ребер между S и V \ S максимальна. Если через w(S) обозначить сумму длин ребер, один конец которых принадлежит S, а другой V \ S, то МАКСИМАЛЬНОЕ СЕЧЕНИЕ это задача о максимизации w(S) по всем подмножествам S ? V . S ? Рассмотрите для этой задачи локальный алгоритм, который, начав с произвольной вершины, последовательно ищет и добавляет к S такую вершину v , что w(S ? {v}) > а) Докажите,что получаемое таким образом решение отличается от оптимального не более, чем в 2 раза. (б) Оцените время работы этого алгоритма 10 Применение графов в анализе социальных сетй 10.1 Социальные сети Социальные сети начали изучаться в социологии в е годы ХХ-го века. В учебниках социологии социальную сеть определяют как совокупность сетевых акторов (точек, вершин, агентов), вступающих во взаимодействие друг с другом и связи между которыми преимущественно социальные, такие как дружественные отношения, совместная работа, обмен информацией и т.п. Таким образом, социальная сеть это граф, вершины которого акторы, а ребра представляют связи, взаимодейсвия отношения между различными акторами. Среди них могут быть связи, отражающие подобие акторов, их социальные отношения, взаимодействия, местоположение, атрибуты, родственные связи, роли, эмоциии, когнитивные отношения и т.п. В некоторых социальных сетях представлены симметричные отношения, например, Быть другом кого-то, Работать над одним проектом с кем-то и др. Такие сети представляются посредством неориентированных графов. Вдругих сетях представлены несимметричные отношения, например Посылать электронное письмо кому-то, Помогать кому-то, Участвовать в некотором событии и др. Сети с такими отношениями представляются ориентированными графами. Иногда естественно рассматривать графы со взвешенными ребрами. Числовая метка ребра может характеризовать вес, интенсивность, силу соответствующего от- ношения. Размеры социальных сетей варьируются от нескольких акторов (в сетях отношений одной семьи, сотрудников малого предприятия и т.п.) до миллионов и десятков миллионов акторов в интернет-сетях таких как Facebook, MySpace, Одноклассники, В контакте и др. Да и вся паутина страниц может рассматриваться (и на самом деле рассматривается поисковыми системами) как одна социальная сеть с отношением "ссылается на". Главные задачи анализа социальных сетей состоят в определении их теоретико графовых свойств, которые характеризуют а) структуру сети (анализ на уровне сети); б) положение в сети (анализ на уровне вершин); в) попарные свойства (анализ на уровне пар). Анализ на уровне сети связан с двумя видами свойств связанностью и формой. Связанность характеризуется такими свойствами как плотность, длина путей, фрагментация. Меры связанности позволяют также выделять в сетях подгруппы (сообщества,клики) области, обладающие таким специфическими свойствами связанности как высокая плотность, небольшая длина путей между акторами и др. Форма сети связана с распределением ее соединений (ребер). Сюда относятся такие свойства как ядерность / переферийность, массивность и т.п. Анализ на уровне вершин занимается свойствами центральности вершин, связанными с важностью вершин, их доминирующим положением в сети. Например, одним из свойств центально- сти является промежуточность по Фримену (Freeman), которая отражает свойство вершины лежать на на кратчайших путях, соединяющих две другие вершины. Это можно интерпретировать как потенциальную силу актора, который может замедлить идущие сквозь него потоки или исказить их в свою пользу. Анализ на уровне пар, как правило, связан с двумя видами свойств парной связанностью и эквивалентностью. Связанность пары вершин означает каких близость в сети, таки наличие многих типов свзей между ними. Эквивалентность оценивает степень, с которой вершины пары играют в структуре сети одинаковые роли, например, изоморфность их окрестностей. Мы будем рассматривать социальные сети как ориентированные или неориентированные графы в зависимости от видов представляемых ими связей, взаимодействий или отношений ( [25, Ребра в графах социальных сетей называются связями (links) или соединениями (ties). 99 Обозначение. Пусть I = {i 1 , . . . i n } это некоторое множество акторов. Социальная сеть это граф без петель G = hI, Ei, где E множество (ориентированных или неориентированных) связей между парами акторов. Для конкретных сетей вершины и ребра представлящих их графов могут иметь специальные метки, содержащие дополнительную информацию. Например, имена вершин, типы и интенсивность связей, веса ребер и т.п. Введем следующие обозначения для сети G =< I, E > и актора i ? I пусть) = |{j |(i, j) ? обозначает степень i в неориентированном графе сети G; d i (i) = |{j |(j, i) ? обозначает (полу)степень захода в i в G (для ориентированного G); d o (i) = |{j |(i, j) ? обозначает (полу)степень исхода изв (для ориентированного Очевидно, максимальная степень актора в сети G с n акторами равна n ? Для акторов i и j обозначим через ?(i, j) длину кратчайшего пути из i to j. Как обычно, для ненагруженных графов длина пути равна числу ребер на этом пути, а для нагруженных сумме длин (весов, стоимостей и т.п.) ребер этого пути. Важную роль в анализе социальных сетей играют следующие формализации в терминах теории графов понятий, содержательно описанных выше. 10.2 Параметры центральности акторов Центральный актор это актор, у которого много связей с другими акторами. Такие ак- торы играют важную роль в анализе социальных сетей. Имеется несколько формализаций центральности в терминах графов. Степень центральности оценивает относительную степень вершины актора в сети. Для неориентированного графа G степень центральности актора i, обозначаемая определяется как) = d(i) n ? Для ориентированного графа G степень центральности актора i, также обозначаемая определяется как) = d o (i) n ? те, учитываются только выходящие из i связи Близкая центральность (closeness centrality (Sabidussi, Эта величина оценивает насколько близки к данному актору остальные акторы сети. Как для ориентированных, таки для неориентированных сетей близкая центральность актора i обозначается и определяется как) = 1 P j?I ?(i, Для ненагруженных графов эту величину обычно нормализуют следующим образом) = n ? 1 P j?I ?(i, В этом случае 0 < C C (i) ? 1 , так как минимальное расстояние ?(i, j) для всех j 6= i равно 1, а минимальное значение суммы P j?I ?(i, равно n ? Чтобы избежать бесконечности в знаменателе из i должны быть достижимы все вершины. Поэтому для определения близкой центральности для всех акторов неориентированный граф должен быть связным, а ориентированный сильно связным 10.2.2 Срединная центральность (Betweenness Срединная центральность (Freeman, 1977; Anthonisse, Срединная центральность определяет важность актора, учитывая, как часто он появляется на путях взаимодействия других акторов. Если актор i появляется на всех или почти всех путях, связывающих акторы j и k, то он может контролировать их взаимодействие. Срединная центральность позволяет выделять акторы, без прохождения через которые нельзя связать многие пары других акторов сети. Неориентированные графы. Для акторов j и k пусть p jk обозначает число кратчайших путей между j и k (будем считать, что p jj = 1 ). Пусть i (i 6= j и i 6= k) это третий актор. Обозначим через p число кратчайших путей между j и k, проходящих через Тогда срединная центральность актора i, обозначаемая определяется как) = X j?I,j6=i X k?I,k6=j,k6=i p jk (i) p Для ненагруженных графов может принимать значения от 0 до (n?1)(n?2) 2 (это число пар акторов, не содержащих i). Поэтому иногда нормализуют следующим образом) = 2 P j?I,j6=i P k?I,k6=j,k6=i p jk (i) p jk (n ? 1)(n ? Ориентированные ненагруженные графы. В этом случае (нормализовнную) срединную центральность определяют как) = P j?I,j6=i P k?I,k6=j,k6=i p jk (i) p jk (n ? 1)(n ? для ориентированного графа (x, y) и (y, x) это разные ребра Алгоритмы вычисления центральности Мы будем рассматривать вычисление центральности вершин для неориентированных графов, в которых веса (длины) всех ребер равны 1, и для нагруженных ориентированных графов = (I, E) , в которых веса (длины) ребер c(e), e ? E, являются неотрицательными числами. |