Связи превращаются в граф
Граф состоит из вершин и соединяющих их рёбер.
В этом занятии
- Самостоятельно решить задачу по теме «Связи превращаются в граф» и объяснить проверку результата.
- Изобрази граф четырёх мест с временем переходов и укажи, какие дороги односторонние.
Пригодится: informatics9-table-filter
Разберёмся перед практикой+
Связи превращаются в граф
Граф состоит из вершин и соединяющих их рёбер. Вершины обозначают объекты, рёбра — выбранный вид связи. Ориентированное ребро допускает движение по указанному направлению; неориентированное — в обе стороны в модели маршрутов.
Вес ребра может означать длину, время или стоимость, поэтому подпиши единицы. Матрица весов хранит значения между парами вершин; отсутствие ребра нужно обозначать отдельно от нулевого веса. Один и тот же рисунок без подписей может описывать разные задачи.
Для A→B с весом 4 и B→C с весом 7 путь A→B→C весит 11. Обратный путь не возникает автоматически.
- Определи смысл вершин и рёбер.
- Подпиши направление и вес.
Попробуй самостоятельно
Запиши рассуждения в черновик или сделай построение на бумаге. Эти задания для самостоятельной работы: автоматической проверки и XP за них пока нет.
- Изобрази граф четырёх мест с временем переходов и укажи, какие дороги односторонние.
- Сначала предположи результат, затем проверь и объясни, что изменилось.
Источники и дальнейшее чтение
Материал изложен своими словами. Здесь можно проверить научные основания и подробнее изучить тему; часть источников — на английском.
Читай и разбирай пример в своём темпе. К практике можно перейти, когда будешь готов.