ПРОБЛЕМА ВЫЧИСЛЕНИЯ КОЛИЧЕСТВА ПРОСТЫХ ЦИКЛОВ В ПРОИЗВОЛЬНОМ ГРАФЕ Шутенко А.В.,Астахов М.С.,Широков И.В.

Омский государственный технический университет


Номер: 8-1
Год: 2014
Страницы: 20-23
Журнал: Актуальные проблемы гуманитарных и естественных наук

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

Просмотр статьи

⛔️ (обновите страницу, если статья не отобразилась)

Аннотация к статье

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

Текст научной статьи

Введение Существует старейшая классическая задача определения является ли граф гамильтоновым или нет [1, 42]. Гамильтонов граф - это граф содержащий путь (цепь), в который входит каждая вершина графа ровно один раз. Однако на сегодняшний день не существует эффективного способа решения данной задачи. Так же не существует эффективного метода поиска всех простых циклов в графе. Цикл называется простым, если каждая вершина входит в него только один раз. Для решения задачи определения (поиска) гамильтонова цикла (а так же простых циклов) существуют такие методы как "поиск в ширину", "поиск в глубину", "колорирование" и др. Поиск в глубину - это один из методов обхода графа [2, 211]. Алгоритм поиска описывается следующим образом: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Поиск в ширину - это так же метод обхода графа, заключающийся в перемещении от исходной вершины ко всем смежным с ней (в ширь) [2, 211]. Сам алгоритм можно понимать как процесс "поджигания" графа: на нулевом шаге поджигаем только исходную вершину. На каждом следующем шаге огонь с каждой уже горящей вершины перекидывается на всех её соседей; т.е. за одну итерацию алгоритма происходит расширение "кольца огня" в ширину на единицу (отсюда и название алгоритма). Колорирование - данный метод заключается в условном окрашивании посещенный вершин в определенный цвет (присвоение метки), что позволяет в любой момент определить является ли данная вершина посещенной или нет [3, 2]. На данном методе базируются другие методы обхода графа. Выше представленные методы способствуют решению задачи поиска гамильтонова цикла, а так же простых циклов. Следует заметить, что данная задача является NP-полной задачей и её решение данными методами малоэффективно и требует невозможно большого времени для графов с большим количеством вершин (ребер) [4, 202-203]. Далее будет представлен способ позволяющий снизить временные затраты на решение данной проблемы. Вывод аналитической формулы Рассмотрим следующее выражение (1) где - матрица смежности графа , - произвольный граф, - -я вершина графа , - след матрицы . Математическим значением формулы (1) является количество циклов длины в графе , умноженное на . Суммирование происходит от до , а это значит, что каждый цикл будет посчитан столько раз, сколько в нем вершин умноженное надвое т.к. цикл можно пройти как в одну, так и в другую сторону. Т.к. матричные элементы обладают следующими свойствами: (2) то выражение будет принимать значение 1, если цикл длины существует, и 0, если такой цикл не существует. Введем обозначение : (3) будем называть препятствием. Препятствия следует учитывать для исключения повтора вершин в цикле, что является необходимым условием для его простоты. Таким образом, формула (3)- это количество простых циклов длины в графе умноженных на . Следовательно, для вычисления всех простых циклов длины необходимо вычислить значение : (4) Для вычисления правой части формулы (3) необходимо воспользоваться следующими очевидными формулами: (5) (6) где - матрица, все элементы которой равны 1. Разберем пример. Задача: найти количество простых циклов длины 3 () в графе . Решением данной задачи является вычисление значения по формуле (4): (7) возведя матрицу смежности в куб и вычислив след полученной матрицы, мы вычислим количество простых циклов длины в графе . Следует заметить, что в данном примере отсутствуют препятствия. Для удобства представления формул (1), (2) введем следующие обозначения: (8) формулы (2) будут иметь следующий вид: (9) Рассмотрим случай : (10) пользуясь обозначениями (8), (9) получаем: (11) Избавляясь от первого препятствия по формуле (5) получаем: (12) пользуясь формулами (2) упрощаем это выражение: (13) Избавляясь от второго препятствия имеем: (14) Вновь пользуясь формулами (2) для упрощения выражения получаем: (15) В общем виде результат будет иметь вид: (16) пользуясь (6) запишем следующим образом: (17) т.к. присутствуют одинаковые слагаемые, то после упрощения выражения получаем: (18) Таким образом, будет вычисляться следующим образом (19) Вычислить значение формулы (18) достаточно просто, для этого необходимо уметь умножать матрицы (возводить в квадрат), а так же вычислять след матрицы. Если оценивать сложность умножения матриц, а это умножение таблиц смежности, содержащих только 0 и 1, то получим , где - размер матрицы. Использование приведенных во введении методов означает, что для поиска всех простых циклов длины 4 в графе с вершинами необходимо совершить операций. Отсюда следует, что данные методы имеют сложность . Очевидно, что предложенный нами способ вычисления является эффективным по времени относительно общеизвестных методов, представленных во введении.

Научные конференции

 

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