Задание: В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую таблице.
ПРАКТИЧЕСКАЯ РАБОТА №10
Тема: Построение графа по условиям ситуационных задач: в управлении инфраструктурами на транспорте; в структуре взаимодействия различных видов транспорта.
Цель работы: Закрепить и систематизировать знания по теме: «Основы дискретной математики».
Задание: Выберите верный вариант определения понятия
1. Граф – это …
c один из способов графического представления информации, отражающий количество объектов изучаемой системы и взаимосвязи между ними;
c воинское звание в средние века;
c способ представления данных в табличной форме;
c модель, реализованная на компьютере средствами программного обеспечения.
2. Порядком графа называется…
c количество ребер графа;
c количество кратных ребер графа;
c количество вершин графа;
c количество концевых вершин графа.
3. Цикл – это …
c путь, в котором первая и последняя вершина совпадают;
c путь, в котором первая и последняя вершина не совпадают;
c количество ребер пути;
c количество вершин пути.
4. Размером графа называется...
c количество ребер графа;
c количество кратных ребер графа;
c количество вершин графа;
c количество концевых вершин графа.
5. Путем в графе называют…
c последовательность ребер графа, в которой конец одного ребра служит началом следующего;
c последовательность ребер графа, в которой первая и последняя вершины совпадают;
c конечную последовательность вершин, каждая из которых (кроме последней) соединена со следующей вершиной ребром;
|
|
|
c перечень всех вершин графа.
6. Деревом называют…
c граф, в котором существует один-единственный путь между любой парой вершин и не имеется ни одного цикла;
c граф, в котором связи между любыми парами концевых вершин являются двунаправленными;
c граф, полученный из исходного графа путем смены направлений ребер на противоположные;
c путь, в котором первая и последняя вершина совпадают.
Задание: На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
7.
8.
9.
10. 
11.
12.
Задание:
13. Путешественник пришел в 08:00 на автостанцию поселка ЛЕСНОЕ и увидел следующее расписание автобусов:
Отправление из Прибытие в Время отправления Время прибытия
ЛЕСНОЕ ОЗЕРНОЕ 07:45 08:55
ЛУГОВОЕ ЛЕСНОЕ 08:00 09:10
ПОЛЕВОЕ ЛЕСНОЕ 08:55 11:25
|
|
|
ПОЛЕВОЕ ЛУГОВОЕ 09:10 10:10
ЛЕСНОЕ ПОЛЕВОЕ 09:15 11:45
ОЗЕРНОЕ ПОЛЕВОЕ 09:15 10:30
ЛЕСНОЕ ЛУГОВОЕ 09:20 10:30
ОЗЕРНОЕ ЛЕСНОЕ 09:25 10:35
ЛУГОВОЕ ПОЛЕВОЕ 10:40 11:40
ПОЛЕВОЕ ОЗЕРНОЕ 10:45 12:00
Определите самое раннее время, когда путешественник сможет оказаться в пункте ПОЛЕВОЕ согласно этому расписанию.
1) 10:30 2) 11:25 3)11:40 4) 11:45
14. Путешественник пришел в 08:00 на автостанцию поселка КАЛИНИНО и увидел следующее расписание автобусов:
Отправление из Прибытие в Время отправления Время прибытия
КАМЫШИ КАЛИНИНО 08:15 09:10
КАЛИНИНО БУКОВОЕ 09:10 10:15
РАКИТИНО КАМЫШИ 10:00 11:10
|
|
|
РАКИТИНО КАЛИНИНО 10:05 12:25
РАКИТИНО БУКОВОЕ 10:10 11:15
КАЛИНИНО РАКИТИНО 10:15 12:35
КАЛИНИНО КАМЫШИ 10:20 11:15
БУКОВОЕ КАЛИНИНО 10:35 11:40
КАМЫШИ РАКИТИНО 11:25 12:30
БУКОВОЕ РАКИТИНО 11:40 12:40
Определите самое раннее время, когда путешественник сможет оказаться в пункте РАКИТИНО согласно этому расписанию.
1) 12:25 2) 12:30 3)12:35 4) 12:40
15. Между четырьмя местными аэропортами: ВОСТОРГ, ЗАРЯ, ОЗЕРНЫЙ и ГОРКА, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:
Аэропорт вылета Аэропорт прилета Время вылета Время прилета
ВОСТОРГ ГОРКА 13:10 17:15
ОЗЕРНЫЙ ЗАРЯ 13:00 14:30
|
|
|
ОЗЕРНЫЙ ВОСТОРГ 12:10 14:20
ГОРКА ОЗЕРНЫЙ 11:15 15:30
ВОСТОРГ ОЗЕРНЫЙ 12:35 14:50
ЗАРЯ ОЗЕРНЫЙ 12:30 14:20
ВОСТОРГ ЗАРЯ 10:30 12:15
ЗАРЯ ГОРКА 14:40 16:45
ГОРКА ЗАРЯ 15:15 17:20
ОЗЕРНЫЙ ГОРКА 14:30 16:20
Путешественник оказался в аэропорту ВОСТОРГ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт ГОРКА.
1) 13:10 2) 16:20 3)16:45 4) 17:15
16. Путешественник пришел в 08:00 на автостанцию поселка ОЛЬГИНО и увидел следующее расписание автобусов:
Отправление из Прибытие в Время отправления Время прибытия
САВВИНО ОЛЬГИНО 07:10 08:25
ОЛЬГИНО ПАВЛИНО 07:30 08:40
ПАВЛИНО КУЧИНО 07:50 09:00
ОЛЬГИНО КУЧИНО 09:15 10:20
ПАВЛИНО САВВИНО 09:15 10:25
ОЛЬГИНО САВВИНО 09:30 10:30
ПАВЛИНО ОЛЬГИНО 09:30 10:45
КУЧИНО ПАВЛИНО 10:10 11:20
САВВИНО ПАВЛИНО 11:05 12:15
КУЧИНО ОЛЬГИНО 11:30 12:40
Определите самое раннее время, когда путешественник сможет оказаться в пункте ПАВЛИНО согласно этому расписанию.
1) 08:40 2) 10:45 3)11:20 4) 12:15
17. Путешественник пришел в 08:00 на автостанцию поселка ЧЕРНОЕ и увидел следующее расписание автобусов:
Отправление из Прибытие в Время отправления Время прибытия
СВЕТЛОЕ ЧЕРНОЕ 06:15 08:55
КРАСНОЕ ЛАЗАРЕВО 07:15 09:45
ЧЕРНОЕ КРАСНОЕ 07:30 11:40
ЧЕРНОЕ ЛАЗАРЕВО 08:25 10:45
КРАСНОЕ СВЕТЛОЕ 09:05 10:25
ЧЕРНОЕ СВЕТЛОЕ 09:10 11:50
ЛАЗАРЕВО КРАСНОЕ 10:30 13:00
ЛАЗАРЕВО ЧЕРНОЕ 11:05 13:45
СВЕТЛОЕ КРАСНОЕ 12:10 13:25
КРАСНОЕ ЧЕРНОЕ 13:10 17:25
Определите самое раннее время, когда путешественник сможет оказаться в пункте КРАСНОЕ согласно этому расписанию.
1) 11:40 2) 13:00 3)13:10 4) 13:25
18. Путешественник пришел в 08:00 на автостанцию поселка ЛИСЬЕ и увидел следующее расписание автобусов:
Отправление из Прибытие в Время отправления Время прибытия
ЛИСЬЕ ЗАЙЦЕВО 07:50 09:05
СОБОЛЕВО ЛИСЬЕ 08:55 10:05
ЕЖОВО ЛИСЬЕ 09:05 10:15
ЗАЙЦЕВО ЕЖОВО 10:00 11:10
ЛИСЬЕ СОБОЛЕВО 10:15 11:30
ЛИСЬЕ ЕЖОВО 10:45 12:00
ЗАЙЦЕВО ЛИСЬЕ 11:05 12:15
СОБОЛЕВО ЗАЙЦЕВО 11:10 12:15
ЕЖОВО ЗАЙЦЕВО 12:15 13:25
ЗАЙЦЕВО СОБОЛЕВО 12:45 13:55
Определите самое раннее время, когда путешественник сможет оказаться в пункте ЗАЙЦЕВО согласно этому расписанию.
1) 9:05 2) 12:15 3)12:25 4) 13:25
Задание: В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую таблице.
19.
| A | B | C | D | E | |
| A | 2 | 4 | 1 | ||
| B | 2 | ||||
| C | 4 | 5 | |||
| D | 1 | 4 | |||
| E | 5 | 4 |
| 1) | 2) | 3) | 4) |
 
| 
| 
| 
|
| A | B | C | D | |
| A | 4 | 5 | ||
| B | 4 | 3 | 6 | |
| C | 3 | |||
| D | 5 | 6 |
20.
| 1) | 2) | 3) | 4) |
| 
| 
| 
|
21.
| A | B | C | D | |
| A | 1 | 2 | ||
| B | 2 | 3 | ||
| C | 1 | 2 | 5 | |
| D | 2 | 3 | 5 |
| 1) | 2) | 3) | 4) |
| 
| 
|  
|
| A | B | C | D | |
| A | 3 | 1 | ||
| B | 3 | 2 | 1 | |
| C | 2 | 4 | ||
| D | 1 | 1 | 4 |
22.
| 1) | 2) | 3) | 4) |
| 
| 
| 
|
| A | B | C | D | E | |
| A | 1 | 4 | 1 | ||
| B | 1 | 2 | |||
| C | 4 | 2 | 3 | ||
| D | 3 | ||||
| E | 1 |
23.
| 1) | 2) | 3) | 4) |
| 
|  
|  
|
24. 
1) 
2) 
3) 
4) 
Задание: В таблицах приведена протяженность автомагистралей между соседними населенными пунктами. Если пересечение строки и столбца пусто, то соответствующие населенные пункты не соединены автомагистралями. Протяженность маршрута складывается из протяженности автомагистралей между соответствующими соседними населенными пунктами. При этом через любой насеченный пункт маршрут должен проходить не более одного раза.
Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта А до пункта С не больше 5». Протяженность маршрута складывается из протяженности автомагистралей между соответствующими соседними населенными пунктами. При этом любой населенный пункт должен встречаться на маршруте не более одного раза.
| 1) | 2) | 3) | 4) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
26. Укажите таблицу, для которой выполняется условие «Минимальная стоимость перевозки грузов от пункта А до пункта В не больше 3».
| 1) | 2) | 3) | 4) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
27. Укажите номер таблицы, для которой выполняется условие «Максимальная стоимость перевозки грузов от пункта В до пункта D не больше 6».
| 1) | 2) | 3) | 4) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
28. Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта А до пункта С не больше 6».
| 1) | 2) | 3) | 4) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
29. Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта C до пункта B не больше 6».
| 1) | 2) | 3) | 4) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
30. Укажите номер таблицы, для которой выполняется условие «Максимальная стоимость перевозки грузов от пункта В до пункта D не больше 6».
| 1) | 2) | 3) | 4) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
Пояснения к работе:
Необходимые формулы:
Граф- это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Вершины, прилегающие к одному и тому же ребру, называются смежными.
Если ребра ориентированны, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом.
Если ребра не имеют ориентации, граф называется неориентированным.
Петля- это дуга, начальная и конечная вершина которой совпадают.
Простой граф- граф без кратных ребер и петель.
Степень вершины- это удвоенное количество петель, находящихся у этой вершины плюс количество остальных прилегающих к ней ребер.
Пустым называется граф без ребер.
Полным называется граф, в котором каждые две вершины смежные.
Путь в ориентированном графе — это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Маршрут в графе путь, ориентацией дуг которого можно пренебречь.
Цепь- маршрут, в котором все ребра попарно различны.
Цикл- замкнутый маршрут, являющийся цепью.
Граф называется связным, если любая пара его вершин связана.
Дерево — это связный граф без циклов.
Содержание отчета
1. Титульный лист в соответствии с СТП1.2-2005.
2. Цель работы
3. Задание
4. Выполненная практическая работа в соответствии с заданием
5. Ответы на контрольные вопросы
6. Вывод
Контрольные вопросы:
1. Дайте определение ориентированного графа.
2. Сформулируйте понятие смежных ребер.
3. Дайте определение правильного графа.
4. Запишите формулу суммы степеней графа.
5. Дайте определение изолированной вершины графа.
ПРАКТИЧЕСКАЯ РАБОТА №11
Тема: Построение графа по условиям ситуационных задач: в формировании технологического цикла оказания услуг на транспорте.
Цель работы: Закрепить и систематизировать знания по теме: «Основы дискретной математики».
Форма выполнения задания: реферат
Подготовить рефераты на следующие темы:
1. Графы в электротехнике.
2. Особенности применения теории графов в образовании.
3. Применение теории графов в экономике.
4. Сетевое планирование и управление комплексом работ.
5. Применение теории графов в кодировании и декодировании.
6. Графы в архитектурном проектировании.
7. Применение теории графов в информатике.
8. Теория графов в алгоритме ссылочного ранжирования.
9. Теория графов и социальные сети.
10. Теория графов в логистике.
Пояснения к работе:
Дата добавления: 2020-11-23; просмотров: 600; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!