105
правок
Изменения
→Критерий Эйлеровости
'''Достаточность:'''
<br/>
Рассмотрим Эйлеров цикл <math>p</math> в <math>G</math>.<br/>
Каждое вхождение вершины в цикл(кроме первого и последнего вхождения начальной вершины) добавляет 2 к ее степени.<br/>
Для начальной вершины ее первое и последнее вхождение также суммарно добавляют 2 к ее степени.<br/>
''Переход:''<br>
Рассмотри граф, в котором степени всех вершин четные.<br/>
В нем найдется простой цикл, т.к. иначе граф является лесом <math>-></math> в нем есть хотя бы два листа, что противоречит четности степеней всех вершин.<br/>Рассмотрим цикл <math>c</math> такой, что при удалении его ребер не образуется компонент связности размера больше 1.<br/>
Такой всегда существует, т.к. граф компонент двусвязности произвольного связного графа является деревом, а т.к. все вершины <math>G</math> <br/>
Рассмотрим вершину <math>u</math> со степенью больше 2. После удаления цикла <math>c</math> из графа степени всех вершин останутся четными,<br/> при этом количество ребер в графе уменьшится. Для <math>G - c</math>, по предположению индукции, существует эйлеров цикл <math>e</math>.<br/>
Тогда в <math>G</math> тоже существует Эйлеров обход - сначала обойти цикл с, начиная с вершины <math>u</math>, затем обойти <math>e</math>.<br/>
}}
