FINDING THE BETA CYCLE IN A GRAPH – NP- COMPLETE PROBLEM

Белаш А.Н.

Доцент, Северо-Кавказский федеральный университет

НАХОЖДЕНИЕ БЕТА ЦИКЛА НА ГРАФЕ – NP-ПОЛНАЯ ЗАДАЧА

Аннотация

В статье рассмотрено – доказательство NP-полноты задачи нахождения Бета цикла на графе

Ключевые слова: теория графов, циклы, NP-полнота.

Belash A.N.

Lecturer, North-Caucasus Federal University

FINDING THE BETA CYCLE IN A GRAPH – NP- COMPLETE PROBLEM

Abstract

The article considers the proof of NP-completeness of the problem of finding the beta cycle in a graph

Keywords: graph theory, cycles, NP-completeness.

 

Теорема.  Нахождение цикла Бета на графе представляет собой  полную задачу.

 

Доказательство

УСЛОВИЕ. Задан граф . А также задано множество  граней Бета, где

ВОПРОС. Верно ли, что  содержит цикл Бета (БЦ)?

Так мы можем сформулировать фиксированную индивидуальную задачу из БЦ. Далее мы будем определять задачу, которая будет связана с нахождением ГЦ и будет связана с индивидуальной задачей БЦ.

Пусть задан граф . Множество вершин  совпадает с множеством . Для любых двух вершин  расстояние  между ними полагаем равным 1, если грани  и  имеют общее ребро, то есть они смежные. Если они не смежные, то расстояние между  и  будем полагать равным 2. Граница  для длины искомого маршрута берется равной .

Проверим первое требование сводимости:

Существует ДМТ-программа, вычисляющая с временной сложностью, ограниченной полиномом [1].

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

Далее проверим второе требование сводимости:

Для любого  в том и только в том случае, если  [1].

Для проверки второго условия необходимо показать, что  содержит БЦ тогда и только тогда, когда в имеется проходящий через все вершины маршрут длины, не превосходящей . Вначале допустим, что  - БЦ в . Тогда - маршрут в , а его длина равна  , так как расстояние между соседними вершинами равно 1, поскольку оно соответствует ребру (для двух смежных граней) в .

Наоборот, предположим, что  - маршрут в , длина которого не превосходит . Поскольку расстояние между двумя вершинами в  равно либо 1, либо 2 и при вычислении длины маршрута суммируется ровно  таких расстояний, то из равенства  следует, что расстояние между каждой парой соседних вершин в маршруте равно 1. По определению , отсюда следует, что  -  БЦ в , где , ,…, . Теорема доказана.