ВЕЛИХОВСКИЙ О.В. МЕТОД ПОСТРОЕНИЯ ЗАМКНУТОГО ПУТИ НА НЕОРИЕНТИРОВАННОМ СИММЕТРИЧНОМ ГРАФЕ ПРИ РЕШЕНИИ ЗАДАЧ ОПТИМИЗАЦИИ


ВЕЛИХОВСКИЙ О.В. МЕТОД ПОСТРОЕНИЯ ЗАМКНУТОГО ПУТИ НА НЕОРИЕНТИРОВАННОМ СИММЕТРИЧНОМ ГРАФЕ ПРИ РЕШЕНИИ ЗАДАЧ ОПТИМИЗАЦИИ


Рубрика: 01.00.00 ФИЗИКО-МАТЕМАТИЧЕСКИЕ НАУКИ, 05.00.00 ТЕХНИЧЕСКИЕ НАУКИ

Библиографическая ссылка на статью:
// Современные научные исследования и инновации. 2012. № 3 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2012/03/10417 (дата обращения: 29.09.2017).


Велиховский О.В., инженер, бакалавр кафедры

электрические системы и сети, КПИ, г. Киев

Исходные данные

Предположим, что задано некоторое конечное множество вершин в трёхмерном Евклидовом пространстве и множество неупорядоченных пар из этих вершин

|E |= n , |V |= m , ( n,m ) =1,2,3,… (1)


Таким образом задан неориентированный симметричный граф:

G ( V , E )

На заданном графе требуется построить минимальный элементарный цикл или цикл Гамильтона.

Метод построения

Для решения задачи построения будем применять некоторый предикат :

R ( V , E )

Такой предикат будем называть предикатом выбора по наиболее удалённой паре вершин или по диаметру графа

R ( V, E ) = R ( diam(G) ) (2)

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

(v1 ,v2) | V | (3)

Emax=En=diam(G) (4)

Затем выберем следующую вершину v3
из | V | , которая находится на максимальном расстоянии от одной из вершин диаметра или одного из полюсов
Вершины образующие диаметр графа будем называть полюсами графа и обозначать (
V ,U )


E
n = {
V, U }
(5)

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

Соединим вершины ребра Еn= diam(G) c вершиной v3 по кратчайшему пути, то есть минимальному расстоянию между ними , соответственно.

Для наглядного представления предположим , что множество всех вершин | V |
расположено внутри некоторой мнимой сферы, и такая сфера сжимается равномерно по всем направлениям. Тогда поверхность этой сферы будет последовательно касаться всех вершин, начиная от самых удалённых друг от друга и заканчивая менее удалёнными соответственно, до тех пор пока поверхность этой сферы коснётся (соединит) всех вершин |V| в порядке уменьшения расстояния между ними .


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


Рисунок 1.                                                    Рисунок 2.

Из рисунка 2 видно, что на первом и втором этапах построения из цикла исключается ребро En= diam(G). В результате был построен цикл Гамильтона, состоящий из четырёх вершин .

На следующих двух этапах определяем новую вершину v5 следующую за вершиной v4 по максимальной удалённости от одного из полюсов графа и новую вершину v6 следующую за вершиной v5 по максимальной удалённости от одного из полюсов графа. Затем соединяем новые вершины аналогично предыдущему этапу построения с ближайшими к ним рёбрами соответственно. Сначала с ближайшей вершиной из предыдущего цикла, а затем с вершиной того же ребра максимально удалённой от полюса графа ближайшего к новой вершине соответственно .

Рисунок 3.                                               Рисунок 4.

Из рисунка 4 видно, что на втором и третьем этапах построения из цикла исключаются ребра ближайшие к новым вершинам v5 и v. В результате был построен цикл Гамильтона состоящий из шести вершин .

На следующих этапах построения проводятся аналогично предыдущим этапам для любого количества новых вершин vm из | V | . В результате будет построен цикл Гамильтона для всех заданных вершин | V | и по величине состоящий из множества рёбер | E| .


 Рисунок 5.                                                                                  Рисунок 6.

На рисунке 6 построен цикл Гамильтона состоящий из восьми вершин .

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

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

Рисунок 7.                                                                  Рисунок 8.

На рисунках 7 и 8 построены два очередных элементарных цикла, следующих сразу за минимальным циклом Гамильтона по увеличению | E |

| E|< | Ek-1|< | Ek-2| (6)

Построение максимального цикла Гамильтона

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

Рисунок 9.                                                                             Рисунок 10.

На рисунке10 изображён цикл Гамильтона максимальной величины, состоящий из восьми вершин .

Упрощение построений

Построение элементарного цикла можно упростить, если вместо диаметра графа использовать параметр радиуса графа radius(G). Тогда вместо расстояний между вершинами и полюсами графа в построении будут принимать участие расстояния от вершин до мнимого центра диаметра графа и минимальные расстояния между вершинами графа | V |.

Количество шагов для построения описанного элементарного цикла равняется количеству заданных вершин, уменьшенное на две единицы

R( VE )= (Vm- 2(8)


(
|V|,|E |) >2 (9)


Таким образом задача построения минимального цикла Гамильтона разрешима при помощи предиката выбора R(V,
E) за полиномиальное время и принадлежит классу P.

Дополнение


Допустим, что будут справедливы следующие соответствия между представлениями множества слов
 из языка L на алфавите


V
 


E
  (11)

G (V ,E ) L (12)


Предикат выбора R( V
E ) обозначим как D – (define), а задачу построения некоторого элементарного цикла как  (cycle), тогда будем говорить, что некоторое высказывание C из языка L на алфавите разрешимо при помощи предиката выбора D ( V ,E ) за полиномиальное время 

( VE ) T P (13)

Свойство селективности цикла Гамильтона определяет существование диаметра графа diam(G), по которому определён предикат выбора R(VE).

Если существует некоторый предикат выбора D для языка L на алфавите , тогда некоторое высказывание C из языка L разрешимо алгоритмически в классе P.

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

  1. Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи., М.: Мир, 1982.
  2. Лорьер Ж.-Л. Системы искусственного интеллекта., М.: Мир, 1991.


Все статьи автора «Oleg Velikh»


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

Связь с автором (комментарии/рецензии к статье)

Один комментарий к “Велиховский О.В. Метод построения замкнутого пути на неориентированном симметричном графе при решении задач оптимизации”

  1. 15.03.2012 в 21:37

    В разделе “Дополнение” данной статьи формулы (10) и (11) обозначают следующее:
    (10)- обозначает, что множество вершин графа V определяет некоторый Алфавит
    (11)- обозначает, что множество пар из V , или рёбер E, определяет множество слов x
    из языка L, который определён по заданному графу G(V,E), на этом Алфавите.
    В формуле (13) символ T обозначает, что некоторое высказывание C(V,E) из языка L
    разрешимо в полиномиальном смысле.

Оставить комментарий

Вы должны авторизоваться, чтобы оставить комментарий.

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться: