Изменения

Перейти к: навигация, поиск

Эйлеровость графов

12 байт добавлено, 04:42, 9 октября 2010
Критерий Эйлеровости
Рассмотрим вершину <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/>
105
правок

Навигация