10. Новый взгляд на схемы путей

Определения и обозначения

Граф — модель, в которой объекты изображаются вершинами, а связи между ними — рёбрами. Например, пункты можно заменить точками, а дороги — линиями между ними. Граф нужен, чтобы изучать маршруты без лишних деталей настоящей карты.

Вершина графа — точка, обозначающая объект или место на схеме путей. Это может быть не только остановка, но и город, перекрёсток, компьютер или любой другой объект. По вершинам определяют, откуда начинается и где заканчивается переход.

Ребро графа — линия или стрелка, показывающая связь или возможность перехода между вершинами. Линия обычно означает переход в обе стороны, а стрелка задаёт одно разрешённое направление. По рёбрам проверяют, какие объекты непосредственно связаны.

Путь в графе — последовательность вершин, соединённых рёбрами, по которой можно пройти от начальной вершины к конечной. Каждая следующая вершина должна быть достижима из предыдущей. Это понятие позволяет записывать и сравнивать маршруты.

Как это устроено

Обычная схема может содержать названия улиц, форму зданий, условные значки и другие подробности. Для построения графа оставляют только то, что влияет на переход: точки объектов и соединения между ними. Такое упрощение нужно, чтобы быстро увидеть структуру маршрутов и не потерять связи среди лишней информации.

Направление движения обозначают стрелкой, потому что одна и та же дорога может разрешать движение только в одну сторону. Если стрелки нет, в простейшей схеме переход обычно возможен в обоих направлениях. Поэтому при чтении ориентированного графа нельзя автоматически считать обратный переход разрешённым.

Путь читают слева направо или от начальной вершины к конечной, последовательно называя все посещённые вершины. Между каждой парой соседних вершин должно быть ребро, а при наличии стрелки нужно совпадение с её направлением. Если хотя бы один переход отсутствует или выполнен против стрелки, записанная последовательность не является допустимым путём.

Подпись на ребре добавляет к связи числовое свойство: расстояние, время, цену или другое значение. Она нужна, когда вариантов перехода несколько и их требуется сравнить не только по существованию. При движении по пути такие значения складывают, чтобы получить общую длину, стоимость или продолжительность маршрута.

Для выбора маршрута сначала находят все подходящие варианты или те из них, которые удалось построить по схеме. Затем для каждого варианта проверяют переходы и вычисляют сумму подписей рёбер. Побеждает путь, который лучше соответствует условию: имеет наименьшую длину, стоимость или время, а иногда — наибольшую пропускную способность.

Элементы и свойства схемы путей как графа

Таблица помогает переводить изображение схемы в язык графов. Сначала находят точки и соединения, затем проверяют стрелки и подписи. После этого можно записывать пути и считать их общую длину или стоимость.

Разбор задач

Задача 1. На схеме есть точки A, B, C и D, соединённые линиями AB, AC, BC и CD. Нужно назвать вершины и рёбра графа. Схема дана без стрелок, поэтому каждую линию рассматриваем как связь в обе стороны.

1. Выписываем все обозначенные точки: A, B, C и D.
2. Проверяем каждую линию и записываем соединённые ею пары: AB, AC, BC и CD.
3. Отделяем объекты от связей: точки становятся вершинами, а линии — рёбрами.

Ответ: вершины — A, B, C, D; рёбра — AB, AC, BC, CD. Например, последовательность A–C–D является допустимым путём.

Задача 2. Ориентированный граф имеет стрелки A → B, A → C, B → D, C → D и C → B. Нужно перечислить все пути из A в D. Обратные переходы по стрелкам не разрешены.

1. Из A можно перейти в B или C, поэтому начинаем с двух вариантов.
2. После B доступно D, получаем путь A–B–D.
3. После C доступны D и B: это дают пути A–C–D и A–C–B–D.

Ответ: существуют три пути: A–B–D, A–C–D и A–C–B–D. Переход, например, D–B не добавляем, потому что стрелка B → D направлена в обратную сторону.

Задача 3. Между пунктами проложены маршруты: A–B = 5 км, A–C = 2 км, C–B = 1 км, B–D = 4 км и C–D = 8 км. Требуется найти кратчайший путь из A в D. Сравниваем не количество рёбер, а сумму расстояний.

1. Путь A–B–D имеет длину 5 + 4 = 9 км.
2. Путь A–C–D имеет длину 2 + 8 = 10 км.
3. Путь A–C–B–D имеет длину 2 + 1 + 4 = 7 км.

Ответ: кратчайший маршрут — A–C–B–D, его длина равна 7 км. Хотя в нём три ребра, он короче маршрута из двух рёбер A–B–D.

Типичные ошибки

Считать вершинами только остановки. Вершиной может быть любой объект, изображённый отдельной точкой, например перекрёсток или компьютер. Проверьте все узлы схемы, а не только знакомые места.

Идти против стрелки. Так ошибаются, когда воспринимают ребро как обычную линию без направления. Сверяйте каждый переход со стрелкой и мысленно двигайтесь только по её направлению.

Называть путём несвязанные точки. В последовательности могут оказаться вершины, между которыми нет ребра. Для проверки рассмотрите каждую соседнюю пару и найдите соединяющую её линию или стрелку.

Выбирать маршрут по числу рёбер. Коротким по количеству переходов маршрут может оказаться длиннее или дороже. Сложите подписи всех рёбер и сравните именно получившиеся суммы.

Связь с другими темами

До изучения графов нужно уметь читать схемы, понимать условные обозначения и выполнять переходы между связанными объектами. Эти навыки помогают не путать вершины с рёбрами и правильно учитывать стрелки.

Графы применяются при составлении алгоритмов поиска маршрута, а также при описании транспортных и компьютерных сетей. С их помощью можно формально представить дороги, соединения устройств и возможные действия.

Понятие графа станет основой для изучения поиска кратчайшего пути и других алгоритмов на графах. Позже схемы можно будет исследовать уже не только вручную, но и с помощью программ.

Что запомнить

• Граф состоит из вершин и рёбер.
• Вершины изображают объекты, а рёбра — связи между ними.
• Стрелка задаёт направление перехода.
• Путь — это последовательность связанных вершин.
• Подписи на рёбрах могут задавать расстояние, время или стоимость.
• Кратчайший путь определяется суммой весов рёбер, а не обязательно их количеством.