Инструменты пользователя

Инструменты сайта


examination:diskretka:question16

Вопрос №16. Эйлерова цепь и условия ее существования.

Цепь Эйлерова, если она включает все ребра данного неорграфа.

Для удобства - эйлеров цикл не Эйлерова цепь. У эйлеровой цепи начало и конец не совпадают.

Теорема: условие существования эйлеровой цепи

Чтобы в конечном неорграфе Г существовала Эйлерова цепь, необходимо и достаточно, чтобы граф Г был связен и ровно 2 его вершины имели бы нечетные локальные степени. При этом эти 2 вершины обязательно оказываются началом и концом эйлеровой цепи.

Доказательство: Приклеим к графу еще 1 ребро, соединяющее выделенные 2 вершины, те самые, степени которых нечетны. Новый граф окажется эйлеровым, значит, вне есть эйлеров цикл. Тот цикл пройдет и по новому ребру. Убираем ребро, и эйлеров цикл превращается вэйлерову цепь.

examination/diskretka/question16.txt · Последние изменения: 2014/01/15 08:14 (внешнее изменение)