Пошук ейлерового ланцюга графа

Вступ

ейлеревий ланцюг теорія граф

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

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

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

Конкуренція на ринку технологій — природна річ, що допомагає швидкому поступу вперед, і зародилася вона ще з часу винайдення транзистору, яскравий приклад тому — світові гіганти напівпровідникових приладів Intel та AMD, що виникли внаслідок розділення команди розробників транзистору ще в кінці п’ятдесятих років двадцятого століття.

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

1. Теоретична частина

1.1 Загальні поняття теорії графів

З формальної точки зору граф представляє собою впорядковану пару G = (V, Е) множин, перша з яких складається з вершин або так званих вузлів графа, а друга — з його ребер. Ребро пов’язує між собою дві вершини. При роботі з графами часто цікавить, як прокласти шлях з ребер від однієї вершини графа до іншої. Тому будемо говорити про рух по ребру; це означає, що відбувається перехід з вершини, А графа в іншу вершину В, пов’язану з нею ребром АВ (ребро графа, що зв’язує дві вершини, для стислості позначається цією парою вершин). У цьому випадку ми говоримо, що, А примикає до В, або що ці дві вершини — сусідні. Граф може бути орієнтованим або ні. Ребра неорієнтованого графа, найчастіше званого просто графом, можна проходити в обох напрямках. У цьому випадку ребро — це невпорядкована пара вершин, його кінців. У орієнтованому графі, або орграфі, ребра представляють собою впорядковані пари вершин: перша вершина — це початок ребра, а друга — його кінець.

Повний граф — це граф, в якому кожна вершина з'єднана зі всіма іншими. Число ребер в повному графі без петель з N вершинами рівне / 2. У повному орієнтованому графі дозволяється перехід з будь-якої вершини в будь-яку іншу. Оскільки в графі перехід по ребру дозволяється в обох напрямках, а перехід по ребру в орграфі - тільки в одному, в повному орграфі в два рази більше ребер, тобто їх число дорівнює .

Підграф графа чи орграфа (V, E) складається з деякої підмножини вершин, з V, і деякої підмножини ребер, їх з'єднуючих, з E. Шлях у графі або орграфі - це послідовність ребер, по котрим можна по черзі проходити. Іншими словами, шлях з вершини, А в вершину В починається в, А і проходить по ребрах до того часу, поки не буде досягнута вершина В. З формальної точки зору, шлях з вершини у вершину — це послідовність ребер графа. Необхідно, щоб будь-яка вершина зустрічалась на такому шляху не більш ніж одного разу. У всякого шляху є довжина — число ребер у ньому. Довжина шляху АВ, ВС, CD, DE дорівнює 4. У зваженому графі або орграфі кожному ребру приписано число, зване вагою ребра. При зображенні графа будемо записувати вагу ребра поруч з ребром. При формальному описі вага буде додатковим елементом невпорядкованою або впорядкованої пари вершин (утворюючи разом з цією парою «триплет»). При роботі з орієнтованими графами ми вважаємо вагу ребра ціною проходу по ньому. Вартість шляху по зваженому графу дорівнює сумі ваг всіх ребер шляху. Найкоротший шлях в зваженому графі - це шлях з мінімальною вагою, навіть якщо число ребер в дорозі і можна зменшити. Якщо, наприклад, шлях складається з п’яти ребер з загальною вагою 24, а шлях — з трьох ребер з загальною вагою 36, то шлях вважається більш коротким. Граф або орграф називається зв’язним, якщо будь-яку пару вузлів можна з'єднати принаймні одним шляхом. Цикл — це шлях, який починається і закінчується в одній і тій же вершині. У ациклічному графі або або орграфі цикли відсутні. Зв’язний ациклічний граф називається неукоріненим деревом. Структура неукоріненого дерева така ж, що й у дерева, тільки в ньому не виділено корінь. Однак кожна вершина неукоріненого дерева може служити його коренем.

Інформацію про графи або орграфи можна зберігати двома способами: у вигляді матриці суміжності або у вигляді списку ребер. Матриця суміжності забезпечує швидкий доступ до інформації про ребра графа, проте якщо в графі мало ребер, то ця матриця буде містити набагато більше порожніх комірок, ніж заповнених. Довжина списку ребер пропорційна числу ребер у графі, однак при користуванні списком час отримання інформації про ребро збільшується. Жоден з цих методів не перевершує інший свідомо. У основу вибору підходящого методу повинні лежати попередні знання про графи, які будуть оброблятися алгоритмом. Якщо в графі багато вершин, причому кожна з них пов’язана лише з невеликою кількістю інших вершин, список ребер виявляється ефективнішим, оскільки він займає менше місця, а довжина списків ребер, що переглядаються, невелика. Якщо ж число вершин у графі мале, то краще скористатися матрицею суміжності: вона буде невелика, і навіть втрати при зберіганні в матричному вигляді розрідженого графа будуть незначні. Якщо ж у графі багато ребер і він майже повний, то матриця суміжності завжди є кращим способом зберігання графа. У реалізації програмного продукту обраний спосіб зберігання даних саме матрицею суміжності, адже для даного алгоритму вона виявляється більш універсальною.

Матриця суміжності AdjMat графу G = (V, E) з кількістю вершин записується у вигляді двовимірного масиву розміром. В кожній комірці цього масиву записане значення 0 за виключенням лише тих випадків, коли з вершини у вершину проходить ребро, і тоді в комірці записане значення 1, тобто Діагональні елементи матриці будуть рівні 0, оскільки шлях із вершини в неї саму не коштує нічого.

Список ребер AdjList графу з кількістю вершин записується у вигляді одновимірного масиву довжини N, кожен елемент якого — посилання на список. Такий список присвоєний до кожної вершини графу і він складає по одному елементу на кожну вершину графа, сусідню з даною.

Елементи списку ребер для зваженого графу містять додаткове поле, призначене для зберігання ваги ребра.

1.2 Пошук в глибину

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

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

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

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

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

Рисунок 1.1 — Приклад графу Розглянемо граф з мал. 1.1. Починаючи прохід з вершини 1, ми потім пройдемо послідовно вершини 2, 3, 4, 7, 5, 6 та зайдемо в глухий кут. Тоді нам доведеться повернутися у вершину 7 і побачити, що вершина 8 залишилася не пройденою. Але перейшовши в цю вершину, ми знову опиняємося в глухому куті. Повернувшись у вершину 4, ми бачимо, що не пройденою залишилася вершина 9; її прохід знову заводить в глухий кут. Знову повертаємося назад в початкову вершину, і оскільки всі сусідні з нею вершини виявилися пройденими, то обхід завершений.

Загальний алгоритм обходу виглядає так:

DepthFirstTraversal (G, v)

G граф

v даний вузол

Visit (v)

Mark (v)

for кожного ребра vw графа G do

if вершина w невідмічена then

DepthFirstTraversal (G, w)

end if

end for

1.3 Ланцюг, цикл. Зв’язність. Метричні характеристики графа

Вершина v називається такою, що досягається з вершини u, якщо існує (u, v) — маршрут. Будь-яка вершина вважається такою, що досягається із самої себе.

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

Властивості маршрутів, ланцюгів та циклів:

1) Будь-який незамкнений (u, v)-маршрут містить в собі простий (u, v)-ланцюг. Зокрема, будь-який (u, v)-ланцюг містить в собі простий (u, v)-ланцюг. До того ж, якщо (u, v)-маршрут складає в собі вершину w (), то в загальному випадку простий (u, v)-ланцюг може не містити в собі вершину w.

2) Будь-який непростий цикл можна розкласти на два чи більше простих. Але для замкненого маршруту таке твердження невірне.

3) Будь-який непростий (u, v)-ланцюг може бути розбитий на простий (u, v)-ланцюг та один або більше простих циклів. Для замкненого маршруту це твердження невірне.

4) Для будь-яких трьох вершин u, w, v із існування (u, w)-ланцюга та (w, v)-ланцюга слідує існування (u, v)-ланцюга. До того ж, не може існувати (u, v)-ланцюга, що містить вершину w.

5) Об'єднання двох простих (u, v)-ланцюгів, що не співпадають, має простий цикл.

6) Якщо граф має в собі 2 цикли, що не співпадають, із спільним ребром е, то після видалення цього ребра граф все одно має цикл.

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

Кожен максимальний зв’язний підграф графа G називається зв’язною компонентою (чи просто компонентою) графа G. Слово «максимальний» означає максимальний відносно включення, тобто такий, що не входить у зв’язний підграф з більшою кількістю елементів. Множина вершин зв’язної компоненти називається областю зв’язності.

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

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

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

Орграф є односторонньозв’язним тоді і тільки тоді, коли коли він має остовний маршрут. Сильнозв’язною компонентою графу називається його максимальний відносно включення сильнозв’язний граф. Нехай G — зв’язний граф, а u і v — дві його вершини, що не співпадають. Довжина найкоротшого (u, v)-маршруту називається відстанню між вершинами u та v і позначається d (u, v). Нехай d (u, u)=0. Очевидно, що введена таким чином відстань задовольняє такі аксіоми:

1) ;

2) тоді і тільки тоді, коли ;

3) для неорієнотованого графа;

4) (так звана нерівність трикутника).

Для фіксованої вершини u величина називається ексцентриситетом вершини u. Максимальний серед ексцентриситетів вершин називається діаметром графу G і позначається через d (G), тобто .

Вершина v називається периферійною, якщо. Простий ланцюг довжини, відстань між кінцями якого рівна, називається діаметральним ланцюгом.

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

Вершина v називається центральною, якщо. Множина всіх центральних вершин графа називається його центром. Граф може мати єдину центральну вершину або декілька. Центр графа може співпадати з множиною всіх вершин. Наприклад, центр простого ланцюга при парній кількості вершин n складається рівно з двох вершин, а при непарній — з однієї; для циклу всі вершини є центральними.

1.4 Ейлеровий граф, ланцюг, цикл

Ланцюг, що містить всі ребра графа, називають ейлеровим ланцюгом. Цикл в графі називається ейлеровим, якщо він містить всі ребра графа. Зв’язний граф, в котрому є ейлеровий цикл, називається ейлеровим графом. Такий граф можна намалювати, не відриваючи олівця від паперу і не повторюючи ліній.

Теорема Ейлера. Зв’язний граф є ейлеровим тоді і тільки тоді, коли степені всіх його вершин парні.

Необхідність. Нехай G — ейлеровий граф. Ейлеровий цикл цього графу, що проходить через кожну його вершину, входить в неї через одне ребро, а виходить через інше. Це означає, що кожна вершина інцидентна парному числу ребер ейлерового циклу, а оскільки такий цикл містить всі ребра графа G, то звідси випливає парність ступенів усіх його вершин.

Достатність. Припустимо тепер, що степені вершин графа G парні. Почнемо ланцюг P1 з довільної вершини v1 і будемо продовжувати її, наскільки можливо, обираючи щоразу нове ребро. Так як степені усіх вершин парні, то потрапивши в чергову відмінну від v1 вершину, ми завжди будемо мати в розпорядженні ще не пройдене ребро. Тому ланцюг P1 можна продовжити шляхом додавання цього ребра. Таким чином, побудова ланцюга P1 закінчиться у вершині v1, тобто P1 неодмінно будемо циклом. Якщо виявиться, що P1 містить всі ребра графа G, то це буде потрібний ейлеровий цикл. В іншому випадку, видаливши з G всі ребра циклу P1, розглянемо граф G1, отриманий в результаті такої операції. Оскільки P1 і G мали вершини тільки парних степенів, то, очевидно, і G1 будемо володіти тим же властивістю. Крім того, в силу зв’язності графа G графи P1 і G1 повинні мати хоча б одну спільну вершину v2. Тепер, починаючи з вершини v2, побудуємо цикл P2 в графі G1 подібно до того, як будували цикл P1. Позначимо через P1'і P1″ частини циклу P1 від V1 до V2 і від v2 до v1 відповідно. Отримаємо новий цикл P = 3P1 котрий, починаючи з v1, проходить по ребрах ланцюга P1″ до v2, потім обходить всі ребра циклу P2 і, нарешті, повертається в v1 по ребрах ланцюга P1″. Якщо цикл P3 не є ейлеровим, то проробивши аналогічні побудови, отримаємо ще більший цикл і т.д. Цей процес закінчиться побудовою ейлерового циклу. Будемо говорити, що набір реберно-непересічних ланцюгів (не обов’язково простих) покриває граф G, якщо кожне ребро графа G входить в один із цих ланцюгів. Якщо зв’язний граф містить рівно к вершин непарної степені, то мінімальне число покриваючих його реберно-непересічних ланцюгів рівне к / 2. Нехай зв’язний граф G містить K вершин непарної степені. Розглянемо граф G', отриманий додаванням до G нової вершини V і ребер, що з'єднують V з вершинами графа G ступеня непарної. Оскільки степені усіх вершин графу G' парні, то G' містить Ейлеровий цикл. Якщо тепер викинути V з цього циклу, то вийде к / 2 ланцюгів, що містять всі ребра графа G, тобто покривають G. З іншого боку, граф, є об'єднанням R реберно-непересічних ланцюгів, має найбільше 2r вершин непарного степеня. Тому меншим числом ланцюгів граф G покрити неможливо. Як знайти хоча б один Ейлеровий цикл в Ейлеровому графі G, тобто як занумеровані ребра графа числами 1, 2, …, | Є. | так, щоб номер, присвоєний ребру, вказував, яким за порядком це ребро знаходиться в ейлеровому циклі? Так виникає поняття алгоритму Флері.

Алгоритм Флері

Крок 1. Починаючи з довільною вершини n, присвоїти випадковому ребру {U, V} номер 1. Потім викреслити ребро {U, V} і перейти в вершину v.

Крок 2. Нехай W — вершина, до якої перейшли в результаті виконання попереднього кроку, і k — номер, присвоєний деякому ребру на цьому кроці. Вибрати будь-яке ребро, iнцидентне вершині W, причому міст вибирати тільки в тому випадку, коли немає інших варіантів; присвоїти обраному ребру номер К+1 і викреслити його.

Крок 3. Повторювати крок 2 поки не всі ребра викреслені.

2. Особливості роботи в середовищах Visual C++, NetBeans

Робота над проектом на етапі створення програмної реалізації алгоритму та розробки дружнього середовища користувача проводилася в інтегрованих середовищах розробки (IDE) Microsoft Visual Studio 2010 та NetBeans 7.0, адже вони дозволяють прискорити процес налагодження завдяки наявності потужних відлагоджувачів (debugger), що надають широкі можливості у корекції та від слідкуванні помилок власне під час покрокового виконання програми. Основна різниця між цими середовищами полягає у частково більш дружньому середовищі другого (виділення фігурних закриваючих дужок при наведенні на відкриваючі, змінної по всьому тексті програми при наведенні на неї курсору, можливість швидкої зміни назв змінних, прослідкування окремих змінних при роботі програми), але більш продуманому механізму відлагодження першого (наявність «гарячих» клавіш для вибору змінної для перегляду (watch), що приносило багато незручностей у NetBeans, а також можливості швидкого перемикання на локальні та глобальні змінні, змінні, що задані для перегляду користувачем). Тож в залежності від етапу використовувалися почергово обидва середовища, що значно спростило процес розробки (використовувалося NetBeans) та відлагодження (використовувалося Visual Studio).

Основні функції, що значно допомогли при розробці проекту:

1) Можливість проведення покрокових операцій (Debug-> Step Into);

2) Можливість проведення операцій, що «переступали» через функції та виклики файлів заголовків (Debug-> Step Over);

3) Можливість запуску програми до певної точки (Debug-> Run To Cursor);

4) Можливість встановлення точок перегляду — стаціонарних станів на певному етапі виконання програми (Debug-> Breakpoints);

5) Можливість перегляду значень змінних та функцій під час покрокового виконання програми (Debug-> Watch);

Не були вказані конкретні клавіатурні скорочення та шляхи, бо для NetBeans та Visual Studio вони дещо різняться, проте цей функціонал існує в обох середовищах розробки.

3.Програмна реалізація

3.1 Опис структури програми

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

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

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

3.2 Опис розроблених функцій

Int translate (char*) — функція, що реалізує перетворення рядка в число. Кожний елемент рядка char* перевіряється на належність цифрі; якщо це не так, то прапорець всередині функції сповіщає про це і замість простого використання функції atoi повертає значення -1; якщо ж все вірно, то повертається значення — результат виконання функції atoi.

Int atoi (char*) — функція із бібліотеки stdlib, що перетворює значення рядка char* і повертає як числове значення int.

Int** create matrix (int) — функція, що створює матрицю розмірами .

Void destroy matrix (int**, int) — функція, що знищує матрицю тих же розмірів.

Void show matrix (int**, int) — Функция вывода матрици смежности на экран.

3.3 Інструкція користувача

Ввести кількість вершин графа та його ребер (невід'ємні числа)

Для кожного ребра вводяться дві вершини, що його утворюють (так звані суміжні вершини) — невід'ємні числа в межах від 1 до N, де N — це кількість вершин графа

Після виконання даних дій повинно бути виведене повідомлення вигляду «->->…->», в якому ,…, — координати вершин шляху.

Висновки

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

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

Перелік посилань

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

1980.

2. Дейтел, Х., Дейтел, П. Как программировать на С++: Пер. с англ. — М: «Издательство БИНОМ», 1999 г. — 1024 с.

3. Керниган, Б., Ритчи, Г. Язык программирования С, 2-е изд.: Пер. с англ. — М: Издательский дом «Вильямс», 2010. 304 с.

4. Макконнелл, Дж. Основы современных алгоритмов. 2-е доп. изд.: Пер. с англ. — М: Техносфера, 2004. — 368с.

Додаток А

Текст програми

#include

#include

#include

#include

using namespace std;

//Функция перевода из символов в числа

int translation (char* c){

bool ok=false;

int i=0;

while (c[i] ≠ '')(c[i]<'0'))

ok=true;

i++;

if (ok == false)

return atoi (c);

else

return -1;

}

//Функция создание матрици

int** createMatrix (int n){

int** t = new int*[n];

for (int i=0; i

t[i]=new int [n];

for (int i=0; i

for (int j=0; j

t[i][j]=0;

return t;

}

//Функция удаления матрици

void destroyMatrix (int** a, int n)

{

for (int i=0;i

delete [] a[i];

delete [] a;

}

//Функция вывода матрици смежности на экран

void showMatrix (int** a, int n){

cout << endl << «Матрица смежности: n» ;

for (int j=0; j

for (int i=0; i

cout << a[j][i];

if (i == n-1){

cout << endl;

}

}

}

cout << endl;

}

int main (){

int n;

int m;

//Не четные вершины

int nv = 0;

//Вершина 1

int v1;

//Вершина 2

int v2;

int ns;

int x = 1;

int i = 0;

char t1[100];

char t2[100];

//Установка русского языка

setlocale (LC_ALL, «Russian»);

do {

cout << «Введите количество вершин и рёбер: n» ;

//t1-количество вершин

//t2-количество рёбер

cin >> t1 >> t2;

//Преобразование данных из символьного типа в числовой, если было введено НЕ число, то вывод сообщения об ошибке

n = translation (t1);

m = translation (t2);

//Если количество вершин или рёбер отрицательного значения — вывод сообщения об ошибке

if ((n<0)||(m<0)){

cout << «Введены неверные данные, повторите ввод еще раз. n» ;

}

} while ((n == -1)||(m == -1));

//Присваиваем указателю с именем ms адрес динамически созданной матрици (МАТРИЦИ СМЕЖНОСТИ) размерностью n на n заполненной нулями

int** ms = createMatrix (n);

//Присваиваем указателю с именем tv адрес динамически созданного одномерного массива типа int размерностью n+3

int* tv = new int [n+3];

for (int i=0;i

cout << «Введите две смежные вершины: n» ;

//t1-одна вершина

//t2-другая вершина

cin >> t1 >> t2;

//Преобразование данных из символьного типа в числовой, если было введено НЕ число, то вывод сообщения об ошибке

v1 = translation (t1);

v2 = translation (t2);

//Если любая из введенных вершин отрицательная или больше общего количества всех вершин, то вывести сообщение об ошибке

while ((v1 > n)||(v1 < 0)||(v2 > n)||(v2 < 0)){

cout << «Введены неверные данные, повторите ввод еще раз. n» ;

i—;

continue;

}

//Заполнение матрици смежности

ms[v1−1][v2−1]=1;

ms[v2−1][v1−1]=1;

}

//Вывод матрици смежности

showMatrix (ms, n);

//Подсчет количества не четных вершин

for (int i=0; i

int t=0;

for (int j=0; j

if (ms[i][j] == 1) t++;

if (t % 2 == 1) nv++;

}

//Если граф имеет более двух не четных вершин — вывод сообщения

if (nv > 2){

cout << «Граф не имеет Эйлеровой цепи. n» ;

system («pause»);

exit (0);

}

//Поиск начала цепи

for (int i=0; i

int t=0;

for (int j=0; j

if (ms[i][j] == 1) t++;

if (t%2 == 1){

ns = i;

break;

}

}

//Запись начальной вершины пути в начало массива, хранящего путь прохождения

tv[0] = ns;

//Поиск пути прохождения цепи

while (x < m){

while (i < n){

if (ms[ns][i] == 1){

ms[ns][i] = 0;

ms[i][ns] = 0;

ns = i;

tv[x] = ns;

x++;

i = 0;

} else i++;

}

}

cout << «Эйлерова цепь: n» ;

cout << tv[0]+1;

//Цикл вывода Эйлеровой цепи на экран

for (int i=1; i

cout << «->» ;

//Если элемент массива НЕ пустой — выводим элемент на экран

if ((tv[i]+1) ≠ NULL){

cout << tv[i]+1;

}

}

//Удаляем матрицу

destroyMatrix (ms, n);

//Освобождаем память, занимаемую массивом tv

delete [] tv;

//Ждем пока пользователь не нажмёт любую клавишу

_getch ();

return 0;

}

Додаток Б

Результат програми

Рисунок 1 — Результат роботи програми