Задача о кратчайшем (MIN) пути

Задача о КРАТЧАЙШЕМ (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 пути.