Алгоритм Дейкстри 2 страница

Класичні комбінаторні завдання - це завдання вибору і розташування елементів кінцевого безлічі, що мають в якості вихідної деяку формулювання розважального змісту типу головоломок.

У 1859 р У. Гамільтон придумав гру «Навколосвітня подорож», що складається в знаходженні такого шляху, що проходить через всі вершини (міста, пункти призначення) графа, зображеного на рис. 1, щоб відвідати кожну вершину одноразово і повернутися у вихідну. Шляхи, що володіють такою властивістю, називаються Гамільтона циклу.

Завдання про гамільтонових циклах в графі отримала різні узагальнення. Одне з цих узагальнень - завдання комівояжера, що має ряд застосувань в дослідженні операцій, зокрема при вирішенні деяких транспортних проблем.

1.2 Постановка задачі

Завдання комівояжера (надалі скорочено - ЗК) є однією із знаменитих завдань теорії комбінаторики. Вона була поставлена в 1934 році, і про неї, як про Велику теорему Ферма обламували зуби кращі математики. У своїй області (оптимізації дискретних задач) ЗК служить своєрідним полігоном, на якому випробовуються все нові методи.

Постановка завдання наступна.

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

Щоб привести задачу до наукового увазі, введемо деякі терміни. Отже, міста перенумеровані числами jТ = (1,2,3..n). Тур комівояжера може бути описаний циклічної перестановкою t = (j1, j2,.., jn, j1), причому всі j1..jn - різні номери; повторюваний на початку і в кінці j1, показує, що перестановка зациклена. Відстані між парами вершин Сij утворюють матрицю С. Завдання полягає в тому, щоб знайти такий тур t, щоб мінімізувати функціонал.

Щодо математизированной формулювання ЗК доречно зробити два зауваження.

По-перше, у постановці Сij означали відстані, тому вони повинні бути невід'ємними, тобто для всіх jТ:

Сij0; Cjj = ∞ (2)

(останнє рівність означає заборону на петлі в турі), симетричними, тобто для всіх i, j:

Сij = Сji. (3)

і задовольняти нерівності трикутника, тобто для всіх:

Сij + СjkCik (4)

У математичній постановці йдеться про довільній матриці. Зроблено це тому, що є багато прикладних задач, які описуються основний моделлю, але всім умовам (2) - (4) не задовольняють. Особливо часто порушується умова (3) (наприклад, якщо Сij - НЕ відстань, а плата за проїзд: часто туди квиток коштує одну ціну, а назад - іншу). Тому ми будемо розрізняти два варіанти ЗК: симетричну задачу, коли умова (3) виконано, і несиметричну - в іншому випадку. Умови (2) - (4) за замовчуванням ми будемо вважати виконаними.

Друге зауваження стосується числа всіх можливих турів. У несиметричною ЗК всі тури t = (j1, j2,.., jn, j1) і t '= (j1, jn,.., j2, j1) мають різну довжину і повинні враховуватися обидва. Різних турів очевидно (n-1)!.

Зафіксуємо на першому і останньому місці в циклічній перестановці номер j1, а що залишилися n-1 номерів переставимо усіма (n-1)! можливими способами. В результаті отримаємо всі несиметричні тури. Симетричних турів мається на два раз менше, тому кожен зарахований два рази: як t і як t '.

Можна уявити, що С складається тільки з одиниць і нулів. Тоді З можна інтерпретувати, як граф, де ребро (i, j) проведено, якщо Сij = 0 і не проведено, якщо Сij = 1. Тоді, якщо існує тур довжини 0, то він пройде по циклу, який включає всі вершини по одному разу. Такий цикл називається гамільтоновим циклом. Незамкнутий гамільтонів цикл називається гамильтоновой ланцюгом (гамільтоновим шляхом).

У термінах теорії графів симетричну ЗК можна сформулювати так:

Дана повна мережу з n вершинами, довжина ребра (i, j) = Сij. Знайти гамільтонів цикл мінімальної довжини.

У несиметричною ЗК замість «цикл» треба говорити «контур», а замість «ребра» - «дуги» або «стрілки».

Деякі прикладні завдання формулюються як ЗК, але в них потрібно мінімізувати довжину трохи Гамільтона циклу, а гамильтоновой ланцюга. Такі завдання називаються незамкненими. Деякі моделі зводяться до задачі про декілька комівояжера, але ми тут їх розглядати не будемо.

1.3 Методи рішення задачі комівояжера

1.3.1. Жадібний алгоритм

Жадібний алгоритм - алгоритм знаходження найкоротшого відстані шляхом вибору найкоротшого, ще не обраного ребра, за умови, що воно не утворює циклу з вже обраними ребрами. «Жадібним» цей алгоритм названий тому, що на останніх кроках доводиться жорстоко розплачуватися за жадібність.

Подивимося, як поведеться при вирішенні ЗК жадібний алгоритм. Тут він перетвориться на стратегію «йди у найближчий (у який ще не входив) місто». Жадібний алгоритм, очевидно, безсилий у цьому завданні. Розглянемо для прикладу мережу на рис. 2, що представляє вузький ромб. Нехай комівояжер стартує з міста 1. Алгоритм «йди ви найближчий місто» виведе його в місто 2, потім 3, потім 4; на останньому кроці доведеться платити за жадібність, повертаючись по довгій діагоналі ромба. В результаті вийде не найкоротший, а довжелезний тур.

На користь процедури «йди у найближчий» можна сказати лише те, що при старті з одного міста вона не поступиться стратегії «йди в подальший».

Як бачимо, жадібний алгоритм помиляється. Чи можна довести, що він помиляється помірковано, що отриманий ним тур гірше мінімального, покладемо, в 1000 разів? Ми доведемо, що цього довести не можна, причому не тільки для жодного логарифма, а для алгоритмів набагато потужніших. Але спочатку потрібно домовитися, як оцінювати похибка неточних алгоритмів, для визначеності, в задачі мінімізації. Нехай fB - справжній мінімум, а fA - той квазімінімум, який отримано за алгоритмом. Ясно, що fA / fB≥1, але це - тривіальне твердження, що може бути похибка. Щоб оцінити її, потрібно затиснути ставлення оцінкою зверху:

fA / fB ≥1 + nε, (5)

де, як зазвичай у вищій математиці, ε≥0, але, проти звичаю, може бути дуже великим. Величина ε і буде служити мірою похибки. Якщо алгоритм мінімізації буде задовольняти нерівності (5), ми будемо говорити, що він має похибку ε.

Припустимо тепер, що є алгоритм А рішення ЗК, похибка якого потрібно оцінити. Візьмемо довільний граф G (V, E) і по ньому складемо вхідну матрицю ЗК:

С [i, j] = {1, якщо ребро (i, j) належить Е

1 + nε в іншому випадку

Якщо в графі G є гамільтонів цикл, то мінімальний тур проходить по цьому циклу і fB = n. Якщо алгоритм А теж завжди знаходитиме цей шлях, то за результатами алгоритму можна судити, чи є гамільтонів цикл в довільному графі. Однак, непереборного алгоритму, який міг би відповісти, чи є гамільтонів цикл в довільному графі, досі нікому не відомо. Таким чином, наш алгоритм А повинен іноді помилятися і включати в тур хоча б одне ребро довжини 1 + nε. Але тоді fA (n-1) + (1 + nε) так що fA / fB = 1 + nε тобто перевершує похибка ε на задану нерівністю (5). Про величину ε в нашому міркуванні ми не домовлялися, так що ε може бути безпідставно великий.

Таким чином доведена наступна теорема.

Або алгоритм А визначає, чи існує в довільному графі гамільтонів цикл, або похибка А при вирішенні ЗК може бути безпідставно велика.

Це міркування було вперше опубліковано Сани і Гонзалесом в 1980 р Теорема Сани-Гонзалеса заснована на тому, що немає ніяких обмежень на довжину ребер. Теорема не проходить, якщо відстані підпорядковуються нерівності трикутника (4).

Якщо воно дотримується, можна запропонувати кілька алгоритмів з похибкою 12. Перш, ніж описати такий алгоритм, слід згадати старовинну головоломку. Чи можна накреслити однією лінією відкритий конверт? Рис.2 показує, що можна (цифри на відрізках показують порядок їх проведення). Закритий конверт (рис.3.) Однією лінією намалювати не можна і ось чому. Будемо називати лінії ребрами, а їх перехрестя - вершинами.

Коли через точку проводиться лінія, то використовується два ребра - одне для входу в вершину, одне - для виходу. Якщо ступінь вершини непарна - то в ній лінія повинна початися або скінчитися. На рис. 3 вершин непарної ступеня дві: в одній лінія починається, в іншій - кінчається. Однак на рис. 4 є чотири вершини ступеня три, але в однієї лінії не може бути чотири кінця. Якщо ж потрібно прокреслити фігуру однією замкненою лінією, то всі її вершини повинні мати парну ступінь.

Вірно і зворотне твердження: якщо всі вершини мають парну ступінь, то постать можна намалювати однієї незамкненою лінією. Дійсно, процес проведення лінії може скінчитися, тільки якщо лінія прийде в вершину, звідки вже виходу немає: всі ребра, приєднані до цієї вершини (зазвичай кажуть: інцідентние цій вершині), вже прокреслені. Якщо при цьому намальована вся постать, то потрібне твердження доведено; якщо ні, видалимо вже намальовану частина G '. Після цього від графа залишиться одна або кілька зв'язкових компонент; нехай G '- одна з таких компонент. В силу зв'язності вихідного графа G, G 'і G' 'мають хоч одну загальну вершину, скажімо, v. Якщо в G '' видалені якісь ребра, то по парним числом від кожної вершини. Тому G '' - зв'язний і всі його вершини мають парну ступінь. Побудуємо цикл в G '' (можливо, не намалювавши всього G '') і через v додамо промальовувала частина G '' до G '. Збільшуючи таким чином промальовувала частина G ', ми доб'ємося того, що G' охопить весь G.

Це завдання колись вирішив Ейлер, і замкнуту лінію, яка покриває всі ребра графа, тепер називаю ейлеровим циклом. По суті була доведена наступна теорема.

Ейлером цикл в графі існує тоді і тільки тоді, коли (1) граф зв'язний і (2) всі його вершини мають парні ступеня.

1.3.2. Дерев’яний алгоритм

Тепер можна обговорити алгоритм рішення ЗК через побудова найкоротшого остовного дерева. Для стислості буде називати цей алгоритм дерев'яним.

Спочатку обговоримо властивість випрямлення. Розглянемо яку-небудь ланцюг, наприклад, на рис.5. Якщо справедливо нерівність трикутника, то d [1,3] d [1,2] + d [2,3] і d [3,5] d [3,4] + d [4,5] Склавши ці два нерівності, отримаємо d [1,3] + d [3,5] d [1,2] + d [2,3] + d [3,4] + d [4,5]. По нерівності трикутника отримаємо. d [1,5] d [1,3] + d [3,5]. остаточно

d [1,5] d [1,2] + d [2,3] + d [3,4] + d [4,5]

Отже, якщо справедливо нерівність трикутника, то для кожного ланцюга вірно, що відстань від початку до кінця ланцюга менше (або дорівнює) сумарної довжини всіх ребер ланцюга. Це узагальнення розхожого переконання, що пряма коротше кривої.

Повернемося до ЗК і опишемо вирішальний її дерев'яний алгоритм.

Побудуємо на вхідний мережі ЗК найкоротший кістяк і подвоїмо усі його ребра. Отримаємо граф G - зв'язний і з вершинами, що мають лише парні ступеня.

Побудуємо Ейлером цикл G, починаючи з вершини 1, цикл задається переліком вершин.

Переглянемо перелік вершин, починаючи з 1, і будемо закреслювати кожну вершину, яка повторює вже зустрінуту в послідовності. Залишиться тур, який і є результатом алгоритму.

Приклад 1. Дана повна мережу, показана на рис.5. Знайти тур жадібним і дерев'яним алгоритмами.

-
	-
		-
			-
				-
					-
						-
табл. 1

Рішення. Жадібний алгоритм (йди в найближче місто із міста 1) дає тур 1- (4) -3- (3) -5 (5) -4- (11) -6- (10) -2- (6) -1, де без дужок показані номери вершин, а в дужках - довжини ребер. Довжина туру дорівнює 39, тур показана на рис. 5.

2. Дерев'яний алгоритм спочатку будує остовное дерево, показане на рис. 6 штриховий лінією, потім Ейлером цикл 1-2-1-3-4-3-5-6-5-3-1, потім тур 1-2-3-4-5-6-1 довжиною 43, який показаний суцільний лінією на рис. 6.

Теорема. Похибка дерев'яного алгоритму дорівнює 1.

Доказ. Візьмемо мінімальний тур довжини fB і видалимо з нього максимальне ребро. Довжина вийшла гамильтоновой ланцюга LHC менше fB. Але цю ж ланцюг можна розглядати як кістяк, т. К. Ця ланцюг сягає все вершини і не має циклів. Довжина найкоротшого остовного дерева LMT менше або дорівнює LHC. Маємо ланцюжок нерівностей

fB> LHCLMT (6)

Але подвоєне дерево - воно ж Ейлером граф - ми звели до туру допомогою випрямлення, отже, довжина отриманого за алгоритмом туру задовольняє нерівності

2LMT> fA (7)

Множачи (6) на два і з'єднуючи з (7), отримуємо ланцюжок нерівностей

2fB> 2LHC2LMTfA (8)

Тобто 2fB> fA, тобто fA / fB> 1 + ;  = 1.

Теорема доведена.

Таким чином, ми довели, що дерев'яний алгоритм помиляється менш, ніж у два рази. Такі алгоритми вже називають приблизними, а не просто евристичними.

Відомо ще кілька простих алгоритмів, які гарантують у гіршому випадку  = 1. Для того, щоб знайти серед них алгоритм точніше, зайдемо з іншого кінця і для початку опишемо «brute-forceenumeration» - «перебір тваринної силою», як його називають в англомовній літературі. Зрозуміло, що повний перебір практично застосуємо тільки в задачах малого розміру. Нагадаємо, що ЗК з n містами вимагає при повному переборі розгляду (n-1)! / 2 турів в симетричній завданню і (n-1)! Турів в несиметричною, а факторіал, як показано в наступній таблиці, зростає гнітюче швидко:

5!	10!	15!	20!	25!	30!	35!	40!	45!	50!
~102	~106	~1012	~1018	~10125	~1032	~1040	~1047	~1056	~1064

Щоб проводити повний перебір в ЗК, потрібно навчитися (зрозуміло, без повторень) генерувати всі перестановки заданого числа m елементів. Це можна зробити декількома способами, але найпоширеніший (тобто застосовний для переборних алгоритмів вирішення інших завдань) - це перебір в лексикографічному порядку.

Нехай є деякий алфавіт і набори символів алфавіту (букв), звані словами. Букви в алфавіті впорядковані: наприклад, в російській алфавіті порядок букв абя (символ  читається «передує)». Якщо заданий порядок букв, можна впорядкувати і слова. Скажімо, дано слово u = (u1, u2,.., um) - складається з букв u1, u2,.., um - і слово v = (v1, v2,.., vb). Тоді якщо u1v1, то і uv, якщо ж u1 = v1, то порівнюють другу букви і т.д. Цей порядок слів і називається лексикографічним. Тому в російських словниках (лексиконах) слово «абажур» стоїть раніше слова «абака». Слово «бур» стоїть раніше слова «бура», бо пробіл вважається попереднім будь букві алфавіту.

Розглянемо, скажімо, перестановки з п'яти елементів, позначених цифрами 1..5. Лексикографічно першої перестановкою є 1-2-3-4-5, другий - 1-2-3-5-4,..., останньою - 5-4-3-2-1. Потрібно усвідомити загальний алгоритм перетворення будь перестановки в безпосередньо наступну.

Правило таке: скажімо, дана перестановка 1-3-5-4-2. Потрібно рухатися по перестановці справа наліво, поки вперше не побачимо число, менше, ніж попереднє (у прикладі це 3 після 5). Це число, Pi-1 треба збільшити, поставивши замість нього якесь число з розташованих правіше, від Pi до Pn. Число більше, ніж Pi-1, безсумнівно, знайдеться, так як Pi-1 <Pi. Якщо є кілька великих чисел, то, очевидно, треба ставити менше з них. Нехай це буде Pj, j> i-1. Потім число Pi-1 і всі числа від Pi до Pn, не рахуючи Pj потрібно впорядкувати по зростанню. В результаті вийде безпосередньо наступна перестановка, у прикладі - 1-4-2-3-5. Потім вийде 1-4-2-5-3 (той же алгоритм, але спрощений випадок) і т.д.

Потрібно розуміти, що в ЗК з n містами не потрібні всі перестановки з n елементів. Тому що перестановки, скажімо, 1-3-5-4-2 і 3-5-4-2-1 (останній елемент з'єднаний з першим) ставлять одне і те ж тур, лічений спершу з міста 1, а потім з міста 3. Тому потрібно зафіксувати початковий місто 1 і приєднувати до нього всі перестановки з інших елементів. Цей перебір дасть (n-1)! різних турів, тобто повний перебір в несиметричною ЗК (ми як і раніше будемо розрізняти тури 1-3-5-4-2 і 1-2-4-5-3).

Даний алгоритм описаний мовою Паскаль (див. Додатки).

Приклад 2. Вирішимо ЗК, поставлену в Прімері 1 лексикографічним перебором. Наведена вище програма надрукує міста, складові кращий тур: 1-2-6-5-4-3 і егодліну 36.

Бажано удосконалити перебір, застосувавши розум. У наступному пункті описаний алгоритм, який реалізує просту, але широко застосовну і дуже корисну ідею.

1.3.3. Метод гілок і меж

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

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

Викладемо алгоритм Літтла на прикладі 1 попереднього розділу.. Повторно запишемо матрицю:

-
	-
		-
			-
				-
					-
						-
табл. 2

-
	-
		-
			-
				-
					-
						-
табл. 3

-
	-
		-
			-
				-
					-
						-
табл. 4

Нам буде зручніше трактувати Сij як вартість проїзду з міста i в місто j. Припустимо, що добрий мер міста j видав указ виплачувати кожному в'їхали в місто комівояжеру 5 доларів. Це означає, що будь-який тур подешевшає на 5 доларів, оскільки в будь-якому турі потрібно в'їхати в місто j. Але оскільки всі тури рівномірно подешевшали, то колишній мінімальний тур буде і тепер коштувати менше всіх. Добрий же вчинок мера можна представити як зменшення всіх чисел j-го шпальти матриці С на 5. Якби мер хотів спровадити комівояжерів з j-го міста і встановив нагороду за виїзд в розмірі 10 доларів, це можна було б висловити відніманням 10 з усіх елементів j-й тієї рядки. Це знову б змінило вартість кожного туру, але мінімальний тур залишився б мінімальним. Отже, доведена наступна лема.

Віднімаючи будь-яку константу з усіх елементів будь-якого рядка або стовпця матриці С, ми залишаємо мінімальний тур мінімальним.

Для алгоритму нам буде зручно отримати побільше нулів в матриці С, не отримуючи там, однак, негативних чисел. Для цього ми віднімемо з кожного рядка її мінімальний елемент (це називається приведенням по рядках, див. Табл. 3), а потім віднімемо з кожного шпальти матриці, наведеної по рядках, його мінімальний елемент, отримавши матрицю, наведену по стовпцях, див. Табл. 4).

Прочерки по діагоналі означають, що з міста i в місто i ходити не можна. Зауважимо, що сума констант приведення по рядках дорівнює 27, сума по стовпцях 7, сума сум дорівнює 34.

Тур можна задати системою з шести підкреслених (виділених іншим кольором) елементів матриці С, наприклад, такий, як показано на табл. 2. Підкреслення елемента означає, що в турі з i-го елемента йдуть саме в j-тий. Для туру з шести міст підкреслених елементів має бути шість, так як в турі з шести міст є шість ребер. Кожен стовпець повинен містити рівно один підкреслений елемент (в кожне місто комівояжер в'їхав один раз), в кожному рядку повинен бути рівно один підкреслений елемент (з кожного міста комівояжер виїхав один раз); крім того, підкреслені елементи повинні описувати один тур, а не кілька менших циклів. Сума чисел підкреслених елементів є вартість туру. На табл. 2 вартість дорівнює 36, це той мінімальний тур, який отримано лексикографічним перебором.

Тепер будемо міркувати від наведеної матриці на табл. 2. Якщо в ній вдасться побудувати правильну систему підкреслених елементів, тобто систему, що задовольняє трьом вищеописаним вимогам, і цими підкресленими елементами будуть лише нулі, то ясно, що для цієї матриці ми отримаємо мінімальний тур. Але він же буде мінімальним і для вихідної матриці С, тільки для того, щоб отримати правильну вартість туру, потрібно буде назад додати всі константи приведення, і вартість туру зміниться з 0 до 34. Таким чином, мінімальний тур не може бути менше 34. Ми отримали оцінку знизу для всіх турів.

Тепер приступимо до розгалуження. Для цього виконаємо крок оцінки нулів. Розглянемо нуль у клітині (1,2) наведеної матриці. Він означає, що ціна переходу з міста 1 в місто 2 дорівнює 0. А якщо ми не підемо з міста 1 в місто 2? Тоді все одно потрібно в'їхати в місто 2 за ціни, зазначені у другому стовпці; найдешевше за 1 (з міста 6). Далі, все одно треба буде виїхати з міста 1 за ціну, зазначену в першому рядку; найдешевше в місто 3 за 0. Підсумовуючи ці два мінімуму, маємо 1 + 0 = 1: якщо не їхати «по нулю» з міста 1 в місто 2, то треба заплатити не менше 1. Це і є оцінка нуля. Оцінки всіх нулів поставлені на табл. 5 правіше і вище нуля (оцінки нуля, рівні нулю, не ставилися).

Виберемо максимальну з цих оцінок (у прикладі є кілька оцінок, рівних одиниці, виберемо першу з них, у клітці (1,2)).

Отже, вибрано нульове ребро (1,2). Розіб'ємо всі тури на два класи - включають ребро (1,2) і не включають ребро (1,2). Про другий клас можна сказати, що доведеться доплатити ще 1, так що тури цього класу коштують 35 або більше.

Що стосується першого класу, то в ньому треба розглянути матрицю на табл. 6 з викресленої першим рядком і другим стовпцем.

	-
		-
			-
				-
					-
						-
табл. 5

		-
			-
				-
					-
табл. 6

		-
			-
				-
					-
табл. 7

		-
			-
				-
табл. 8

Додатково в зменшеної матриці поставлений заборона в клітці (2,1), т. К. Вибрано ребро (1,2) і замикати передчасно тур руба (2,1) не можна. Зменшену матрицю можна привести на 1 по першому стовпцю, так що кожен тур, їй відповідає, коштує не менше 35. Результат наших розгалужень і отримання оцінок показаний на рис.6.

Гуртки представляють класи: верхній гурток - клас всіх турів; нижній лівий - клас всіх турів, що включають ребро (1,2); нижній правий - клас всіх турів, що не включають ребро (1,2). Числа над кружками - оцінки знизу.

Продовжимо розгалуження в позитивну сторону: вліво - вниз. Для цього оцінимо нулі в зменшеної матриці C [1,2] на табл. 7. Максимальна оцінка в клітці (3,1) дорівнює 3. Таким чином, оцінка для правої нижньої вершини на рис. 7 є 35 + 3 = 38. Для оцінки лівої нижньої вершини на рис. 7 потрібно викреслити з матриці C [1,2] ще рядок 3 і стовпець 1, отримавши матрицю C [(1,2), (3,1)] на табл. 8. У цю матрицю потрібно поставити заборону в клітку (2,3), так як вже побудований фрагмент туру з ребер (1,2) і (3,1), тобто [3,1,2], і потрібно заборонити передчасне замикання (2,3). Ця матриця наводиться по стовпцю на 1 (табл. 9), таким чином, кожен тур відповідного класу (тобто тур, що містить ребра (1,2) і (3,1)) стоїть 36 і більше.

		-
			-
				-
табл. 9

Дата добавления: 2015-06-28