ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
 Скачать 4.33 Mb.
|
|
3. Алгоритм Флойда. Алгоритм Флойда схож с алгоритмом Уоршелла нахождения транзитивного замыкания. В этом алгоритме последовательно рассматриваются вершины орграфа и, если существует путь в две дуги от некоторой вершины x до вершины y через рассматриваемую вершину z и его длина меньше длины пути между вершинами x и y через рассмотренные ранее вершины, тов качестве кратчайшего пути изв нужно принять путь через вершину z. В начальный момент, когда ни одна из вершин графа не рассмотрена, информацию о кратчайших путях и их длинах между каждой парой вершин орграфа представляет модифицированная матрица весов M (см. выше метод Шимбелла). Алгоритм Флойда представлен блок-схемой на рис. Алгоритм 4.14 нахождения кратчайших путей между каждой парой вершин во взвешенном орграфе. Вход M модифицированная матрица весов N — количество вершин в орграфе. Выход W — матрица кратчайших путей и их длин между каждой парой вершин орграфа. 203 + Рис. Алгоритм Флойда нахождения кратчайших путей между каждой парой вершин во взвешенном орграфе 4.15. Центры и медианы во взвешенном орграфе Определим для каждой вершины v i взвешенного орграфа число s o (v i ) как максимум среди кратчайших расстояний от вершины v i до каждой вершины орграфа, число s t (v i ) как максимум среди кратчайших расстояний до вершины v i от каждой вершины орграфа и число s ot (v i ) как сумму чисел s o (v i ) и s t (v i ): s ot (v i ) = s o (v i ) + s t (v i ). Число s o (v i ) называется числом внешнего разделения вершины v i , число s t (v i ) — числом внутреннего разделения вершины v i и число s ot (v i ) — числом внешне-внутреннего разделения вершины Вершина с минимальным числом внешнего разделения называется внешним центром, вершина с минимальным числом внутреннего разделения называется внутренним центром и вершина с минимальным числом внешне-внутреннего разделения называется внешне-внутренним центром. Конец W := M z := 1, N x := 1, N W xy .d :=W xz .d+W zy .d W xy .t:= W zy .t y := 1, N Алгоритм Флойда W xz +W zy xy 204 1 2 3 4 5 6 1 2 2 3 4 5 6 4 Определим для каждой вершины v i взвешенного орграфа число f o (v i ) как сумму кратчайших расстояний от вершины v i до каждой вершины орграфа, число f t (v i ) как сумму среди кратчайших расстояний доверши- ны v i от каждой вершины орграфа и число f ot (v i ) как сумму чисел f o (v i ) и f t (v i ): f ot (v i ) = f o (v i ) + f t (v i ). Число f o (v i ) называется внешним передаточным числом вершины v i , число f t (v i ) — внутренним передаточным числом вершины v i и число f ot (v i ) — внешне-внутренним передаточным числом вершины Вершина с минимальным внешним передаточным числом называется внешней медианой, вершина с минимальным внутренним передаточным числом называется внутренней медианой и вершина с минимальным внешне-внутренним передаточным числом называется внешне- внутренней медианой. На рис представлен взвешенный орграф, матрица D кратчайших расстояний, числа внешнего s o , внутреннего s t и внешне-внутреннего разделения, а также внешние f o , внутренние f t и внешне-внутренние передаточные числа вершин орграфа. В этом орграфе вершины 2 и 5 являются внешними центрами, вершины 3 и 5 — внутренними центрами, вершина 5 — внешне-внутренним центром, вершины 1 и 2 — внешними медианами, вершина 3 — внутренней медианой и вершины 1, 2 и 6 — внешне-внутренней медианой. s o f o 32 13 34 10 66 18 44 12 26 10 26 11 0 9 13 5 3 2 5 0 4 10 8 7 15 10 0 6 18 17 9 4 8 0 12 11 3 6 10 2 0 5 4 7 11 3 1 0 D s t 17 18 10 13 10 15 f t 42 42 26 49 36 36 s ot 28 28 22 31 20 28 f ot 68 68 70 115 70 68 Рис. Определение центров и медиан орграфа 205 Рассмотрим задачи, решение которых сводится к нахождению центров и медиан взвешенного орграфа. Задача 4.7. Несколько жилых районов связаны дорожной сетью. Необходимо разместить водном из них пожарное депо так, чтобы самый отдаленный пункт находился от него на минимально возможном расстоянии. Решение Построим взвешенный орграф, в котором вершины соответствуют районам, дуги соответствуют дорогам между районами, вес дуги — длина дороги. Пожарное депо можно разместить в районе, который соответствует вершине орграфа, являющейся внешним центром. Задача 4.8. Несколько жилых районов связаны дорожной сетью. Необходимо разместить водном из них больницу так, чтобы доставка пациента в больницу машиной скорой помощи из самого отдаленного района занимала минимально возможное время. Решение Построим взвешенный орграф, в котором вершины соответствуют районам, дуги соответствуют дорогам между районами, вес дуги — время проезда машины скорой помощи по соответствующей дороге. Больницу можно разместить в районе, который соответствует вершине орграфа, являющейся внешне-внутренним центром. Задача 4.9. Потребители обслуживаются товарами со склада. Потребитель посылает машину на склад, она загружается товаром и возвращается. Необходимо разместить складна территории одного из потребителей так, чтобы общее расстояние, проходимое транспортом, было бы минимально возможным. Решение Построим взвешенный орграф, в котором вершины соответствуют потребителям, дуги соответствуют дорогам между потребителями, вес дуги — длина дороги. Склад можно разместить на территории потребителя, который соответствует вершине орграфа, являющейся внешне-внутренней медианой. Задача 4.10. Электросеть должна охватывать заданные районы. Необходимо разместить водном из них подстанцию и протянуть линии электропередач от подстанции к каждому району так, чтобы суммарная длина проводников была минимально возможной. Решение Построим полный взвешенный граф, в котором вершины соответствуют районам, а вес ребра — расстоянию между соответствующими районами. Подстанцию можно разместить в районе, который соответствует вершине орграфа, являющейся медианой. 206 4.16. Клики и независимые множества Множество вершин M графа G = (V,E) называется кликой, если любые две вершины из этого множества смежны. Подграф графа G, построенный на множестве вершин M, являющимся кликой, представляет собой полный подграф. Обычно в графе можно найти несколько клик, например, каждая пара смежных вершин является кликой. Клика называется максимальной, если она не является собственным подмножеством никакой другой клики. В максимальную клику нельзя добавить ни одной вершины графа так, чтобы полученное множество было кликой. Максимальных клик в графе может быть несколько. Различные максимальные клики могут не пересекаться или находиться в общем положении, могут содержать одинаковое или различное число вершин. В графе, диаграмма которого представлена на рис, максимальных клик шесть, {2,3,6,7}, {3,4,7}, {5,6,2}, {5,8}, {7,8}. Рис. Диаграмма графа В полном графе есть только одна максимальная клика, состоящая из всех вершин графа. Наибольшее количество максимальных клик имеют графы Муна — Мозера. Граф Муна — Мозера с 3n вершинами строится следующим образом. Множество вершин разбивается на n непересе- кающихся классов потри вершины в каждом. Каждая вершина класса смежна только со всеми вершинами, не принадлежащими классу Взяв в таком графе по одной вершине из каждого класса, получим максимальную клику. Учитывая, что каждый класс состоит из трех вершин, количество максимальных клик в графе Муна — Мозера с 3n вершинами равно 3 n . На рис представлена диаграмма графа Муна — Мозера с двенадцатью вершинами. Множество вершин разбито на четыре класса 8 5 6 7 4 1 2 3 4 207 4 5 6 12 11 10 {1,2,3}, {4,5,6}, {7,8,9}, {10,11,12}. Выбирая из каждого класса по одной вершине, получим максимальную клику. Всего в этом графе 81 максимальная клика. Рис. Диаграмма графа Муна — Мозера Найти одну из максимальных клик можно последующему алгоритму. Алгоритм 4.15 поиска одной из максимальных клик Вход:граф G = (V,E). Выход M — максимальная клика. 1. M := {x}, x V; 2. V’ := V – ; 3. Пока V’ ≠ выполнять п 4. M := M {x}, x V’; V’ := V’ – ; 5. M — максимальная клика 6. Конец. В этом алгоритме на первом шаге в множество M включается одна из вершин графа. На втором шаге определяется множество вершин V’, элементы которого могут быть включены в формируемую клику M. На четвертом шаге вершина из множества V’ добавляется в M и V’ пересчитывается. ) (x Г ) (x Г 9 8 7 1 2 3 208 Все максимальные клики можно найти, используя метод поиска с возвращением. Алгоритм 4.16 (рис) поиска всех максимальных клик Вход:граф G = (V,E); M — клика V’ — множество вершин, смежных с каждой вершиной множества M. Выход последовательность максимальных клик. + Рис. Рекурсивный алгоритм получения всех максимальных клик Этот алгоритм имеет огромный недостаток каждая элементная максимальная клика будет повторяться n! раз. Процесс поиска всех максимальных клик в графе (рис) можно представить в виде дерева рис, в котором корень дерева соответствует исходной ситуации ни одна вершина не включена в клику, а листья — максимальным кликам. В этом дереве двухэлементные максимальные клики {1,2} и {2,5} повторяются по 2 раза, а трехэлементная клика {2,3,4} — 6 раз. Наиболее эффективным алгоритмом получения всех максимальных клик, основанном на методе поиска с возвращением, является алгоритм Брона — Кербоша. В этом алгоритме шаг назад выполняется в том случае, если продолжение поиска решения может привести только к получению максимальных клик, которые уже были получены ранее. В результате этого дерево поиска, а следовательно, и время выполнения алгоритма, значительно сокращается. Клика (V’,M) x V’ M’:=M {x} V’- ) (x Г = ; Конец Клика (Г) M’ 209 1,2 2,1 2,3 2,4 2,5 3,2 3,4 4,2 4,3 5,2 2,3,4 2,4,3 3,2,4 3,4,2 4,2,3 4,3,2 5,2 1 2 3 4 5 Рис. Диаграмма графа Рис.4.49. Дерево поиска всех максимальных клик На каждом шаге выполнения алгоритма Брона — Кербоша используются три множества 1) M — формируемая клика 2) K — множество кандидатов, те. вершин, каждая из которых может быть добавлена в формируемую клику M; 3) P — множество просмотренных вершин, каждая из которых не может быть добавлена в текущую клику, так как уже добавлялась ранее. Алгоритм 4.17 (рис) Брона — Кербоша поиска всех максимальных клик Вход:граф G = Выход последовательность максимальных клик. 2 3 4 1 5 210 + K := K – {v}; P := P {v} + Рис. Блок-схема алгоритма Брона — Кербоша Процесс выполнения алгоритма Брона — Кербоша при поиске всех максимальных клик в графе, диаграмма которого изображена на рис, можно представить в виде дерева (рис. Максимальная клика, содержащая наибольшее количество вершин по отношению ко всем другим максимальным кликам, называется наибольшей. Для поиска наибольшей клики можно перебрать все максимальные клики, используя алгоритм Брона — Кербоша, и выбрать среди них клику наибольшей мощности. Учитывая, что количество максимальных клик в графе с n вершинами может достигать 3 n/3 , этот подход не является эффективным. Эффективный алгоритм поиска наибольшей клики еще не найден. Брон — Кербош (G) Конец M := M {v} K := K – Г P := P – Г K:=V; P;= ; стек пуст Из стека (v,P,K,M) K или M M В стек (M,K,P,v|v K) 211 1,2 2,3 2,4 2,5 3,4 2,3,4 1 2 3 4 5 Рис. Дерево поиска всех максимальных клик по алгоритму Брона — Кербоша Для поиска максимальной клики, близкой по мощности к наибольшей, применяют эвристические алгоритмы, которые позволяют быстро получить решение. В большинстве случаев это решение представляет собой наибольшую клику, а иногда — максимальную клику меньшей мощности, чем наибольшая. Рассмотрим три алгоритма поиска максимальной клики, близкой по мощности к наибольшей. В первом алгоритме сначала в множество M, в котором по окончании выполнения алгоритма будет находиться максимальная клика, включаются все вершины графа. Затем из этого множества последовательно исключаются вершины, которые не смежны с наибольшим числом вершин из множества M. Исключения вершин продолжается до тех пор, пока все вершины в множестве M будут попарно смежны. Это и будет максимальная клика, близкая по мощности к наибольшей. Алгоритм 4.18 поиска максимальной клики, близкой по мощности к наибольшей Вход:граф G = (V,E). Выход M — максимальная клика, близкая по мощности к наибольшей. 1. Определить G’ = (V’,E’), где V’ = V, E’ = E. 2. M := V’. 3. Вычислить степени вершин в графе G’. Пусть x — вершина, степень которой минимальна, d(x) — степень вершины x. 4. Пока d(x) < |V’| – выполнять 4.1. M := M – {x}. 4.2. Удалить из графа G’ вершину x с инцидентными ребрами. 4.3. Выполнить п. 5. Конец алгоритма. 212 Во втором алгоритме в исходном состоянии множество M пусто и на каждом шаге добавляется в него вершина наибольшей степени, смежная всем вершинам этого множества. Если на некотором шаге не найдется вершины, которую можно добавить в множество M, то множество M содержит максимальную клику. Алгоритм 4.19 поиска максимальной клики, близкой по мощности к наибольшей Вход:граф G = (V,E). Выход M — максимальная клика, близкая по мощности к наибольшей. 1. Определить G’ = (V’,E’), где V’ = V, E’ = E. 2. M := . 3. Пока V’ выполнять 3.1. Вычислить степени вершин в графе G’. Пусть x — вершина, степень которой максимальна. 3.2. M := M {x}. 3.3. Вершины ) (x Г удалить из графа G’ с инцидентными им ребрами. 4. Конец алгоритма. В третьем алгоритме для каждой пары смежных вершин (каждого ребра) e = {v i ,v j } вычисляется характеристика h(e) = min(d(v i ), d(v j )), где d(v i ) и d(v j ) — степени концевых вершин v i и ребра e. Вероятно, пара вершин, имеющая большую характеристику, может быть включена в максимальную клику большей мощности, чем пара вершин, имеющая меньшую характеристику. Максимальная клика, близкая по мощности к наибольшей, строится по алгоритму 4.19, в котором во втором пункте в множество М включается пара вершин с наибольшей характеристикой и вершины, не смежные этим вершинам, удаляются с инцидентными им ребрамииз графа G’. Пары вершин, характеристики которых меньше мощности полученной клики не могут быть включены в клику большей мощности, поэтому такие пары вершин исключаются из дальнейшего рассмотрения. Из оставшихся пар смежных вершин снова выбирается пара с наибольшей характеристикой и относительно нее строится новая максимальная клика, возможно, большей мощности. Процесс заканчивается когда все пары смежных вершин будут рассмотрены. Этот алгоритм позволяет быстро находить наибольшую клику в графах, в которых никакой полный подграф не является подмножеством объединения всех остальных полных подграфов. 213 Алгоритм 4.20 поиска максимальной клики, близкой по мощности к наибольшей Вход:граф G = (V,E). Выход M — максимальная клика, близкая по мощности к наибольшей. 1. Построить последовательность P пар смежных вершин, упорядоченных по неубыванию характеристик. 2. M := . 3. Пока последовательность P не пуста, выполнять 3.1. Найти максимальную клику M’, содержащую первую пару {v i ,v j } вершин из последовательности P по алгоритму 4.19, в котором 2. M := заменить на 2. M := {v i ,v j }. Вершины, не смежные си, удалить из графа G’ с инцидентными им ребрами. Если |M’ |> |M|, то M := M’. 3.3. Исключить из последовательности P пары вершин, характеристика которых меньше |M|. 4. Конец алгоритма. Множество вершин M графа G = (V,E) называется независимым, если никакие две вершины из этого множества не смежны. Независимое множество является некоторой противоположностью клики. Граф ) ' , ( E V G называется дополнением графа G = (V,E), если в нем две вершин смежны только в том случае, если эти вершины не смежны в графе G. Независимое множество вершин графа G = (V,E) представляет собой клику в графе ) ' , ( E V G и клика графа G = (V,E) представляет собой независимое множество в графе Независимое множество называется максимальным, если оно не является собственным подмножеством никакого другого независимого множества. Максимальное независимое множество, содержащее наибольшее количество вершин по отношению ко всем другим максимальным независимым множествам, называется наибольшим. Для поиска максимальных и наибольших независимых множеств в графе G могут применяться рассмотренные выше алгоритмы поиска максимальных и наибольших клик в графе G 214 Рассмотрим задачи, решение которых сводится к нахождению наибольшего независимого множества. Задача 4.11. Передатчик может передавать сигналы приемнику из конечного множества V = {v 1 , v 2 ,…, v n }. При передаче возникают искажения сигналов и приемник может перепутать некоторые сигналы, какие именно — известно. Для кодирования передаваемых сообщений необходимо найти наибольшее количество сигналов из множества V, которые приемник не перепутает. Решение. Построим граф, вершины которого соответствуют сигналам из множества V, пара вершин образует ребро, если соответствующие им сигналы приемник может перепутать. Наибольшее по мощности множество сигналов, которое можно использовать для кодирования сообщений, соответствует наибольшему независимому множеству. Задача 4.12. Имеется n проектов, которые должны быть выполнены. Для выполнения каждого проекта требуется определенное подмножество ресурсов. Один и тот же ресурс не может быть использован одновременно в выполнении различных проектов. Требуется выбрать максимальное подмножество проектов, которые могут быть выполнены одновременно. Решение. Построим граф, вершины которого соответствуют проектам, пара вершин образует ребро, если для выполнения соответствующих им проектов требуется хотя бы один общий ресурс. Такие проекты нельзя выполнять одновременно. Максимальное подмножество проектов, которые могут быть выполнены одновременно, соответствует наибольшему независимому множеству. Задача 4.13. Имеется n проектов, которые должны быть выполнены. Для выполнения каждого проекта требуется определенное подмножество ресурсов. Один и тот же ресурс не может быть использован одновременно в выполнении различных проектов. Известна стоимость каждого проекта. Требуется выбрать подмножество проектов с максимальной суммарной стоимостью, которые могут быть выполнены одновременно. Решение. Построим граф, вершины которого соответствуют проектам, пара вершин образует ребро, если соответствующие им проекты нельзя выполнять одновременно. Найдем все максимальные независимые множества. Определим суммарную стоимость подмножеств проектов, соответствующих максимальным независимым множествами выберем среди них подмножество с максимальной суммарной стоимостью. |