Автор работы: Пользователь скрыл имя, 11 Ноября 2013 в 21:36, контрольная работа
Граф представляет собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек. Обозначать граф будем буквой Г. При изображении графов на рисунках или схемах отрезки могут быть прямолинейными или криволинейными; длины отрезков и расположение точек произвольны. Все три фигуры на рисунке 1.9 изображают один и тот же граф. Точки иначе называют вершинами, отрезки – ребрами графа. Вершины графа на рисунке выделяют обычно кружками или квадратиками хотя бы потому, что не всегда точки пересечения ребер принимаются за вершины графа.
Если снова найдутся ребра, которые не вошли в путь, то найдем новые циклы. Число ребе и вершин конечно, процесс закончится.
Итак, приведен алгоритм, позволяющий отыскать эйлеров цикл, и показано, что он применим во всех случаях, допускаемых условиями теоремы.
Таким образом, замкнутую фигуру, в которой все вершины четные, можно начертить одним росчерком без повторений, начиная обводить ее с любой точки.
Если граф не обладает эйлеровым циклом, то можно поставить задачу об отыскании одного эйлерова пути или нескольких эйлеровых путей, содержащих все ребра графа.
Теорема: Если граф Г обладает эйлеровым путем с концами А и В (А не совпадает с В), то граф Г связный и А и В – единственные нечетные его вершины.
Доказательство: Связность графа следует из определения эйлерова пути. Если путь начинается в А, а заканчивается в другой вершине В, то А и В – нечетные, даже если путь неоднократно проходил через А и В. В любую другую вершину графа путь должен был привезти и вывести из нее, то есть все остальные вершины должны быть четными.
Верно и обратное.
Теорема: Если граф Г связный и А и В единственные и нечетные вершины его, то граф Г обладает эйлеровым путем с концами А и В.
Доказательство: Вершины А и В могут быть соединены ребром в графе (рис. 2.27), а могут быть и не соединены (рис. 2.28).
Если А и В соединены ребром, то удалим его; тогда все вершины станут четными. Новый граф, согласно предыдущей теореме, обладает эйлеровым циклом, началом и концом которого может служить любая вершина. Найдем эйлеров путь в вершине А и кончим его в вершине А. Добавим ребро (А, В) и получим эйлеров путь с началом в А и концом в В.
Если А и В не соединены ребром, то к графу добавим новое ребро (А, В), тогда все вершины его станут четными. Новый граф, согласно предыдущей теореме, обладает эйлеровым циклом. Начнем его из вершины А по ребру (А, В). Закончится путь тоже в вершине А. Если удалить теперь из полученного цикла ребро (А, В), то останется эйлеров путь с началом в В и концом в А или с началом в А и концом в В.
Таким образом, всякую замкнутую
фигуру, имеющую в точности две
нечетные вершины, можно начертить
одним росчерком без
Теорема: Если связный граф имеет 2k нечетных вершин, то найдется семейство из k путей, которые в совокупности содержат все ребра графа в точности по одному разу.
Доказательство: Половину нечетных вершин обозначим А1, А2, …, Аk, другую – В1, В2, …, Вk (рис 2.29). Если вершины Аl и Вl (1 ≤ l ≤ k) соединены ребром, то удалим из графа Г ребро (Аl, Вl). Если вершины Аl и Вl не соединены ребром, то добавим к Г ребро (Аl, Вl). Все вершины нового графа будут четными, то есть в новой графе найдется эйлеров цикл. При восстановлении графа Г цикл разобьется на k отдельных путей, содержащих все ребра графа.
Эйлеровым графом может быть план выставки; это позволяет так расставить указатели маршрута, что бы посетитель смог пройти по каждому залу в точности по одному разу.
Теорема: Если граф Г связный, то можно построить цикличный маршрут, содержащий все ребра графа в точности два раза, по одному в каждом направлении.
Доказательство: Дадим точное правило построения такого пути, предложенное Тарри.
Из произвольной вершины А пройдем вдоль какого-нибудь ребра (А, В), отметив его стрелкой, указывающей направление пути (рис. 2.37). Из В пройдем к третьей вершине, снова отметив стрелкой направление прибытия и так далее. Ребро, по которому впервые прибываем в вершину, будем отмечать стрелкой. Выходя из вершины, выбирают дальнейший путь: либо ребро, еще не проходили ни разу, либо ребро, по которому прибыли в эту вершину. Договариваемся, что ребро, по которому впервые попали в вершину, будем использовать для выхода только тогда, когда оно остается единственным выходом из этой вершины.
Продолжаем строить путь, пока это возможно. Заметим, что в каждой вершине имеется одинаковое число возможностей для входа и выхода. Процесс может закончиться только в исходной вершине А.
На рисунке 2.37 дан связный граф Г, на котором по правилу Тарри построен искомый цикл; для удобства стрелки пронумерованы.
Итак, процесс закончился в А. Теперь необходимо доказать, что в обоих направлениях пройдены все ребра. Выхода из А более нет, так как иначе процесс бы не закончился и мы могли бы двигаться дальше. Все входы в вершину А тоже использованы, так как иначе процесс бы не закончился и мы могли бы двигаться дальше. Все входы в вершину А тоже использованы, так как их число равно числу путей, по которому мы выходили из А. В частности, ребро (А, В) пройдено в обоих направлениях. Следовательно, все ребра, которые которым принадлежит В, тоже пройдены в обоих направлениях, так как первое входящее в В ребро (А, В) по условию могло быть использовано в качестве входящего лишь в последнюю очередь.
То же рассуждение применимо к третьему в пути ребру (С, D) и следующей вершины С и т. д. Поскольку граф связный и имеет конечное число вершин и ребер, аналогично можно исследовать все его вершины и все его ребра.
Гамильтонов цикл