1. Возможно ли в сети существование нескольких кратчайших путей между одними и теми же узлами?
2. Можно ли использовать алгоритм Дейкстры для задачи нахождения кратчайших путей между всеми парами узлов?
3. Можно ли использовать алгоритмы нахождения кратчайшего пути от одного узла до другого для решения задачи нахождения кратчайших путей между всеми парами узлов?
4. Можно ли использовать алгоритм Дейкстры в неориентированной сети с отрицательными весами дуг?
5. Справедливо ли следующее утверждение. В неориентированной сети с положительными расстояниями кратчайшая дуга всегда принадлежит дереву кратчайших путей.
6. Справедливо ли следующее утверждение. Если все длины дуг сети различны, то существует единственное дерево кратчайших путей из V0 во все другие узлы.
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. Верно ли что, понятия NP-полный и NP-трудный эквивалентны?
1. Ху Т.Ч., Шинг М.Т. Комбинаторные алгоритмы. Перевод с англ. В.Е. Алексеева, Н.Ю.Золотых и др. – Нижний Новгород. Изд-во Нижегородского госуниверситета им. Н.И.Лобочевского, 2004. –329 с.
2. Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. 3-е изд. – СПб.: Питер, 2008. -384 с.
3. Костюкова, Нина Ивановна. Графы и их применение. Комбинаторные алгоритмы для программистов : учебное пособие / Н. И. Костюкова .— М. : Интернет - Ун-т информ. технологий : БИНОМ. Лаб. знаний, 2007 .— 310 с.
4. Логинов Б.М. Введение в дискретную математику. Лекции и упражнения по курсу «Введение в дискретную математику». – Моск. гос. техн. ун-т им. Н.Э.Баумана Калужский филиал. 1998 г. 423 с.
5. Garey M.R., Johnson D.S. Computers and Intractability. — Freeman Co.,1979.
ФИЛИППОВА Анна Сергеевна
Лекции по дисциплине
«комбинаторные алгоритмы»
Учебное издание
Редактор
Подписано в печать . Формат 60х84 1/16.
Бумага офсетная. Печать плоская.
Гарнитура Times New Roman Cyr. Усл. печ. л. . Усл. кр.-отт., Уч.-изд. л. . Тираж ….. зкз.
Заказ №
Уфимский государственный авиационный технический университет
Редакционно-издательский комплекс УГАТУ
450000, Уфа-центр, ул. К.Маркса, 12
[1]РЕКГ-метод разработан в 1956 году корпорацией Lockheed Air Craft, консалтинговой компанией Booz, Allen & Hamilton и особым проектным бюро ВМС США в процессе создания ракетного комплекса Polaris. Вскоре этот метод стал повсеместно применяться для планирования проектов в вооруженных силах США.
Курс лекций
Курск 2008
ОГЛАВЛЕНИЕ
Лекция 1
Введение. 3
Глава 1. Цели и задачи математического моделирования процессов и систем.. 3
1.1. Понятие «математическая модель». 3
1.2. Классификация математических моделей. 3
Контрольные вопросы к лекции 1. 3
Лекция 2
1.3. Геометрическое представление математических моделей. 3
Глава 2. Теоретические математические модели аналитического типа. 3
2.1. Построение математической модели сверления лазером.. 3
2.2. Линейные математические модели. 3
Контрольные вопросы к лекции 2. 3
Лекция 3
2.3. Исследование простейшей математической модели работы газотурбинного двигателя. 3
2.4. Нелинейные детерминированные модели. 3
2.4.1. Полиномиальные модели. 3
2.4.2. Позиномные модели. 3
Контрольные вопросы к лекции 3. 3
Лекция 4
(2.4.3. Математическая модель кратчайшего пути. 3
Контрольные вопросы к лекции 4. 3
Лекция 5
2.5. Математическая модель в виде обыкновенных дифференциальных уравнений. 3
2.6. Модели, заданные в виде уравнений в частных производных. 3
Редакционно-издательский комплекс УГАТУ
450000, Уфа-центр, ул. К.Маркса, 12