Эйлеровы циклы и цепи
Алгоритм выделения эйлерова цикла в связном мультиграфе с четными степенями вершин. Гамильтоновы циклы и цепи. Остовное дерево с минимальной суммой длин содержащихся в нем ребер. Висячая вершина с инцидентным ей ребром. Изучение свойств деревьев.
| Рубрика | Математика |
| Вид | лекция |
| Язык | русский |
| Дата добавления | 18.10.2013 |
| Размер файла | 28,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Лекция
Эйлеровы циклы и цепи
Нужно пройти по всем мостам по одному разу и вернуться обратно.
Утв. Если в псевдографе G имеется хотя бы одно ребро и отсутствуют висячие вершины, то G содержит хотя бы один простой цикл.
Доказательство ||
Если в G имеется петля, то это уже цикл, если в G есть кратные ребра, то это тоже цикл. Допустим, что петель и кратных ребер нет.
Пусть v1 и v2 - произвольные смежные вершины. Будем строить последовательность v1, v2, v3… такую, что для любого i>2 вершины vi, vi-1 смежны и vivi-1 (т.к. в G нет висячих вершин, то эту последовательность можно продолжать неограниченно). Но рано или поздно какая-то из вершин повторится. Это и будет искомый цикл.
Утв. Для того чтобы связный псевдограф G обладал эйлеровым циклом необходимо и достаточно чтобы степени всех его вершин были четными.
См. алгоритм.
Утв. Для того чтобы связный псевдограф G обладал эйлеровой цепью необходимо и достаточно, чтобы он имел ровно 2 вершины нечетной степени.
(Нужно соединить начало и конец. Тогда задача сводится к предыдущей).
Алгоритм выделения эйлерова цикла в связном мультиграфе с четными степенями вершин
1) Выделим из G цикл 1. (т.к. степени верш. четны, то висячие верш. отсутств.). Положим l=1, G'=G.
2) Удаляем из G' ребра, принадлежащие выделенному циклу. Полученный псевдограф снова обозначаем G'. Если в G' отсутствуют ребра, то переходим к шагу 4.
3) Выделяем из G' цикл. Присваиваем l:=l+1 и переходим к шагу 2.
4) По построению выделенные циклы содержат все ребра по одному разу. Если l:=1, то искомый эйлеров цикл найден (конец работы алгоритма). В противном случае находим циклы, содержащие хотя бы по одной общей вершине (в силу связности графа это всегда можно сделать). Склеиваем эти циклы. Повторяем эти операции, пока не останется один цикл. Он и является искомым.
Пример. Задача о Кенигсбергских мостах не имеет решения, т.к. есть вершины с нечетными степенями.
Гамильтоновы циклы и цепи
Опр || Пусть G псевдограф. Цепь и цикл в G называются гамильтоновыми если они проходят через каждую вершину ровно один раз.
Задача коммивояжера: в нагруженном графе G определить гамильтонов цикл минимальной длины.
Решение этой задачи проводится с помощью метода ветвей и границ.
Гамильтоновы цепи и циклы относятся к числу специальных маршрутов в графах. Очевидно, что свойство маршрутов: проходить через каждую вершину не более одного раза является латинским, а следовательно, все гамильтоновы циклы и цепи можно получить применяя метод латинской композиции.
В этом случае все гамильтоновы цепи будут перечислены в непустых элементах матрицы Ln-1(G), за исключением элементов главной диагонали, а все гамильтоновы циклы - в каждом диагональном элементе матрицы Ln(G).
Деревья и циклы
Опр. Граф G называется деревом, если он является связным и не имеет циклов.
Опр. Граф G называется лесом, если все его компоненты связности - деревья.
Свойства деревьев:
Следующие утверждения эквивалентны
1) Граф G есть дерево.
2) Граф G является связным и не имеет простых циклов.
3) Граф G является связным и число его ребер ровно на 1 меньше числа вершин.
4) две различные вершины графа G можно соединить единственной (и при этом простой) цепью.
5) Граф G не содержит циклов, но, добавляя к нему любое новое ребро, получаем ровно один и притом простой цикл
Утв. Если у дерева G имеется, по крайней мере, 1 ребро, то у него найдется висячая вершина.
Предположим, что в графе G нет висячей вершины, тогда найдется цикл (в начале лекции это было доказано), тогда граф - не дерево.
Утв. Пусть G связный граф, а висячая вершина в G, граф получается из G в результате удаления вершины и инцидентного ей ребра. Тогда тоже является связным.
Д-во: иллюстрация.
Утв. Пусть G - дерево с n-вершинами и m-ребрами. Тогда m(G)=n(G)-1.
Если m<n-1 то граф не связный.
Если m>n-1, и висячих вершин в графе нет, то можно выделить цикл, а следовательно, это - не дерево. В противном случае удалим висячую вершину вместе с инцидентным ей ребром. Повторяя эту операцию n-2 раза, придем к графу с двумя вершинами и более чем одним ребром это не дерево.
Утв. Пусть G - дерево. Тогда любая цепь в G будет простой.
Если цепь - не простая, то в G есть циклы G - не дерево.
Цепь единственна по той же причине.
Опр. Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.
Пусть G - связный граф. Тогда остовное дерево графа G должно содержать n(G)-1 ребер. Значит, для получения остовного дерева из графа G нужно удалить ребер. Число называется цикломатическим числом графа G.
Алгоритм выделения остовного дерева
1) Выберем в G произвольную вершину , которая образует подграф, являющийся деревом. Положим i=1.
2) Если i=n(G), то задача решена и Gi - искомое остовное дерево графа G. Иначе переходим к п. 3.
3) Пусть уже построено дерево являющееся подграфом графа G, в которое входят вершины , где . Строим граф , добавляя к графу Gi новую вершину , смежную с некоторой вершиной графа и новое ребро . Во-первых, это можно всегда сделать, поскольку граф связен. Во-вторых, - дерево, т.к. если в не было циклов, то и в их не могло появиться.
Присваиваем i:=i+1 и переходим к шагу 2).
Замечание. Остовное дерево может быть выделено, вообще говоря, не единственным способом.
Если граф - нагруженный, то можно выделить остовное дерево с минимальной суммой длин содержащихся в нем ребер.
Алгоритм выделения минимального остовного дерева нагруженного графа
1) Выберем в графе G ребро минимальной длины. Вместе с инцидентными ему двумя вершинами оно образует подграф G2 графа G. Положим i=2.
2) Если i=n(G), то задача решена и Gi - искомое минимальное ост. дерево графа G. Иначе переходим к шагу 3).
3) Строим граф Gi+1, добавляя к графу Gi новое ребро минимальной длины из оставшихся, которое инцидентно какой-нибудь верш. графа Gi и одновременно вершине, не содержащейся в Gi. Вместе с этим ребром включаем в Gi+1 и эту инцидентную ему верш. Присваиваем i:=i+1 и переходим к шагу 2).
эйлеров цикл инцидентный остовной
Размещено на Allbest.ru
...Подобные документы
Эйлеровы цепи и циклы, теоремы. Алгоритм построения эйлерова цикла. Обоснование алгоритма. Нахождение кратчайших путей в графе. Алгоритм Форда отыскания кратчайшего пути. Задача отыскания кратчайших расстояний между всеми парами вершин. Алгоритм Флойда.
реферат [108,4 K], добавлен 01.12.2008Общее понятие теоремы Эйлера, этапы ее доказательства. Необходимые и достаточные условия существования эйлерова цикла. Сущность задачи о построении каркаса куба. Алгоритм Флери построения эйлерова цикла. Обход полуэйлерова графа с нечетной вершины.
презентация [27,1 K], добавлен 12.04.2014Понятия теории графов, их связность и задача о кратчайшей цепи. Программная реализация метода Дейкстры, его сравнение с методом простого перебора. Описание логики программного модуля. Примеры работы программы нахождения кратчайшей цепи в связном графе.
курсовая работа [330,2 K], добавлен 25.11.2011Основные понятия теории графов. Степень вершины. Маршруты, цепи, циклы. Связность и свойства ориентированных и плоских графов, алгоритм их распознавания, изоморфизм. Операции над ними. Обзор способов задания графов. Эйлеровый и гамильтоновый циклы.
презентация [430,0 K], добавлен 19.11.2013Основные понятия теории графов. Маршруты и связность. Задача о кёнигсбергских мостах. Эйлеровы графы. Оценка числа эйлеровых графов. Алгоритм построения эйлеровой цепи в данном эйлеровом графе. Практическое применение теории графов в науке.
курсовая работа [1006,8 K], добавлен 23.12.2007Минимальное остовное дерево связного взвешенного графа и его нахождение с помощью алгоритмов. Описание алгоритма Краскала, возможность строить дерево одновременно для нескольких компонент связности. Пример работы алгоритма Краскала, код программы.
курсовая работа [192,5 K], добавлен 27.03.2011Остовное дерево связного неориентированного графа. Алгоритм создания остовного дерева, его нахождение. Сущность и главные особенности алгоритма Крускала. Порядок построения алгоритма Прима, вершина наименьшего веса. Промежуточная структура данных.
презентация [140,8 K], добавлен 16.09.2013Основные понятия, связанные с графом. Решение задачи Эйлера о семи кёнигсбергских мостах. Необходимые и достаточные условия для эйлеровых и полуэйлеровых графов. Применение теории графов к решению задач по математике; степени вершин и подсчёт рёбер.
курсовая работа [713,8 K], добавлен 16.05.2016Алгоритм перехода к графическому представлению для неориентированного графа. Количество вершин неориентированного графа. Чтение из матрицы смежностей. Связи между вершинами в матрице. Задание координат вершин в зависимости от количества секторов.
лабораторная работа [34,0 K], добавлен 29.04.2011Теория динамического программирования. Понятие об оптимальной подструктуре. Независимое и полностью зависимое множество вершин. Задача о поиске максимального независимого множества в дереве. Алгоритм Брона-Кербоша как метод ветвей, границ для поиска клик.
реферат [224,1 K], добавлен 09.10.2012Понятие и матричное представление графов. Ориентированные и неориентированные графы. Опеределение матрицы смежности. Маршруты, цепи, циклы и их свойства. Метрические характеристики графа. Применение теории графов в различных областях науки и техники.
курсовая работа [423,7 K], добавлен 21.02.2009Изучение основных вопросов теории графов и области ее применения на практике. Разработка алгоритма кластеризации по предельному расстоянию и построение минимального остовного дерева каждого кластера. Результаты тестирований работы данного алгоритма.
курсовая работа [362,9 K], добавлен 24.11.2010Понятие "граф". Отношения между разнородными элементами. Матричное представление графов. Операции над графами. Маршруты, цепи, циклы. Метрические характеристики графа. Приложение теории графов в различных областях науки и техники. Листинг программы.
курсовая работа [725,8 K], добавлен 15.12.2008Основные понятия теории графов. Содержание метода Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Программная реализация исследуемого алгоритма. Построение матриц смежности и инцидентности.
курсовая работа [228,5 K], добавлен 30.01.2012Цепь Маркова как простой случай последовательности случайных событий, области ее применения. Теорема о предельных вероятностях в цепи Маркова, формула равенства Маркова. Примеры для типичной и однородной цепи Маркова, для нахождения матрицы перехода.
курсовая работа [126,8 K], добавлен 20.04.2011Дифференциальные уравнения при входном воздействии типа скачка для заданной электрической цепи. Применение преобразования Лапласа при нулевых начальных условиях. Решение уравнения операторным методом. Построение частотных характеристик цепи. Ее динамика.
курсовая работа [721,0 K], добавлен 27.05.2008Основные понятия теории графов. Расстояния в графах, диаметр, радиус и центр. Применение графов в практической деятельности человека. Определение кратчайших маршрутов. Эйлеровы и гамильтоновы графы. Элементы теории графов на факультативных занятиях.
дипломная работа [145,5 K], добавлен 19.07.2011Определение многогранника, его сторон и вершин, отрезков, соединяющих вершины. Описание основания, боковых граней и высоты призмы. Правильная и усеченная пирамида. Теорема Эйлера. Анализ особенностей и геометрических свойств правильных многогранников.
презентация [6,5 M], добавлен 27.10.2013Анализ цепи с применением методов переменных состояния, операторного и частотного при апериодическом и периодическом воздействии. Определение амплитудного и фазового спектров входного сигнала. Получение тока на выходе цепи в виде отрезка ряда Фурье.
курсовая работа [1,9 M], добавлен 11.01.2012Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014
