39;язний і ступінь входу кожної вершини дорівнює ступеня виходу. [1] В
Оцінка числа ейлерових графів
В
Лемма : У будь-якому графі число вершин непарного ступеня парне.
Доказ: За теоремою 1 сума ступенів усіх вершин число парне. Сума ступенів вершин парному ступеня парна, значить, сума ступенів вершин непарного ступеня також парна, значить, їх парне число.
Нехай G (p) - безліч всіх графів з р вершинами, а Е (р) - безліч ейлерових графів з р вершинами.
Теорема 6: ейлерова графів майже немає, тобто
lim
Доказ: Нехай E / (р) - безліч графів з р вершинами і парними ступенями. Тоді за теореме1 Е (р) ГЊЕ / (p) і | Е (р) | ВЈ | Е / (p) |. У будь-якому графі число вершин непарного ступеня парне, отже, будь граф з Е / (p) можна отримати з деякого графа G (p-1), якщо додати нову вершину і з'єднати її з усіма старими вершинами непарного ступеня. Отже, | Е / (p) | ВЈ | G (p-1) |. Але | G (p) | = 2 C ( p , 2) . Зауважимо, що
С (k, 2)-C (k-1, 2) =
=
Далі маємо:
| Е (р) | ВЈ | Е / (p) | ВЈ | G (p-1) | = 2 C ( p -1,2) = 2 C ( p < sup>, 2) - ( p -1) = | G (p) | 2 - ( p -1)
і
, звідки lim. [3]
Алгоритм побудови ейлеровой кола в цьому ейлерова графі.
Цей метод відомий під назвою алгоритму Флері. p> Теорема 7: Нехай G - Ейлером граф, тоді наступна процедура завжди можлива і призводить до ейлеровой ланцюга графа G. Виходячи з довільної вершини і, йдемо по ребрах графа довільним чином, дотримуючись лише наступні правила:
1) стираємо ребра по мірі їх проходження і стираємо також ізольовані вершини, які при цьому утворюються;
2) на кожному етапі йдемо по мосту тільки тоді, коли немає інших можливостей.
Доказ: Покажемо спочатку, що зазначена процедура може бути виконана на кожному етапі. Припустимо, що ми досягли певної вершини V; тоді якщо V В№ U, то залишився подграф H зв'язний і містить рівно дві вершини непарного ступеня, а саме U і V. Згідно з теоремою 3 та визначенню полуейлерова графа, граф H містить полуейлерову ланцюг P з V в U. Оскільки видалення першого ребра ланцюга Р чи не порушує зв'язності графа Н, то описане в теоремі побудова (Т 1б)) можливо на кожному етапі. Якщо ж V = U, то доказ залишається тим же самим до тих пір, поки є ще ребра, інцідентние вершині U.
Залишилося тільки показати, що дана процедура завжди призводить до повної ейлеровой ланцюга. Але це очевидно, так як в G НЕ може бути ребер, залишилося не пройденими після використання останнього ребра, Інцидентне U. В іншому випадку видалення деякого ребра, суміжного од...
