Задача о КРАТЧАЙШЕМ (MIN) ПУТИ
Задан граф с 20 вершинами/пунктами (рёбра не ориентированы; начало –
в левом верхнем углу, конец – в правом нижем), расположенными в виде прямоугольника (в виде прямоугольной сетки). Каждая вершина соединена с соседними с ней вершинами справа, слева, снизу и сверху неориентированными ребрами. “Длины” ребер указаны между вершинами.
(решение без обоснования в виде отсутствия в процессе алгоритма нумерации порядка проставления постоянных пометок, т.е. “*”-ек, снижает баллы ВДВОЕ)
Вариант 1 ┌2┬3┬6┬5┐ 7 4 7 4 5 ├5┼2┼4┼5┤ 3 6 3 2 7 ├6┼7┼5┼6┤ 4 5 5 6 5 └6┴3┴7┴3┘ | Вариант 2 ┌6┬7┬3┬5┐ 3 6 3 6 2 ├2┼5┼6┼3┤ 3 3 4 7 5 ├6┼3┼6┼4┤ 7 3 4 3 7 └4┴4┴3┴7┘ | Вариант 3 ┌2┬7┬4┬6┐ 5 7 5 4 5 ├2┼3┼3┼5┤ 2 2 5 2 4 ├2┼6┼6┼3┤ 5 3 6 4 2 └7┴7┴6┴2┘ | Вариант 4 ┌6┬5┬5┬2┐ 5 5 4 5 2 ├7┼3┼5┼3┤ 2 2 5 2 7 ├7┼4┼5┼2┤ 2 6 7 7 4 └3┴4┴3┴4┘ | Вариант 5 ┌7┬2┬3┬5┐ 3 2 6 4 6 ├6┼2┼7┼3┤ 5 2 3 2 2 ├6┼2┼6┼6┤ 6 3 5 3 4 └7┴2┴7┴6┘ | Вариант 6 ┌5┬5┬3┬6┐ 6 7 5 3 2 ├3┼4┼5┼4┤ 7 4 5 2 4 ├5┼3┼3┼2┤ 7 5 2 7 5 └5┴2┴6┴3┘ | Вариант 7 ┌4┬3┬5┬7┐ 6 4 7 6 7 ├5┼6┼2┼3┤ 5 5 7 3 6 ├3┼2┼4┼6┤ 3 4 4 6 4 └5┴6┴5┴2┘ | Вариант 8 ┌2┬4┬2┬4┐ 2 6 6 6 5 ├5┼2┼3┼2┤ 3 3 6 6 4 ├4┼7┼6┼6┤ 5 2 6 2 5 └5┴7┴5┴5┘ | |||||||
Вариант 9 ┌4┬3┬2┬7┐ 2 4 6 3 4 ├2┼4┼2┼7┤ 5 2 6 6 4 ├7┼3┼5┼6┤ 4 6 6 3 2 └5┴5┴6┴4┘ | Вариант 10 ┌5┬7┬7┬3┐ 2 4 4 5 4 ├3┼2┼3┼4┤ 4 7 6 7 5 ├5┼6┼7┼6┤ 5 7 2 6 3 └2┴4┴2┴7┘ | Вариант 11 ┌3┬7┬2┬6┐ 4 3 7 3 5 ├7┼2┼2┼7┤ 2 6 6 3 2 ├7┼6┼2┼5┤ 7 4 2 2 4 └3┴3┴7┴3┘ | Вариант 12 ┌4┬3┬2┬7┐ 2 6 7 5 4 ├7┼7┼6┼7┤ 3 4 2 7 6 ├6┼4┼7┼3┤ 6 2 3 3 4 └4┴4┴3┴7┘ | Вариант 13 ┌4┬4┬6┬3┐ 6 3 5 5 2 ├6┼3┼3┼6┤ 3 6 4 5 5 ├5┼6┼4┼5┤ 5 3 5 6 3 └3┴6┴2┴4┘ | Вариант 14 ┌2┬6┬7┬6┐ 2 4 2 4 4 ├7┼7┼2┼5┤ 5 3 2 3 2 ├3┼2┼3┼5┤ 7 6 2 6 2 └3┴2┴5┴5┘ | Вариант 15 ┌4┬5┬5┬7┐ 5 5 4 3 7 ├7┼4┼7┼4┤ 6 6 3 6 3 ├2┼2┼2┼7┤ 7 6 4 3 3 └7┴2┴2┴7┘ | Вариант 16 ┌3┬3┬2┬2┐ 5 5 7 4 5 ├4┼2┼7┼4┤ 7 6 7 3 6 ├2┼6┼5┼7┤ 6 4 3 5 7 └3┴6┴4┴6┘ | |||||||
Вариант 17 ┌4┬2┬4┬2┐ 2 4 7 6 3 ├6┼7┼2┼3┤ 3 4 4 3 4 ├3┼2┼2┼4┤ 6 2 2 5 4 └4┴2┴3┴2┘ | Вариант 18 ┌4┬4┬3┬6┐ 3 6 6 2 6 ├5┼3┼7┼6┤ 4 3 3 3 6 ├5┼7┼2┼4┤ 4 5 7 5 3 └6┴2┴3┴3┘ | Вариант 19 ┌6┬6┬3┬7┐ 5 4 6 3 6 ├6┼4┼3┼6┤ 3 6 2 5 3 ├4┼4┼5┼6┤ 2 5 2 3 2 └6┴4┴7┴3┘ | Вариант 20 ┌5┬4┬7┬5┐ 2 3 7 6 4 ├5┼7┼3┼4┤ 2 4 6 4 4 ├7┼3┼6┼6┤ 6 4 3 6 3 └6┴6┴4┴4┘ | Вариант 21 ┌5┬7┬4┬7┐ 6 7 4 2 7 ├7┼5┼7┼4┤ 6 2 4 5 2 ├7┼2┼5┼3┤ 5 6 4 6 6 └5┴6┴7┴5┘ | Вариант 22 ┌5┬5┬4┬7┐ 3 2 4 6 4 ├3┼3┼2┼7┤ 5 3 5 2 4 ├7┼6┼3┼4┤ 6 6 2 3 7 └7┴7┴7┴3┘ | Вариант 23 ┌7┬2┬3┬7┐ 4 4 3 6 6 ├3┼7┼4┼4┤ 5 7 4 4 6 ├6┼6┼2┼2┤ 7 5 5 2 2 └5┴5┴4┴7┘ | Вариант 24 ┌3┬6┬3┬6┐ 3 4 2 2 5 ├6┼5┼2┼5┤ 5 6 7 2 6 ├4┼4┼2┼5┤ 7 3 7 6 6 └3┴7┴6┴7┘ | |||||||
Вариант 25 ┌4┬2┬7┬3┐ 4 6 6 2 5 ├3┼6┼4┼6┤ 5 7 6 3 4 ├2┼7┼5┼2┤ 6 6 5 2 2 └4┴3┴4┴4┘ | Вариант 26 ┌4┬5┬5┬4┐ 6 5 3 2 6 ├6┼4┼2┼6┤ 3 3 3 2 2 ├5┼7┼4┼4┤ 5 5 3 7 3 └5┴4┴5┴7┘ | Вариант 27 ┌5┬7┬2┬7┐ 4 5 6 2 5 ├5┼5┼7┼3┤ 6 3 6 6 7 ├6┼3┼4┼7┤ 3 7 5 4 3 └5┴5┴6┴6┘ | Вариант 28 ┌5┬4┬3┬4┐ 6 3 5 5 7 ├7┼5┼2┼7┤ 5 6 6 6 3 ├7┼7┼3┼6┤ 4 5 2 5 4 └4┴3┴7┴7┘ | Вариант 29 ┌7┬6┬3┬6┐ 6 5 5 2 6 ├2┼4┼2┼4┤ 4 2 6 6 3 ├6┼4┼7┼7┤ 2 4 3 5 7 └4┴4┴6┴6┘ |
|
|
|
|
Найти “длину” кратчайшего пути и сам кратчайший путь из левой верхней вершины в правую нижнюю вершину (решение без обоснования в виде нумерации порядка проставления постоянных пометок – не принимается!).
См. на др. стр. З. о СГ.
Задача о СЕТЕВОМ ГРАФИКЕ.
Задан комплекс из 20 работ, схематично расположенных в виде прямоугольника 4´5 длительностей их выполнения. Каждую работу можно начинать выполнять только после окончания выполнения соседних с ней работ слева и сверху.
Вариант 1 6─5─3─2─6 │ │ │ │ │ 2─7─4─7─7 │ │ │ │ │ 5─2─4─5─3 │ │ │ │ │ 6─5─7─6─3 | Вариант 2 2─6─5─2─3 │ │ │ │ │ 3─3─7─3─2 │ │ │ │ │ 4─6─5─3─2 │ │ │ │ │ 7─6─3─5─4 | Вариант 3 5─7─2─7─6 │ │ │ │ │ 5─4─3─3─2 │ │ │ │ │ 4─2─3─5─7 │ │ │ │ │ 5─2─4─5─2 | Вариант 4 2─3─2─5─6 │ │ │ │ │ 3─4─2─7─2 │ │ │ │ │ 4─4─3─5─7 │ │ │ │ │ 4─7─3─3─2 | Вариант 5 6─3─3─2─3 │ │ │ │ │ 5─7─5─5─7 │ │ │ │ │ 7─4─4─7─2 │ │ │ │ │ 5─5─7─6─7 | Вариант 6 4─6─4─6─4 │ │ │ │ │ 3─4─7─3─2 │ │ │ │ │ 3─4─4─6─5 │ │ │ │ │ 2─3─2─6─4 | Вариант 7 2─2─5─3─6 │ │ │ │ │ 4─6─5─2─4 │ │ │ │ │ 7─6─6─4─7 │ │ │ │ │ 5─2─2─7─4 | Вариант 8 3─4─5─5─5 │ │ │ │ │ 5─6─6─4─3 │ │ │ │ │ 6─5─6─7─6 │ │ │ │ │ 7─2─6─4─3 | |||||||
Вариант 9 5─2─5─4─7 │ │ │ │ │ 3─3─3─5─4 │ │ │ │ │ 5─5─7─3─4 │ │ │ │ │ 6─3─4─6─2 | Вариант 10 4─3─2─7─7 │ │ │ │ │ 7─5─5─7─4 │ │ │ │ │ 3─4─3─3─7 │ │ │ │ │ 5─3─7─4─7 | Вариант 11 3─4─5─3─5 │ │ │ │ │ 7─2─3─7─3 │ │ │ │ │ 2─4─7─5─2 │ │ │ │ │ 2─6─3─5─5 | Вариант 12 3─5─5─5─5 │ │ │ │ │ 2─6─2─4─3 │ │ │ │ │ 6─4─7─6─4 │ │ │ │ │ 7─7─4─7─3 | Вариант 13 5─3─6─7─6 │ │ │ │ │ 3─2─7─5─3 │ │ │ │ │ 6─2─4─4─4 │ │ │ │ │ 7─5─5─3─2 | Вариант 14 4─5─2─2─5 │ │ │ │ │ 5─7─5─6─2 │ │ │ │ │ 6─4─6─6─3 │ │ │ │ │ 7─5─5─2─2 | Вариант 15 5─2─5─4─6 │ │ │ │ │ 3─4─6─5─4 │ │ │ │ │ 6─6─6─6─3 │ │ │ │ │ 3─7─3─5─6 | Вариант 16 6─7─4─4─5 │ │ │ │ │ 2─5─5─3─7 │ │ │ │ │ 4─5─2─7─2 │ │ │ │ │ 6─4─4─5─3 | |||||||
Вариант 17 7─5─7─5─3 │ │ │ │ │ 4─5─3─3─5 │ │ │ │ │ 6─5─7─5─6 │ │ │ │ │ 6─3─5─3─4 | Вариант 18 5─4─4─5─3 │ │ │ │ │ 2─6─4─6─2 │ │ │ │ │ 2─6─6─4─6 │ │ │ │ │ 4─3─5─5─6 | Вариант 19 2─7─5─4─3 │ │ │ │ │ 4─3─5─2─2 │ │ │ │ │ 4─3─7─4─3 │ │ │ │ │ 5─3─7─5─5 | Вариант 20 7─4─3─4─4 │ │ │ │ │ 3─7─7─7─5 │ │ │ │ │ 2─5─4─5─4 │ │ │ │ │ 3─2─5─2─3 | Вариант 21 3─3─3─6─5 │ │ │ │ │ 7─3─6─5─4 │ │ │ │ │ 7─5─2─6─4 │ │ │ │ │ 4─2─2─3─5 | Вариант 22 4─2─4─3─5 │ │ │ │ │ 5─3─5─5─4 │ │ │ │ │ 4─2─2─3─2 │ │ │ │ │ 7─6─5─5─3 | Вариант 23 4─3─2─5─6 │ │ │ │ │ 3─6─3─7─4 │ │ │ │ │ 3─5─2─2─6 │ │ │ │ │ 7─6─3─5─5 | Вариант 24 2─2─5─3─7 │ │ │ │ │ 3─2─7─6─3 │ │ │ │ │ 5─4─7─3─4 │ │ │ │ │ 7─7─4─5─2 | |||||||
Вариант 25 4─4─3─2─6 │ │ │ │ │ 6─3─7─3─7 │ │ │ │ │ 3─5─5─6─7 │ │ │ │ │ 7─6─4─5─3 | Вариант 26 7─4─5─4─3 │ │ │ │ │ 7─7─6─3─2 │ │ │ │ │ 2─7─5─3─2 │ │ │ │ │ 5─2─5─3─3 | Вариант 27 4─6─4─5─2 │ │ │ │ │ 2─3─4─2─3 │ │ │ │ │ 6─2─3─3─5 │ │ │ │ │ 5─7─4─7─4 | Вариант 28 3─2─4─4─6 │ │ │ │ │ 3─4─2─6─6 │ │ │ │ │ 2─5─4─2─4 │ │ │ │ │ 2─2─7─4─2 | Вариант 29 7─6─7─6─3 │ │ │ │ │ 7─7─2─2─7 │ │ │ │ │ 6─2─6─2─2 │ │ │ │ │ 4─3─5─3─2 |
|
|
|
|
Найти:
1) минимальное время выполнения комплекса работ
(включить в “Ответ”, как: |T| =...);
2) самые ранние и самые поздние сроки выполнения каждой работы;
3) полный и свободный резервы каждой работы;
4) критический путь;
5) число критических работ
(включить в “Ответ”, как: |Критич.раб.| =...);
6) количество работ, у которых свободный резерв равен 0
(включить в “Ответ”, как: |Раб. с нул. Св.рез.| =...);
7) количество работ, у которых свободный резерв равен полному
(включить в “Ответ”, как: |Раб. с равн. Св. и Полн. рез.| =...).
См. на др. стр. З. о MIN пути.
ТД-131:
Варианты студентов группы:
30. Борисова | 31. Булатова | 32. Дубровская | 33. Ефименко | 34. Кубарева | 35. Манжосов | 36. Манихин | 37. Матюшина |
38. Пужинина | 39. Соловец | 40. Тайсумов | 41. Тарасенко | 42. Тихоновская | 43. Черноусов | 44. Шапорова | 45. Штепина |
Задача о КРАТЧАЙШЕМ (MIN) ПУТИ
Задан граф с 20 вершинами/пунктами (рёбра не ориентированы; начало – в левом верхнем углу, конец – в правом нижем), расположенными в виде прямоугольника (в виде прямоугольной сетки). Каждая вершина соединена с соседними с ней вершинами справа, слева, снизу и сверху неориентированными ребрами. “Длины” ребер указаны между вершинами.
(решение без обоснования в виде отсутствия в процессе алгоритма нумерации порядка проставления постоянных пометок, т.е. “*”-ек, снижает баллы ВДВОЕ)
Вариант 30 ┌5┬4┬7┬2┐ 4 2 5 4 5 ├3┼7┼5┼7┤ 3 6 2 2 5 ├7┼4┼4┼6┤ 5 5 2 2 3 └3┴5┴5┴5┘ | Вариант 31 ┌7┬2┬6┬3┐ 4 7 5 5 7 ├7┼4┼4┼2┤ 4 2 5 3 5 ├5┼4┼5┼4┤ 5 2 7 4 7 └5┴3┴6┴3┘ | Вариант 32 ┌7┬3┬3┬6┐ 3 4 4 6 2 ├2┼7┼7┼2┤ 6 5 6 2 3 ├6┼3┼4┼2┤ 4 7 2 7 4 └6┴5┴6┴3┘ | Вариант 33 ┌5┬6┬6┬6┐ 3 5 4 4 3 ├4┼7┼5┼6┤ 5 6 7 6 4 ├4┼7┼3┼7┤ 6 2 7 2 3 └2┴2┴7┴6┘ | Вариант 34 ┌6┬7┬7┬4┐ 7 4 4 2 4 ├6┼2┼2┼4┤ 4 4 2 6 7 ├3┼3┼2┼3┤ 3 2 3 7 3 └3┴7┴6┴4┘ | Вариант 35 ┌3┬5┬6┬4┐ 7 3 7 5 3 ├2┼6┼4┼7┤ 7 4 2 5 6 ├5┼2┼2┼4┤ 6 5 2 6 3 └7┴2┴6┴6┘ | Вариант 36 ┌5┬4┬3┬5┐ 4 7 7 2 5 ├3┼2┼7┼6┤ 3 3 3 2 4 ├7┼7┼7┼5┤ 2 3 7 7 7 └6┴5┴3┴5┘ | Вариант 37 ┌4┬2┬5┬7┐ 6 4 3 5 6 ├7┼6┼3┼7┤ 6 3 5 7 7 ├4┼7┼4┼7┤ 7 3 3 4 3 └7┴2┴7┴7┘ | |||||||
Вариант 38 ┌2┬3┬6┬7┐ 7 5 7 6 7 ├4┼2┼7┼7┤ 6 7 7 5 7 ├5┼3┼3┼2┤ 6 5 5 3 4 └2┴4┴2┴7┘ | Вариант 39 ┌6┬6┬4┬2┐ 6 4 7 6 4 ├3┼2┼4┼2┤ 6 5 7 5 2 ├6┼5┼7┼2┤ 2 6 6 5 3 └4┴3┴4┴4┘ | Вариант 40 ┌6┬7┬7┬3┐ 7 6 3 7 2 ├4┼3┼6┼7┤ 5 3 6 7 6 ├2┼4┼6┼3┤ 4 4 2 4 2 └2┴7┴4┴2┘ | Вариант 41 ┌2┬3┬6┬5┐ 7 4 7 4 5 ├5┼2┼4┼5┤ 3 6 3 2 7 ├6┼7┼5┼6┤ 4 5 5 6 5 └6┴3┴7┴3┘ | Вариант 42 ┌6┬7┬3┬5┐ 3 6 3 6 2 ├2┼5┼6┼3┤ 3 3 4 7 5 ├6┼3┼6┼4┤ 7 3 4 3 7 └4┴4┴3┴7┘ | Вариант 43 ┌2┬7┬4┬6┐ 5 7 5 4 5 ├2┼3┼3┼5┤ 2 2 5 2 4 ├2┼6┼6┼3┤ 5 3 6 4 2 └7┴7┴6┴2┘ | Вариант 44 ┌6┬5┬5┬2┐ 5 5 4 5 2 ├7┼3┼5┼3┤ 2 2 5 2 7 ├7┼4┼5┼2┤ 2 6 7 7 4 └3┴4┴3┴4┘ | Вариант 45 ┌7┬2┬3┬5┐ 3 2 6 4 6 ├6┼2┼7┼3┤ 5 2 3 2 2 ├6┼2┼6┼6┤ 6 3 5 3 4 └7┴2┴7┴6┘ |
Найти “длину” кратчайшего пути и сам кратчайший путь из левой верхней вершины в правую нижнюю вершину (решение без обоснования в виде нумерации порядка проставления постоянных пометок – не принимается!).
Задача о СЕТЕВОМ ГРАФИКЕ.
Задан комплекс из 20 работ, схематично расположенных в виде прямоугольника 4´5 длительностей их выполнения. Каждую работу можно начинать выполнять только после окончания выполнения соседних с ней работ слева и сверху.
Вариант 30 6─4─7─6─4 │ │ │ │ │ 3─6─3─7─4 │ │ │ │ │ 4─7─6─4─4 │ │ │ │ │ 3─7─7─7─3 | Вариант 31 6─6─5─2─7 │ │ │ │ │ 5─2─4─3─5 │ │ │ │ │ 2─4─2─7─7 │ │ │ │ │ 3─6─3─7─4 | Вариант 32 3─3─3─4─6 │ │ │ │ │ 3─3─7─5─3 │ │ │ │ │ 6─4─5─3─6 │ │ │ │ │ 5─2─7─7─6 | Вариант 33 7─5─7─6─2 │ │ │ │ │ 5─4─2─6─4 │ │ │ │ │ 7─5─7─4─5 │ │ │ │ │ 6─2─5─7─3 | Вариант 34 6─3─6─5─5 │ │ │ │ │ 5─3─7─2─3 │ │ │ │ │ 5─4─6─6─2 │ │ │ │ │ 3─7─4─6─7 | Вариант 35 4─3─7─3─3 │ │ │ │ │ 2─4─2─2─6 │ │ │ │ │ 4─3─3─3─2 │ │ │ │ │ 2─7─7─6─3 | Вариант 36 5─6─4─6─6 │ │ │ │ │ 3─6─2─2─6 │ │ │ │ │ 2─5─3─5─5 │ │ │ │ │ 5─6─6─2─6 | Вариант 37 7─7─3─2─6 │ │ │ │ │ 4─3─4─2─6 │ │ │ │ │ 3─7─6─6─6 │ │ │ │ │ 2─3─3─4─4 | |||||||
Вариант 38 5─7─5─5─4 │ │ │ │ │ 7─6─6─3─5 │ │ │ │ │ 7─7─7─3─4 │ │ │ │ │ 3─3─2─2─4 | Вариант 39 2─2─7─2─6 │ │ │ │ │ 5─6─5─5─4 │ │ │ │ │ 2─6─6─3─5 │ │ │ │ │ 2─3─5─7─3 | Вариант 40 4─5─7─2─4 │ │ │ │ │ 3─4─7─7─3 │ │ │ │ │ 2─6─4─3─3 │ │ │ │ │ 7─6─3─5─5 | Вариант 41 6─5─3─2─6 │ │ │ │ │ 2─7─4─7─7 │ │ │ │ │ 5─2─4─5─3 │ │ │ │ │ 6─5─7─6─3 | Вариант 42 2─6─5─2─3 │ │ │ │ │ 3─3─7─3─2 │ │ │ │ │ 4─6─5─3─2 │ │ │ │ │ 7─6─3─5─4 | Вариант 43 5─7─2─7─6 │ │ │ │ │ 5─4─3─3─2 │ │ │ │ │ 4─2─3─5─7 │ │ │ │ │ 5─2─4─5─2 | Вариант 44 2─3─2─5─6 │ │ │ │ │ 3─4─2─7─2 │ │ │ │ │ 4─4─3─5─7 │ │ │ │ │ 4─7─3─3─2 | Вариант 45 6─3─3─2─3 │ │ │ │ │ 5─7─5─5─7 │ │ │ │ │ 7─4─4─7─2 │ │ │ │ │ 5─5─7─6─7 |
Найти:
1) минимальное время выполнения комплекса работ
(включить в “Ответ”, как: |T| =...);
2) самые ранние и самые поздние сроки выполнения каждой работы;
3) полный и свободный резервы каждой работы;
4) критический путь;
5) число критических работ
(включить в “Ответ”, как: |Критич.раб.| =...);
6) количество работ, у которых свободный резерв равен 0
(включить в “Ответ”, как: |Раб. с нул. Св.рез.| =...);
7) количество работ, у которых свободный резерв равен полному
(включить в “Ответ”, как: |Раб. с равн. Св. и Полн. рез.| =...).
УП-131:
Варианты студентов группы:
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. Цой |
Задача о КРАТЧАЙШЕМ (MIN) ПУТИ
Задан граф с 20 вершинами/пунктами (рёбра не ориентированы; начало – в левом верхнем углу, конец – в правом нижем), расположенными в виде прямоугольника (в виде прямоугольной сетки). Каждая вершина соединена с соседними с ней вершинами справа, слева, снизу и сверху неориентированными ребрами. “Длины” ребер указаны между вершинами.
(решение без обоснования в виде отсутствия в процессе алгоритма нумерации порядка проставления постоянных пометок, т.е. “*”-ек, снижает баллы ВДВОЕ)
Вариант 46 ┌5┬5┬3┬6┐ 6 7 5 3 2 ├3┼4┼5┼4┤ 7 4 5 2 4 ├5┼3┼3┼2┤ 7 5 2 7 5 └5┴2┴6┴3┘ | Вариант 47 ┌4┬3┬5┬7┐ 6 4 7 6 7 ├5┼6┼2┼3┤ 5 5 7 3 6 ├3┼2┼4┼6┤ 3 4 4 6 4 └5┴6┴5┴2┘ | Вариант 48 ┌2┬4┬2┬4┐ 2 6 6 6 5 ├5┼2┼3┼2┤ 3 3 6 6 4 ├4┼7┼6┼6┤ 5 2 6 2 5 └5┴7┴5┴5┘ | Вариант 49 ┌4┬3┬2┬7┐ 2 4 6 3 4 ├2┼4┼2┼7┤ 5 2 6 6 4 ├7┼3┼5┼6┤ 4 6 6 3 2 └5┴5┴6┴4┘ | Вариант 50 ┌5┬7┬7┬3┐ 2 4 4 5 4 ├3┼2┼3┼4┤ 4 7 6 7 5 ├5┼6┼7┼6┤ 5 7 2 6 3 └2┴4┴2┴7┘ | Вариант 51 ┌3┬7┬2┬6┐ 4 3 7 3 5 ├7┼2┼2┼7┤ 2 6 6 3 2 ├7┼6┼2┼5┤ 7 4 2 2 4 └3┴3┴7┴3┘ | Вариант 52 ┌4┬3┬2┬7┐ 2 6 7 5 4 ├7┼7┼6┼7┤ 3 4 2 7 6 ├6┼4┼7┼3┤ 6 2 3 3 4 └4┴4┴3┴7┘ | Вариант 53 ┌4┬4┬6┬3┐ 6 3 5 5 2 ├6┼3┼3┼6┤ 3 6 4 5 5 ├5┼6┼4┼5┤ 5 3 5 6 3 └3┴6┴2┴4┘ | |||||||
Вариант 54 ┌2┬6┬7┬6┐ 2 4 2 4 4 ├7┼7┼2┼5┤ 5 3 2 3 2 ├3┼2┼3┼5┤ 7 6 2 6 2 └3┴2┴5┴5┘ | Вариант 55 ┌4┬5┬5┬7┐ 5 5 4 3 7 ├7┼4┼7┼4┤ 6 6 3 6 3 ├2┼2┼2┼7┤ 7 6 4 3 3 └7┴2┴2┴7┘ | Вариант 56 ┌3┬3┬2┬2┐ 5 5 7 4 5 ├4┼2┼7┼4┤ 7 6 7 3 6 ├2┼6┼5┼7┤ 6 4 3 5 7 └3┴6┴4┴6┘ | Вариант 57 ┌4┬2┬4┬2┐ 2 4 7 6 3 ├6┼7┼2┼3┤ 3 4 4 3 4 ├3┼2┼2┼4┤ 6 2 2 5 4 └4┴2┴3┴2┘ | Вариант 58 ┌4┬4┬3┬6┐ 3 6 6 2 6 ├5┼3┼7┼6┤ 4 3 3 3 6 ├5┼7┼2┼4┤ 4 5 7 5 3 └6┴2┴3┴3┘ | Вариант 59 ┌6┬6┬3┬7┐ 5 4 6 3 6 ├6┼4┼3┼6┤ 3 6 2 5 3 ├4┼4┼5┼6┤ 2 5 2 3 2 └6┴4┴7┴3┘ | Вариант 60 ┌5┬4┬7┬5┐ 2 3 7 6 4 ├5┼7┼3┼4┤ 2 4 6 4 4 ├7┼3┼6┼6┤ 6 4 3 6 3 └6┴6┴4┴4┘ | Вариант 61 ┌5┬7┬4┬7┐ 6 7 4 2 7 ├7┼5┼7┼4┤ 6 2 4 5 2 ├7┼2┼5┼3┤ 5 6 4 6 6 └5┴6┴7┴5┘ | |||||||
Вариант 62 ┌5┬5┬4┬7┐ 3 2 4 6 4 ├3┼3┼2┼7┤ 5 3 5 2 4 ├7┼6┼3┼4┤ 6 6 2 3 7 └7┴7┴7┴3┘ | Вариант 63 ┌7┬2┬3┬7┐ 4 4 3 6 6 ├3┼7┼4┼4┤ 5 7 4 4 6 ├6┼6┼2┼2┤ 7 5 5 2 2 └5┴5┴4┴7┘ | Вариант 64 ┌3┬6┬3┬6┐ 3 4 2 2 5 ├6┼5┼2┼5┤ 5 6 7 2 6 ├4┼4┼2┼5┤ 7 3 7 6 6 └3┴7┴6┴7┘ | Вариант 65 ┌4┬2┬7┬3┐ 4 6 6 2 5 ├3┼6┼4┼6┤ 5 7 6 3 4 ├2┼7┼5┼2┤ 6 6 5 2 2 └4┴3┴4┴4┘ | Вариант 66 ┌4┬5┬5┬4┐ 6 5 3 2 6 ├6┼4┼2┼6┤ 3 3 3 2 2 ├5┼7┼4┼4┤ 5 5 3 7 3 └5┴4┴5┴7┘ | Вариант 67 ┌5┬7┬2┬7┐ 4 5 6 2 5 ├5┼5┼7┼3┤ 6 3 6 6 7 ├6┼3┼4┼7┤ 3 7 5 4 3 └5┴5┴6┴6┘ | Вариант 68 ┌5┬4┬3┬4┐ 6 3 5 5 7 ├7┼5┼2┼7┤ 5 6 6 6 3 ├7┼7┼3┼6┤ 4 5 2 5 4 └4┴3┴7┴7┘ | Вариант 69 ┌7┬6┬3┬6┐ 6 5 5 2 6 ├2┼4┼2┼4┤ 4 2 6 6 3 ├6┼4┼7┼7┤ 2 4 3 5 7 └4┴4┴6┴6┘ | |||||||
Вариант 70 ┌5┬4┬7┬2┐ 4 2 5 4 5 ├3┼7┼5┼7┤ 3 6 2 2 5 ├7┼4┼4┼6┤ 5 5 2 2 3 └3┴5┴5┴5┘ | Вариант 71 ┌7┬2┬6┬3┐ 4 7 5 5 7 ├7┼4┼4┼2┤ 4 2 5 3 5 ├5┼4┼5┼4┤ 5 2 7 4 7 └5┴3┴6┴3┘ |
Найти “длину” кратчайшего пути и сам кратчайший путь из левой верхней вершины в правую нижнюю вершину (решение без обоснования в виде нумерации порядка проставления постоянных пометок – не принимается!).
См. на др. стр. З. о СГ.
Задача о СЕТЕВОМ ГРАФИКЕ.
Задан комплекс из 20 работ, схематично расположенных в виде прямоугольника 4´5 длительностей их выполнения. Каждую работу можно начинать выполнять только после окончания выполнения соседних с ней работ слева и сверху.
Вариант 46 4─6─4─6─4 │ │ │ │ │ 3─4─7─3─2 │ │ │ │ │ 3─4─4─6─5 │ │ │ │ │ 2─3─2─6─4 | Вариант 47 2─2─5─3─6 │ │ │ │ │ 4─6─5─2─4 │ │ │ │ │ 7─6─6─4─7 │ │ │ │ │ 5─2─2─7─4 | Вариант 48 3─4─5─5─5 │ │ │ │ │ 5─6─6─4─3 │ │ │ │ │ 6─5─6─7─6 │ │ │ │ │ 7─2─6─4─3 | Вариант 49 5─2─5─4─7 │ │ │ │ │ 3─3─3─5─4 │ │ │ │ │ 5─5─7─3─4 │ │ │ │ │ 6─3─4─6─2 | Вариант 50 4─3─2─7─7 │ │ │ │ │ 7─5─5─7─4 │ │ │ │ │ 3─4─3─3─7 │ │ │ │ │ 5─3─7─4─7 | Вариант 51 3─4─5─3─5 │ │ │ │ │ 7─2─3─7─3 │ │ │ │ │ 2─4─7─5─2 │ │ │ │ │ 2─6─3─5─5 | Вариант 52 3─5─5─5─5 │ │ │ │ │ 2─6─2─4─3 │ │ │ │ │ 6─4─7─6─4 │ │ │ │ │ 7─7─4─7─3 | Вариант 53 5─3─6─7─6 │ │ │ │ │ 3─2─7─5─3 │ │ │ │ │ 6─2─4─4─4 │ │ │ │ │ 7─5─5─3─2 | |||||||
Вариант 54 4─5─2─2─5 │ │ │ │ │ 5─7─5─6─2 │ │ │ │ │ 6─4─6─6─3 │ │ │ │ │ 7─5─5─2─2 | Вариант 55 5─2─5─4─6 │ │ │ │ │ 3─4─6─5─4 │ │ │ │ │ 6─6─6─6─3 │ │ │ │ │ 3─7─3─5─6 | Вариант 56 6─7─4─4─5 │ │ │ │ │ 2─5─5─3─7 │ │ │ │ │ 4─5─2─7─2 │ │ │ │ │ 6─4─4─5─3 | Вариант 57 7─5─7─5─3 │ │ │ │ │ 4─5─3─3─5 │ │ │ │ │ 6─5─7─5─6 │ │ │ │ │ 6─3─5─3─4 | Вариант 58 5─4─4─5─3 │ │ │ │ │ 2─6─4─6─2 │ │ │ │ │ 2─6─6─4─6 │ │ │ │ │ 4─3─5─5─6 | Вариант 59 2─7─5─4─3 │ │ │ │ │ 4─3─5─2─2 │ │ │ │ │ 4─3─7─4─3 │ │ │ │ │ 5─3─7─5─5 | Вариант 60 7─4─3─4─4 │ │ │ │ │ 3─7─7─7─5 │ │ │ │ │ 2─5─4─5─4 │ │ │ │ │ 3─2─5─2─3 | Вариант 61 3─3─3─6─5 │ │ │ │ │ 7─3─6─5─4 │ │ │ │ │ 7─5─2─6─4 │ │ │ │ │ 4─2─2─3─5 | |||||||
Вариант 62 4─2─4─3─5 │ │ │ │ │ 5─3─5─5─4 │ │ │ │ │ 4─2─2─3─2 │ │ │ │ │ 7─6─5─5─3 | Вариант 63 4─3─2─5─6 │ │ │ │ │ 3─6─3─7─4 │ │ │ │ │ 3─5─2─2─6 │ │ │ │ │ 7─6─3─5─5 | Вариант 64 2─2─5─3─7 │ │ │ │ │ 3─2─7─6─3 │ │ │ │ │ 5─4─7─3─4 │ │ │ │ │ 7─7─4─5─2 | Вариант 65 4─4─3─2─6 │ │ │ │ │ 6─3─7─3─7 │ │ │ │ │ 3─5─5─6─7 │ │ │ │ │ 7─6─4─5─3 | Вариант 66 7─4─5─4─3 │ │ │ │ │ 7─7─6─3─2 │ │ │ │ │ 2─7─5─3─2 │ │ │ │ │ 5─2─5─3─3 | Вариант 67 4─6─4─5─2 │ │ │ │ │ 2─3─4─2─3 │ │ │ │ │ 6─2─3─3─5 │ │ │ │ │ 5─7─4─7─4 | Вариант 68 3─2─4─4─6 │ │ │ │ │ 3─4─2─6─6 │ │ │ │ │ 2─5─4─2─4 │ │ │ │ │ 2─2─7─4─2 | Вариант 69 7─6─7─6─3 │ │ │ │ │ 7─7─2─2─7 │ │ │ │ │ 6─2─6─2─2 │ │ │ │ │ 4─3─5─3─2 | |||||||
Вариант 70 6─4─7─6─4 │ │ │ │ │ 3─6─3─7─4 │ │ │ │ │ 4─7─6─4─4 │ │ │ │ │ 3─7─7─7─3 | Вариант 71 6─6─5─2─7 │ │ │ │ │ 5─2─4─3─5 │ │ │ │ │ 2─4─2─7─7 │ │ │ │ │ 3─6─3─7─4 |
Найти:
1) минимальное время выполнения комплекса работ
(включить в “Ответ”, как: |T| =...);
2) самые ранние и самые поздние сроки выполнения каждой работы;
3) полный и свободный резервы каждой работы;
4) критический путь;
5) число критических работ
(включить в “Ответ”, как: |Критич.раб.| =...);
6) количество работ, у которых свободный резерв равен 0
(включить в “Ответ”, как: |Раб. с нул. Св.рез.| =...);
7) количество работ, у которых свободный резерв равен полному
(включить в “Ответ”, как: |Раб. с равн. Св. и Полн. рез.| =...).
См. на др. стр. З. о MIN пути.