Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Гамильтоновы циклы - файл Введение.doc


Загрузка...
Гамильтоновы циклы
скачать (313.2 kb.)

Доступные файлы (11):

~WRL2147.tmp
Введение.doc615kb.22.05.2006 04:41скачать
Основная часть.doc633kb.02.06.2006 20:13скачать
gamcycl.bak
gamcycl.cfg
GAMCYCL.exe
GAMCYCL.FPW
GAMCYCL.fsm
gamcycl.pas
example.txt1kb.22.05.2006 04:04скачать
Содержание.doc23kb.22.05.2006 04:53скачать

Введение.doc

Реклама MarketGid:
Загрузка...
Введение


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

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

Маршрутом в графе G(V,E) называется чередующаяся последовательность вершин и ребер: ,, … ,, в которой любые два соседних элемента инцидентны. Если = , то маршрут замкнут, иначе открыт.

Если все ребра различны, то маршрут называется цепью. Если все вершины (а значит, ребра) различны, то маршрут называется простой цепью.

Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом. Граф без циклов называется ациклическим. Для орграфов цепь называется путем, а цикл — контуром.
Теоретическая часть

^

Гамильтоновы циклы



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

^

Основные понятия и определения



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

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

Замечание.

Любой граф G можно превратить в гамильтонов граф, добавив достаточное количество вершин. Для этого, например, достаточно к вершинам v1,…,vp графа G добавить вершины u1,…,up и множество ребер {(vi,ui)}{(ui,vi+1)}.

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

^

Условия существования гамильтонова цикла



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

^ Теорема Дирака. Если в графе G(V,E) c n вершинами (n ≥ 3) выполняется условие d(v) ≥ n/2 для любого vV, то граф G является гамильтоновым.

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

От противного. Пусть G — не гамильтонов. Добавим к G минимальное количество новых вершин u1, … ,un, соединяя их со всеми вершинами G так, чтобы G’:= G + u1 + … + un был гамильтоновым.

Пусть v, u1, w, … ,v — гамильтонов цикл в графе G’, причем vG, u1G’, u1G. Такая пара вершин v и u1 в гамильтоновом цикле обязательно найдется, иначе граф G был бы гамильтоновым. Тогда wG, w {u1,…,un}, иначе вершина u1 была бы не нужна. Более того, вершина v несмежна с вершиной w, иначе вершина u1 была бы не нужна.

Далее, если в цикле v,u1,w, … ,u’,w’, … ,v есть вершина w’, смежная с вершиной w, то вершина v’ несмежна с вершиной v, так как иначе можно было бы построить гамильтонов цикл v,v’, … ,w,w’, … ,v без вершины u1, взяв последовательность вершин w, … ,v’ в обратном порядке. Отсюда следует, что число вершин графа G’, не смежных с v, не менее числа вершин, смежных с w. Но для любой вершины w графа G d(w) ≥ p/2+n по построению, в том числе d(v) ≥ p/2+n. Общее число вершин (смежных и не смежных с v) составляет n+p-1. Таким образом, имеем:

n+p-1 = d(v)+d(V) ≥ d(w)+d(v) ≥ p/2+n+p/2+n = 2n+p.

Следовательно, 0 ≥ n+1, что противоречит тому, что n > 0.

Теорема Оре. Если число вершин графа G(V,E) n ≥ 3 и для любых двух несмежных вершин u и v выполняется неравенство:

d(u)+d(v) ≥ n и (u,v)E, то граф G — гамильтонов.

Граф G имеет гамильтонов цикл если выполняется одно из следующих условий:

Условие Поша: d(vk) ≥ k+1 для k < n/2.

^ Условие Бонди: из d(vi) ≤ i и d(vk) ≤ k => d(vi)+d(vk)≥n (k≠i)

Условие Хватала: из d(vk) ≤ k ≤ n/2 => d(vn-k) ≥ n-k.

Далее, известно, что почти все графы гамильтоновы, то есть

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

Пример графа, когда не выполняется условие теоремы Дирака, но граф является гамильтоновым.



N = 8; d(vi) = 3; 3 ≥ 8/2 = 4 не гамильтонов граф, но существует гамильтонов цикл: M = (1, 2, 3, 4, 5, 6, 7, 8, 1)
^

Задачи связанные с поиском гамильтоновых циклов



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

Возникает вопрос о том, может ли быть найдена циклическая последовательность производства продуктов pi (i=1,2,…,n), не требующая перенастройки аппаратуры. Если представить эту задачу в виде ориентированного графа, то ответ на поставленный вопрос зависит от того, имеет ли этот ориентированный граф гамильтонов цикл или нет.

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

Таким образом мы рассмотрим следующие две задачи.

Задача 1. Дан ориентированный граф G, требуется найти в G гамильтонов цикл (или все циклы), если существует хотя бы один такой цикл.

Задача 2. Дан полный ориентированный цикл G, дугам которого приписаны произвольные веса C=[cij], найти такой гамильтонов цикл, который имеет наименьший общий вес. Следует отметить, что если ориентированный граф G не полный, то его можно рассматривать как полный ориентированный граф, приписывая отсутствующим дугам бесконечный вес.

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

Очевидно, что сформулированная выше задача (1) является частным случаем задачи (2). В самом деле, приписывая случайным образом дугам заданного ориентированного графа G конечные веса, получаем задачу коммивояжера. Если решение для этой задачи, т.е. кратчайший гамильтонов цикл, имеет конечное значение, то это решение является гамильтоновым циклом ориентированного графа G (т.е. ответом на задачу 1). Если же решение имеет бесконечное значение, то G не имеет гамильтонова цикла.

С другой стороны можно дать еще одну интерпретацию задачи 1). Рассмотрим снова полный ориетированный граф G1 с общей матрицей весов дуг [cij] и рассмотрим задачу нахождения такого гамильтонова цикла, в котором самая длинная дуга минимальна. Эту задачу можно назвать минимаксной задачей коммивояжера. Тогда классическую задачу коммивояжера в той же терминологии можно было бы назвать минисуммной задачей коммивояжера. Покажем теперь, что задача (1) действительно эквивалентна минимаксной задаче коммивояжера.

В вышеупомянутом полном ориентированном графе G1 мы можем наверняка найти гамильтонов цикл. Пусть это будет цикл Ф1, и пусть вес самой длинной его дуги равен ĉ1. Удалив из G1 любую дугу, вес которой не меньше ĉ1, получим ориентированный граф G2. Найдем в ориентированном графе G2 гамильтонов цикл Ф2, и пусть вес его самой длинной дуги равен ĉ2. Удалим из G2 любую дугу, вес которой не меньше ĉ2, и так будем продолжать до тех пор, пока не получим ориентированный граф Gm+1, не содержащий никакого гамильтонова цикла. Гамильтонов цикл Фm в Gm (с весом ĉm) является тогда по определению решением минимаксной задачи коммивояжера, так как из отсутствия гамильтонова цикла в Gm+1 следует, что в G1 не существует никакого гамильтонова цикла, не использующего по крайней мере одну дугу с весом, большим или равным ĉm.

Таким образом, алгоритм нахождения гамильтонова цикла в ориентированном графе решает также минимаксную задачу коммивояжера. Наоборот, если мы располагаем алгоритмом решения последней задачи, то гамильтонов цикл в произвольном ориентированном графе G может быть найден с помощью построения полного ориентированного графа G1 с тем же самым множеством вершин, что и в G, дугам которого, соответствующим дугам из G, приписаны единичные веса, а остальным дугам — бесконечные веса. Если решение минимаксной задачи коммивояжера для G1 имеет конечный вес (на самом деле равный единице), то в графе G может быть найден соответствующий гамильтонов цикл. Если же решение имеет бесконечный вес, то в графе G не существует никакого гамильтонова цикла. Следовательно, две указанные задачи можно рассматривать как эквивалентные, поскольку было продемонстрировано, что алгоритм нахождения гамильтонова цикла позволяет решать минимаксную задачу коммивояжера и наоборот.

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

^

Методы построения гамильтоновых циклов в графе


Пока неизвестно никакого простого критерия или алгебраического метода, позволяющего ответить на вопрос, существует или нет в произвольном графе G гамильтонов цикл. Критерии существования, данные выше, представляют теоретический интерес, но являются слишком общими и не пригодны для произвольных графов, встречающихся на практике. Алгебраические методы определения гаильтоновых циклов не могут быть применены с более чем несколькими десятками вершин, так как они требуют слишком большого времени работы и большой памяти компьютера. Более приемлемым является способ Робертса и Флореса, который не предъявляет чрезмерных требований к памяти компьютера, но время в котором зависит экспоненциально от числа вершин в графе. Однако другой неявный метод перебора имеет для большинства типов графов очень небольшой показатель роста времени вычислений в зависимости от числа вершин. Он может быть использован для нахождения гамильтоновых циклов в очень больших графах.
^

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



Этот метод включает в себя построение всех простых цепей с помощью последовательного перемножения матриц. «Внутреннее произведение вершин» цепи x1, x2, … ,xk-1, xk определяется как выражение вида x2*x3* … xk-1, не содержащее две концевые вершины x1 и xk. «Модифицированная матрица смежности» B=[β(i,j)] — это (n×n)- матрица, в которой β(i,j) — xj, если существует дуга из xi в xj и нуль в противном случае. Предположим теперь, что у нас есть матрица PL = [pL(i ,j)], где pL(i,j) — сумма внутренних произведений всех простых цепей длины L (L≥1) между вершинами xi и xj для xi≠xj. Положим pL(i,i)=0 для всех i. Обычное алгебраическое произведение матриц определяется как

B*PL=P’L+1=[p’L+1(s,t)]


т.е. p’L+1(s,t) является суммой внутренних произведений всех цепей из xs в xt длины l+1. Так как все цепи из xk в xt, представленные внутренними произведениями из pL(k,t), являются простыми, то среди цепей, получающихся из указанного выражения, не являются простыми лишь те, внутренние произведения которых в pL(k,t) содержат вершину xs. Таким образом, если из p’L+1(s,t) исключить все слагаемые, содержащие xs (а это можно сделать простой проверкой), то получим pL+1(s,t). Матрица PL+1=[pL+1(s,t)], все диагональные элементы которой равны 0, является тогда матрицей всех простых цепей длины L+1.

В
ычисляя затем B*PL+1, находим PL+2 и т.д., пока не будет построена матрица Pn-1, дающая все гамильтоновы цепи (имеющие длину n-1) между всеми парами вершин. Гамильтоновы циклы получаются тогда сразу из цепей в Pn-1 и тех дуг из G, которые соединяют начальную и конечную вершины каждой цепи. С другой стороны, гамильтоновы циклы даются членами внутреннего произведения вершин, стоящими в любой диагональной ячейке матрицы B*Pn-1 (все диагональные элементы этой матрицы одинаковые).

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

Недостатки этого метода совершенно очевидны. В процессе умножения матриц (т.е. когда L увеличивается) каждый элемент матрицы PL будет состоять из все большего числа членов вплоть до некоторого критического значения L, после которого число членов снова начнет уменьшаться. Это происходит вследствие того, что для малых значений L и для графов, обычно встречающихся на практике, число цепей длины L+1, как правило, больше, чем число цепей длины L, а для больших значений L имеет место обратная картина. Кроме того, так как длина каждого члена внутреннего произведения вершин увеличивается на единицу, когда L увеличивается на единицу, то объем памяти, необходимый для хранения матрицы PL, растет очень быстро вплоть до максимума при некотором критическом значении L, после которого этот объем снова начинает уменьшаться.
^ Практическая часть
Примеры решения задач
Задача 1.

Найти все гамильтоновы циклы в графе


Матрица смежности данного графа равна

0

1

0

1

0

0

0

0

1

1

0

1

0

0

1

0

0

1

0

0

1

0

1

0

0


А=

и модифицированная матрица смежности равна



0

b

0

d

0

0

0

0

d

e

0

b

0

0

e

0

0

c

0

0

a

0

c

0

0


В=

Положим ≡А. Матрица получается равной

0

0

d

b

b

e

0

d+e

0

0

e

0

0

b

b

0

c

0

0

c

0

a+c

0

a

0


=


Матрица равна

0

dc

bd+be

0

dc

0

0

0

ea

dc

be

ea

0

ea

0

ce

0

0

0

cb

0

0

ad

ab+cb

0


=
Матрица гамильтоновых цепей равна

0

0

0

0

bdc+dcb

dce

0

ead

0

0

0

0

0

bea+eab

0

cbe

cea

0

0

0

0

adc

abd

0

0


=

получаем гамильтоновы циклы abdcea и adcbea.
Задача 2.

Найти все гамильтоновы циклы в графе


Матрица смежности данного графа равна

0

1

0

0

0

0

0

1

0

1

0

0

1

0

1

0


А=

и модифицированная матрица смежности равна

0

b

0

0

0

0

0

d

0

b

0

0

a

0

c

0

В=

Положим ≡А. Матрица получается равной



0

0

0

b

d

0

d

0

0

0

0

b

0

a+c

0

0



=

Матрица гамильтоновых цепей равна


0

0

bd

0

0

0

0

0

bd

0

0

0

0

0

0

0


=


Получаем цепи acbd и cabd, но дуга ac отсутствует, значит решений нет.
Задача 3

Найти все гамильтоновы циклы в графе


Матрица смежности данного графа равна


0

0

0

1

0

0

1

0

0

0

0

1

0

1

0

0

0

0

0

0

1

0

0

0

0

1

0

1

0

0

1

0

0

0

1

0



A=

и модифицированная матрица смежности равна



0

0

0

d

0

0

a

0

0

0

0

f

0

b

0

0

0

0

0

0

c

0

0

0

0

b

0

d

0

0

a

0

0

0

e

0

B=
Положим ≡А. Матрица получается равной


0

0

d

0

0

0

f

0

0

a

f

0

b

0

0

0

0

b

0

c

0

0

0

0

b

0

d

0

0

b

0

e

0

a+e

0

0



=

Матрица равна


0

dc

0

0

0

0

0

0

ad

fa+fe

0

0

bf

0

0

ba

bf

0

cb

0

0

0

0

cb

bf

dc

0

ba

0

0

eb

0

ad+ed

0

0

0

=


Матрица равна

0

0

0

0

0

dcb

0

0

fad+fed

0

0

0

0

0

0

bfa+bfe

0

0

cbf

0

0

0

cbf

0

dcb

0

bad

bfa

0

dcb

0

adc+edc

0

eba

0

0


=

Матрица гамильтоновых цепей равна

0

0

0

0

dcbf

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

dcbf

0

bfad

0

0

0

edcb

0

ebad

0

0

0

=

Получаем цепи eadcbf, cebfad, afedcb, cfebad. Ни одна из них не подходит, значит решения отсутствуют.
Задача 4.

Найти все гамильтоновы циклы в графе



Матрица смежности данного графа равна


0

1

0

0

0

0

0

0

1

0

1

0

1

0

0

1

0

0

0

0

1

0

0

1

0

0

1

1

0

0

1

1

1

0

0

0

А=

и модифицированная матрица смежности равна

0

b

0

0

0

0

0

0

c

0

e

0

a

0

0

d

0

0

0

0

c

0

0

f

0

0

c

d

0

0

a

b

c

0

0

0

В=
Положим ≡А. Матрица получается равной


0

0

b

0

b

0

c

0

e

c+e

0

0

0

a

0

0

0

d

c+f

f

f

0

0

0

c

0

d

c

0

d

c

a

b

c

b

0

=

Матрица равна


0

0

be

bc+be

0

0

ec

0

ed

ec

0

cd+ed

df

df

0

0

ab

0

fc

ca+fa

fb

0

fb

0

dc+df

ca+df

df

0

0

cd

bc

ca

ab+be

bc+be

ab

0

=

Матрица равна

0

0

bed

bec

0

bcd+bed

cdf+edc+edf

0

edf

0

0

ecd

0

dfa

0

abe

dfb

0

fbc

fca

fab+fbe

0

cab+fab

0

cdf+dfc

cdf+dca+dfa

dfb

0

0

0

bec

0

abe+bed

abc+ace+bec

cab

0

=

Матрица гамильтоновых цепей равна


0

0

bedf

0

0

becd

ecdf+edfc

0

0

0

0

0

0

0

0

0

dfab

abed

fbec

0

fabe

0

fcab

0

dfbc

cdfa+dfca

dfab

0

0

0

bedc

0

abed

abec+cabe

0

0


=

получаем гамильтоновы циклы cabedfc и fabecdf.
Блок-схемы
Тело программы





Процедура rename_p1_p2


Процедура delete_povtor





Процедура multi_b_p1(ij)



Процедура delete_vrm



Процедура INI_P1



Процедура INI_B



Программный код
Содержимое файла gamcycl.pas

Uses

dos,crt;

VAR a,b:array[1..100,1..100] of integer;

i,j,n,ij:integer;

stro:text;

procedure ini_b;

var i,j:integer;

begin;

for i:=1 to n do

for j:=1 to n do

b[i,j]:=a[i,j]*j;

end;
procedure ini_p1;

var i,j:integer;

s_i,s_j:string[3];

f1:text;

begin;

for i:=1 to n do

for j:=1 to n do

begin;

str(i,s_i); if i<10 then s_i:='00'+s_i else if i<100 then s_i:='0'+s_i;

str(j,s_j); if j<10 then s_j:='00'+s_j else if j<100 then s_j:='0'+s_j;

assign(f1,'vrm\p'+s_i+s_j+'.txt');

rewrite(f1);

if a[i,j]<>0 then writeln(f1,a[i,j]:4);

close(f1);

end;

end;
procedure multi_B_P1(nom:integer);

var ii,i,j,k,s,ip:integer;

s_i,s_j,s_k:string[3];

f1,f2:text;

label q1;

begin;

for i:=1 to n do

for j:=1 to n do

begin;

str(i,s_i); if i<10 then s_i:='00'+s_i else if i<100 then s_i:='0'+s_i;

str(j,s_j); if j<10 then s_j:='00'+s_j else if j<100 then s_j:='0'+s_j;

assign(f2,'vrm\p2'+s_i+s_j+'.txt');

rewrite(f2);

if i<>j then begin;

for k:=1 to n do

begin;

str(k,s_k); if k<10 then s_k:='00'+s_k else if k<100 then s_k:='0'+s_k;
if (b[i,k]=i) or (b[i,k]=j) or (b[i,k]=0) then goto q1;

assign(f1,'vrm\p'+s_k+s_j+'.txt');

reset(f1);

ii:=0;

ip:=0;

while not eof(f1) do begin;

ip:=0;ii:=0;

while not eoln(f1) do begin;

ip:=0;

read(f1,ip);

if (nom=1) and (ip<>0) then begin; {write(f2,ip:4);}ii:=2;end;

if (nom>1) and (ip<>0)then begin;

if ii=0 then begin;write(f2,b[i,k]:4);ii:=1;end; write(f2,ip:4);end;

end;

if ii=2 then begin;write(f2,b[i,k]:4);end;

if ii>0 then writeln(f2);

ii:=0;

readln(f1);

end;

close(f1);

q1: end;

end;

close(f2);

end;

end;

procedure rename_P1_P2;

var i,j,IP1,IP2:integer;

s_i,s_j:string[3];

f1,F2:text;

^ AA:ARRAY[1..100] OF INTEGER;

ia,k,li,llj:integer;

label mm,mm2;

begin;

for i:=1 to n do

for j:=1 to n do

begin;

str(i,s_i); if i<10 then s_i:='00'+s_i else if i<100 then s_i:='0'+s_i;

str(j,s_j); if j<10 then s_j:='00'+s_j else if j<100 then s_j:='0'+s_j;

assign(f1,'vrm\p'+s_i+s_j+'.txt');

erase(f1);

assign(f1,'vrm\p2'+s_i+s_j+'.txt');

reset(f1);

assign(f2,'vrm\p'+s_i+s_j+'.txt');

rewrite(f2);

ia:=1; llj:=0;

while not eof(f1) do begin;

ia:=1;

while not eoln(f1) do begin;

read(f1,aa[ia]); inc(ia);

end;

if ia=1 then goto mm;

dec(ia);

for k:=1 to ia do if (aa[k]=0) or (aa[k]=i) or (aa[k]=j) then goto mm;

for k:=1 to ia do begin;

for li:=1 to k-1 do if (aa[k]=aa[li]) then goto mm2;

write(f2,aa[k]:4);llj:=1; mm2:end;

mm: readln(f1);if llj>0 then writeln(f2);

end;

close(f1);close(f2);

erase(f1);

end;

end;
procedure viv_P;

var ii,jj,i,j,k,s,ip:integer;

s_i,s_j:string[3];

f1:text;

begin;

clrscr;

for i:=1 to n do

for j:=1 to n do

begin;

str(i,s_i); if i<10 then s_i:='00'+s_i else if i<100 then s_i:='0'+s_i;

str(j,s_j); if j<10 then s_j:='00'+s_j else if j<100 then s_j:='0'+s_j;

write('p[',i,',',j,']=');

assign(f1,'vrm\p'+s_i+s_j+'.txt');

reset(f1);

ii:=0;jj:=0;

while not eof(f1) do begin;

while not eoln(f1) do begin;

read(f1,ip);

if (ii=0) and (jj>0) then write('+');

if ii>0 then write('*'); write(ip);ii:=1;

end;

readln(f1); jj:=1; II:=0;

end;

readln;

close(f1);

end;

end;

procedure viv_P2;

var ii,jj,i,j,k,s,ip:integer;

s_i,s_j:string[3];

f1:text;

begin;

writeln(stro,'*********************************************');

for i:=1 to n do

for j:=1 to n do

begin;

str(i,s_i); if i<10 then s_i:='00'+s_i else if i<100 then s_i:='0'+s_i;

str(j,s_j); if j<10 then s_j:='00'+s_j else if j<100 then s_j:='0'+s_j;

write(stro,'p[',i,',',j,']=');

assign(f1,'vrm\p'+s_i+s_j+'.txt');

reset(f1);

ii:=0;jj:=0;

while not eof(f1) do begin;

while not eoln(f1) do begin;

read(f1,ip);

if (ii=0) and (jj>0) then write(stro,'+');

if ii>0 then write(stro,'*'); write(stro,ip);ii:=1;

end;

readln(f1); jj:=1; II:=0;

end; writeln(stro);
close(f1);

end;

end;
procedure viv_res;

var ii,jj,i,j,k,s,ip,iij:integer;

ss_i,ss_j, s_i,s_j:string[3];

f1:text;

begin;

clrscr;

for i:=1 to n do

for j:=1 to n do

begin;

str(i,s_i); if i<10 then s_i:='00'+s_i else if i<100 then s_i:='0'+s_i;

str(j,s_j); if j<10 then s_j:='00'+s_j else if j<100 then s_j:='0'+s_j;

str(j,ss_j);

str(i,ss_i);

assign(f1,'vrm\p'+s_i+s_j+'.txt');

reset(f1);

ii:=0;jj:=0;iij:=0;

while not eof(f1) do begin;

while not eoln(f1) do begin;

read(f1,ip);

if (ii=0) and (jj>0) then begin;write(' '); iij:=0;end;

if ii>0 then write('-');

if iij=0 then begin;

write('CHAIN p[',i,',',j,']=',ss_j,'-',ss_i,'-');

iij:=1;

end;

write(ip);ii:=1;

end;

readln(f1); jj:=1; II:=0;

end;

if iij>0 then readln;

close(f1);

end;

end;

procedure delete_povtor;

var ii,jj,i,j,k,s,ip,iij:integer;

s_i,s_j:string[3];

f1:text;

et1:array[1..100,0..100] of integer;

kol_et,i3:integer;
function prov_povtor:boolean;

var iaa,k2,l,l2:integer;

label ddd,ddd2;

begin;

for k2:=1 to et1[i,0]-1 do

if et1[i,k2]<>et1[j,k2] then goto ddd;

prov_povtor:=true;exit;

ddd:

for l:=1 to et1[i,0]-1 do

begin;

iaa:=et1[i,1];

for l2:=2 to et1[i,0]-1 do et1[i,l2-1]:=et1[i,l2];

et1[i,et1[i,0]-1]:=iaa;

for k2:=1 to et1[i,0]-1 do

if et1[i,k2]<>et1[j,k2] then goto ddd2;

prov_povtor:=true;exit;

ddd2:

end;

prov_povtor:=false;exit;

end;
label yyy;

begin;

kol_et:=1; s:=0;

for i:=1 to 100 do et1[i,0]:=1;

for i:=1 to n do

for j:=1 to n do

begin;

str(i,s_i); if i<10 then s_i:='00'+s_i else if i<100 then s_i:='0'+s_i;

str(j,s_j); if j<10 then s_j:='00'+s_j else if j<100 then s_j:='0'+s_j;

assign(f1,'vrm\p'+s_i+s_j+'.txt');

reset(f1);

while not eof(f1) do begin;

ii:=0;

while not eoln(f1) do begin;

read(f1,ip);

if ip>0 then begin;

if ii=0 then begin;

et1[kol_et,et1[kol_et,0]]:=j;

inc(et1[kol_et,0]);

et1[kol_et,et1[kol_et,0]]:=i;

inc(et1[kol_et,0]);

ii:=1;end;

et1[kol_et,et1[kol_et,0]]:=ip;

inc(et1[kol_et,0]);

end;

end;

readln(f1); ii:=0;

if (a[et1[kol_et,et1[kol_et,0]-1],et1[kol_et,1]]=1) and

(a[et1[kol_et,1],et1[kol_et,2]]=1) then inc(kol_et);

end;

close(f1);

end;

for i:=1 to kol_et-1 do begin;

for j:=1 to i-1 do begin;

if prov_povtor then goto yyy;

end;

if s=0 then begin

writeln;

writeln('Найденные пути:');end;

writeln;

s:=1;

for k:=1 to et1[i,0]-1 do write(et1[i,k],'-'); write(et1[i,1]);

yyy: end;


if s=0 then writeln('Нет решения');
{ for i:=1 to kol_et-1 do begin;

writeln;

for j:=1 to et1[i,0]-1 do write(et1[i,j],'-');

end;

}
end;

procedure delete_vrm;

var i,j:integer;

s_i,s_j:string[3];

f1:text;

begin;

for i:=1 to n do

for j:=1 to n do

begin;

str(i,s_i); if i<10 then s_i:='00'+s_i else if i<100 then s_i:='0'+s_i;

str(j,s_j); if j<10 then s_j:='00'+s_j else if j<100 then s_j:='0'+s_j;

assign(f1,'vrm\p'+s_i+s_j+'.txt');

erase(f1);

end;

end;
BEGIN;

clrscr;

gotoxy(1,1);writeln('Программа поиска гамильтоновых циклов Антонов Д.В. ');
gotoxy(1,2);writeln('Введите количество вершин графа  ');

gotoxy(1,3);readln(n);

if (n<3) or (n>100) then begin;writeln('Превышены возможности программы’);

readkey;exit;end;

gotoxy(1,4);writeln('Введите матрицу смежности графа');
for i:=1 to n do begin

for j:=1 to n do begin

gotoxy(3*j,3+2*i+1);read(A[i,j]);

if not ((A[i,j]=0) or (A[i,j]=1)) then begin

writeln(' Превышены возможности программы’');readkey;exit;end;

end;end;

ini_B;

ini_p1;

assign(stro,'vrm\example.txt');

rewrite(stro);

for ij:=1 to n-2 do begin;

multi_b_p1(ij);

rename_p1_p2;

viv_p2;

end;

close(stro);

// viv_p;

delete_povtor;

delete_vrm;

//viv_res;

readkey;

end.


^ Примеры работы программы

Данная программа делает запрос количества вешин графа

а также матрицы смежности графа


после ввода матрицы сразу выводятся найденные гамильтоновы циклы

после нажатия любой клавиши программа закрывается.
При вводе количества вершин графа менее 3 или более 100 программа сообщит об ошибке и закроется.

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

Если в заданном графе будут отсутствовать гамильтоновы циклы, то вместо ответа появится надпись: «Нет решения».


Вывод

Программа сначала модифицирует матрицу смежности, Далее в цикле перемножает полученную матрицу В с создаваемыми матрицами Р. Матрица ≡А, А-матрица смежности. Цикл производится n-2 раз, где n-это число вершин графа. Из полученных цепей отсеиваются повторные, из оставшихся отсеиваются те, которые не замыкаются.

Оставшиеся цепи выводятся на экран. При отсутствии оставшихся цепей выводится надпись: «Нет решений».

При написании данной программы был использован компилятор TMT Pascal Multi-target 4, поскольку на данный момент откомпилированные им приложения являются наиболее производительными по сравнению с Turbo Pascal, C++, MFC, Delphi. Использованный алгоритм решения требует много оперативной памяти, однако программа использует оперативную память по минимуму. Промежуточные массивы с данными сохраняются на жестком диске в папке vrm. Таким образом данную программу можно использовать на компьютерах с малым количеством оперативной памяти. Также быстродействия удалось достигнуть за счет того, что Windows кэширует создаваемые и копируемые файлы.

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


  1. Кристофидес Н. Теория графов. Алгоритмический подход. -М.: Мир, 1978.-432с.

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

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



Скачать файл (313.2 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации