що він не є ейлеровим циклом. [1]
Теорема 2: Якщо граф G має ейлеровим шляхом з кінцями А і В (А не співпадає з В), то граф G зв'язний і А і В - єдині непарні його вершини.
Доказ: Зв'язність графа випливає з визначення ейлерова шляху. Якщо шлях починається в А, а закінчується в іншій вершині, то і А і В - непарні навіть якщо шлях неодноразово проходив через А і В. У будь-яку іншу вершину графа шлях повинен був привести і вивести з неї, тобто всі інші вершини повинні бути парними.
Теорема 3 : (зворотна) Якщо граф G зв'язний і А і В єдині непарні вершини його, то граф G володіє ейлеровим шляхом з кінцями А і В.
Доказ: Вершини А і В можуть бути з'єднані ребром у графі, а можуть бути з'єднані.
Якщо А і В з'єднані ребром, то видалимо його; тоді всі вершини стануть парними. Новий граф (по теоремі 1) володіє ейлеровим циклом, початком і кінцем якого може служити будь-яка вершина. Почнемо Ейлером шлях у вершині А і кінчимо його в вершині А. Додамо ребро (А, В) і отримаємо Ейлером шлях з початком в А і кінцем в В.
Якщо А і В не з'єднані ребром, то до графа додамо нове ребро (А, В), тоді всі вершини його стануть парними. Новий граф (по теоремі 1) володіє ейлеровим циклом. Почнемо його з вершини А по ребру (А, В). Закінчується шлях теж у вершині А. Якщо видалити тепер з отриманого циклу ребро (А, В), то залишиться Ейлером шлях з початком у В і кінцем в А або початком в А і кінцем В.
Таким чином, будь-яку замкнену фігуру, що має в точності дві непарні вершини, можна накреслити одним розчерком без повторень, почавши в одній з непарних вершин, а скінчивши в іншій.
Теорема 4 : Якщо зв'язний граф G має 2k непарних вершин, то знайдеться сімейство з k шляхів, які в сукупності містять всі ребра графа в точності по одному разу.
Доказ: Половину непарних вершин позначимо А 1 , А 2 , ..., А k , іншу половину У 1 , У 2 , ..., У k (рис.7). Якщо вершини А i і В i (1 i , У i ). Якщо вершини А і В не з'єднані ребром, то додамо до G ребро (А i , У i ). Всі вершини нового графа будуть парними, то є в новому графі знайдеться Ейлером цикл. При відновленні графа G цикл розіб'ється на k окремих шляхів, що містять всі ребра графа. [2]
В
Рис.7
Нехай G = (V, E) - орієнтований граф. Орієнтованим циклом називається орієнтований шлях ненульовий довжини з вершини в ту ж вершину без повторення ребер.
Нехай G = (V, E) - орієнтований граф. Орієнтований цикл, який включає всі ребра і вершини графа G, називається ейлеровим циклом. Кажуть, що орієнтований граф G має Ейлером цикл.
Теорема 5 : Орієнтований граф має Ейлером цикл тоді і тільки тоді, коли він зв&#...
