11. Схема движения транспорта

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

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

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

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

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

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

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

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

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

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

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

Элементы транспортной схемы и их обозначение в графе

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

Разбор задач

Маршрут по связанным вершинам

На схеме остановка A соединена с B, а B — с C. Требуется записать путь из A в C. Нужно проверить соседние вершины и не пропустить промежуточную остановку.

1. Начинаем в вершине A.
2. По первому ребру переходим в B.
3. По следующему ребру из B переходим в C.

Ответ: маршрут A—B—C. Он состоит из двух рёбер и включает одну промежуточную вершину.

Сравнение по числу участков

Из A в C можно ехать через B или через D и E. Маршрут A—B—C состоит из двух участков, а A—D—E—C — из трёх. Сравниваем именно количество рёбер, потому что в условии не указаны их длина и время.

1. В первом маршруте считаем участки A—B и B—C: всего 2.
2. Во втором маршруте считаем A—D, D—E и E—C: всего 3.
3. Сопоставляем результаты: 2 меньше 3.

Ответ: по числу участков короче маршрут A—B—C. Это сравнение ничего не говорит о времени или расстоянии, если характеристики участков различаются.

Сравнение по расстоянию

Участок A—B имеет длину 3 км, B—C — 4 км, а прямой участок A—C — 8 км. Нужно найти путь с наименьшей общей длиной. Поэтому сравниваем суммы весов, а не только количество рёбер.

1. Для пути A—B—C складываем длины: 3 км + 4 км = 7 км.
2. Для прямого пути берём указанное значение: 8 км.
3. Сравниваем 7 км и 8 км и выбираем меньшую сумму.

Ответ: маршрут A—B—C, его длина равна 7 км. Хотя он состоит из двух участков, он короче прямого участка A—C на 1 км.

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

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

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

Маршрут с наименьшим числом участков не всегда самый быстрый. Участки могут иметь разное время или расстояние, поэтому короткая по записи цепочка окажется длиннее по весу. Сначала определите критерий задачи, а затем сравнивайте именно его.

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

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

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

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

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

• Остановка или перекрёсток в модели — вершина графа.
• Участок пути между объектами — ребро.
• Стрелка показывает разрешённое направление движения.
• Маршрут — цепочка связанных вершин и рёбер.
• Число у ребра может задавать расстояние или время.
• Оптимальный маршрут выбирают по заданному критерию, например по длине или времени.