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