Математика/5. Математическое моделирование

Студентка Каирова З.Г.

ГБОУ ВПО «Ставропольский государственный педагогический институт»

ОТЫСКАНИЕ ГАМИЛЬТОНОВЫХ ЦИКЛОВ

Название «гамильтонов цикл» произошло от задачи «Кругосветное путешествие» предложенной ирландским математиком Вильямом Гамильтоном в 1859 году. Нужно было, выйдя из исходной вершины графа, обойти все его вершины и вернуться в исходную точку. Граф представлял собой укладку додекаэдра, каждой из 20 вершин графа было приписано название крупного города мира [1] .

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

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

В отличие от эйлеровых графов, где имеется критерий для графа быть эйлеровым, для гамильтоновых графов такого критерия нет. Более того, задача проверки существования гамильтонова цикла оказывается NP-полной [2] . Большинство известных теорем имеет вид: «если граф G имеет достаточное количество ребер, то граф является гамильтоновым».

В настоящее время неизвестно никакого простого критерия или алгебраического метода, позволяющего ответить на вопрос, существует или нет в произвольном графе G гамильтонов цикл. Критерии существования представляют теоретический интерес, но являются общими и не пригодны для произвольных графов, встречающихся на практике. Алгебраические методы определения гамильтоновых циклов не могут быть применены с более чем несколькими десятками вершин, так как они требуют слишком большого времени работы и большой памяти компьютера. Более приемлемым является способ Робертса и Флореса, не предъявляющий чрезмерных требований к памяти компьютера, но время, от которого зависит экспоненциально от числа вершин в графе [5]. Однако другой неявный метод перебора имеет для большинства типов графов очень небольшой показатель роста времени вычислений в зависимости от числа вершин. Он может быть использован для нахождения гамильтоновых циклов в очень больших графах. Этот метод включает в себя построение всех простых цепей с помощью последовательного перемножения матриц. «Внутреннее произведение вершин» цепи определяется как выражение вида , не содержащее две концевые вершины  и . «Модифицированная матрица смежности» — это - матрица, в которой — , если существует дуга из  в и нуль в противном случае. Предположим теперь, что у нас есть матрица , где — сумма внутренних произведений всех простых цепей длины между вершинами  и для . Положим для всех . Обычное алгебраическое произведение матриц , где определяется как является сумма внутренних произведений всех цепей из в длины . Так как все цепи из в , представленные внутренними произведениями из , являются простыми, то среди цепей, получающихся из указанного выражения, не являются простыми лишь те, внутренние произведения которых в содержат вершину x_s. Таким образом, если из исключить все слагаемые, содержащие (а это можно сделать простой проверкой), то получим . Матрица , все диагональные элементы которой равны , является тогда матрицей всех простых цепей длины .

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

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

Недостатки этого метода совершенно очевидны. При умножении матриц (т.е. когда увеличивается) каждый элемент матрицы  будет состоять из все большего числа членов вплоть до некоторого критического значения , после которого число членов снова начнет уменьшаться. Происходит это вследствие того, что для малых значений и для графов, встречающихся на практике, число цепей длины , как правило, больше, чем число цепей длины , а для больших значений имеет место обратная картина. Кроме того, так как длина каждого члена внутреннего произведения вершин увеличивается на единицу, когда увеличивается на единицу, то, необходимый для хранения матрицы , объем памяти растет очень быстро вплоть до максимума при некотором критическом значении , после которого этот объем снова начинает уменьшаться [3].

Небольшая модификация вышеприведенного метода позволяет во много раз уменьшить необходимый объем памяти и время вычислений. Так как нас интересуют только гамильтоновы циклы, которые могут быть получены из членов внутреннего произведения любой диагональной ячейки матрицы , то необходимо знать только элемент . При этом на каждом этапе не обязательно вычислять и хранить всю матрицу , достаточно лишь найти первый столбец . Эта модификация уменьшает необходимый объем памяти и время вычислений в n раз. Однако даже при использовании этой модификации программа для ЭВМ, написанная на языке , который позволяет построчную обработку литер и переменное распределение памяти, не была способна найти все гамильтоновы циклы в неориентированных графах с более чем примерно 20 вершинами и средним значением степени вершины, большим 4 [4]. При использовании компьютера IBM 360/65 с памятью 120 000 байтов. данный метод занимал фактически весь объем памяти и время вычислений равнялось 1,8 минуты.

Литература

1. Белов В.В. Теория графов: Учебное пособие для студ. высш. техн. учебных заведений. — М.: Высшая школа, 1976. —392с.

2. Бондарев В.М., Рублинецкий В.И., Качко Е.Г. Основы программирования, Изд-во: Феникс, 1998.-368 с.

3. Культин Н.Б. Программирование в TurboPascal 7.0 и Delphi— Санкт-Петербург: BHV, 1998. —240c.

4. Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. 3- е изд. — СПб.: Питер , 2009 . — 384 с.

5. Носов В.А. Комбинаторика и теория графов, М., Московский государственный институт электроники и математики, 1999 г. — 116 с.