Построение минимальных расширений графа методом канонических представителей | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/50

Построение минимальных расширений графа методом канонических представителей

Граф G* называется вершинным (рёберным) k-расширением графа G, если после удаления любых k вершин (рёбер) из графа G* граф G вкладывается в получившийся граф. Вершинное (рёберное) k-расширение графа G называется минимальным, если оно имеет наименьшее число вершин и рёбер среди всех вершинных (рёберных) k-расширений графа G. Предлагается алгоритм построения всех неизоморфных минимальных вершинных (рёберных) k-расширений заданного графа без проверки на изоморфизм.

On the generation of minimal graph extensions by the method of canonical representatives.pdf В разработке безопасных систем большое значение имеет отказоустойчивость. Под отказоустойчивостью понимается свойство системы сохранять работоспособность после отказа. В 1976 г. JohnP. Hayes [1] предложил основанную на графах модель для исследования отказоустойчивости элементов. Позднее модель была распространена на отказы связей [2]. Формализацией отказоустойчивой реализации системы является расширение графа системы [3]. Граф G* = (V*,а*) называется минимальным вершинным k-расширением n-вер-шинного графа G = (V, а), если выполняются следующие условия: 1) граф G* является вершинным k-расширением графа G, то есть G вкладывается в каждый граф, получающийся из G* удалением любых его k вершин; 2) граф G* содержит n + k вершин, то есть |V* | = |V| + k; 3) а* имеет минимальную мощность при выполнении условий 1 и 2. Граф G* = (V*, а*) называется минимальным рёберным k-расширением n-вершин-ного графа G = (V, а), если выполняются следующие условия: 1) граф G* является рёберным k-расширением графа G, то есть G вкладывается в каждый граф, получающийся из G* удалением любых его k рёбер; 2) граф G* содержит n вершин, то есть |V*| = |V|; 3) а* имеет минимальную мощность при выполнении условий 1 и 2. Определение минимального рёберного k-расширения отличается тем, что дополнительные вершины не добавляются. Задача построения минимальных вершинных и рёберных k-расширений является вычислительно сложной [4]. Для построения минимальных k-расширений графов с малым числом вершин можно использовать переборный алгоритм 1 [3]. Алгоритм 1. Построение всех минимальных вершинных k-расширений графа 1: m := 0. 2: m := m +1. 3: Строим все графы, получающиеся из графа G добавлением k вершин и m дополнительных рёбер. 4: Выбираем среди построенных графов вершинные k-расширения графа G. 5: Если на шаге 4 не было найдено графов, то переходим на шаг 2. 6: Среди графов, выбранных на шаге 4, оставляем по одному представителю от классов изоморфных графов. Для построения минимальных рёберных k-расширений на шаге 3 не нужно добавлять k вершин, а на шаге 4 нужно проверять, является ли граф рёберным k-рас-ширением. Далее будем рассматривать задачу построения минимальных вершинных k-расширений, хотя все идеи применимы и для построения минимальных рёберных k-расширений. У алгоритма 1 можно выделить несколько недостатков, связанных с избыточным перебором. Один из них состоит в следующем: если на шаге 3 могут появляться изоморфные графы, то необходимо хранить все построенные расширения, чтобы на шаге 6 исключить изоморфные копии. Если на шаге 3 строить только неизоморфные графы, то необходимость хранения всех построенных расширений исчезнет. Можно использовать метод канонических представителей, при котором из каждого класса изоморфных графов выбирается один канонический представитель. Идея метода в общем виде состоит в следующем [5]: 1) определяется способ кодирования графов; 2) среди всех кодов изоморфных графов выбирается канонический код (представитель); 3) порождаются все возможные коды графов; 4) порождённый граф принимается, если его код канонический, в противном случае исключается. Получим алгоритм 2. Алгоритм 2. Построение всех минимальных вершинных k-расширений графа без проверки на изоморфизм 1: m := 0. 2: m := m +1. 3: Строим все неизоморфные графы, получающиеся из графа G добавлением k вершин и m рёбер. 4: Выбираем среди построенных графов вершинные k-расширения графа G. 5: Если на шаге 4 не было найдено графов, то переходим на шаг 2. 6: Полученные на шаге 4 графы являются минимальными вершинными k-расшире-ниями графа G. Для использования метода канонических представителей самым важным является выбор канонического кода. Предлагается взять код, основанный на матрице смежности графа. Для простых неориентированных графов матрица смежности симметрична относительно главной диагонали, а на главной диагонали расположены нули. Через G обозначим граф, для которого требуется найти минимальное вершинное или рёберное k-расширение, через H - граф, для которого будем строить код. Если число вершин в графе G меньше числа вершин графа H, то добавляем к графу G изолированные вершины. Определим код CG(H) графа H следующим образом: будем дважды просматривать элементы матрицы смежности графа G, находящиеся выше главной диагонали, по столбцам слева направо и выписывать соответствующие элементы матрицы смежности графа H по следующим правилам: 1) в первый раз выписываем элемент матрицы смежности H, если в матрице смежности G стоит 1; 2) во второй раз выписываем элемент матрицы смежности H, если в матрице смежности G стоит 0. В столбце элементы матрицы смежности перечисляются сверху вниз. На рис. 1 приведён пример построения кода. Будем называть граф H каноническим относительно G (либо просто каноническим) и его код каноническим, если среди всех графов, изоморфных H, код графа H является лексикографически наибольшим: VR = H, R = H(CG(R) < CG(H))). Если G является частью графа H, то Cg(G) ^ CG(H), иначе Cg(G) > CG(H). Справедливо следующее утверждение: граф G вкладывается в граф H тогда и только тогда, когда существует W = H, такой, что Cg(W) ^ Cg(G). Это означает, что M„ Порядок выписывания M 0 1 0 0 0 0 1 5 6 8 0 1 0 0 0 1 0 1 0 0 1 0 2 7 9 1 0 1 1 0 0 1 0 1 1 0 1 0 3 4 0 1 0 0 1 0 0 1 0 0 0 1 0 0 10 0 1 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 1 1 0 CJG) = 1111000000 C(H) = 1101001001 Рис. 1. Пример построения кода Cg(H) если граф G вкладывается в граф H, то существует изоморфный ему канонический граф W, для которого CG(W) ^ Cg(G). Таким образом, канонический представитель класса изоморфизма каждого графа, в который вкладывается G, может быть получен добавлением рёбер в граф G. Следовательно, алгоритм 2 является корректным.

Ключевые слова

отказоустойчивость, расширение графа, изоморфизм, канонический код, метод канонических представителей, fault tolerance, graph extension, isomorphism, canonical code, generating canonical representatives

Авторы

ФИООрганизацияДополнительноE-mail
Камил Ихаб Абдулджаббар КамилСаратовский национальный исследовательский государственный университет им. Н. Г. Чернышевскогоаспирантkamil.iehab@mail.ru
Судани Хайдер Хуссейн КаримСаратовский национальный исследовательский государственный университет им. Н. Г. Чернышевскогоаспирантhayder.1977@mail.ru
Лобов Александр АндреевичСаратовский национальный исследовательский государственный университет им. Н. Г. Чернышевскогостарший лаборантaisanekai@mail.ru
Абросимов Михаил БорисовичСаратовский национальный исследовательский государственный университет им. Н. Г. Чернышевскогодоктор физико-математических наук, заведующий кафедройmic@rambler.ru
Всего: 4

Ссылки

Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. V.C.25. No. 9. P. 875-884.
Harary F. and Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. V. 23. P. 135-142.
Абросимов М. Б. Графовые модели отказоустойчивости. Саратов: Изд-во Сарат. ун-та, 2012. 192 с.
Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. №5(88). С. 643-650.
Brinkmann G. Isomorphism rejection in structure generation programs // DIMACS Series Discr. Math. Theor. Comput. Sci. 2000. V.51. P. 25-38
 Построение минимальных расширений графа методом канонических представителей | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/50

Построение минимальных расширений графа методом канонических представителей | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/50