§ 44. Графы

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

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

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

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

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

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

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

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

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

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

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

Основные понятия и способы описания графа

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

Разбор задач

Задача 1. Степени вершин

Условие: дан неориентированный граф с вершинами A, B, C, D и рёбрами AB, AC, BC, CD. Перечислите вершины и рёбра и найдите степени всех вершин. Важно пройти по каждому ребру и отметить оба его конца, иначе легко пропустить вклад связи в степень.

1. Выписываем вершины: A, B, C, D; рёбра: AB, AC, BC, CD.
2. Считаем инцидентные рёбра: к A относятся AB и AC, к B — AB и BC.
3. К C относятся AC, BC и CD, к D — только CD.

Ответ: степени вершин равны deg(A) = 2, deg(B) = 2, deg(C) = 3, deg(D) = 1. Проверка: сумма степеней равна 8, то есть вдвое больше числа рёбер — четырёх. Это подтверждает подсчёт для данного графа без петель.

Задача 2. Список смежности и матрица

Условие: дороги соединяют пункты A—B, A—C и B—C; все дороги двусторонние. Запишите граф списками смежности и матрицей смежности. Сначала договоримся о порядке вершин A, B, C, чтобы строки и столбцы матрицы соответствовали одному и тому же порядку.

1. Для A соседями будут B и C; для B — A и C; для C — A и B.
2. Создаём матрицу 3 × 3 и ставим 1, если пара соединена дорогой, иначе 0.
3. На главной диагонали ставим 0, поскольку дорог из пункта в него самого нет.

Ответ: списки смежности — A: B, C; B: A, C; C: A, B. Матрица по порядку A, B, C: строки 0 1 1; 1 0 1; 1 1 0. Она симметрична, потому что каждая дорога двусторонняя.

Задача 3. Маршрут минимального веса

Условие: в графе дорог есть маршруты A—B—D с весами 4 и 7, A—C—D с весами 3 и 5, а также прямой путь A—D с весом 11. Найдите маршрут из A в D с наименьшей суммой весов. Сравнивать нужно именно суммарную длину, а не только число участков.

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

Ответ: маршрут A—C—D, его суммарный вес равен 8. Хотя он состоит из двух рёбер, это не мешает ему быть короче по весу, чем прямой участок. Решение опирается на характеристики дорог, а не на их количество.

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

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

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

В матрице неориентированного графа нельзя отметить связь только в одном направлении: такая матрица должна быть симметричной относительно главной диагонали. Ошибка появляется, когда заполняют строку одной вершины и забывают соответствующую ячейку в строке другой. Сверьте ячейки aᵢⱼ и aⱼᵢ для каждой пары. Если связь есть, обе должны показывать её наличие.

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

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

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

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

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

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