ПОИСК МИНИМАЛЬНЫХ ДОМИНИРУЮЩИХ МНОЖЕСТВ И ИХ ПРИМЕНЕНИЕ

В теории графов доминирующее множество для графа G = (V, E) — это подмножество D множества вершин V, такое, что любая вершина не принадлежащая D смежна хотя бы одному элементу из D. Число доминирования γ(G) — это число вершин в  наименьшем доминирующем множестве G. Например, для графа, представленного на рисунке 1 множество  является доминирующим, а множество  – наименьшим доминирующим множеством.[2]

Рисунок 1. Доминирующие множества

Примерами доминирующих множеств могут быть объекты в пространстве – магазины, школы, больницы и т.д., которые находятся «в шаговой доступности», а число доминирование – общее количество таких объектов.

Алгоритм поиска

Прежде чем говорить о практическом применении доминирующих множеств в нашей жизни, рассмотрим алгоритм поиска. Для начала стоит сказать, что данная задача является NP-полной, т.е. не существует эффективного алгоритма для её решения (за полиномиальное время). Поэтому разработанный алгоритм является модифицированным алгоритмом полного перебора. За основу был взят метод Магу, принцип действия которого состоит в следующем [1, c. 102 – 132]:

• Для графа составляется матрица смежности;
• Матрица смежности дополняется единицами на главной диагонали;
• Для каждой строки выписываются дизъюнкции;
• Выражение приводится к ДНФ;
• Все вершины, входящие в элементарную конъюнкцию, образуют доминирующее множество.

Предложенный алгоритм нахождения минимальных доминирующих множеств работает следующим образом:

• Для графа составляется матрица смежности;
• Матрица смежности дополняется единицами на главной диагонали;
• Рассмотрим по очереди все возможные сочетания дизъюнкции столбцов, т.е. подмножества вершин: {1}, {2} , …,{n}, {1,2}, {1,3} , … , {1, n}, … , {n-1,n} , {1,2,3}, {1,2,4}, {1,2,3,…,n-1,n}, где n – количество вершин в графе;
• Если полученный столбец состоит только из единиц, тогда выписываем комбинацию данных вершин, запоминаем их количество (например, k) и переходим к следующему подмножеству;
• Когда были рассмотрены все подмножества мощности k, алгоритм останавливает свою работу, т.к. минимальное доминирующее множество было найдено.

Рассмотрим пример работы алгоритма:

Следовательно, комбинация вершин 1 и 3 не является элементом доминирующего множества. Перебирая все возможные подмножества мощности 2, мы получим ответ: {(1,2) , (1,4), (2,3) , (3,4)}.

Преимущества и недостатки алгоритма

Преимущества:

• Работает абсолютно для всех графов (неориентированных, ориентированных, с циклами и т.д.);
• Алгоритм прост для понимания;
• Найдет всегда полное минимальное доминирующее множество.

Недостатки:

• Алгоритм полного перебора;
• Добавление вершины к исходному графу увеличивает среднее работы программы примерно в 1,5 - 2 раза;
• При большом количестве вершин (> 30) потребляет большое количество ресурсов

Практическое применение

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

Для начала возьмём карту Промышленного района г. Самара (см. рисунок 2) и составим для неё граф с помощью следующих правил:

1. Микрорайон – это вершина графа.
2. Если два микрорайона имеют общие границы, то вершины, соответствующие им, соединяются ребром.

Рисунок 2. Карта Промышленного района

Для полученного графа (см. рисунок 3) составим матрицу смежности для нахождения минимального доминирующего множества. С помощью разработанного алгоритма получим следующий результат: {(1,6,8,13), (1,7,8,13), (2,6,8,13), (2,7,8,13), (3,6,8,13), (3,6,9,12), (3,6,10,12), (3,6,10,13), (3,6,10,14), (3,6,11,14), (3,6,12,14), (3,7,8,13)}.

Рисунок 3. Граф, построенный на основе карты Промышленного района

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

Детские сады

Из рисунка 4 видно, что больше всего детских садов расположено в «вершинах» (1,8,10,11) (на рисунке изображены красным цветом), что не соответствует результату работы программы. Такое решение является оптимальным, так как удаленные точки графа (7,14) имеют свои детские сады.

Рисунок 4. Расположение детских садов

Школы

Для школ складывается похожая ситуация, как и для детских садов: наибольшее количество школ находятся в вершинах (1,7,8,11) (данные микрорайоны выделены красным цветом на рисунке 5). Удаленные точки графа (13,14) имеют свои собственные школы, так что данное решение можно назвать оптимальным.

Рисунок 5. Расположение школ

Больницы

Если же посмотреть на расположение больниц в Промышленном районе (рис. 6), то увидим следующую ситуацию: кроме того, что их не так уж и много, расположены они не самым удачным образом. Жителям удаленных микрорайонов (3,4) не очень удобно добираться до больниц, так как ближайшие учреждения находятся в вершинах 1 или 7 либо ещё дальше в вершинах 9 и 12.

Рисунок 6. Расположение больниц

Заключение

Из рассмотренных примеров можно сделать следующие выводы:

1. Расположение детских садов и школ в Промышленном районе можно считать оптимальным: жителям каждого из микрорайонов будет удобно и быстро добираться до каждого из этих учреждений. Стоит отметить, что этот эффект достигается ввиду большого количества исследуемых учреждений, а не качеством распределения имеющихся ресурсов.
1. Подтверждает это и расположение больниц, которых в Промышленном районе значительно меньше, чем школ или детских садов. На рисунке 5 видно, как верхняя левая часть карты буквально «пустует», и жителям тех микрорайонов, очевидно, придется потратить больше времени и сил, чтобы добраться до больницы, чем их соседям.

Из этого следует, что доминирующие множества все ещё не нашли своего применения в окружающей нас реальности. С другой стороны, для более детального изучения этой проблемы стоит, как расширить область для анализа (например, проанализировать не только Промышленный район, а весь город), так и посмотреть на другие виды жизнедеятельности человека.

Список литературы:

1. Лекции по теории графов [Текст]: учебное пособие для студентов/В.А. Емиличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. – Москва: «Наука» Гл. ред. физ.-мат. лит., 1990 – 384с.
2. Википедия [Электронный ресурс]: доминирующие множества – режим доступа: URL - https://ru.wikipedia.org/wiki/Доминирующее_множество