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