Вопросы к экзамену

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. Разыгрывание нормальной случайной величины с помощью равномерно распределенной на (0, 1) случайной величины.

42. Оценка точности величин, полученных методом Монте-Карло.

43. Применение метода Монте-Карло к сетевым графикам.

44. Оптимизация стоимости проекта путем сокращения продолжительности работ на критических путях (методом «стоимость – время»).

45. Отыскание варианта выполнения работ, обеспечивающего минимальную стоимость проекта при условии минимально возможного времени его завершения.

46. Сведение задач оптимизации на сетевых графиках к задачам линейного программирования. Три типа таких задач.

47. Транспортные сети и их особенности. Поток в сети. Величина потока. Пропускная способность дуги. Условие сохранения потока. Разрез сети.

48. Теорема Форда-Фалкерсона о максимальном потоке.

49. Алгоритм Форда-Фалкерсона отыскания максимального потока в транспортной сети.