§ 15. Граф. Рёбра со стрелками

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

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

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

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

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

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

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

Стрелка меняет смысл связи, потому что ограничивает направление перехода. Если дуга ведёт из A в B, это означает, что по данной связи можно попасть из A в B, но не обязательно обратно. Такое обозначение нужно, например, для односторонних улиц и действий, которые переводят систему из одного состояния в другое. Обратный переход считают возможным лишь тогда, когда в графе есть отдельная дуга B→A.

Дуги, направленные к вершине, называют входящими, а направленные от неё — исходящими. Это различие помогает понять, откуда можно попасть в вершину и куда можно отправиться из неё. У одной вершины могут быть дуги обоих видов: одни стрелки приходят к ней, другие уходят. Например, если есть A→B и B→C, то у B есть входящая дуга из A и исходящая в C.

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

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

Обычный и ориентированный граф

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

Разбор задач

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

1. Обозначим города A, B и C тремя вершинами. Каждая вершина соответствует одному городу, поэтому дополнительных точек не требуется.

2. Перечислим пары: A и B, A и C, B и C. Соединим ребром каждую пару, так как дорога есть между всеми городами.

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

Ответ: три вершины A, B и C соединены рёбрами AB, AC и BC без стрелок.

Задача 2. Даны вершины A, B, C и связи A→B, B→C, A→C. Укажите, из каких вершин можно попасть в C за один переход, а из каких — за два. Сначала проверим, какие дуги заканчиваются в C, а затем — какие маршруты из двух дуг приводят туда.

1. За один переход можно попасть в C по дуге, которая начинается в другой вершине и сразу заканчивается в C. Такая дуга есть: A→C.

2. Для двух переходов проверим, есть ли последовательность из двух дуг. Из A можно пройти A→B, затем B→C, поэтому за два перехода в C попадают из A.

3. Проверим, не следует ли считать путь из A в C единственным способом попасть туда за два перехода. Среди заданных дуг другого маршрута из двух шагов к C нет; из B до C ведёт только одна дуга.

Ответ: за один переход в C можно попасть из A; за два перехода — из A по маршруту A→B→C.

Задача 3. Переходы между состояниями заданы дугами A→B, B→C, C→A, B→D. Можно ли попасть из A в D? Запишите маршрут и объясните, почему обратный маршрут из D в A не задан. Здесь нужно проследить разрешённые переходы, не принимая дугу за двустороннюю связь.

1. Начинаем в A. Из A задана дуга A→B, поэтому первым переходом можно попасть только в B.

2. Из B есть две дуги: B→C и B→D. Выбираем B→D и достигаем нужной вершины.

3. Чтобы проверить обратный маршрут, смотрим на дуги, выходящие из D. Таких дуг в условии нет, значит, начать обратный переход из D по заданным связям нельзя.

Ответ: попасть из A в D можно по маршруту A→B→D. Обратный маршрут из D в A не задан, потому что обратные дуги не появляются автоматически.

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

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

Ошибка — путать начало и конец дуги. На схеме легко принять вершину у наконечника за начало, особенно если смотреть на линию, не следя за стрелкой. На самом деле дуга начинается у хвоста и заканчивается у наконечника стрелки. Чтобы проверить направление, прочитайте запись как переход: A→B означает из A в B.

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

Ошибка — путать путь из нескольких дуг с одной дугой. Если из A можно попасть в B, а из B — в C, путь A→B→C существует, но прямой дуги A→C может не быть. Для каждого шага маршрута нужно найти отдельную дугу и проверить её направление. Так вы убедитесь, что переход возможен целиком, а не только на отдельных участках.

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

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

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

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