Алгоритмы решения некоторых теоретико-графовых задач
Изучение понятия и разновидностей графов. Явление изоморфизма и гомеоморфизма. Пути и циклы. Дерево или произвольно-связный граф без циклов. Цикломатическое число и фундаментальные циклы. Независимые множества и покрытия. Алгоритм Дейкстры, Краскала.
| Рубрика | Математика |
| Вид | шпаргалка |
| Язык | русский |
| Дата добавления | 08.09.2013 |
| Размер файла | 137,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
2. k=0;
3. если |E(SST')|=n-1, то SST=SST'; КОНЕЦ;
4. k=k+1;
5. e=<k-ое по возрастанию весов ребро графа G>;
6. если добавление e в SST' не приводит к появлению цикла, то добавить его в SST';
7. перейти на шаг 3.
Доказательство корректности алгоритма Краскала
A.
Алгоритм Краскала (АК) завершает работу за конечное число шагов и строит остовное дерево графа, т.к. он является частным случаем следующего алгоритма построения остовного дерева графа (без весов).
Алгоритм построения остовного дерева графа (алгоритм ST)
Вход: связный граф
G=(V,E), n=|V|, m=|E|.
Выход: ST - остовное дерево графа G.
1. Занумеровать произвольным образом ребра графа G;
2. ST'=<пустой граф с n вершинами>;
3. k=0;
4. если |E(ST')|=n-1, то ST=ST'; КОНЕЦ;
5. k=k+1;
6. e=<k-ое ребро графа G>;
7. если добавление e в ST' не приводит к появлению цикла, то добавить его в ST';
8. перейти на шаг 4.
Доказательство корректности алгоритма ST
A.
Докажем, что алгоритм ST завершает работу не более чем за m шагов, т.е. на шаге 4 при некотором k_m выполняется равенство |E(ST')|=n-1. Допустим обратное: |E(ST')|<n-1 при k=m (*). После выполнения шага 2 алгоритма |V(ST')|=n, следовательно, граф ST' не является связным (по следствию 1 леммы 3). Рассмотрим два произвольных связных компонента графа ST': графы T' и T''. В G не может существовать ни одного ребра, один из концов которого лежал бы в T', а другой в T'' (**) - в противном случае такое ребро было бы добавлено в ST' при некотором k_m на шаге 7 алгоритма, т.к. это ребро заведомо не привело бы к появлению цикла. Но из (**) следует, что G несвязен - получили противоречие с (*).
B. Получаемый подграф ST является деревом по теореме 3 п.3 и является остовным деревом по определению, т.к. в него входят все вершины графа G.
АК является вариантом алгоритма ST, в котором ребра занумерованы по возрастанию весов.
B. Докажем индукцией по числу ребер, что получаемое в результате работы АК остовное дерево является кратчайшим.
Базис индукции: при m=1 остовное дерево единственно, поэтому дерево, которое строит АК, является кратчайшим.
Допустим, что АК строит SST для всех графов G=(V,E), таких, что |E(G)|_m. Докажем, что АК строит SST для графа G'=(V',E'): |E(G')|=m+1. Рассмотрим ребро e'ОE(G'), вес которого максимален. Возможны два варианта:
1. e' - кольцевое;
2. e' - ациклическое.
Рассмотрим первый случай (e' - кольцевое). Удалим e' из G'; получим связный граф G''=(V',E'\e'). В силу предположения индукции АК строит его SST. Вернемся к графу G': в силу максимальности веса e' АК "обработает" e' в последнюю очередь, поэтому при k=m граф SST'k(G') совпадает с SST(G''). При k=m+1 ребро e' не будет добавлено к SST'(G'), т.к. это привело бы к возникновению цикла, следовательно, SST(G') совпадает с SST(G''). Остается доказать, что при добавлении в связный граф ребра, вес которого не меньше, чем вес любого другого его ребра, длина кратчайшего остовного дерева графа не уменьшается. Но это верно в силу Леммы 1 (см. ниже). Таким образом, длина кратчайшего остовного дерева G' не меньше длины кратчайшего остовного дерева G''. Это минимальное значение достигается на SST(G'), следовательно, SST(G') является кратчайшим остовным деревом графа G'.
Лемма 1. Пусть G=G(V,E) - связный взвешенный граф; G'=(V,E+e'), Weight(e')_Weight(e), "eОE(G) (*). Тогда существует кратчайшее остовное дерево графа G' , в которое не входит ребро e' (если Weight(e')>Weight(e), "eОE(G) (**), то e' не входит ни в какое кратчайшее остовное дерево G').
Доказательство: допустим, e' входит в кратчайшее остовное дерево T=SST(G') графа G'. Удалим из T ребро e': T распадется на два дерева T1 и T2. Найдем в графе G ребро e''ОE(G), один из концов которого лежит в T1, а второй - в T2: e''=(v,u), vОT1, uОT2 (такое ребро существует, т.к. в противном случае G не был бы связным). Соединим деревья T1 и T2 ребром e'': получим дерево T', которое является остовным деревом графа G', причем в силу (*) Weight(T') = Weight(T1) + Weight(T2) + Weight(e'')--_ Weight(T1) + Weight(T2) + Weight(e') = Weight(T) - построили остовное дерево не большего суммарного веса (длины), в которое не входит ребро e'; в случае (**), очевидно, Weight(T') < Weight(T).
Рассмотрим второй случай (e' - ациклическое). Удалим e' из G'; получим граф G''=(V',E'\e'), состоящий из двух связных компонент G''1 и G''2, количество ребер в каждой из которых не превосходит m. В силу предположения индукции АК построит их SST. Как и в первом случае, при k=m граф SST'k(G') совпадает с SST(G''). При k=m+1 ребро e' будет добавлено в G' на шаге 7 АК, поэтому Weight(SST'm+1(G')) = Weight(SST(G''1)) + Weight(SST(G''2)) + Weight(e'). Но это минимальное возможное значение веса кратчайшего остовного дерева G', следовательно, АК построил кратчайшее остовное дерево G'.
Алгоритм Прима
Определим расстояние между произвольной вершиной v взвешенного графа G=(V,E) и некоторым его подграфом G'НG как минимальный вес ребра, одним из концов которого является v, а другой лежит в G': d(v,G')=min(v,w)ОE(G),wОG'Weight(v,w).
1. SST'=<граф, состоящий из одной произвольной вершины графа G>;
2. если |E(SST')|=n-1, то SST=SST'; КОНЕЦ;
3. среди множества I вершин графа G, не входящих в SST', но инцидентных хотя бы одной вершине из SST' (I={u | uОV(G), uПSST', (u,v)ОE(G), vОSST'}), найти вершину wОI, расстояние которой до SST' минимально: d(w,SST')=minvОId(v,SST');
4. добавить ребро (w,u), на котором достигается минимальное расстояние d(w,SST'), в SST';
5. перейти на шаг 2.
(без доказательства - можно доказать по аналогии с АК)
Размещено на Allbest.ru
...Подобные документы
Основные понятия теории графов. Степень вершины. Маршруты, цепи, циклы. Связность и свойства ориентированных и плоских графов, алгоритм их распознавания, изоморфизм. Операции над ними. Обзор способов задания графов. Эйлеровый и гамильтоновый циклы.
презентация [430,0 K], добавлен 19.11.2013Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры.
контрольная работа [466,3 K], добавлен 11.03.2011Граф как совокупность объектов со связями между ними. Характеристики ориентированного и смешанного графов. Алгоритм поиска кратчайшего пути между вершинами, алгоритм дейкстры. Алгебраическое построение матрицы смежности, фундаментальных резервов и циклов.
методичка [29,4 M], добавлен 07.06.2009Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".
курсовая работа [2,4 M], добавлен 08.10.2014Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014Вид графов, используемых в теории электрических цепей, химии, вычислительной технике и в информатике. Основные свойства деревьев. Неориентированный граф. Алгоритм построения минимального каркаса. Обоснование алгоритма. Граф с нагруженными ребрами.
реферат [131,8 K], добавлен 11.11.2008Рассмотрение понятия и видов графов как совокупности непустого конечного множества элементов; условия их связанности. Доказательства существования замкнутых Эйлеровой, Гамильнотовой и бесконечной цепей. Ознакомление с элементарными свойствами деревьев.
курсовая работа [1,4 M], добавлен 10.02.2012Понятия теории графов, их связность и задача о кратчайшей цепи. Программная реализация метода Дейкстры, его сравнение с методом простого перебора. Описание логики программного модуля. Примеры работы программы нахождения кратчайшей цепи в связном графе.
курсовая работа [330,2 K], добавлен 25.11.2011Минимальное остовное дерево связного взвешенного графа и его нахождение с помощью алгоритмов. Описание алгоритма Краскала, возможность строить дерево одновременно для нескольких компонент связности. Пример работы алгоритма Краскала, код программы.
курсовая работа [192,5 K], добавлен 27.03.2011Основные понятия теории графов. Содержание метода Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Программная реализация исследуемого алгоритма. Построение матриц смежности и инцидентности.
курсовая работа [228,5 K], добавлен 30.01.2012Граф как множество вершин (узлов), соединённых рёбрами, способы и сфера их применения. Специфика теории графов как раздела дискретной математики. Основные способы преобразования графов, их особенности и использование для решения математических задач.
курсовая работа [1,8 M], добавлен 18.01.2013Основные понятия теории графов. Матричные способы задания графов. Выбор алгоритма Форда–Бэллмана для решения задачи поиска минимальных путей (маршрутов) в любую достижимую вершину нагруженного орграфа. Способы выделения пути с наименьшим числом дуг.
курсовая работа [109,1 K], добавлен 22.01.2016Понятие "граф". Отношения между разнородными элементами. Матричное представление графов. Операции над графами. Маршруты, цепи, циклы. Метрические характеристики графа. Приложение теории графов в различных областях науки и техники. Листинг программы.
курсовая работа [725,8 K], добавлен 15.12.2008Понятие и матричное представление графов. Ориентированные и неориентированные графы. Опеределение матрицы смежности. Маршруты, цепи, циклы и их свойства. Метрические характеристики графа. Применение теории графов в различных областях науки и техники.
курсовая работа [423,7 K], добавлен 21.02.2009Понятие и содержание теории графов. Правила построения сетевых графиков и требования к ним. Сетевое планирование в условиях неопределенности. Теория принятия решений, используемые алгоритмы и основные принципы. Пример применения алгоритма Дейкстры.
курсовая работа [1,0 M], добавлен 26.09.2013Нахождение минимального пути от фиксированной до произвольной вершины графа с помощью алгоритма Дейкстры, рассмотрение основных принципов его работы. Описание блок-схемы алгоритма решения задачи. Проверка правильности работы разработанной программы.
курсовая работа [495,4 K], добавлен 19.09.2011Постановка задачи коммивояжера и основные алгоритмы решения. Маршруты и пути. Понятия транспортной сети. Понятие увеличивающая дуга, цепь, разрез. Алгоритм Флойда-Уоршелл. Решение задачи аналитическим методом. Создание приложения для решения задачи.
курсовая работа [541,3 K], добавлен 08.10.2015Понятие и внутренняя структура графа, его применение и матричное представление (матрица инциденций, разрезов, цикломатическая, Кирхгофа). Специальные свойства и признаки графов, решение оптимизационных задач. Венгерский алгоритм, матричная интерпретация.
курсовая работа [664,6 K], добавлен 24.12.2013Составление таблицы значений функции алгебры логики и нахождение всех существенных переменных. Связный ориентированный и взвешенный граф. Построение функции полиномом Жегалкина. Текст программы для алгоритма Дейкстры. Определение единиц и нулей функции.
контрольная работа [43,2 K], добавлен 27.04.2011История возникновения, основные понятия графа и их пояснение на примере. Графический или геометрический способ задания графов, понятие смежности и инцидентности. Элементы графа: висячая и изолированная вершины. Применение графов в повседневной жизни.
курсовая работа [636,2 K], добавлен 20.12.2015
