Изменения
→Эйлеров граф
==Эйлеров граф==
{{Определение|definition=
Граф <tex>G = (V, E)</tex> называется Эйлеровым'''эйлеровым''', если содержит Эйлеров эйлеров цикл. Граф, содержащий Эйлеров эйлеров путь, не являющийся циклом, называют '''полуэйлеровым'''. <br/>
}}
===Критерий Эйлеровостиэйлеровости===
{{Определение|definition=
Неориентированный граф назовем '''почти связным''', если все его [[Отношение_связности,_компоненты_связности|компоненты связности]], кроме, быть может, одной, имеют размер 1.<br/>Ориентированный граф назовем '''почти связным''', если все его [[Отношение_связности,_компоненты_связности|компоненты слабой связности]], кроме, быть может, одной, имеют размер 1.
}}
====[[Основные определения теории графов|Неориентированный граф]]====
{{Теорема
|statement=
Неориентированный почти связный граф <tex>G = (V, E)</tex> является Эйлеровым эйлеровым тогда и только тогда, когда не содержит вершин нечетной [[Основные определения теории графов|степени]].<br/>
|
proof=
'''Достаточность:'''
<br/>
Рассмотрим Эйлеров эйлеров цикл <tex>p</tex> в <tex>G</tex>.
Каждое вхождение вершины в цикл(кроме первого и последнего вхождения начальной вершины) добавляет 2 к ее степени.<br/>
Для начальной вершины ее первое и последнее вхождение также суммарно добавляют 2 к ее степени. В итоге, каждая вершина имеет четную степень.
