Графическое представление алгоритма получения аналитической формулы для вычисления количества простых циклов в произвольном графе

Графическое представление алгоритма получения аналитической формулы для вычисления количества простых циклов в произвольном графе Широков И.В.1, Шутенко А.В.2, Астахов М.С.3

1Широков Игорь Викторович /Shirokov Igor Viktorovich - кафедра комплексной защиты информации, профессор, доктор физико-математических наук; 2Шутенко Александр Викторович /Shutenko Aleksandr Viktorovich - кафедра комплексной защиты

информации, аспирант; 3Астахов Михаил Сергеевич / Astakhov Mikhail Sergeevich - кафедра комплексной защиты

информации, аспирант Омский государственный технический университет, г. Омск

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

Ключевые слова: граф, ребро, вершина, простой цикл, гамильтонов цикл. Keywords: graph, edge, vertex, simple cycle, Hamiltonian cycle.

Задача определения количества простых циклов заданной длины в произвольном графе является КР-полной и её решение не является тривиальным [1, 42]. В случае с графами, имеющими достаточно небольшое количество вершин, решение сводится к анализу графа с целью упростить задачу или к широко известным методам «поиск в ширину», «поиск в глубину» [2, 211], «окрашивание» и др. [3, 2], которые в свою очередь сводятся к простому перебору или по крайне мере сравнимы по временным затратам на решение задачи с ним. Ввиду того, что данная задача является №-полной задачей, то временные затраты на её решение в случае большого количества вершин в графе будут превосходить оптимально допустимые временные рамки [4, 202-203].

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

Алгоритм получения аналитической формулы вычисления количества простых циклов заданной длины в произвольном графе

Рассмотрим следующее выражение

Введение

n

где А - матрица смежности графа G , G - произвольный граф, к - к -я вершина графа G , №А - след матрицы А . Математическим значением формулы (1) является количество циклов длины к в графе G , умноженное на 2к.

Суммирование происходит от /1 до ¡к , а это значит, что каждый цикл будет посчитан столько раз, сколько в нем вершин умноженное надвое т.к. цикл можно пройти как в одну, так и в другую сторону.

Т.к. матричные элементы обладают следующими свойствами:

аг,у = 0 аг,у = ау,г , аг,^г,у = у ,

то выражение аи аи ...аи будет принимать значение 1, если цикл г1 ^ г2 ^ ...1к ^ г1 длины к существует, и 0, если такой цикл не существует.

Введем обозначение /г Ак :

К Ак = V а„ а,, ...а,,, гз)

12 2 3 'к1!*

г1,г2'---'гк> гу *ь

, - Фц будем называть препятствием. Препятствия следует учитывать для исключения повтора вершин в цикле, что является необходимым условием для его простоты. Таким образом, формула (3) - это количество простых циклов длины к в графе О, умноженных на 2к . Следовательно, для вычисления всех простых циклов длины к необходимо вычислить значение Ск (О) :

Ск

к w 2к

Для вычисления правой части формулы (3) следует пользоваться следующими очевидными формулами:

ТА = ТА - А

г*] г

п

Та, = гт

г * У

Графическое представление алгоритма получения аналитической формулы

Будем считать а^. ребром графа О , тогда граф О будет содержать ребра а^а^ --а^

. Следовательно, 1г Ак можно представить в специальном виде.

Рассмотри пример ¿г А4 . Алгоритм получения аналитической формулы можно представить в графическом виде, если каждому сомножителю аи , входящему в сумму

Еаи аи

12 2 3

а

'к'1 '

поставить в соответствие ребро, тогда сумма (7) будет иметь вид:

Рисунок 1. Графическое представление суммы

При этом каждое слагаемое на выходе формулы (7) получается путем склейки не смежных двух вершин, а каждое двойное ребро заменяется одинарным.

Рассмотрим к = 4. Возможные склейки 1=3 и 2=4. После выполнения склеек получатся 2 изоморфных графа:

Рисунок 2. Возможные склейки

в графе (1,2)(2,3)(3,1) также присутствует препятствие 1 ^ 3 , результат процедуры склейки даст следующий результат:

Рисунок 3. Возможные склейки

При записи получаемых графов, в результате склейки, следует пользоваться следующим правилом определения знака: если склейка выполняется на четном этапе следует поставить «+», если нечетном, то «-».

Конечный результат соответствует действительности и имеет следующий вид:

Рисунок 4. Возможные склейки

Следует отметить, что по получаемым графам можно восстановить исходную формулу путем замены графов суммами, с сохранением знака, и суммирования по каждой вершине.

Рассмотрим к = 5. Представим (г А5 в виде графа: (1,2)(2,3)(3,4)(4,5)(5,1). в котором пунктирными линиями обозначены возможные склейки: 1=3, 1=4, 2=4, 2=5, 3=5. При поэтапном избавлении от препятствий (от пунктирных линий, путем склейки соединенных ими вершин) вывод аналитической формулы будет иметь следующий вид:

Рисунок 5. Вычисление аналитической формулы с помощью графического метода

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

Литература

1. Оре О. Графы и их применение. М.: Мир,1965.175 с.

2. Девитин А. Алгоритмы. Введение в разработку и анализ. М.: Вильямс, 2006. с.576.

3. Радионова А.В. Демонстрационная компьютерная модель «Обход графов» // Молодой ученый. 2012. № 8. с.42-45.

4. Колмогоров А. Н. Теория информации и теория алгоритмов. М.: Наука, 1987. с.304.