і вершини Тільки парних степенів, то, очевидно, и 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, ..., | Є. | Так, щоб номер, прісвоєній ребру, Вказував, Яким за порядком це ребро находится в ейлеровому ціклі? Так вінікає Поняття алгоритму Флері. p align="justify"> Алгоритм Флері
Крок 1. Починаючі з довільною вершини n, прісвоїті Випадкове ребру {U, V} номер 1. Потім вікресліті ребро {U, V} и перейти в вершину v. p align="justify"> Крок 2. Нехай W - вершина, до Якої перейшлі в результаті Виконання попередня Крока, и k - номер, прісвоєній Деяк ребру на цьом кроці. Вібрато будь-яке ребро, iнцідентне вершіні W, причому міст вібіраті Тільки в того випадка, коли немає других варіантів; прісвоїті вибраному | ребру номер К +1 и вікресліті его. p align="justify"> Крок 3. Повторюваті крок 2 пока не ВСІ ребра вікреслені. br/>
2. Особливості роботи в СЕРЕДОВИЩА Visual C + +, NetBeans
Робота над проектом на етапі создания програмної реалізації алгоритму та розробки дружними середовища користувача проводили в інтегрованіх СЕРЕДОВИЩА розробки (IDE) Microsoft Visual Studio 2010 та NetBeans 7.0, Аджея смороду дозволяють пріскоріті процес налагодження Завдяк наявності потужном відлагоджувачів (debugger ), что Надаються шірокі возможности у корекції та від слідкуванні помилок власне во время покроковий Виконання ...
