§ 17. Графы

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

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

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

Ребро графа — связь между двумя вершинами. Его изображают линией, соединяющей соответствующие точки, и называют по обозначениям концов: например, ребро AB соединяет вершины A и B. Такое обозначение позволяет точно указать, какие объекты связаны.

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

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

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

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

Вершины называют смежными, если между ними есть ребро; рёбра смежны, если у них есть общая вершина. Например, если проведены AB и BC, то вершины A и B смежны, а рёбра AB и BC тоже смежны: они встречаются в B. Эти понятия помогают описывать соседние элементы графа, не перечисляя всю схему заново.

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

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

Виды графов и способы представления

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

Разбор задач

Задача 1. Изобразите граф, в котором вершины A, B, C соединены рёбрами AB и BC. Укажите, какие вершины смежны.

1. Обозначаем на листе три вершины: A, B и C. Их можно расположить в ряд, поскольку расположение не меняет набор связей.
2. Проводим ребро между A и B, затем между B и C. Ребра AC в условии нет, поэтому соединять эти вершины не нужно.
3. Проверяем смежность: у пары вершин должна быть общая линия. Так получаем пары A и B, B и C.

Ответ: смежны вершины A и B, а также B и C. Вершины A и C не смежны, поскольку ребра между ними нет.

Задача 2. По таблице смежности для вершин A, B, C, D постройте неориентированный граф и перечислите его рёбра.

Для примера используем таблицу, где отметки стоят в ячейках A–B, A–D и C–D, а остальные ячейки не отмечены. Сначала сопоставляем каждой строке и каждому столбцу вершину с тем же обозначением. Так можно читать каждую отметку как пару объектов, которые требуется соединить.

1. На рисунке размещаем четыре вершины: A, B, C и D.
2. По отмеченным парам проводим линии AB, AD и CD. Пары B–A, D–A и D–C, если они также отмечены, повторяют уже построенные связи.
3. Сверяем каждую проведённую линию с таблицей и убеждаемся, что ни одной пары не пропустили.

Ответ: рёбра графа — AB, AD и CD. Каждую неориентированную связь записываем один раз, даже если таблица показывает её в двух симметричных ячейках.

Задача 3. Составьте ориентированный граф дорог с односторонним движением по заданному списку маршрутов и определите, можно ли попасть из A в D.

Возьмём для примера список дорог A → B, B → C, C → D и A → C. Стрелки здесь передают направление разрешённого движения, поэтому заменять их обычными линиями нельзя. Чтобы ответить на вопрос, нужно найти непрерывную последовательность стрелок, начинающуюся в A и заканчивающуюся в D.

1. Изображаем вершины A, B, C и D.
2. Проводим стрелки по списку: A → B, B → C, C → D и A → C.
3. Прослеживаем маршрут A → B → C → D. Каждая следующая стрелка начинается там, где заканчивается предыдущая, и все они направлены в нужную сторону.

Ответ: попасть из A в D можно, например, по маршруту A → B → C → D. Также в этом примере существует более короткий маршрут A → C → D.

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

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

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

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

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

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

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

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

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