Федеральное агентство по образованию РФ
САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИМЕНИ Н.Г. ЧЕРНЫШЕВСКОГО
Кафедра геометрии
Гамильтоновы графы и сложность отыскания гамильтоновыхциклов
КУРСОВАЯ РАБОТА
Научный руководитель
Старший преподаватель ______________
должн., уч. степень, уч. зван. подпись, дата инициалы,фамилия
Саратов 2010
Содержание
Введение
1. Гамильтоновыграфы
1.1 Основные определения и результаты
1.2 Теоремы достаточности гамильтоноваграфа
2. Методыотыскания гамильтоновых циклов
2.1 Алгебраические методы
2.2 Метод перебора Робертса и Флореса
2.2.1 Улучшение метода Робертса иФлореса
Приложение
Заключение
Список литературы
Введение
Целью моей курсовой работы является:
1. Ознакомление с основными понятиями, связанными с гамильтоновыми графами и циклами.
2. Рассмотреть задачи и методы отыскания гамильтоновых циклов в графах
3. Создание программы для нахождения гамильтоновых циклов.
Прежде всего, чтобы внести ясность и уточнить терминологию, хотелось бы дать определения некоторым элементам графа таким, как маршрут, цепь, цикл.
Маршрутом в графе G(V,E) называется чередующаяся последовательность вершин и ребер: />,/>, … />, />, в которой любые два соседних элемента инцидентны. Если /> = />, то маршрут замкнут, иначе открыт.
Если все ребра различны, то маршрут называется цепью. Если все вершины (а значит, ребра) различны, то маршрут называется простой цепью.
Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом. Граф без циклов называется ациклическим. Для орграфов цепь называется путем, а цикл — контуром.
1. Гамильтоновы графы
1.1 Основные определенияи результаты
/>
Название «гамильтоновцикл» произошло от задачи «Кругосветное путешествие» предложенной ирландскимматематиком Вильямом Гамильтоном в 1859 году. Нужно было, выйдя из исходнойвершины графа, обойти все его вершины и вернуться в исходную точку. Графпредставлял собой укладку додекаэдра, каждой из 20 вершин графа было приписаноназвание крупного города мира.
Если граф имеет простойцикл, содержащий все вершины графа по одному разу, то такой цикл называется гамильтоновымциклом, а граф называется гамильтоновым графом. Граф, которыйсодержит простой путь, проходящий через каждую его вершину, называется полугамильтоновым.Это определение можно распространить на ориентированные графы, если путьсчитать ориентированным.
Гамильтонов цикл необязательно содержит все ребра графа. Ясно, что гамильтоновым может быть толькосвязный граф и, что всякий гамильтонов граф является полугамильтоновым.Заметим, что гамильтонов цикл существует далеко не в каждом графе.
Замечание.
Любой граф Gможно превратить в гамильтонов граф, добавив достаточное количество вершин. Дляэтого, например, достаточно к вершинам v1,…,vp графа Gдобавить вершины u1,…, up и множестворебер {(vi, ui)}/> {(ui,vi+1)}.
Степенью вершины vназывается число ребер d(v),инцидентных ей, при этом петля учитывается дважды. В случае ориентированногографа различают степень do(v)по выходящим дугам и di(v)— по входящим.
В отличии от эйлеровыхграфов, где имеется критерий для графа быть эйлеровым, для гамильтоновых графовтакого критерия нет. Более того, задача проверки существования гамильтоновацикла оказывается NP-полной.Большинство известных теорем имеет вид: «если граф Gимеет достаточное количество ребер, то граф является гамильтоновым». Приведемнесколько таких теорем.
1.2 Теоремыдостаточности гамильтонова графа
Теорема (Дирак, 1952) 1. Если в простом графе с n≥ 3вершинами p(v) ≥ n/2 для любой вершины v, то граф G является гамильтоновым.
Замечание Существует несколько доказательств этой широко известнойтеоремы, здесь мы приводим доказательство Д. Дж. Ньюмана.
Доказательство. Добавим к нашемуграфу k новых вершин, соединяякаждую из них с каждой вершиной из G. Будем предполагать, что k— наименьшее число вершин, необходимых для того, чтобыполученный граф G¢стал гамильтоновым.Затем, считая, что k > 0, придем кпротиворечию.
Пусть v→p→w→…→v гамильтонов цикл в графе G¢, где v, w— вершины из G, а p— одна из новых вершин.Тогда w не является смежной с v, так как в противномслучае мы могли бы не использовать вершину p, что противоречитминимальности k. Более того, вершина, скажем, w¢, смежная вершине w, не можетнепосредственно следовать за вершиной v¢, смежной вершине v, потому что тогда мымогли бы заменить v→p→w→…→v¢→ w¢→v на v→v¢→…→w→w¢→…→v, перевернув частьцикла, заключенную между w и v¢. Отсюда следует, чточисло вершин графа G¢, не являющихсясмежными с w, не меньше числа вершин, смежных с v (то есть равно, по меньшей мере, n/2 + k); с другой стороны,очевидно, что число вершин графа G¢, смежных с w, тоже равно, поменьшей мере, n/2 + k. А так как ни одна вершина графа G¢не может быть одновременно смежной и не смежной вершине w, то общее число вершинграфа G¢, равное n + k, не меньше, чем n + 2k. Это и есть искомоепротиворечие.
Теорема (Оре) 2. Есличисло вершин графа G(V,E)n≥3 и для любых двух несмежных вершин uи v выполняетсянеравенство:
d(u)+ d(v)≥ n и />(u,v)/>E,то граф G — гамильтонов.
Граф Gимеет гамильтонов цикл если выполняется одно из следующих условий:
Условие Бонди: из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)
2. Методы отыскания гамильтоновых циклов2.1 Алгебраические методы
Пока неизвестноникакого простого критерия или алгебраического метода, позволяющего ответить навопрос, существует или нет в произвольном графе 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), являются простыми,то среди цепей,
k p¢1+1(s,t) = ∑b(s,k) * p1(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,после которого этот объем снова начинает уменьшаться.
Небольшая модификациявышеприведенного метода позволяет во много раз уменьшить необходимый объемпамяти и время вычислений. Так как нас интересуют только гамильтоновы циклы и,как было отмечено выше, они могут быть получены из членов внутреннего произведениялюбой диагональной ячейки матрицы B*Pn-1,то необходимо знать только элемент pn-1(1,1). При этом на каждом этапе не обязательно вычислять и хранить всю матрицу PL,достаточно лишь найти первый столбец PL.Эта модификация уменьшает необходимый объем памяти и время вычислений в nраз. Однако даже при использовании этой модификации программа для ЭВМ,написанная на языке PL/1,который позволяет построчную обработку литер и переменное распределение памяти,не была способна найти все гамильтоновы циклы в неориентированных графах сболее чем примерно 20 вершинами и средним значением степени вершины, большим 4.Использовался компьютер IBM360/65 с памятью 120 000 байтов. Более того, даже для графа с вышеуказанными«размерами» данный метод использовал фактически весь объем памяти и времявычислений равнялось 1.8 минуты. Не такое уж незначительное время для стольнебольшого графа.
2.2 Метод перебораРобертса и Флореса
В противоположностьалгебраическим методам, с помощью которых пытаются найти сразу все гамильтоновыциклы и при реализации которых приходится хранить, поэтому все цепи, которыемогут оказаться частями таких циклов, метод перебора имеет дело с одной цепью,непрерывно продлеваемой вплоть до момента, когда либо получается гамильтоновцикл, либо становится ясно, что эта цепь не может привести к гамильтоновуциклу. Тогда цепь модифицируется некоторым систематическим способом (которыйгарантирует, что, в конце концов, будут исчерпаны все возможности), после чегопродолжается поиск гамильтонова цикла. В этом способе для поиска требуетсяочень небольшой объем памяти и за один раз находится один гамильтонов цикл.
Следующая схемаперебора, использующая обычную технику возвращения, была первоначальнопредложена Робертсом и Флоресом. Начинают с построения (k×n)-матрицы M=[mij],где элемент mijесть i-я вершина (скажем xq),для которой в графе G(X,Г)существует дуга (xj,xq). Вершины xqво множестве Г(xj)можно упорядочить произвольно, образовав элементы j-гостолбца матрицы M. Число строк kматрицы M будет равно наибольшейполустепени исхода вершины.
Метод состоит вследующем. Некоторая начальная вершина (скажем, x1)выбирается в качестве отправной и образует первый элемент множества S,которое каждый раз будет хранить уже найденные вершины строящейся цепи. К Sдобавляетсяпервая вершина (например, вершина a)в столбце x1.Затем к множеству Sдобавляется первая возможная вершина (например, вершина b)в столбце a, потом добавляется к Sпервая возможная вершина (например, вершина c)в столбце b и т.д. Под «возможной»вершиной мы понимаем вершину, еще не принадлежащую S.Существуют две причины, препятствующие включению некоторой вершины на шаге rво множество S = {x1,a, b,c, …, xr-1,xr}:
1) Встолбце xr нет возможной вершины.
2) Цепь,определяемая последовательностью вершин в S,имеет длину n-1,т.е. является гамильтоновой цепью.
В случае 2) возможныследующие случаи:
a) Вграфе G существует дуга (xr,x1),и поэтому найден гамильтонов цикл.
b) Дуга(xr, x1)не существует и не может быть получен никакой гамильтонов цикл.
В случаях (1) и (2b)следует прибегнуть к возвращению, в то время как в случае (2a)можно прекратить поиск и напечатать результат (если требуется найти только одингамильтонов цикл), или (если нужны все такие циклы) произвести печать иприбегнуть к возвращению.
Возвращение состоит вудалении последней включенной вершины xrиз S, после чего остаетсямножество S = {x1,a, b,c, …, xr-1},и добавлении к S первойвозможной вершины, следующей за xr,в столбце xr-1матрицы M. Если не существуетникакой возможной вершины, делается следующий шаг возвращения и т.д.
Поиск заканчивается втом случае, когда множество Sсостоит только из вершины x1и не существует никакой возможной вершины, которую можно добавить к S,так что шаг возвращения делает множество Sпустым. Гамильтоновы циклы, найденные к этому моменту, являются тогда всемигамильтоновыми циклами, существующими в графе.
Рассмотрим примерпоиска гамильтонова цикла в графе переборным методом Робертса и Флореса.
Пример:
/>
«2»
1) S= {1}
2) S= {1, 2}
3) S= {1, 2, 3}
4) S= {1, 2, 3, 4}
5) S= {1, 2, 3, 4, 5} — Г 4→3 4→5
6) S= {1, 2, 3, 4}
7) S= {1, 2, 3} 3→1 3→2 3→4
8) S= {1, 2}
9) S= {1}
«3»
10)S = {1, 3} 3→2
11)S = {1, 3, 2} 2→1
12)S = {1, 3} 2→3
13)S = {1, 3, 4} 3→4 4→5
14)S = {1, 3, 4, 5, 4} 5→нет
15)S = {1, 3, 4}
16)S = {1, 3}
17)S = {1}
«5»
18)S = {1, 5}
19)S = {1, 5, 4}
20)S = {1, 5, 4, 3}
21)S = {1, 5, 4, 3, 2} — Г
22)S = {1, 5, 4, 3}
23)S = {1, 5, 4}
24)S = {1, 5}
25)S = {1}
26) S= Ø/> 2.2.1 Улучшение метода Робертса и Флореса
Рассмотрим улучшениеосновного переборного метода Робертса и Флореса. Допустим, что на некоторомэтапе поиска построенная цепь задается множеством S={x1, x2,…, xr} и чтоследующей вершиной, которую предполагается добавить к S,является x*/>S.Рассмотрим теперь две следующие ситуации, в которых вершина является изолированнойв подграфе, остающемся после удаления из G(X, Г)всех вершин, образующих построенную до этого цепь.
a) Еслисуществует такая вершина x/>X\S,что x/>Г(xr)и Г-1(x) /> S,то, добавляя к S любую вершину x*,отличную от x, мы не сможем впоследующем достигнуть вершины xни из какой конечной вершины построенной цепи, и, значит, эта цепь не сможетпривести нас к построению гамильтонова цикла. Таким образом, в этом случае xявляется единственной вершиной, которую можно добавить к Sдля продолжения цепи.
b) Еслисуществует такая вершина x/>X\S,что x/>Г-1(x1)и Г(x)/>S/>{x*}для некоторой другой вершины x*,то x*не может быть добавлена к S,так как тогда в остающемся подграфе не может существовать никакой цепи между xи x1.Цепь, определяемая множеством S/> {x*},не может поэтому привести к гамильтонову циклу, а в качестве кандидата надобавление к множеству Sследует рассмотреть другую вершину, отличную от x*.
Проверка условий (a)и (b) будет, конечно, замедлять итеративнуюпроцедуру, и для небольших графов (менее чем с 20 вершинами) не получаетсяникакого улучшения первоначального алгоритма Робертса и Флореса. Но для большихграфов эта проверка приводит к заметному сокращению необходимого временивычислений, уменьшая его обычно в 2 или более раз.
Заключение
В данной работе мыпознакомились с основными понятиями, определениями и результатами, связанными сгамильтоновыми графами и циклами. Так же мы рассмотрели ту часть теориисложности, которая затрагивает задачи отыскания гамильтонова цикла. И в итогипроведённых изучений была написана программа отыскания гамильтонова цикла вграфе.
Список литературы
1. КристофидесН. Теория графов. Алгоритмический подход. -М.: Мир, 1978.-432с.
2. БеловВ.В. Теория графов: Учеб. пособие для студ.высш.техн.учеб. заведений.-М.:Высш.школа, 1976.-392с.
3. КультинН.Б. Программирование в TurboPascal 7.0 и Delphi.-Санкт-Петербург:BHV, 1998.-240c.
4. В.М.Бондарев, В.И. Рублинецкий, Е.Г. Качко. Основы программирования, 1998 г.
5. Ф.А.Новиков. Дискретная математика для программистов, Питер, 2001 г.
6. В.А.Носов. Комбинаторика и теория графов, МГТУ, 1999 г.
7. О.Оре. Теория графов, Наука, 1982 г.
8. www.codenet.ru
9. www.algolist.ru
Приложение
Программа отысканиягамильтонова цикла в графе:
Uses
dos,crt;
VARa,b:array[1..100,1..100] of integer;
i,j,n,ij:integer;
stro:text;
procedureini_b;//модифицирование матрицы смежности (из А создаем В)
vari,j:integer;
begin;
fori:=1 to n do
forj:=1 to n do
b[i,j]:=a[i,j]*j;
end;
procedureini_p1;// Формирование матрицы /> из А
vari,j:integer;
s_i,s_j:string[3];
f1:text;
begin;
fori:=1 to n do
forj:=1 to n do
begin;
str(i,s_i);if i
str(j,s_j);if j
assign(f1,'vrm\p'+s_i+s_j+'.txt');
rewrite(f1);
ifa[i,j]0 then writeln(f1,a[i,j]:4);
close(f1);
end;
end;
proceduremulti_B_P1(nom:integer); //перемножениематриц/> иВ,
запись результата в />
varii,i,j,k,s,ip:integer;
s_i,s_j,s_k:string[3];
f1,f2:text;
labelq1;
begin;
fori:=1 to n do
forj:=1 to n do
begin;
str(i,s_i);if i
str(j,s_j);if j
assign(f2,'vrm\p2'+s_i+s_j+'.txt');
rewrite(f2);
ifij then begin;
fork:=1 to n do
begin;
str(k,s_k);if 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;
whilenot eof(f1) do begin;
ip:=0;ii:=0;
whilenot eoln(f1) do begin;
ip:=0;
read(f1,ip);
if(nom=1) and (ip0) then begin; {write(f2,ip:4);}ii:=2;end;
if(nom>1) and (ip0)then begin;
ifii=0 then begin;write(f2,b[i,k]:4);ii:=1;end; write(f2,ip:4);end;
end;
ifii=2 then begin;write(f2,b[i,k]:4);end;
ifii>0 then writeln(f2);
ii:=0;
readln(f1);
end;
close(f1);
q1:end;
end;
close(f2);
end;
end;
procedurerename_P1_P2;// теперь нам /> уже не требуется и ейприсваиваются //значения />, в свою очередь в />будут записаны новыеданные при втором проходе
vari,j,IP1,IP2:integer;
s_i,s_j:string[3];
f1,F2:text;
AA:ARRAY[1..100]OF INTEGER;
ia,k,li,llj:integer;
labelmm,mm2;
begin;
fori:=1 to n do
forj:=1 to n do
begin;
str(i,s_i);if i
str(j,s_j);if 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;
whilenot eof(f1) do begin;
ia:=1;
whilenot eoln(f1) do begin;
read(f1,aa[ia]);inc(ia);
end;
ifia=1 then goto mm;
dec(ia);
fork:=1 to ia do if (aa[k]=0) or (aa[k]=i) or (aa[k]=j) then goto mm;
fork:=1 to ia do begin;
forli:=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;
procedureviv_P;// процедура использовалась при отладке программы,
отвечала за вывод наэкран промежуточных матриц />и />
varii,jj,i,j,k,s,ip:integer;
s_i,s_j:string[3];
f1:text;
begin;
clrscr;
fori:=1 to n do
forj:=1 to n do
begin;
str(i,s_i);if i
str(j,s_j);if j
write('p[',i,',',j,']=');
assign(f1,'vrm\p'+s_i+s_j+'.txt');
reset(f1);
ii:=0;jj:=0;
whilenot eof(f1) do begin;
whilenot eoln(f1) do begin;
read(f1,ip);
if(ii=0) and (jj>0) then write('+');
ifii>0 then write('*'); write(ip);ii:=1;
end;
readln(f1);jj:=1; II:=0;
end;
readln;
close(f1);
end;
end;
procedureviv_P2; // запись вфайлexample.txt промежуточных матриц
varii,jj,i,j,k,s,ip:integer;
s_i,s_j:string[3];
f1:text;
begin;
writeln(stro,'*********************************************');
fori:=1 to n do
forj:=1 to n do
begin;
str(i,s_i);if i
str(j,s_j);if j
write(stro,'p[',i,',',j,']=');
assign(f1,'vrm\p'+s_i+s_j+'.txt');
reset(f1);
ii:=0;jj:=0;
whilenot eof(f1) do begin;
whilenot eoln(f1) do begin;
read(f1,ip);
if(ii=0) and (jj>0) then write(stro,'+');
ifii>0 then write(stro,'*'); write(stro,ip);ii:=1;
end;
readln(f1);jj:=1; II:=0;
end;writeln(stro);
close(f1);
end;
end;
procedureviv_res;// изначально использовалась для вывода результатов на экран
varii,jj,i,j,k,s,ip,iij:integer;
ss_i,ss_j,s_i,s_j:string[3];
f1:text;
begin;
clrscr;
fori:=1 to n do
forj:=1 to n do
begin;
str(i,s_i);if i
str(j,s_j);if 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;
whilenot eof(f1) do begin;
whilenot eoln(f1) do begin;
read(f1,ip);
if(ii=0) and (jj>0) then begin;write(' '); iij:=0;end;
ifii>0 then write('-');
ifiij=0 then begin;
write('CHAINp[',i,',',j,']=',ss_j,'-',ss_i,'-');
iij:=1;
end;
write(ip);ii:=1;
end;
readln(f1);jj:=1; II:=0;
end;
ifiij>0 then readln;
close(f1);
end;
end;
proceduredelete_povtor; // удаление повторовивыводрезультатов
varii,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;
functionprov_povtor:boolean; // непосредственнопроверканаповторы
variaa,k2,l,l2:integer;
labelddd,ddd2;
begin;
fork2:=1 to et1[i,0]-1 do
ifet1[i,k2]et1[j,k2] then goto ddd;
prov_povtor:=true;exit;
ddd:
forl:=1 to et1[i,0]-1 do
begin;
iaa:=et1[i,1];
forl2:=2 to et1[i,0]-1 do et1[i,l2-1]:=et1[i,l2];
et1[i,et1[i,0]-1]:=iaa;
fork2:=1 to et1[i,0]-1 do
ifet1[i,k2]et1[j,k2] then goto ddd2;
prov_povtor:=true;exit;
ddd2:
end;
prov_povtor:=false;exit;
end;
labelyyy;
begin;
kol_et:=1;s:=0;
fori:=1 to 100 do et1[i,0]:=1;
fori:=1 to n do
forj:=1 to n do
begin;
str(i,s_i);if i
str(j,s_j);if j
assign(f1,'vrm\p'+s_i+s_j+'.txt');
reset(f1);
whilenot eof(f1) do begin;
ii:=0;
whilenot eoln(f1) do begin;
read(f1,ip);
ifip>0 then begin;
ifii=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;
fori:=1 to kol_et-1 do begin;
forj:=1 to i-1 do begin;
ifprov_povtor then goto yyy;
end;
ifs=0 then begin
writeln;
writeln('Найденныепути:');end;
writeln;
s:=1;// выводнайденныхпутей
fork:=1 to et1[i,0]-1 do write(et1[i,k],'-'); write(et1[i,1]);
yyy:end;
ifs=0 then writeln('Нет решения');
{for i:=1 to kol_et-1 do begin;
writeln;
forj:=1 to et1[i,0]-1 do write(et1[i,j],'-');
end;}
end;
proceduredelete_vrm; // удаление временныхфайлов
vari,j:integer;
s_i,s_j:string[3];
f1:text;
begin;
fori:=1 to n do
forj:=1 to n do
begin;
str(i,s_i);if i
str(j,s_j);if 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(n100) then begin;writeln('Превышенывозможностипрограммы’);
readkey;exit;end;
gotoxy(1,4);writeln('Введитематрицусмежностиграфа');
fori:=1 to n do begin
forj:=1 to n do begin
gotoxy(3*j,3+2*i+1);read(A[i,j]);// считываниематрицыА
ifnot ((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);
forij:=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.