🗊Презентация Гамильтоновы циклы

Категория: Математика
Нажмите для полного просмотра!
Гамильтоновы циклы, слайд №1Гамильтоновы циклы, слайд №2Гамильтоновы циклы, слайд №3Гамильтоновы циклы, слайд №4Гамильтоновы циклы, слайд №5Гамильтоновы циклы, слайд №6Гамильтоновы циклы, слайд №7Гамильтоновы циклы, слайд №8Гамильтоновы циклы, слайд №9Гамильтоновы циклы, слайд №10Гамильтоновы циклы, слайд №11Гамильтоновы циклы, слайд №12Гамильтоновы циклы, слайд №13Гамильтоновы циклы, слайд №14Гамильтоновы циклы, слайд №15Гамильтоновы циклы, слайд №16Гамильтоновы циклы, слайд №17Гамильтоновы циклы, слайд №18Гамильтоновы циклы, слайд №19Гамильтоновы циклы, слайд №20Гамильтоновы циклы, слайд №21Гамильтоновы циклы, слайд №22Гамильтоновы циклы, слайд №23Гамильтоновы циклы, слайд №24Гамильтоновы циклы, слайд №25Гамильтоновы циклы, слайд №26Гамильтоновы циклы, слайд №27Гамильтоновы циклы, слайд №28Гамильтоновы циклы, слайд №29Гамильтоновы циклы, слайд №30Гамильтоновы циклы, слайд №31Гамильтоновы циклы, слайд №32Гамильтоновы циклы, слайд №33Гамильтоновы циклы, слайд №34Гамильтоновы циклы, слайд №35Гамильтоновы циклы, слайд №36Гамильтоновы циклы, слайд №37Гамильтоновы циклы, слайд №38Гамильтоновы циклы, слайд №39Гамильтоновы циклы, слайд №40Гамильтоновы циклы, слайд №41Гамильтоновы циклы, слайд №42Гамильтоновы циклы, слайд №43Гамильтоновы циклы, слайд №44Гамильтоновы циклы, слайд №45Гамильтоновы циклы, слайд №46Гамильтоновы циклы, слайд №47Гамильтоновы циклы, слайд №48Гамильтоновы циклы, слайд №49Гамильтоновы циклы, слайд №50Гамильтоновы циклы, слайд №51Гамильтоновы циклы, слайд №52Гамильтоновы циклы, слайд №53Гамильтоновы циклы, слайд №54Гамильтоновы циклы, слайд №55Гамильтоновы циклы, слайд №56Гамильтоновы циклы, слайд №57Гамильтоновы циклы, слайд №58Гамильтоновы циклы, слайд №59Гамильтоновы циклы, слайд №60Гамильтоновы циклы, слайд №61Гамильтоновы циклы, слайд №62Гамильтоновы циклы, слайд №63Гамильтоновы циклы, слайд №64Гамильтоновы циклы, слайд №65Гамильтоновы циклы, слайд №66Гамильтоновы циклы, слайд №67Гамильтоновы циклы, слайд №68Гамильтоновы циклы, слайд №69Гамильтоновы циклы, слайд №70Гамильтоновы циклы, слайд №71Гамильтоновы циклы, слайд №72Гамильтоновы циклы, слайд №73Гамильтоновы циклы, слайд №74Гамильтоновы циклы, слайд №75Гамильтоновы циклы, слайд №76
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Гамильтоновы циклы. Доклад-сообщение содержит 76 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Гамильтоновы циклы Перебор вершин с возвратом
Описание слайда:
Гамильтоновы циклы Перебор вершин с возвратом

Слайд 2


Определение Граф называется гамильтоновым, если он содержит цикл, включающий все вершины графа. Этот цикл тоже называется гамильтоновым. Не все связные графы гамильтоновы.
Описание слайда:
Определение Граф называется гамильтоновым, если он содержит цикл, включающий все вершины графа. Этот цикл тоже называется гамильтоновым. Не все связные графы гамильтоновы.

Слайд 3


Не найдено ни одного необходимого и достаточного условия существования гамильтонового цикла в произвольном графе… Не найдено ни одного необходимого и достаточного условия существования гамильтонового цикла в произвольном графе…
Описание слайда:
Не найдено ни одного необходимого и достаточного условия существования гамильтонового цикла в произвольном графе… Не найдено ни одного необходимого и достаточного условия существования гамильтонового цикла в произвольном графе…

Слайд 4


Постановка задачи Дан связный неориентированный граф. Найти все гамильтоновы циклы (если они есть).
Описание слайда:
Постановка задачи Дан связный неориентированный граф. Найти все гамильтоновы циклы (если они есть).

Слайд 5


“Простой” способ поиска: Сгенерируем все перестановки вершин графа. Дальше можно просто проверить каждую, не является ли она гамильтоновым циклом. Так ли это просто?
Описание слайда:
“Простой” способ поиска: Сгенерируем все перестановки вершин графа. Дальше можно просто проверить каждую, не является ли она гамильтоновым циклом. Так ли это просто?

Слайд 6


Рассмотрим пример: Пусть у графа, скажем, 20 вершин. Сколько существует перестановок вершин?
Описание слайда:
Рассмотрим пример: Пусть у графа, скажем, 20 вершин. Сколько существует перестановок вершин?

Слайд 7


А если вершин 100? Число перестановок будет равно: 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 ≈ 9.3•10157
Описание слайда:
А если вершин 100? Число перестановок будет равно: 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 ≈ 9.3•10157

Слайд 8


Это не все… Чтобы проверить каждую из этих перестановок на “гамильтоновость” нужно затратить еще N операций. Таким образом, “лобовое” решение требует N•N! операций. Это число растет с ростом N очень быстро…
Описание слайда:
Это не все… Чтобы проверить каждую из этих перестановок на “гамильтоновость” нужно затратить еще N операций. Таким образом, “лобовое” решение требует N•N! операций. Это число растет с ростом N очень быстро…

Слайд 9


Конечно, “лобовое” решение крайне нерационально. Ведь при построении всех перестановок вершин не используется информация о том, какие из вершин связаны друг с другом. Конечно, “лобовое” решение крайне нерационально. Ведь при построении всех перестановок вершин не используется информация о том, какие из вершин связаны друг с другом. Есть более рациональный алгоритм…
Описание слайда:
Конечно, “лобовое” решение крайне нерационально. Ведь при построении всех перестановок вершин не используется информация о том, какие из вершин связаны друг с другом. Конечно, “лобовое” решение крайне нерационально. Ведь при построении всех перестановок вершин не используется информация о том, какие из вершин связаны друг с другом. Есть более рациональный алгоритм…

Слайд 10


Структуры данных: Будем использовать два массива целых: Arr[N] – в этом массиве будет находиться последовательность вершин; Nnew[N] – если i-й элемент этого массива есть 0, значит на текущем шаге i-я вершина графа еще не посещалась. Для задания структуры графа будем использовать матрицу смежности Matr[N][N]
Описание слайда:
Структуры данных: Будем использовать два массива целых: Arr[N] – в этом массиве будет находиться последовательность вершин; Nnew[N] – если i-й элемент этого массива есть 0, значит на текущем шаге i-я вершина графа еще не посещалась. Для задания структуры графа будем использовать матрицу смежности Matr[N][N]

Слайд 11


Алгоритм Будем предполагать, что поиск циклов мы ведем c вершины 1. На очередном шаге в массиве Arr находится последовательность связанных друг с другом вершин, которые, возможно, являются началом гамильтонова цикла.
Описание слайда:
Алгоритм Будем предполагать, что поиск циклов мы ведем c вершины 1. На очередном шаге в массиве Arr находится последовательность связанных друг с другом вершин, которые, возможно, являются началом гамильтонова цикла.

Слайд 12


Алгоритм Центральной процедурой алгоритма является рекурсивная функция Step. Эта функция принимает один целый параметр – номер шага.
Описание слайда:
Алгоритм Центральной процедурой алгоритма является рекурсивная функция Step. Эта функция принимает один целый параметр – номер шага.

Слайд 13


Алгоритм 1. Функция берет последнюю добавленную в массив Arr вершину, делает ее текущей, и ищет (в цикле по матрице смежности) вершины, связанные с текущей. 2. Если номер шага = N+1, а текущая вершина связана с первой вершиной, то в Arr находится гамильтонов цикл. Его можно вывести, а затем выйти из Step.
Описание слайда:
Алгоритм 1. Функция берет последнюю добавленную в массив Arr вершину, делает ее текущей, и ищет (в цикле по матрице смежности) вершины, связанные с текущей. 2. Если номер шага = N+1, а текущая вершина связана с первой вершиной, то в Arr находится гамильтонов цикл. Его можно вывести, а затем выйти из Step.

Слайд 14


Алгоритм 3. Если найдена вершина, связанная с текущей и еще непосещенная, то: Эта новая вершина добавляется в “хвост” Arr; Новая вершина отмечается как посещенная; Вызывается процедура Step cо значением параметра, увеличенным на 1; После возврата новая вершина вновь отмечается, как непосещенная. 4. Если все вершины, связанные с текущей уже посещались, то осуществляется выход из Step.
Описание слайда:
Алгоритм 3. Если найдена вершина, связанная с текущей и еще непосещенная, то: Эта новая вершина добавляется в “хвост” Arr; Новая вершина отмечается как посещенная; Вызывается процедура Step cо значением параметра, увеличенным на 1; После возврата новая вершина вновь отмечается, как непосещенная. 4. Если все вершины, связанные с текущей уже посещались, то осуществляется выход из Step.

Слайд 15


На каждом шаге к массиву Arr добавляется еще не посещенная вершина. Поскольку число вершин конечно, то процесс должен рано или поздно закончиться. На каждом шаге к массиву Arr добавляется еще не посещенная вершина. Поскольку число вершин конечно, то процесс должен рано или поздно закончиться. Смущает то, что после возврата из функции Step, последняя вершина помечается как непосещённая. Не приведет ли это к зацикливанию?..
Описание слайда:
На каждом шаге к массиву Arr добавляется еще не посещенная вершина. Поскольку число вершин конечно, то процесс должен рано или поздно закончиться. На каждом шаге к массиву Arr добавляется еще не посещенная вершина. Поскольку число вершин конечно, то процесс должен рано или поздно закончиться. Смущает то, что после возврата из функции Step, последняя вершина помечается как непосещённая. Не приведет ли это к зацикливанию?..

Слайд 16


for (j=1; j <= gN; j++) for (j=1; j <= gN; j++) { if (isBound(j,v)) { … if (Nnew[j]==0) // сюда управление { // попадет при каждом j Arr[k]=j; // не более 1 раза! Nnew[j]=1; Step(k+1); Nnew[j]=0; }
Описание слайда:
for (j=1; j <= gN; j++) for (j=1; j <= gN; j++) { if (isBound(j,v)) { … if (Nnew[j]==0) // сюда управление { // попадет при каждом j Arr[k]=j; // не более 1 раза! Nnew[j]=1; Step(k+1); Nnew[j]=0; }

Слайд 17


Рассмотрим граф: Этот граф имеет два гамильтоновых цикла: (1,2,3,4,5) и (1,5,4,2,1)
Описание слайда:
Рассмотрим граф: Этот граф имеет два гамильтоновых цикла: (1,2,3,4,5) и (1,5,4,2,1)

Слайд 18


На желтом поле показывается массив Arr, на зеленом – признаки прохождения вершин На желтом поле показывается массив Arr, на зеленом – признаки прохождения вершин
Описание слайда:
На желтом поле показывается массив Arr, на зеленом – признаки прохождения вершин На желтом поле показывается массив Arr, на зеленом – признаки прохождения вершин

Слайд 19


В прямых скобках показан параметр цикла в соответствующем вызове при поиске вершины В прямых скобках показан параметр цикла в соответствующем вызове при поиске вершины
Описание слайда:
В прямых скобках показан параметр цикла в соответствующем вызове при поиске вершины В прямых скобках показан параметр цикла в соответствующем вызове при поиске вершины

Слайд 20


Гамильтоновы циклы, слайд №20
Описание слайда:

Слайд 21


Гамильтоновы циклы, слайд №21
Описание слайда:

Слайд 22


Параметр вызова=N+1 и из последней вершины достижима первая – выполнено условие цикла. Параметр вызова=N+1 и из последней вершины достижима первая – выполнено условие цикла.
Описание слайда:
Параметр вызова=N+1 и из последней вершины достижима первая – выполнено условие цикла. Параметр вызова=N+1 и из последней вершины достижима первая – выполнено условие цикла.

Слайд 23


Гамильтоновы циклы, слайд №23
Описание слайда:

Слайд 24


Гамильтоновы циклы, слайд №24
Описание слайда:

Слайд 25


Гамильтоновы циклы, слайд №25
Описание слайда:

Слайд 26


Гамильтоновы циклы, слайд №26
Описание слайда:

Слайд 27


Гамильтоновы циклы, слайд №27
Описание слайда:

Слайд 28


Гамильтоновы циклы, слайд №28
Описание слайда:

Слайд 29


Гамильтоновы циклы, слайд №29
Описание слайда:

Слайд 30


Гамильтоновы циклы, слайд №30
Описание слайда:

Слайд 31


Гамильтоновы циклы, слайд №31
Описание слайда:

Слайд 32


Гамильтоновы циклы, слайд №32
Описание слайда:

Слайд 33


Гамильтоновы циклы, слайд №33
Описание слайда:

Слайд 34


Гамильтоновы циклы, слайд №34
Описание слайда:

Слайд 35


Гамильтоновы циклы, слайд №35
Описание слайда:

Слайд 36


Гамильтоновы циклы, слайд №36
Описание слайда:

Слайд 37


Гамильтоновы циклы, слайд №37
Описание слайда:

Слайд 38


Гамильтоновы циклы, слайд №38
Описание слайда:

Слайд 39


Гамильтоновы циклы, слайд №39
Описание слайда:

Слайд 40


Гамильтоновы циклы, слайд №40
Описание слайда:

Слайд 41


Гамильтоновы циклы, слайд №41
Описание слайда:

Слайд 42


Гамильтоновы циклы, слайд №42
Описание слайда:

Слайд 43


Гамильтоновы циклы, слайд №43
Описание слайда:

Слайд 44


Гамильтоновы циклы, слайд №44
Описание слайда:

Слайд 45


Гамильтоновы циклы, слайд №45
Описание слайда:

Слайд 46


Гамильтоновы циклы, слайд №46
Описание слайда:

Слайд 47


Гамильтоновы циклы, слайд №47
Описание слайда:

Слайд 48


Гамильтоновы циклы, слайд №48
Описание слайда:

Слайд 49


Гамильтоновы циклы, слайд №49
Описание слайда:

Слайд 50


Гамильтоновы циклы, слайд №50
Описание слайда:

Слайд 51


Кратчайшие пути в графах
Описание слайда:
Кратчайшие пути в графах

Слайд 52


Постановка задачи Дан ориентированный граф; Каждой дуге приписана “длина” – вес дуги; Веса дуг хранятся в матрице смежности, причем, если i-я и j-я вершины не связаны дугой, то A[i,j]=∞ “Длина” или оценка пути = сумме весов дуг, составляющих путь. Требуется находить пути с минимальной оценкой (т.е. кратчайшие).
Описание слайда:
Постановка задачи Дан ориентированный граф; Каждой дуге приписана “длина” – вес дуги; Веса дуг хранятся в матрице смежности, причем, если i-я и j-я вершины не связаны дугой, то A[i,j]=∞ “Длина” или оценка пути = сумме весов дуг, составляющих путь. Требуется находить пути с минимальной оценкой (т.е. кратчайшие).

Слайд 53


Пример: Каков будет кратчайший путь из 1 в 4?
Описание слайда:
Пример: Каков будет кратчайший путь из 1 в 4?

Слайд 54


Контуры отрицательного веса Если граф содержит контуры отрицательного веса, то поиск минимальной длины пути теряет смысл
Описание слайда:
Контуры отрицательного веса Если граф содержит контуры отрицательного веса, то поиск минимальной длины пути теряет смысл

Слайд 55


Если мы ищем кратчайший путь из 1 в 5, то проходя контур 3-4-2-3 несколько раз, можно сделать путь 1-5 меньше любой наперед заданной величины. Если мы ищем кратчайший путь из 1 в 5, то проходя контур 3-4-2-3 несколько раз, можно сделать путь 1-5 меньше любой наперед заданной величины.
Описание слайда:
Если мы ищем кратчайший путь из 1 в 5, то проходя контур 3-4-2-3 несколько раз, можно сделать путь 1-5 меньше любой наперед заданной величины. Если мы ищем кратчайший путь из 1 в 5, то проходя контур 3-4-2-3 несколько раз, можно сделать путь 1-5 меньше любой наперед заданной величины.

Слайд 56


Соглашение: Мы далее будем рассматривать только графы без контуров отрицательного веса. (но дуги с отрицательной длиной могут существовать)
Описание слайда:
Соглашение: Мы далее будем рассматривать только графы без контуров отрицательного веса. (но дуги с отрицательной длиной могут существовать)

Слайд 57


Обозначим длину минимального пути между i-й и j-й вершинами через D(i,j). Обозначим длину минимального пути между i-й и j-й вершинами через D(i,j). К настоящему времени неизвестен алгоритм, позволяющий найти минимальный путь только для пары вершин. Все алгоритмы требуют определения оценки минимального пути для всех вершин графа.
Описание слайда:
Обозначим длину минимального пути между i-й и j-й вершинами через D(i,j). Обозначим длину минимального пути между i-й и j-й вершинами через D(i,j). К настоящему времени неизвестен алгоритм, позволяющий найти минимальный путь только для пары вершин. Все алгоритмы требуют определения оценки минимального пути для всех вершин графа.

Слайд 58


Для некоторой вершины p обозначим массив кратчайших расстояний до всех остальных вершин через Dp. Для некоторой вершины p обозначим массив кратчайших расстояний до всех остальных вершин через Dp. Предположим,что есть алгоритм определения этого массива для любой вершины графа.
Описание слайда:
Для некоторой вершины p обозначим массив кратчайших расстояний до всех остальных вершин через Dp. Для некоторой вершины p обозначим массив кратчайших расстояний до всех остальных вершин через Dp. Предположим,что есть алгоритм определения этого массива для любой вершины графа.

Слайд 59


Алгоритм определения пути Ищем кратчайший путь из i-й вершины в j-ю. Можно найти такую вершину k, что: Di(j)=Di(k)+A[k,j] Таким свойством обладает предпоследняя вершина кратчайшего пути из i в j. Запомним вершину k в стеке и ищем вершину l, для которой: Di(k)=Di(l)+A[l,j]
Описание слайда:
Алгоритм определения пути Ищем кратчайший путь из i-й вершины в j-ю. Можно найти такую вершину k, что: Di(j)=Di(k)+A[k,j] Таким свойством обладает предпоследняя вершина кратчайшего пути из i в j. Запомним вершину k в стеке и ищем вершину l, для которой: Di(k)=Di(l)+A[l,j]

Слайд 60


На каждом шаге мы приближаемся к исходной вершине, и, в конце концов, дойдем до нее. На каждом шаге мы приближаемся к исходной вершине, и, в конце концов, дойдем до нее. В стеке будет искомый путь (последовательность вершин).
Описание слайда:
На каждом шаге мы приближаемся к исходной вершине, и, в конце концов, дойдем до нее. На каждом шаге мы приближаемся к исходной вершине, и, в конце концов, дойдем до нее. В стеке будет искомый путь (последовательность вершин).

Слайд 61


Таким образом, если для каждой вершины известен массив кратчайших расстояний до всех вершин графа, можно построить кратчайший путь. Таким образом, если для каждой вершины известен массив кратчайших расстояний до всех вершин графа, можно построить кратчайший путь. Но как определить массив кратчайших расстояний?
Описание слайда:
Таким образом, если для каждой вершины известен массив кратчайших расстояний до всех вершин графа, можно построить кратчайший путь. Таким образом, если для каждой вершины известен массив кратчайших расстояний до всех вершин графа, можно построить кратчайший путь. Но как определить массив кратчайших расстояний?

Слайд 62


Общая схема такова: Пусть зафиксирована i-я вершина, для которой мы ищем массив кратчайших расстояний. Для каждой вершины j вычисляем верхние ограничения Di(j) на расстояние (i – j). Далее стараемся улучшить эти ограничения.
Описание слайда:
Общая схема такова: Пусть зафиксирована i-я вершина, для которой мы ищем массив кратчайших расстояний. Для каждой вершины j вычисляем верхние ограничения Di(j) на расстояние (i – j). Далее стараемся улучшить эти ограничения.

Слайд 63


Если для вершины k нашли вершину q, такую, что: Если для вершины k нашли вершину q, такую, что: Di(k) > Di(q)+A[k,q], то заменяем Di(k) на сумму Di(q)+A[k,q]. Процесс завершается, когда дальнейшее улучшение невозможно.
Описание слайда:
Если для вершины k нашли вершину q, такую, что: Если для вершины k нашли вершину q, такую, что: Di(k) > Di(q)+A[k,q], то заменяем Di(k) на сумму Di(q)+A[k,q]. Процесс завершается, когда дальнейшее улучшение невозможно.

Слайд 64


Описанной схеме не хватает существенного момента – порядка выбора вершин k и q. Описанной схеме не хватает существенного момента – порядка выбора вершин k и q. В реальности этот порядок важен, т.к. от него существенно зависит эффективность алгоритма.
Описание слайда:
Описанной схеме не хватает существенного момента – порядка выбора вершин k и q. Описанной схеме не хватает существенного момента – порядка выбора вершин k и q. В реальности этот порядок важен, т.к. от него существенно зависит эффективность алгоритма.

Слайд 65


Алгоритм Форда-Беллмана Этот алгоритм применим к любому ориентированному графу без контуров отрицательной длины
Описание слайда:
Алгоритм Форда-Беллмана Этот алгоритм применим к любому ориентированному графу без контуров отрицательной длины

Слайд 66


Первоначально присваиваем всем элементам массива Di[k] значения A[i,k]; Элементу Di[i] присваиваем значение 0. Первоначально присваиваем всем элементам массива Di[k] значения A[i,k]; Элементу Di[i] присваиваем значение 0. (N-2) раза повторяем следующие действия: Для всех вершин q (кроме i) Для всех вершин w вычисляем: Di[q]=min(Di[q],Di[w]+A[w,q])
Описание слайда:
Первоначально присваиваем всем элементам массива Di[k] значения A[i,k]; Элементу Di[i] присваиваем значение 0. Первоначально присваиваем всем элементам массива Di[k] значения A[i,k]; Элементу Di[i] присваиваем значение 0. (N-2) раза повторяем следующие действия: Для всех вершин q (кроме i) Для всех вершин w вычисляем: Di[q]=min(Di[q],Di[w]+A[w,q])

Слайд 67


Если веса всех дуг графа неотрицательны, то алгоритм Форда-Беллмана можно улучшить до производительности O(N2). Если веса всех дуг графа неотрицательны, то алгоритм Форда-Беллмана можно улучшить до производительности O(N2).
Описание слайда:
Если веса всех дуг графа неотрицательны, то алгоритм Форда-Беллмана можно улучшить до производительности O(N2). Если веса всех дуг графа неотрицательны, то алгоритм Форда-Беллмана можно улучшить до производительности O(N2).

Слайд 68


Алгоритм Дейкстры
Описание слайда:
Алгоритм Дейкстры

Слайд 69


Первоначально присваиваем всем элементам массива Di[k] значения A[i,k]; Элементу Di[i] присваиваем значение 0. Первоначально присваиваем всем элементам массива Di[k] значения A[i,k]; Элементу Di[i] присваиваем значение 0. Обозначим через T совокупность вершин графа без вершины i. Выполнять, пока T не пусто, следующие действия: - искать в T вершину u, для которой величина Di[u] минимальна; - исключить u из T; - для всех оставшихся вершин w из T вычислить: Di[w]=min(Di[w],Di[w]+A[u,w]
Описание слайда:
Первоначально присваиваем всем элементам массива Di[k] значения A[i,k]; Элементу Di[i] присваиваем значение 0. Первоначально присваиваем всем элементам массива Di[k] значения A[i,k]; Элементу Di[i] присваиваем значение 0. Обозначим через T совокупность вершин графа без вершины i. Выполнять, пока T не пусто, следующие действия: - искать в T вершину u, для которой величина Di[u] минимальна; - исключить u из T; - для всех оставшихся вершин w из T вычислить: Di[w]=min(Di[w],Di[w]+A[u,w]

Слайд 70


Алгоритм Дейкстры имеет сложность Алгоритм Дейкстры имеет сложность O(N2)
Описание слайда:
Алгоритм Дейкстры имеет сложность Алгоритм Дейкстры имеет сложность O(N2)

Слайд 71


Является ли этот граф бесконтурным?
Описание слайда:
Является ли этот граф бесконтурным?

Слайд 72


А этот?
Описание слайда:
А этот?

Слайд 73


Бесконтурные графы обладают замечательным свойством: их вершины можно перенумеровать так, что для любой дуги (p,q) всегда будет q > p. Бесконтурные графы обладают замечательным свойством: их вершины можно перенумеровать так, что для любой дуги (p,q) всегда будет q > p.
Описание слайда:
Бесконтурные графы обладают замечательным свойством: их вершины можно перенумеровать так, что для любой дуги (p,q) всегда будет q > p. Бесконтурные графы обладают замечательным свойством: их вершины можно перенумеровать так, что для любой дуги (p,q) всегда будет q > p.

Слайд 74


Гамильтоновы циклы, слайд №74
Описание слайда:

Слайд 75


Cуществует эффективный алгоритм, позволяющий перенумеровать вершины бесконтурного графа и превратить его в “правильный” граф. Cуществует эффективный алгоритм, позволяющий перенумеровать вершины бесконтурного графа и превратить его в “правильный” граф. Сложность этого алгоритма = O(N+M). Для “правильного” бесконтурного графа расстояния считаются очень просто.
Описание слайда:
Cуществует эффективный алгоритм, позволяющий перенумеровать вершины бесконтурного графа и превратить его в “правильный” граф. Cуществует эффективный алгоритм, позволяющий перенумеровать вершины бесконтурного графа и превратить его в “правильный” граф. Сложность этого алгоритма = O(N+M). Для “правильного” бесконтурного графа расстояния считаются очень просто.

Слайд 76


http://catstail.narod.ru/lec/lec-12.zip
Описание слайда:
http://catstail.narod.ru/lec/lec-12.zip

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию