§ 52. Способы представления графов

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

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

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

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

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

Список рёбер — перечень пар вершин, соединённых рёбрами, при необходимости с указанием веса ребра. Например, запись (A, B, 5) может означать ребро между A и B с весом 5. Такой формат кратко хранит сами связи и их дополнительные характеристики.

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

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

Чтобы построить матрицу смежности, сначала задают единый порядок вершин, например A, B, C, и используют его и для строк, и для столбцов. Для каждого ребра отмечают ячейку на пересечении его концов, а пустые связи обозначают нулём. В неориентированном графе ребро AB означает связь в обе стороны, поэтому отмечают и ячейку (A, B), и (B, A); отсюда возникает симметрия матрицы.

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

Матрицу инцидентности строят иначе: сначала каждому ребру назначают отдельный столбец, а затем отмечают в нём его концы. Для неориентированного ребра отмечают обе вершины, с которыми оно соединено; так видно, какие именно вершины относятся к каждому ребру. В ориентированном графе направление нужно сохранить отдельно: часто в столбце ставят −1 у начала дуги и +1 у конца, но конкретное соглашение следует указать и применять последовательно.

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

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

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

Разбор задач

Задача 1. Для графа с вершинами A, B, C и рёбрами AB и BC составьте матрицу смежности. Граф неориентированный, поэтому каждое ребро соединяет вершины в обе стороны. Нужно расположить вершины одинаково по строкам и столбцам и отметить все существующие связи.

1. Выбираем порядок A, B, C для строк и столбцов. Это позволяет каждой ячейке однозначно соответствовать паре вершин.
2. Ребро AB отмечаем единицами в ячейках (A, B) и (B, A), а ребро BC — в ячейках (B, C) и (C, B). Петли нет, поэтому на главной диагонали стоят нули.
3. Связи AC нет, значит, ячейки (A, C) и (C, A) тоже содержат нули. Проверяем, что матрица симметрична, как и должна быть у неориентированного графа.

Ответ: матрица смежности имеет вид: строки и столбцы A, B, C; строка A — 0, 1, 0; строка B — 1, 0, 1; строка C — 0, 1, 0.

Задача 2. Для ориентированного графа с дугами A→B, C→A и B→C составьте списки смежности. Здесь важно перечислить не всех соседей, а только конечные вершины дуг, выходящих из каждой вершины. Поэтому направление проверяем отдельно для каждого начала дуги.

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

Ответ: A: B; B: C; C: A. Например, A не записывают в список B, поскольку дуги B→A в условии нет.

Задача 3. Взвешенный граф задан парами вершин и весами; требуется представить его списком смежности и матрицей смежности, а затем сравнить форматы для разреженного графа. Обозначим число вершин через n, а число рёбер — через m. Так как конкретные пары и веса не заданы, запишем общий порядок действий и сравним объём хранения.

1. Для каждого ребра (u, v, w) добавляем в список смежности вершины u запись о v с весом w; для неориентированного графа такую запись добавляют также в список v о u.
2. В матрице смежности в ячейке (u, v) записываем w, а в ячейках без ребра — принятую отметку отсутствия связи. Для неориентированного графа вес отражают в обеих симметричных ячейках.
3. Сравниваем хранение: матрица требует порядка n² ячеек, а список смежности — порядка n + m записей (в неориентированном случае каждое ребро обычно встречается дважды).

Ответ: веса сохраняются рядом с соответствующими соседями или в ячейках матрицы. При малом m относительно n² список смежности обычно компактнее для разреженного графа.

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

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

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

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

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

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

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

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

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