![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Эйлеровы циклы и цепиСтр 1 из 3Следующая ⇒
Началом математической теории графов послужила задача о Кёнигсбергских мостах, поставленная Леонардом Эйлером (1707 – 1783). Кёнигсберг (теперь Калининград) расположен на обоих берегах реки Преголя и на двух островах этой реки. Берега реки и два острова соединены семью мостами, как показано на рис.1. Эйлер в 1736 г. поставил вопрос: можно ли, начав с некоторой точки, совершить прогулку и вернуться в исходную точку, пройдя по каждому мосту ровно один раз. Если каждый берег и острова считать вершинами графа, а каждый мост – ребром, то карту города можно представить в виде мультиграфа (рис. 1). B с d g g
C a b h a b h
а б Рис. 1. Карта города (а) и эквивалентный ей граф (б)
Эйлеровым циклом (цепью) в мультиграфе Эйлер установил, что задача кёнигсбергских мостов неразрешима, и этот результат ознаменовал возникновение теории графов. Теорема.Мультиграф обладает эйлеровым циклом тогда и только тогда, когда он связный и все его локальные степени четны. Доказательство. Необходимость. Пусть мультиграф Достаточность докажем индукцией по числу ребер Следствия. 1°. Связный мультиграф, имеющий ровно две вершины с нечетной степенью, является полуэйлеровым графом. Действительно, добавим к мультиграфу ребро, соединяющее вершины с нечетной степенью. В результате степени всех вершин станут четными. Построим в новом графе эйлеров цикл, а затем удалим добавленное ребро: цикл разорвется и станет цепью. Эта цепь будет начинаться и заканчиваться в вершинах нечетной степени. 2°. В общем случае число вершин мультиграфа, имеющих нечетную степень, всегда четно. Если мультиграф имеет Обоснование этого утверждения аналогично предыдущему. Ребро графа
Рис. 2. Пример разбиения ребер графа на цикловые и перешейки
Справедливо следующее очевидное утверждение: при удалении из связного графа циклового ребра он остается связным; при удалении из связного графа перешейка граф распадается на две компоненты. Из этого утверждения следует, что при удалении из связного графа циклового ребра число связных компонент не изменяется. При удалении перешейка число связных компонент увеличивается на единицу.
|