Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Доказательство. В графе и – единственные нечетные вершины в графе .






В графе и – единственные нечетные вершины в графе .

Покажем, что существует Эйлеров путь. Возможны 2 случая.

1) Вершины и соединены ребром.



Получили новый граф, путем зачеркивания единственного ребра, степени всех вершин – четные.

а)Граф не распался на 2 компоненты связности.

По предыдущей теореме, существует Эйлеров путь, добавляя назад ребра, получим: .

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

– в одной компоненте связности.

– в другой компоненте связности.

Тогда получаем:

2) Вершины и не соединены ребром.

Добавляем ребро, степени вершин – четные, значит, существует циклический Эйлеров путь. ()

Удаляем ребро, получаем: .

Получили Эйлеров путь.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.