Содержание
- 2. Определение Граф называется гамильтоновым, если он содержит цикл, включающий все вершины графа. Этот цикл тоже называется
- 3. Не найдено ни одного необходимого и достаточного условия существования гамильтонового цикла в произвольном графе…
- 4. Постановка задачи Дан связный неориентированный граф. Найти все гамильтоновы циклы (если они есть).
- 5. “Простой” способ поиска: Сгенерируем все перестановки вершин графа. Дальше можно просто проверить каждую, не является ли
- 6. Рассмотрим пример: Пусть у графа, скажем, 20 вершин. Сколько существует перестановок вершин? 20!=2432902008176640000 ≈ 2.4•1018 Число
- 7. А если вершин 100? Число перестановок будет равно: 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 ≈ 9.3•10157
- 8. Это не все… Чтобы проверить каждую из этих перестановок на “гамильтоновость” нужно затратить еще N операций.
- 9. Конечно, “лобовое” решение крайне нерационально. Ведь при построении всех перестановок вершин не используется информация о том,
- 10. Структуры данных: Будем использовать два массива целых: Arr[N] – в этом массиве будет находиться последовательность вершин;
- 11. Алгоритм Будем предполагать, что поиск циклов мы ведем c вершины 1. На очередном шаге в массиве
- 12. Алгоритм Центральной процедурой алгоритма является рекурсивная функция Step. Эта функция принимает один целый параметр – номер
- 13. Алгоритм 1. Функция берет последнюю добавленную в массив Arr вершину, делает ее текущей, и ищет (в
- 14. Алгоритм 3. Если найдена вершина, связанная с текущей и еще непосещенная, то: Эта новая вершина добавляется
- 15. На каждом шаге к массиву Arr добавляется еще не посещенная вершина. Поскольку число вершин конечно, то
- 16. for (j=1; j { if (isBound(j,v)) { … if (Nnew[j]==0) // сюда управление { // попадет
- 17. Рассмотрим граф: Этот граф имеет два гамильтоновых цикла: (1,2,3,4,5) и (1,5,4,2,1) Посмотрим, как будет работать описанный
- 18. На желтом поле показывается массив Arr, на зеленом – признаки прохождения вершин
- 19. В прямых скобках показан параметр цикла в соответствующем вызове при поиске вершины
- 22. Параметр вызова=N+1 и из последней вершины достижима первая – выполнено условие цикла.
- 26. Какую вершину будем добавлять?
- 29. Какую вершину будем добавлять?
- 34. Какую вершину будем добавлять?
- 42. Следующей будет добавлена 5-я вершина
- 51. Кратчайшие пути в графах
- 52. Постановка задачи Дан ориентированный граф; Каждой дуге приписана “длина” – вес дуги; Веса дуг хранятся в
- 53. Пример: Каков будет кратчайший путь из 1 в 4? Путь (1-3-2-4). Его длина = 6. Другие
- 54. Контуры отрицательного веса Если граф содержит контуры отрицательного веса, то поиск минимальной длины пути теряет смысл
- 55. Если мы ищем кратчайший путь из 1 в 5, то проходя контур 3-4-2-3 несколько раз, можно
- 56. Соглашение: Мы далее будем рассматривать только графы без контуров отрицательного веса. (но дуги с отрицательной длиной
- 57. Обозначим длину минимального пути между i-й и j-й вершинами через D(i,j). К настоящему времени неизвестен алгоритм,
- 58. Для некоторой вершины p обозначим массив кратчайших расстояний до всех остальных вершин через Dp. Предположим,что есть
- 59. Алгоритм определения пути Ищем кратчайший путь из i-й вершины в j-ю. Можно найти такую вершину k,
- 60. На каждом шаге мы приближаемся к исходной вершине, и, в конце концов, дойдем до нее. В
- 61. Таким образом, если для каждой вершины известен массив кратчайших расстояний до всех вершин графа, можно построить
- 62. Общая схема такова: Пусть зафиксирована i-я вершина, для которой мы ищем массив кратчайших расстояний. Для каждой
- 63. Если для вершины k нашли вершину q, такую, что: Di(k) > Di(q)+A[k,q], то заменяем Di(k) на
- 64. Описанной схеме не хватает существенного момента – порядка выбора вершин k и q. В реальности этот
- 65. Алгоритм Форда-Беллмана Этот алгоритм применим к любому ориентированному графу без контуров отрицательной длины Исходные данные алгоритма:
- 66. Первоначально присваиваем всем элементам массива Di[k] значения A[i,k]; Элементу Di[i] присваиваем значение 0. (N-2) раза повторяем
- 67. Если веса всех дуг графа неотрицательны, то алгоритм Форда-Беллмана можно улучшить до производительности O(N2).
- 68. Алгоритм Дейкстры Исходные данные алгоритма: Орграф с дугами неотрицательной длины; Матрица весов дуг; Фиксированная вершина i
- 69. Первоначально присваиваем всем элементам массива Di[k] значения A[i,k]; Элементу Di[i] присваиваем значение 0. Обозначим через T
- 70. Алгоритм Дейкстры имеет сложность O(N2) Имеется еще один частный вид графов, для которых вычисление расстояний имеет
- 71. Является ли этот граф бесконтурным? Нет. Контур выделен.
- 72. А этот?
- 73. Бесконтурные графы обладают замечательным свойством: их вершины можно перенумеровать так, что для любой дуги (p,q) всегда
- 74. У нашего графа есть “неправильная” дуга (2-1): Если сделать вершину 1 вершиной 2, а вершину 2
- 75. Cуществует эффективный алгоритм, позволяющий перенумеровать вершины бесконтурного графа и превратить его в “правильный” граф. Сложность этого
- 77. Скачать презентацию