Рёберный граф: построение, свойства и примеры

Рёберный граф помогает сменить точку зрения: интересоваться не вершинами сети, а связями между её рёбрами. Например, если рёбра обозначают участки дороги, можно исследовать, какие участки непосредственно соприкасаются на перекрёстке. Для этого каждому участку ставят в соответствие новую вершину, а две новые вершины соединяют, когда исходные участки имеют общий конец.
Попробуйте построить такой граф для звезды с разным числом лучей. Обратите внимание: все лучи встречаются в центре, поэтому каждая пара новых вершин будет соединена. Ниже разберём и менее симметричный пример, чтобы увидеть правило в действии.
Определение рёберного графа
Пусть - конечный простой неориентированный граф: в нём нет петель и кратных рёбер. Его рёберный граф обозначают . Каждому ребру исходного графа соответствует ровно одна вершина . Две разные вершины в смежны тогда и только тогда, когда соответствующие им рёбра имеют общую вершину.
Это определение используют, например, в документации NetworkX. Английское название - line graph. Важно удерживать два уровня описания: «соседство рёбер» относится к , а «соседство вершин» - к . Исходные вершины сами по себе вершинами нового графа не становятся.
Изолированная вершина исходного графа не принадлежит ни одному ребру и потому не создаёт вершину в . Напротив, изолированное ребро исходного графа создаст изолированную вершину: соприкасающихся с ним других рёбер нет.
Построение по шагам
Обозначим вершины исходного графа числами , а его рёбра - так: , , , . Запись здесь означает ребро между вершинами и , а не число двенадцать. Построим без догадок по рисунку.
- Создадим четыре новые вершины : по одной на каждое исходное ребро.
- Сравним каждую пару исходных рёбер. У и общий конец , как и у и . Соединим соответствующие пары новых вершин.
- У и тоже общий конец ; у и общий конец ; у и общий конец .
- Пара общих концов не имеет, поэтому ребра между этими новыми вершинами нет.
Итого получаем четыре вершины и пять рёбер: , , , , . Расположение точек на рисунке можно изменить: результат определяется списком смежности, а не формой линий. Проверка всех шести пар новых вершин защищает от пропущенных связей.

Сколько вершин и рёбер получится
Число вершин нового графа сразу известно: . Для числа его рёбер рассмотрим каждую исходную вершину степени . Каждая пара рёбер, выходящих из , даёт одну связь в . Таких пар , поэтому
Для простого графа два разных ребра не могут иметь два общих конца, поэтому одна и та же пара не будет посчитана дважды. В нашем примере степени вершин равны , и сумма составляет . Это совпадает с ручным перечислением. Формула не переносится без оговорок на графы с кратными рёбрами: пара параллельных рёбер имеет оба конца общими и в такой сумме учитывается дважды.
Можно проверить и степень отдельной новой вершины. Если ей соответствует исходное ребро , то рядом с ним находятся все остальные рёбра у и все остальные рёбра у :
Например, для получаем : его соседями будут , и . Здесь простота исходного графа вновь важна, чтобы не пересчитать одного соседа дважды.
Проверка через матрицу инцидентности
Для систематического вычисления удобно составить матрицу инцидентности : строки соответствуют исходным вершинам, столбцы - исходным рёбрам. В ячейке стоит единица, если вершина является концом этого ребра, и ноль в противном случае. В простом неориентированном графе каждый столбец содержит ровно две единицы.
Скалярное произведение двух разных столбцов показывает число общих концов соответствующих рёбер: оно равно единице, если они соприкасаются, и нулю, если нет. Следовательно, матрица смежности рёберного графа выражается как . Здесь - единичная матрица размера, равного числу исходных рёбер: вычитание двойки на диагонали убирает связи вершины с самой собой. В нашем примере элемент для пары равен нулю, а для - единице.
Этот способ особенно удобен, когда граф задан таблицей, а не рисунком. При ручном вычислении всё равно сохраняйте соответствие между порядком столбцов и именами рёбер: перестановка столбцов меняет порядок строк и столбцов результата, но не сам граф с точностью до переименования вершин.
Звезда, путь и цикл
У звезды есть центральная вершина и лучей. Любые два луча встречаются в центре, поэтому её рёберный граф - полный граф : каждая пара его вершин соединена. При получаем треугольник из трёх вершин и трёх рёбер; при - пять вершин и рёбер. Ползунок выше позволяет проверить оба случая и промежуточные значения.
У пути из рёбер каждое внутреннее ребро соприкасается только с предыдущим и следующим. Поэтому его рёберный граф - путь из вершин и рёбер. Для простого цикла длины не меньше трёх каждое ребро имеет ровно двух соседей, а результат снова будет циклом той же длины. Это удобные контрольные примеры для программы или ручного решения.
Не следует заключать, что по одному виду результата всегда можно восстановить исходный граф. Например, и звезда с тремя лучами, и треугольник имеют один и тот же рёберный граф - треугольник. В первом случае три ребра встречаются в одной вершине, а во втором каждая пара имеет свой общий конец.
Связь с паросочетанием и раскраской
Паросочетание в - набор рёбер, никакие два из которых не имеют общего конца. После перехода к тем же рёбрам соответствуют попарно несмежные вершины. Значит, паросочетания взаимно однозначно соответствуют независимым множествам , а размер максимального паросочетания равен размеру максимального независимого множества нового графа. Подробнее о второй задаче можно прочитать в статье про максимальное независимое множество.
Аналогично правильная раскраска рёбер исходного графа превращается в раскраску вершин : соприкасающиеся исходные рёбра должны получить разные цвета. Минимальное число цветов совпадает в этих двух постановках. О подсчёте допустимых раскрасок вершин рассказывает материал про хроматический полином графа.
Такое преобразование полезно для выбора модели, но не обязательно ускоряет вычисление: при вершинах большой степени в рёберный граф может содержать много связей. В частности, звезда с рёбрами порождает новых рёбер.
Где применяется преобразование
В модели дорог исходные вершины могут обозначать перекрёстки, а рёбра - участки между ними. Тогда вершины рёберного графа обозначают участки, а его рёбра показывают возможность перейти между участками через общий перекрёсток. Такая модель сама по себе не учитывает направление движения, запреты поворота или время проезда: их нужно добавить отдельно или выбрать другую модель.
Похожая идея полезна для сетей зависимостей между операциями, если отношения действительно задаются общим концом исходных рёбер. После построения нового графа по нему можно выполнять обычные алгоритмы, например обход в ширину, чтобы считать число переходов между участками. Для ориентированных графов правило соседства нужно определить отдельно: в NetworkX для дуг учитывается последовательный переход от конца первой дуги к началу второй.
На практике храните отображение от каждой новой вершины к исходному ребру. Без него ответ алгоритма будет трудно перевести обратно в термины исходной задачи. Если задача связана с назначением объектов, полезно сравнить её с алгоритмом Куна для паросочетаний: там прямой алгоритм для подходящего исходного графа может оказаться удобнее явного построения .
Частые ошибки
- Создавать новые вершины для исходных вершин. В вершины соответствуют именно рёбрам .
- Соединять исходные рёбра за пересечение на рисунке. Пересечение считается общей вершиной только тогда, когда оно действительно задано вершиной графа.
- Пропускать пары у вершины степени три и выше. При трёх инцидентных рёбрах возникают три пары, а не две.
- Применять формулу суммы без условий. Для кратных рёбер и петель сначала уточните определение и способ подсчёта.
FAQ
Может ли рёберный граф быть пустым?
Да. Если в исходном графе нет рёбер, у его рёберного графа нет вершин. Изолированные исходные вершины на результат не влияют.
Всегда ли связный граф даёт связный рёберный граф?
Если исходный неориентированный граф связен и содержит хотя бы одно ребро, его рёберный граф связен: между любыми двумя исходными рёбрами можно пройти цепочкой попарно соприкасающихся рёбер.
Чем рёберный граф отличается от двойственного плоского графа?
В рёберном графе вершины представляют исходные рёбра. В плоском двойственном графе вершины представляют грани конкретного плоского вложения. Это разные конструкции.
Коротко
Рёберный граф заменяет каждое ребро исходного графа вершиной и соединяет новые вершины при общей исходной вершине. Для простого графа число новых рёбер находят суммированием по вершинам. Такая смена представления связывает задачи о рёбрах, в том числе паросочетание и рёберную раскраску, с задачами о вершинах.
Читайте также

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

Гиперграф: что это такое и как его построить
Гиперграф простыми словами: вершины, гиперрёбра и матрица инцидентности. Разбираем пример, степени вершин, связь с обычным графом и области применения.

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

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

Теорема Форда-Фалкерсона о максимальном потоке
Теорема Форда-Фалкерсона связывает максимальный поток и минимальный разрез. Разбираем доказательство через остаточную сеть, пример и проверку решения.

Теорема Кёнига: двудольный граф, паросочетания и покрытия
Теорема Кёнига для двудольного графа: почему максимальное паросочетание равно минимальному вершинному покрытию. Формулировка, доказательство, пример и связь с теоремой Холла.