Мегаобучалка Главная | О нас | Обратная связь


Нахождение кратчайшего гамильтонова цикла графа



2018-07-06 402 Обсуждений (0)
Нахождение кратчайшего гамильтонова цикла графа 0.00 из 5.00 0 оценок




Варианты заданий Г-4

Нахождение кратчайшего пути между вершинами орграфа

Для заданного орграфа найти кратчайший путь между вершинами 1 и 12. Задачу решить в общем виде. На рисунке рядом с вершинами указан ее вес.

 

В качестве контрольного примера использовать задания по вариантам.

Вариант заданияГ-41-1

 

 

Рис. 4.1

 

Вариант Г-41-1-2

 

Рис. 4.1


 

Вариант Г-41-1-3

 

 

Вариант Г-41-1-4


Вариант Г-41-4

 

 

Рис. 4.4


 

Варианты заданий Г-42

 

Нахождение максимального потока в сети с помощью алгоритма Форда-Фалкерсона

 

Найти максимальный поток в сети с помощью алгоритма Форда-Фалкерсона. Задачу решить в общем виде. В качестве контрольного примера использовать задание соответствующего варианта.

Вариант задания Г-42-1

 

Рис. 4.3

 

Вариант Г-42-2

 

 

Вариант Г-42-3

 

 

 

Вариант Г-42-4

 


 

Варианты заданий Г-43

Топологическая сортировка в сети

Найти порядковую функцию сети. Задачу решить в общем виде. В качестве контрольного примера использовать задание соответствующего варианта.

.

Вариант Г-43-1

 

Рис. 4.8

 

 

Вариант Г-43-2

Вариант Г-43-3

 

Вариант Г-43-4


 

Варианты заданий Г-44

Паросочетание в двудольном графе

Для заданного двудольного графа найти число совершенных паросочетанийP и одно из наибольших паросочетаний. Задачу решить в общем виде. В качестве контрольного примера использовать задание вашего варианта.

Вариант Г-44-1

Вариант Г-44-2

Вариант Г-44-3

Вариант Г-44-4


Варианты к заданию Г-45

Задача о назначениях (венгерский алгоритм)

 

Найти оптимальные назначения и суммарные затраты на производство. Задачу решить в общем виде. В качестве контрольного примера использовать задание вашего варианта.

Оплата труда работника i на рабочем месте j определяется коэффициентом . Найти одно из оптимальных назначений и суммарные затраты Σ на производство.

Вариант Г-45-1

 

Вариант Г-45-1_2

Вариант Г-45-3

Вариант Г-45-4


 

Задание Г-46

Остов наименьшего веса

Варианты Г-46-1

Определение остова наименьшего веса с помощью алгоритма ближайшего соседа

Дан взвешенный граф. Найти число остовов графа и остов наименьшего веса. Для решения использовать алгоритм ближайшего соседа.

Задачу решить в общем виде. В качестве контрольного примера использовать следующее задание.

Вариант Г-46-1-бс-2

Вариант Г-46-1-бс-2

Вариант Г-46-бс-3

Вариант Г-46-бс-4


Задание Г-46_1

Определение остова наименьшего веса с помощью алгоритма Краскала

Дан взвешенный граф. Найти число остовов графа и остов наименьшего веса. Для решения использовать алгоритм Краскала.

Задачу решить в общем виде. В качестве контрольного примера использовать следующее задание.

Вариант Г-46-1-кр-1

Вариант Г-46-1-кр-2

Вариант Г-46-кр-3

Вариант Г-46-кр-3


Задание Г-47

Гамильтоновы циклы

Задачу решить в общем виде. В качестве контрольного примера использовать граф, представленный на рис. Найти все гамильтоновы циклы графа.

Вариант Г-47-1-1

 

 

Вариант Г-47-1-2

 

 

Вариант Г-47-3

Вариант Г-47-1-4


 

Нахождение кратчайшего гамильтонова цикла графа

Задание Г-48-1



2018-07-06 402 Обсуждений (0)
Нахождение кратчайшего гамильтонова цикла графа 0.00 из 5.00 0 оценок









Обсуждение в статье: Нахождение кратчайшего гамильтонова цикла графа

Обсуждений еще не было, будьте первым... ↓↓↓

Отправить сообщение

Популярное:
Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы...
Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе...
Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы...
Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (402)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.008 сек.)