19.
|
| A
| B
| C
| D
| E
|
| A
|
| 2
| 4
| 1
|
|
| B
| 2
|
|
|
|
|
| C
| 4
|
|
|
| 5
|
| D
| 1
|
|
|
| 4
|
| E
|
|
| 5
| 4
|
|
|
| A
| B
| C
| D
|
| A
|
| 4
|
| 5
|
| B
| 4
|
| 3
| 6
|
| C
|
| 3
|
|
|
| D
| 5
| 6
|
|
|
20.
21.
|
| A
| B
| C
| D
|
| A
|
|
| 1
| 2
|
| B
|
|
| 2
| 3
|
| C
| 1
| 2
|
| 5
|
| D
| 2
| 3
| 5
|
|
|
| A
| B
| C
| D
|
| A
|
| 3
|
| 1
|
| B
| 3
|
| 2
| 1
|
| C
|
| 2
|
| 4
|
| D
| 1
| 1
| 4
|
|
22.
|
| A
| B
| C
| D
| E
|
| A
|
| 1
| 4
|
| 1
|
| B
| 1
|
| 2
|
|
|
| C
| 4
| 2
|
| 3
|
|
| D
|
|
| 3
|
|
|
| E
| 1
|
|
|
|
|
23.
24. 
1) 
2) 
3) 
4) 
Задание: В таблицах приведена протяженность автомагистралей между соседними населенными пунктами. Если пересечение строки и столбца пусто, то соответствующие населенные пункты не соединены автомагистралями. Протяженность маршрута складывается из протяженности автомагистралей между соответствующими соседними населенными пунктами. При этом через любой насеченный пункт маршрут должен проходить не более одного раза.
Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта А до пункта С не больше 5». Протяженность маршрута складывается из протяженности автомагистралей между соответствующими соседними населенными пунктами. При этом любой населенный пункт должен встречаться на маршруте не более одного раза.
| 1)
| 2)
| 3)
| 4)
|
|
| A
| B
| C
| D
| | A
|
| 2
|
| 2
| | B
| 2
|
| 1
| 3
| | C
|
| 1
|
| 3
| | D
| 2
| 3
| 3
|
|
| |
| A
| B
| C
| D
| | A
|
| 2
| 2
|
| | B
| 2
|
| 1
| 1
| | C
| 2
| 1
|
| 3
| | D
|
| 1
| 3
|
|
| |
| A
| B
| C
| D
| | A
|
| 2
| 3
| 2
| | B
| 2
|
| 2
| 2
| | C
| 3
| 2
|
|
| | D
| 2
| 2
|
|
|
| |
| A
| B
| C
| D
| | A
|
| 3
| 2
| 1
| | B
| 3
|
| 2
|
| | C
| 2
| 2
|
| 1
| | D
| 1
|
| 1
|
|
|
26. Укажите таблицу, для которой выполняется условие «Минимальная стоимость перевозки грузов от пункта А до пункта В не больше 3».
| 1)
| 2)
| 3)
| 4)
|
|
| A
| B
| C
| D
| Е
| | A
|
|
|
| 1
|
| | B
|
|
| 4
|
| 3
| | C
|
| 4
|
| 4
|
| | D
| 1
|
| 4
|
|
| | Е
|
| 3
|
|
|
|
| |
| A
| B
| C
| D
| Е
| | A
|
|
| 5
| 1
|
| | B
|
|
| 4
|
| 2
| | C
| 5
| 4
|
|
|
| | D
| 1
|
|
|
|
| | Е
|
| 2
|
|
|
|
| |
| A
| B
| C
| D
| Е
| | A
|
|
| 3
| 1
| 1
| | B
|
|
| 2
| 1
|
| | C
| 3
| 2
|
|
|
| | D
| 1
| 1
|
|
|
| | Е
| 1
|
|
|
|
|
| |
| A
| B
| C
| D
| Е
| | A
|
|
| 2
| 1
| 3
| | B
|
|
| 2
|
| 2
| | C
| 2
| 2
|
|
|
| | D
| 1
|
|
|
|
| | Е
| 3
| 2
|
|
|
|
|
27. Укажите номер таблицы, для которой выполняется условие «Максимальная стоимость перевозки грузов от пункта В до пункта D не больше 6».
| 1)
| 2)
| 3)
| 4)
|
|
| A
| B
| C
| D
| | A
|
| 2
|
| 2
| | B
| 2
|
| 4
| 3
| | C
|
| 4
|
| 4
| | D
| 2
| 3
| 4
|
|
| |
| A
| B
| C
| D
| | A
|
| 2
| 1
| 1
| | B
| 2
|
| 4
|
| | C
| 1
| 4
|
| 1
| | D
| 1
|
| 1
|
|
| |
| A
| B
| C
| D
| | A
|
| 1
| 3
| 6
| | B
| 1
|
| 2
| 4
| | C
| 3
| 2
|
|
| | D
| 6
| 4
|
|
|
| |
| A
| B
| C
| D
| | A
|
| 3
| 2
| 1
| | B
| 3
|
| 2
|
| | C
| 2
| 2
|
| 4
| | D
| 1
|
| 4
|
|
|
28. Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта А до пункта С не больше 6».
| 1)
| 2)
| 3)
| 4)
|
|
| A
| B
| C
| D
| | A
|
| 1
|
| 2
| | B
| 1
|
| 4
| 3
| | C
|
| 4
|
| 3
| | D
| 2
| 3
| 3
|
|
| |
| A
| B
| C
| D
| | A
|
| 1
| 2
|
| | B
| 1
|
| 4
| 2
| | C
| 2
| 4
|
| 3
| | D
|
| 2
| 3
|
|
| |
| A
| B
| C
| D
| | A
|
| 3
| 3
| 2
| | B
| 3
|
| 4
| 3
| | C
| 3
| 4
|
|
| | D
| 2
| 3
|
|
|
| |
| A
| B
| C
| D
| | A
|
| 3
| 2
| 1
| | B
| 3
|
| 4
|
| | C
| 2
| 4
|
| 1
| | D
| 1
|
| 1
|
|
|
29. Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта C до пункта B не больше 6».
| 1)
| 2)
| 3)
| 4)
|
|
| A
| B
| C
| D
| E
| | A
|
| 4
| 3
|
| 7
| | B
| 4
|
|
| 2
|
| | C
| 3
|
|
| 6
|
| | D
|
| 2
| 6
|
| 1
| | E
| 7
|
|
| 1
|
|
| |
| A
| B
| C
| D
| E
| | A
|
| 2
| 5
|
| 6
| | B
| 2
|
|
| 3
|
| | C
| 5
|
|
|
|
| | D
|
| 3
|
|
| 1
| | E
| 6
|
|
| 1
|
|
| |
| A
| B
| C
| D
| E
| | A
|
|
| 2
| 2
| 6
| | B
|
|
|
| 2
|
| | C
| 2
|
|
| 2
|
| | D
| 2
| 2
| 2
|
|
| | E
| 6
|
|
|
|
|
| |
| A
| B
| C
| D
| E
| | A
|
| 5
| 2
|
| 6
| | B
| 5
|
|
| 5
|
| | C
| 2
|
|
| 2
|
| | D
|
| 5
| 2
|
| 3
| | E
| 6
|
|
| 3
|
|
|
30. Укажите номер таблицы, для которой выполняется условие «Максимальная стоимость перевозки грузов от пункта В до пункта D не больше 6».
| 1)
| 2)
| 3)
| 4)
|
|
| A
| B
| C
| D
| | A
|
| 2
|
| 2
| | B
| 2
|
| 4
| 3
| | C
|
| 4
|
| 4
| | D
| 2
| 3
| 4
|
|
| |
| A
| B
| C
| D
| | A
|
| 2
| 1
| 1
| | B
| 2
|
| 4
|
| | C
| 1
| 4
|
| 1
| | D
| 1
|
| 1
|
|
| |
| A
| B
| C
| D
| | A
|
| 1
| 3
| 6
| | B
| 1
|
| 2
| 4
| | C
| 3
| 2
|
|
| | D
| 6
| 4
|
|
|
| |
| A
| B
| C
| D
| | A
|
| 3
| 2
| 1
| | B
| 3
|
| 2
|
| | C
| 2
| 2
|
| 4
| | D
| 1
|
| 4
|
|
|
Пояснения к работе:
Необходимые формулы:
Граф- это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Вершины, прилегающие к одному и тому же ребру, называются смежными.
Если ребра ориентированны, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом.
Если ребра не имеют ориентации, граф называется неориентированным.
Петля- это дуга, начальная и конечная вершина которой совпадают.
Простой граф- граф без кратных ребер и петель.
Степень вершины- это удвоенное количество петель, находящихся у этой вершины плюс количество остальных прилегающих к ней ребер.
Пустым называется граф без ребер.
Полным называется граф, в котором каждые две вершины смежные.
Путь в ориентированном графе — это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Маршрут в графе путь, ориентацией дуг которого можно пренебречь.
Цепь- маршрут, в котором все ребра попарно различны.
Цикл- замкнутый маршрут, являющийся цепью.
Граф называется связным, если любая пара его вершин связана.
Дерево — это связный граф без циклов.
Содержание отчета
1. Титульный лист в соответствии с СТП1.2-2005.
2. Цель работы
3. Задание
4. Выполненная практическая работа в соответствии с заданием
5. Ответы на контрольные вопросы
6. Вывод
Контрольные вопросы:
1. Дайте определение ориентированного графа.
2. Сформулируйте понятие смежных ребер.
3. Дайте определение правильного графа.
4. Запишите формулу суммы степеней графа.
5. Дайте определение изолированной вершины графа.
2020-09-24
1040
