1632
правки
Изменения
м
rollbackEdits.php mass rollback
1. Все вершины имели четную степень.
2. Все компоненты связности , кроме, может быть , одной, не содержали ребер.
|proof=
1. Допустим в графе существует вершина с нечетной степенью. Рассмотрим эйлеров обход графа. Заметим, что при попадании в вершину и при выходе из нее мы уменьшаем ее степень на два (помечаем уже пройденые ребра), если эта вершина не является стартовой(она же конечная для цикла). Для стартовой(конечной) вершины мы уменьшаем ее степень на один в начале обхода эйлерова цикла, и на один при завершении. Следовательно вершин с нечетной степенью быть не может. Наше предположение неверно.
1. Все вершины имеют четную степень.
2. Все компоненты связности , кроме, может быть , одной, не содержат ребер.
|proof=
