Описание порядка выполнения определённого набора инструкций для общего метода построения замкнутого пути на симметричном неориентированном графе при решении задач оптимизации | Статья в журнале «Молодой ученый»

Библиографическое описание:

Велиховский О. В. Описание порядка выполнения определённого набора инструкций для общего метода построения замкнутого пути на симметричном неориентированном графе при решении задач оптимизации // Молодой ученый. — 2012. — №4. — С. 11-15. — URL https://moluch.ru/archive/39/4656/ (дата обращения: 20.07.2018).

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

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

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

Таким образом задан не ориентированный симметричный граф G(V,E ). На заданном графе требуется построить минимальный элементарный цикл или цикл Гамильтона.

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

Для решения задачи построения заданного цикла будем применять так называемый Алгоритм выбора selection Algorithm, который в свою очередь будет состоять из некоторой последовательности функций выбора selection Function, по максимально удалённой паре вершин заданного графа или по диаметру графа diam(G ) :

Alg(diam(G )) = { F(V, E ) } (2)

Совместим первый и второй этапы построения в связи с их простотой. Для этого выберем пару вершин из |V | = m, максимально удалённых друг от друга, которые будут определять максимальное ребро заданного графа или его диаметр:

Emax = En = diam(G ) (3)

(V1,V2) inclued {V } (4)

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

pol(G ) = { V, U } (5)

En = {V, U } (6)

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

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

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

Рис.1 Рис.2

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

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

Рис.3 Рис.4

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

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

Рис.5 Рис.6

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

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

Рис.7 Рис.8

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

|Ek | < |Ek-1| < |Ek-2 | (7)

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

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

Рис.9 Рис.10

На рисунке Рис.9 построен максимальный цикл Гамильтона, состоящий из семи вершин. На рисунке Рис.10 построен максимальный цикл Гамильтона, состоящий из восьми вершин, включая оба полюса графа.

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

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


Общие выводы

На каждом этапе построения выполняется один и тот же алгоритм выбора SelAlg, который включает в себя одни и те же три функции выбора selF(V,E ). Функция выбора диаметра графа selF(diam(G )) выполняется только один раз на первом этапе построения.

SelAlg(V,E ) = (selF1(Emax,Vk+1,V,U);selF2(Emin,Vk+1,Vk-i);selF3(Emax,Vk+1,Vk-j))

(i , j ) = 0,1,2,3, . . (8)

Из определения (8) следующая функция:

selF1(Emax,Vk+1,V,U) есть функция выбора очередной новой вершины из множества заданных вершин |V | .

Следующая последовательность функций из определения (8) :

selF2(Emin,Vk+1,Vk-i);selF3(Emax,Vk+1,Vk-j) определяет порядок выбора ближайшего ребра к этой очередной вершине Vk+1, которая в свою очередь состоит из двух функций, сдедующей функции выбора некоторой ближайшей вершины Vk-i из предыдущего цикла к этой очередной вершине Vk+1

selF2(Emin,Vk+1,Vk-i) и следующей функции выбора вершины Vk-j, которая максимально удалена от полюса графа, который в свою очередь является, напротив, ближайшим к этой очередной вершине Vk+1, и принадлежит тому же ближайшему ребру

selF3(Emax,Vk+1,Vk-j)

Количество элементарных шагов выбора для функции selF1 и функции selF2 не превышает степени |V | с показателем два

|steps:(selF1,selF2)| < |V |2 (9)

И количество элементарных шагов или операций выбора для функции selF3 не превышает двух

|steps:(selF3)| = 2 (10)

Количество шагов или этапов построения минимального цикла Гамильтона для алгоритма выбора selAlg(C (V,E )) равно количеству заданных вершин |V |, исключая две вершины, которые определяют Emax или диаметр графа

|steps:SelAlg(Cmin(V,E )) | = |Vm ̶ 2| (11)

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

P:includes:R(Cmin(V,E )) (12)

Это утверждение справедливо и для максимального цикла Гамильтона

P:includes:R(Cmax(V,E )) (12)1


Литература:

  1. Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. ̶М.: Мир, 1982.

  2. Лорьер Ж.-Л. Системы искусственного интеллекта. ̶ М.: Мир, 1991. ̶ 568 c.

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


Похожие статьи

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

гамильтонов цикл, Теория графов, граф, вершина, ребро, граф Г, вычислительный алгоритм, кубический граф, простая цепь, черный цвет.

Автоматизация проектирования маршрутов обхода геометрических...

Ключевые слова: гамильтонов цикл, колония муравьев.

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

Разработка программного обеспечения для конструирования...

Одной из важных задач теории графов является задача раскраски вершин графа.

Данный класс содержит условия, при которых граф является простым циклом или деревом.

Для построения хроматического полинома графа воспользуемся утверждением 3. Для этого...

Графы в Scilab | Статья в сборнике международной научной...

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

Крайние подходы группировки данных в распознавании образов

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

Итак, рассматриваем случай, когда используется dmax, т. е. максимальное расстояние между точками.

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

Задача отыскания наименьшего доминирующего множества вершин неориентированного графа G соответствует ЗНП с матрицей P, в качестве которой выступает матрица

Математические аспекты метода Вагнера — Фишера. Поиск гамильтоновых циклов и цепей в кубических графах.

Комбинированный алгоритм линейной оптимизации с поиском...

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

Методические аспекты обучения доказательству студентов...

Если в графе степень каждой вершины не меньше чем n/2, то этот графгамильтонов.

Основные термины (генерируются автоматически): граф, доказательство, теорема, вершина, простой цикл, связный граф, формулировка теоремы, число ребер, любой, вершина графа.

Обсуждение

Социальные комментарии Cackle

Похожие статьи

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

гамильтонов цикл, Теория графов, граф, вершина, ребро, граф Г, вычислительный алгоритм, кубический граф, простая цепь, черный цвет.

Автоматизация проектирования маршрутов обхода геометрических...

Ключевые слова: гамильтонов цикл, колония муравьев.

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

Разработка программного обеспечения для конструирования...

Одной из важных задач теории графов является задача раскраски вершин графа.

Данный класс содержит условия, при которых граф является простым циклом или деревом.

Для построения хроматического полинома графа воспользуемся утверждением 3. Для этого...

Графы в Scilab | Статья в сборнике международной научной...

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

Крайние подходы группировки данных в распознавании образов

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

Итак, рассматриваем случай, когда используется dmax, т. е. максимальное расстояние между точками.

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

Задача отыскания наименьшего доминирующего множества вершин неориентированного графа G соответствует ЗНП с матрицей P, в качестве которой выступает матрица

Математические аспекты метода Вагнера — Фишера. Поиск гамильтоновых циклов и цепей в кубических графах.

Комбинированный алгоритм линейной оптимизации с поиском...

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

Методические аспекты обучения доказательству студентов...

Если в графе степень каждой вершины не меньше чем n/2, то этот графгамильтонов.

Основные термины (генерируются автоматически): граф, доказательство, теорема, вершина, простой цикл, связный граф, формулировка теоремы, число ребер, любой, вершина графа.

Задать вопрос