![]() Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Доказательство. Пусть связной граф является Эйлеровым, тогда существует циклический Эйлеров путь
Необходимость. Пусть связной граф Достаточность. Пусть степени всех вершин – четные. Докажем, что существует циклический Эйлеров путь. Выберем любую вершину 1 случай: все ребра окрашены. 2 случай: есть хотя-бы одно неокрашенное ребро. Поскольку граф связный, то найдется ребро, один конец которого принадлежит окрашенному ребру. Пусть у
Если остались еще неокрашенные ребра, то продолжаем процедуру. Получаем Эйлеров путь.
|