Гамільтонови графи і складність відшукання гамільтонових циклів

Федеральне агентство з освіти РФ

САРАТОВСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ

ІМЕНІ Н.Г. ЧЕРНИШЕВСЬКОГО

Кафедра геометрії

Гамільтонови графи і складність відшукання гамільтонових циклів

Курсова робота

Науковий керівник

Старший викладач ______________

должн., уч. ступінь, уч. кликаний. підпис, дата ініціали, прізвище

Саратов 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 можна перетворити на гамільтонів граф, додавши достатню кількість вершин. Для цього, наприклад, досить до вершин v 1, ..., vp графа G додати вершини u 1, ..., 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 + 2 k. Це і є шукане протиріччя.

Теорема (Оре) 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 (v k) ≤ k ≤ n / 2 => d (v nk) ≥ 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 гамільтонів цикл. Критерії існування, дані вище, становлять теоретичний інтерес, але є занадто загальними і не придатні для довільних графів, що зустрічаються на практиці. Алгебраїчні методи визначення гаільтонових циклів не можуть бути застосовані з більш ніж кількома десятками вершин, так як вони вимагають надто великого часу роботи і великий пам'яті комп'ютера. Більш прийнятним є спосіб Робертса та Флореса, який не пред'являє надмірні вимоги до пам'яті комп'ютера, але час у якому залежить експоненціально від числа вершин у графі. Однак інший неявний метод перебору має для більшості типів графів дуже невеликий показник зростання часу обчислень в залежності від числа вершин. Він може бути використаний для знаходження гамільтонових циклів у дуже великих графах. Цей метод включає в себе побудову всіх простих ланцюгів за допомогою послідовного перемножування матриць. «Внутрішнє твір вершин» ланцюги x 1, x 2, ..., xk -1, xk визначається як вираз виду x 2 * x 3 * ... xk -1, що не містить дві кінцеві вершини x 1 і 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), є простими, то серед ланцюгів,

p ¢ 1 +1 (s, t) = Σ b (s, k) * p 1 (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 і т.д., поки не буде побудована матриця P n -1, що дає всі Гамільтонови ланцюга (що мають довжину n - 1) між усіма парами вершин. Гамільтонови цикли виходять тоді відразу з ланцюгів в P n -1 і тих дуг з G, які з'єднують початкову та кінцеву вершини кожного ланцюга. З іншого боку, Гамільтонови цикли даються членами внутрішнього твори вершин, що стоять у будь-який діагональної осередку матриці B * Pn -1 (всі діагональні елементи цієї матриці однакові).

Очевидно, що як початкове значення матриці P (тобто P 1) слід взяти матрицю суміжності 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. Використовувався комп'ютер IBM 360/65 з пам'яттю 120 000 байтів. Більш того, навіть для графа з вищевказаними «розмірами» даний метод використовував фактично весь обсяг пам'яті та час обчислень дорівнювало 1.8 хвилини. Не таке вже й незначний час для такого невеликого графа.

2.2 Метод перебору Робертса та Флореса

На противагу алгебраїчним методів, за допомогою яких намагаються знайти відразу всі Гамільтонови цикли і при реалізації яких доводиться зберігати, тому всі ланцюги, які можуть виявитися частинами таких циклів, метод перебору має справу з одним ланцюгом, безперервно подовжують аж до моменту, коли або виходить гамільтонів цикл, або стає ясно, що цей ланцюг не може призвести до гамильтонова циклу. Тоді ланцюг модифікується деяким систематичним способом (який гарантує, що, врешті-решт, будуть вичерпані всі можливості), після чого триває пошук гамильтонова циклу. У цьому способі для пошуку потрібно дуже невеликий обсяг пам'яті і за один раз знаходиться один гамільтонів цикл.

Наступна схема перебору, що використовує звичайну техніку повернення, була спочатку запропонована Робертсом і Флоресом. Починають з побудови (k × n)-матриці M = [mij], де елемент mij є i-я вершина (скажімо xq), для якої в графі G (X, Г) існує дуга (xj, xq). Вершини xq в безлічі Г (xj) можна впорядкувати довільно, утворивши елементи j-го стовпця матриці M. Число рядків k матриці M дорівнюватиме найбільшою полустепені результату вершини.

Метод полягає в наступному. Деяка початкова вершина (скажімо, x 1) вибирається в якості відправної і утворює перший елемент множини S, який щоразу буде зберігати вже знайдені вершини споруджуваної ланцюга. До S додається перша вершина (наприклад, вершина a) у стовпці x 1. Потім до безлічі S додається перша можлива вершина (наприклад, вершина b) у стовпці a, потім додається до S перша можлива вершина (наприклад, вершина c) у стовпці b і т.д. Під «можливою» вершиною ми розуміємо вершину, ще не приналежну S. Існують дві причини, що перешкоджають включенню деякої вершини на кроці r в безліч S = {x 1, a, b, c, ..., xr -1, xr}:

1. У стовпці xr немає можливої ​​вершини.

2. Ланцюг, що визначається послідовністю вершин в S, має довжину n - 1, тобто є гамильтоновой ланцюгом.

У випадку 2) можливі наступні випадки:

1. У графі G існує дуга (xr, x 1), і тому знайдений гамільтонів цикл.

2. Дуга (xr, x 1) не існує і не може бути отриманий ніякої гамільтонів цикл.

У випадках (1) і (2 b) слід вдатися до повернення, в той час як у випадку (2 a) можна припинити пошук і надрукувати результат (якщо потрібно знайти лише один гамільтонів цикл), або (якщо потрібні всі такі цикли) зробити друк і вдатися до повернення.

Повернення полягає у видаленні останньої включеної вершини xr з S, після чого залишається безліч S = {x 1, a, b, c, ..., xr -1}, і додаванні до S першою можливою вершини, наступної за xr, у стовпці xr -1 матриці M. Якщо не існує ніякої можливої ​​вершини, робиться наступний крок повернення і т.д.

Пошук закінчується в тому випадку, коли безліч S складається тільки з вершини x 1 і не існує ніякої можливої ​​вершини, яку можна додати до 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 → 4 березня → 5

6) S = {1, 2, 3, 4}

7) S = {1, 2, 3} 3 → 1 3 → 2 березня → 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 = {x 1, x 2, ..., xr} і що наступною вершиною, яку передбачається додати до S, є x * S. Розглянемо тепер дві наступні ситуації, в яких вершина є ізольованою в підпункті, що залишається після видалення з G (X, Г) усіх вершин, що утворюють побудовану до цього ланцюг.

1. Якщо існує така вершина x X \ S, що x Г (xr) і Г-1 (x) S, то, додаючи до S-яку вершину x *, відмінну від x, ми не зможемо в подальшому досягти вершини x ні з якої кінцевої вершини побудованої ланцюга, і, значить, цей ланцюг не зможе привести нас до побудови гамильтонова циклу. Таким чином, в цьому випадку x є єдиною вершиною, яку можна додати до S для продовження ланцюгу.

2. Якщо існує така вершина x X \ S, що x Г-1 (x 1) і Г (x) S {X *} для деякої іншої вершини x *, то x * не може бути додана до S, оскільки тоді в що залишається підграфі не може існувати ніякої ланцюга між x і x 1. Ланцюг, обумовлена ​​безліччю S {X *}, не може через це призвести до гамильтонова циклу, а в якості кандидата на додавання до безлічі S слід розглянути іншу вершину, відмінну від x *.

Перевірка умов (a) і (b) буде, звичайно, уповільнювати ітеративну процедуру, і для невеликих графів (менше ніж з 20 вершинами) не виходить ніякого поліпшення первісного алгоритму Робертса та Флореса. Але для великих графів ця перевірка призводить до помітного скорочення необхідного часу обчислень, зменшуючи його звичайно в 2 або більше разів.

Висновок

У даній роботі ми познайомилися з основними поняттями, визначеннями і результатами, пов'язаними з гамільтонових графів і циклами. Так само ми розглянули ту частину теорії складності, яка зачіпає задачі відшукання гамильтонова циклу. І в підсумки проведених досліджень була написана програма відшукання гамильтонова циклу в графі.

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

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

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

3. Культін Н.Б. Програмування в Turbo Pascal 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;

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 _ p 1; / / Формування матриці з А

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 _ P 1_ P 2; / / тепер нам вже не потрібно і їй присвоюються / / значення , У свою чергу в будуть записані нові дані при другому проході

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 (f 1);

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; / / запис в файл example.txt проміжних матриць

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.