Теория графов
Основные понятия теории графов. Алгоритм построения эйлерового пути. Теория графов как область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Задача коммивояжера как одна из задач теории комбинаторики.
Рубрика | Математика |
Вид | реферат |
Язык | русский |
Дата добавления | 18.03.2010 |
Размер файла | 647,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Теперь приступим к ветвлению. Для этого проделаем шаг оценки нулей. Рассмотрим нуль в клетке (1,2) приведенной матрицы. Он означает, что цена перехода из города 1 в город 2 равна 0. А если мы не пойдем из города 1 в город 2? Тогда все равно нужно въехать в город 2 за цены, указанные во втором столбце; дешевле всего за 1 (из города 6). Далее, все равно надо будет выехать из города 1 за цену, указанную в первой строке; дешевле всего в город 3 за 0. Суммируя эти два минимума, имеем 1+0=1: если не ехать “по нулю” из города 1 в город 2, то надо заплатить не меньше 1. Это и есть оценка нуля. Оценки всех нулей поставлены на табл. 5 правее и выше нуля (оценки нуля, равные нулю, не ставились).
Выберем максимальную из этих оценок (в примере есть несколько оценок, равных единице, выберем первую из них, в клетке (1,2)).
Итак, выбрано нулевое ребро (1,2). Разобьем все туры на два класса - включающие ребро (1,2) и не включающие ребро (1,2). Про второй класс можно сказать, что придется приплатить еще 1, так что туры этого класса стоят 35 или больше.
Что касается первого класса, то в нем надо рассмотреть матрицу на табл. 6 с вычеркнутой первой строкой и вторым столбцом.
1 |
2 |
3 |
4 |
5 |
6 |
||
1 |
- |
01 |
0 |
3 |
3 |
6 |
|
2 |
01 |
- |
1 |
4 |
1 |
0 |
|
3 |
1 |
2 |
- |
01 |
0 |
3 |
|
4 |
4 |
5 |
01 |
- |
1 |
3 |
|
5 |
4 |
2 |
0 |
1 |
- |
0 |
|
6 |
7 |
1 |
3 |
3 |
01 |
- |
|
табл. 5 |
|||||||
1 |
3 |
4 |
5 |
6 |
|||
2 |
01 |
1 |
4 |
1 |
0 |
||
3 |
1 |
- |
01 |
0 |
3 |
||
4 |
4 |
01 |
- |
1 |
3 |
||
5 |
4 |
0 |
1 |
- |
0 |
||
6 |
7 |
3 |
3 |
01 |
- |
||
табл. 6 |
|||||||
1 |
3 |
4 |
5 |
6 |
|||
2 |
01 |
1 |
4 |
1 |
0 |
||
3 |
03 |
- |
01 |
0 |
3 |
||
4 |
3 |
01 |
- |
1 |
3 |
||
5 |
3 |
0 |
1 |
- |
0 |
||
6 |
6 |
3 |
3 |
01 |
- |
||
табл. 7 |
|||||||
3 |
4 |
5 |
6 |
||||
2 |
1 |
4 |
1 |
0 |
|||
4 |
01 |
- |
1 |
3 |
|||
5 |
0 |
1 |
- |
0 |
|||
6 |
3 |
3 |
01 |
- |
|||
табл. 8 |
Дополнительно в уменьшенной матрице поставлен запрет в клетке (2,1), т. к. выбрано ребро (1,2) и замыкать преждевременно тур ребром (2,1) нельзя. Уменьшенную матрицу можно привести на 1 по первому столбцу, так что каждый тур, ей отвечающий, стоит не меньше 35. Результат наших ветвлений и получения оценок показан на рис.6.
Кружки представляют классы: верхний кружок - класс всех туров; нижний левый - класс всех туров, включающих ребро (1,2); нижний правый - класс всех туров, не включающих ребро (1,2). Числа над кружками - оценки снизу.
3 |
4 |
6 |
||
2 |
1 |
3 |
03 |
|
4 |
03 |
- |
3 |
|
5 |
0 |
03 |
0 |
|
табл. 10 |
Продолжим ветвление в положительную сторону: влево - вниз. Для этого оценим нули в уменьшенной матрице C[1,2] на табл. 7. Максимальная оценка в клетке (3,1) равна 3. Таким образом, оценка для правой нижней вершины на рис. 7 есть 35+3=38. Для оценки левой нижней вершины на рис. 7 нужно вычеркнуть из матрицы C[1,2] еще строку 3 и столбец 1, получив матрицу C[(1,2),(3,1)] на табл. 8. В эту матрицу нужно поставить запрет в клетку (2,3), так как уже построен фрагмент тура из ребер (1,2) и (3,1), т.е. [3,1,2], и нужно запретить преждевременное замыкание (2,3). Эта матрица приводится по столбцу на 1 (табл. 9), таким образом, каждый тур соответствующего класса (т.е. тур, содержащий ребра (1,2) и (3,1)) стоит 36 и более.
3 |
4 |
5 |
6 |
||
2 |
1 |
3 |
1 |
0 |
|
4 |
01 |
- |
1 |
3 |
|
5 |
0 |
02 |
- |
0 |
|
6 |
3 |
2 |
03 |
- |
|
табл. 9 |
|||||
3 |
4 |
||||
4 |
0 |
- |
|||
5 |
0 |
0 |
|||
табл. 11 |
Оцениваем теперь нули в приведенной матрице C[(1,2),(3,1)] нуль с максимальной оценкой 3 находится в клетке (6,5). Отрицательный вариант имеет оценку 38+3=41. Для получения оценки положительного варианта убираем строчку 6 и столбец 5, ставим запрет в клетку (5,6), см. табл. 10. Эта матрица неприводима. Следовательно, оценка положительного варианта не увеличивается (рис.8).
Оценивая нули в матрице на табл. 10, получаем ветвление по выбору ребра (2,6), отрицательный вариант получает оценку 36+3=39, а для получения оценки положительного варианта вычеркиваем вторую строку и шестой столбец, получая матрицу на табл. 11.
В матрицу надо добавить запрет в клетку (5,3), ибо уже построен фрагмент тура [3,1,2,6,5] и надо запретить преждевременный возврат (5,3). Теперь, когда осталась матрица 2х2 с запретами по диагонали, достраиваем тур ребрами (4,3) и (5,4). Мы не зря ветвились, по положительным вариантам. Сейчас получен тур: 1>2>6>5>4>3>1 стоимостью в 36. При достижении низа по дереву перебора класс туров сузился до одного тура, а оценка снизу превратилась в точную стоимость.
Итак, все классы, имеющие оценку 36 и выше, лучшего тура не содержат. Поэтому соответствующие вершины вычеркиваются. Вычеркиваются также вершины, оба потомка которой вычеркнуты. Мы колоссально сократили полный перебор. Осталось проверить, не содержит ли лучшего тура класс, соответствующий матрице С[Not(1,2)], т.е. приведенной матрице С с запретом в клетке 1,2, приведенной на 1 по столбцу (что дало оценку 34+1=35). Оценка нулей дает 3 для нуля в клетке (1,3), так что оценка отрицательного варианта 35+3 превосходит стоимость уже полученного тура 36 и отрицательный вариант отсекается.
Для получения оценки положительного варианта исключаем из матрицы первую строку и третий столбец, ставим запрет (3,1) и получаем матрицу. Эта матрица приводится по четвертой строке на 1, оценка класса достигает 36 и кружок зачеркивается. Поскольку у вершины “все” убиты оба потомка, она убивается тоже. Вершин не осталось, перебор окончен. Мы получили тот же минимальный тур, который показан подчеркиванием на табл. 2.
Удовлетворительных теоретических оценок быстродействия алгоритма Литтла и родственных алгоритмов нет, но практика показывает, что на современных ЭВМ они часто позволяют решить ЗК с n = 100. Это огромный прогресс по сравнению с полным перебором. Кроме того, алгоритмы типа ветвей и границ являются, если нет возможности доводить их до конца, эффективными эвристическими процедурами.
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|||
min bk=12 |
a |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
b |
12 |
25 |
0 |
18 |
? |
? |
? |
? |
||
c |
3 |
3 |
0 |
3 |
3 |
3 |
3 |
3 |
||
min bk=18 |
a |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
b |
12 |
25 |
0 |
18 |
? |
38 |
? |
? |
||
c |
3 |
3 |
0 |
3 |
3 |
4 |
3 |
3 |
||
min bk=25 |
a |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
b |
12 |
25 |
0 |
18 |
47 |
38 |
? |
60 |
||
c |
3 |
3 |
0 |
3 |
2 |
4 |
3 |
2 |
||
min bk=38 |
a |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
|
b |
12 |
25 |
0 |
18 |
47 |
38 |
62 |
60 |
||
c |
3 |
3 |
0 |
3 |
2 |
4 |
6 |
2 |
||
min bk=47 |
a |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
|
b |
12 |
25 |
0 |
18 |
47 |
38 |
61 |
60 |
||
c |
3 |
3 |
0 |
3 |
2 |
4 |
5 |
2 |
||
min bk=60 |
a |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
|
b |
12 |
25 |
0 |
18 |
47 |
38 |
61 |
60 |
||
c |
3 |
3 |
0 |
3 |
2 |
4 |
5 |
2 |
Таким образом, для решения ЗК нужно n раз применить алгоритм Дейкстры следующим образом.
Возьмём произвольную пару вершин j,k. Исключим непосредственное ребро C[j,k]. С помощью алгоритма Дейкстры найдём кратчайшее расстояние между городами j..k. Пусть это расстояние включает некоторый город m. Имеем часть тура j,m,k. Теперь для каждой пары соседних городов (в данном примере - для j,m и m,k) удалим соответственное ребро и найдём кратчайшее расстояние. При этом в кратчайшее расстояние не должен входить уже использованный город.
Далее аналогично находим кратчайшее расстояние между парами вершин алгоритмом Дейкстры, до тех пор, пока все вершины не будут задействованы. Соединим последнюю вершину с первой и получим тур. Чаще всего это последнее ребро оказывается очень большим, и тур получается с погрешностью, однако алгоритм Дейкстры можно отнести к приближённым алгоритмам.
III. Выводы
Изучены эвристический, приближенный и точный алгоритмы решения ЗК. Точные алгоритмы решения ЗК - это полный перебор или усовершенствованный перебор. Оба они, особенно первый, не эффективны при большом числе вершин графа.
Проведён анализ наиболее рациональных методов решения ЗК и определены области их эффективного действия: для малого числа вершин можно использовать точный метод лексического перебора; для большого числа вершин рациональнее применять метод ветвей и границ.
Изучены практические применения ЗК и задачи с переналадками, сводимые к ЗК.
Приведены тексты программ, позволяющие решить ЗК различными методами.
Литература
1. О. Оре Графы и их применение. Пер. с англ. под ред. И.М. Яглома. - М., “Мир”, 1965, 174 с.
2. В. П. Сигорский. Математический аппарат инженера. - К., “Техніка”, 1975, 768 с.
3. Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко. Математическое программирование: учебное пособие. 2-е изд. перераб. и доп. - М.; Высшая школа, 1980, 300 с., ил.
4. Е. В. Маркова, А. Н. Лисенков. Комбинаторные планы в задачах многофакторного эксперимента. - М., Наука, 1979, 345 с.
5. Е. П. Липатов. Теория графов и её применения. - М., Знание, 1986, 32 с.
6. В. М. Бондарев, В. И. Рублинецкий, Е. Г. Качко. Основы программирования. - Харьков, Фолио; Ростов на Дону, Феникс, 1998, 368 с.
7. Ф. А. Новиков Дискретная математика для программистов. - Санкт-Петербург, Питер, 2001, 304 с., ил.
Подобные документы
Теория графов как раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Основные понятия теории графов. Матрицы смежности и инцидентности и их практическое применение при анализе решений.
реферат [368,2 K], добавлен 13.06.2011Основные понятия теории графов. Расстояния в графах, диаметр, радиус и центр. Применение графов в практической деятельности человека. Определение кратчайших маршрутов. Эйлеровы и гамильтоновы графы. Элементы теории графов на факультативных занятиях.
дипломная работа [145,5 K], добавлен 19.07.2011История возникновения, основные понятия графа и их пояснение на примере. Графический или геометрический способ задания графов, понятие смежности и инцидентности. Элементы графа: висячая и изолированная вершины. Применение графов в повседневной жизни.
курсовая работа [636,2 K], добавлен 20.12.2015Граф как множество вершин (узлов), соединённых рёбрами, способы и сфера их применения. Специфика теории графов как раздела дискретной математики. Основные способы преобразования графов, их особенности и использование для решения математических задач.
курсовая работа [1,8 M], добавлен 18.01.2013Основные понятия теории графов. Маршруты и связность. Задача о кёнигсбергских мостах. Эйлеровы графы. Оценка числа эйлеровых графов. Алгоритм построения эйлеровой цепи в данном эйлеровом графе. Практическое применение теории графов в науке.
курсовая работа [1006,8 K], добавлен 23.12.2007Основные понятия теории графов. Степень вершины. Маршруты, цепи, циклы. Связность и свойства ориентированных и плоских графов, алгоритм их распознавания, изоморфизм. Операции над ними. Обзор способов задания графов. Эйлеровый и гамильтоновый циклы.
презентация [430,0 K], добавлен 19.11.2013Спектральная теория графов. Теоремы теории матриц и их применение к исследованию спектров графов. Определение и спектр предфрактального фрактального графов с затравкой регулярной степени. Связи между спектральными и структурными свойствами графов.
дипломная работа [272,5 K], добавлен 05.06.2014Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры.
контрольная работа [466,3 K], добавлен 11.03.2011Сущность и основные понятия теории графов, примеры и сферы ее использования. Формирование следствий из данных теорий и примеры их приложений. Методы разрешения задачи о кратчайшем пути, о нахождении максимального потока. Графическое изображение задачи.
курсовая работа [577,1 K], добавлен 14.11.2009Общее понятие, основные свойства и закономерности графов. Задача о Кенигсбергских мостах. Свойства отношения достижимости в графах. Связность и компонента связности графов. Соотношение между количеством вершин связного плоского графа, формула Эйлера.
презентация [150,3 K], добавлен 16.01.2015