Договариваемся о том, как надо соединять две фигурки.

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

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

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

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

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

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

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

Соединение между двумя вершинами проводят только тогда, когда между соответствующими объектами есть нужная связь. Линия не является украшением: она добавляет в описание конкретное отношение. Поэтому перед каждым соединением полезно спросить себя, подтверждается ли оно условием.

Если связь взаимная, её можно показать неориентированным соединением; если важен переход от одного объекта к другому — стрелкой. Обычная линия подходит, например, для связи «города соединены дорогой», когда рассматривается сам факт соединения. Стрелка нужна для отношений «из пункта A в пункт B», «сообщение отправлено от A к B» или «A указывает на B».

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

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

Как читать соединения между вершинами

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

Разбор задач

Задача 1

Условие: на схеме нужно показать, что два объекта связаны взаимно. Выберите подходящее соединение и объясните выбор.

1. Определяем, что связь действует между объектами без выделения направления.
2. Выбираем обычную линию без стрелки.
3. Соединяем ею две вершины и проверяем, что линия не указывает движение от одной вершины к другой.

Ответ: нужно использовать неориентированное ребро. Оно показывает сам факт взаимной связи, не назначая начало и конец.

Задача 2

Условие: даны вершины «дом» и «школа». Покажите стрелкой путь «из дома в школу» и подпишите, как читать соединение.

1. Находим объект, от которого начинается путь: это «дом».
2. Проводим соединение к вершине «школа».
3. Ставим остриё стрелки у вершины «школа», чтобы стрелка шла от дома к школе.

Ответ: дом → школа. Соединение читается так: «из дома в школу»; начало стрелки находится у дома, остриё — у школы.

Задача 3

Условие: по списку пар объектов постройте схему: одни связи взаимные, другие направленные. Проверьте, не добавлены ли лишние соединения.

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

Ответ: схема верна, если тип и направление каждого соединения совпадают с условием, а лишних линий нет.

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

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

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

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

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

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

До этой темы нужно уметь выделять объекты и связи между ними в описании ситуации. Например, в тексте следует отличать сами города от отношений «между городами есть дорога» или «из одного города можно попасть в другой».

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

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

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