EssayAI
Блог
Блог
Естественные науки

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

8 ноября 2026Время чтения: 8 минут
#рёберный граф#теория графов#смежность рёбер#паросочетание#дискретная математика
Рёберный граф: построение, свойства и примеры

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

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

Определение рёберного графа

Пусть G=(V,E)G=(V,E) - конечный простой неориентированный граф: в нём нет петель и кратных рёбер. Его рёберный граф обозначают L(G)L(G). Каждому ребру исходного графа соответствует ровно одна вершина L(G)L(G). Две разные вершины в L(G)L(G) смежны тогда и только тогда, когда соответствующие им рёбра GG имеют общую вершину.

Это определение используют, например, в документации NetworkX. Английское название - line graph. Важно удерживать два уровня описания: «соседство рёбер» относится к GG, а «соседство вершин» - к L(G)L(G). Исходные вершины сами по себе вершинами нового графа не становятся.

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

Изолированная вершина исходного графа не принадлежит ни одному ребру и потому не создаёт вершину в L(G)L(G). Напротив, изолированное ребро исходного графа создаст изолированную вершину: соприкасающихся с ним других рёбер нет.

Построение по шагам

Обозначим вершины исходного графа числами 1,2,3,41,2,3,4, а его рёбра - так: p1=12p_1=12, p2=23p_2=23, p3=24p_3=24, p4=34p_4=34. Запись 1212 здесь означает ребро между вершинами 11 и 22, а не число двенадцать. Построим L(G)L(G) без догадок по рисунку.

  1. Создадим четыре новые вершины p1,p2,p3,p4p_1,p_2,p_3,p_4: по одной на каждое исходное ребро.
  2. Сравним каждую пару исходных рёбер. У p1p_1 и p2p_2 общий конец 22, как и у p1p_1 и p3p_3. Соединим соответствующие пары новых вершин.
  3. У p2p_2 и p3p_3 тоже общий конец 22; у p2p_2 и p4p_4 общий конец 33; у p3p_3 и p4p_4 общий конец 44.
  4. Пара p1,p4p_1,p_4 общих концов не имеет, поэтому ребра между этими новыми вершинами нет.

Итого получаем четыре вершины и пять рёбер: p1p2p_1p_2, p1p3p_1p_3, p2p3p_2p_3, p2p4p_2p_4, p3p4p_3p_4. Расположение точек на рисунке можно изменить: результат определяется списком смежности, а не формой линий. Проверка всех шести пар новых вершин защищает от пропущенных связей.

Четырём исходным рёбрам соответствуют четыре вершины рёберного графа; пять пар исходных рёбер имеют общий конец
Четырём исходным рёбрам соответствуют четыре вершины рёберного графа; пять пар исходных рёбер имеют общий конец

Сколько вершин и рёбер получится

Число вершин нового графа сразу известно: ∣V(L(G))∣=∣E(G)∣|V(L(G))|=|E(G)|. Для числа его рёбер рассмотрим каждую исходную вершину vv степени dG(v)d_G(v). Каждая пара рёбер, выходящих из vv, даёт одну связь в L(G)L(G). Таких пар (dG(v)2)\binom{d_G(v)}{2}, поэтому

∣E(L(G))∣=∑v∈V(G)(dG(v)2).|E(L(G))|=\sum_{v\in V(G)}\binom{d_G(v)}{2}.

Для простого графа два разных ребра не могут иметь два общих конца, поэтому одна и та же пара не будет посчитана дважды. В нашем примере степени вершин равны 1,3,2,21,3,2,2, и сумма составляет 0+3+1+1=50+3+1+1=5. Это совпадает с ручным перечислением. Формула не переносится без оговорок на графы с кратными рёбрами: пара параллельных рёбер имеет оба конца общими и в такой сумме учитывается дважды.

Можно проверить и степень отдельной новой вершины. Если ей соответствует исходное ребро uvuv, то рядом с ним находятся все остальные рёбра у uu и все остальные рёбра у vv:

dL(G)(uv)=dG(u)+dG(v)−2.d_{L(G)}(uv)=d_G(u)+d_G(v)-2.

Например, для p2=23p_2=23 получаем 3+2−2=33+2-2=3: его соседями будут p1p_1, p3p_3 и p4p_4. Здесь простота исходного графа вновь важна, чтобы не пересчитать одного соседа дважды.

Проверка через матрицу инцидентности

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

Скалярное произведение двух разных столбцов показывает число общих концов соответствующих рёбер: оно равно единице, если они соприкасаются, и нулю, если нет. Следовательно, матрица смежности рёберного графа выражается как BTB−2IB^{T}B-2I. Здесь II - единичная матрица размера, равного числу исходных рёбер: вычитание двойки на диагонали убирает связи вершины с самой собой. В нашем примере элемент для пары p1,p4p_1,p_4 равен нулю, а для p2,p4p_2,p_4 - единице.

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

Звезда, путь и цикл

У звезды K1,kK_{1,k} есть центральная вершина и kk лучей. Любые два луча встречаются в центре, поэтому её рёберный граф - полный граф KkK_k: каждая пара его вершин соединена. При k=3k=3 получаем треугольник из трёх вершин и трёх рёбер; при k=5k=5 - пять вершин и (52)=10\binom{5}{2}=10 рёбер. Ползунок выше позволяет проверить оба случая и промежуточные значения.

У пути из m≥1m\geq 1 рёбер каждое внутреннее ребро соприкасается только с предыдущим и следующим. Поэтому его рёберный граф - путь из mm вершин и m−1m-1 рёбер. Для простого цикла длины не меньше трёх каждое ребро имеет ровно двух соседей, а результат снова будет циклом той же длины. Это удобные контрольные примеры для программы или ручного решения.

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

Связь с паросочетанием и раскраской

Паросочетание в GG - набор рёбер, никакие два из которых не имеют общего конца. После перехода к L(G)L(G) тем же рёбрам соответствуют попарно несмежные вершины. Значит, паросочетания GG взаимно однозначно соответствуют независимым множествам L(G)L(G), а размер максимального паросочетания равен размеру максимального независимого множества нового графа. Подробнее о второй задаче можно прочитать в статье про максимальное независимое множество.

Аналогично правильная раскраска рёбер исходного графа превращается в раскраску вершин L(G)L(G): соприкасающиеся исходные рёбра должны получить разные цвета. Минимальное число цветов совпадает в этих двух постановках. О подсчёте допустимых раскрасок вершин рассказывает материал про хроматический полином графа.

Такое преобразование полезно для выбора модели, но не обязательно ускоряет вычисление: при вершинах большой степени в GG рёберный граф может содержать много связей. В частности, звезда с kk рёбрами порождает k(k−1)/2k(k-1)/2 новых рёбер.

Где применяется преобразование

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

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

На практике храните отображение от каждой новой вершины к исходному ребру. Без него ответ алгоритма будет трудно перевести обратно в термины исходной задачи. Если задача связана с назначением объектов, полезно сравнить её с алгоритмом Куна для паросочетаний: там прямой алгоритм для подходящего исходного графа может оказаться удобнее явного построения L(G)L(G).

Частые ошибки

  • Создавать новые вершины для исходных вершин. В L(G)L(G) вершины соответствуют именно рёбрам GG.
  • Соединять исходные рёбра за пересечение на рисунке. Пересечение считается общей вершиной только тогда, когда оно действительно задано вершиной графа.
  • Пропускать пары у вершины степени три и выше. При трёх инцидентных рёбрах возникают три пары, а не две.
  • Применять формулу суммы без условий. Для кратных рёбер и петель сначала уточните определение и способ подсчёта.

FAQ

Может ли рёберный граф быть пустым?

Да. Если в исходном графе нет рёбер, у его рёберного графа нет вершин. Изолированные исходные вершины на результат не влияют.

Всегда ли связный граф даёт связный рёберный граф?

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

Чем рёберный граф отличается от двойственного плоского графа?

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

Коротко

Рёберный граф заменяет каждое ребро исходного графа вершиной и соединяет новые вершины при общей исходной вершине. Для простого графа число новых рёбер находят суммированием (d(v)2)\binom{d(v)}{2} по вершинам. Такая смена представления связывает задачи о рёбрах, в том числе паросочетание и рёберную раскраску, с задачами о вершинах.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Доминирующее множество в графе: определение и примеры

Доминирующее множество в графе: определение и примеры

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

8 ноября 20268 минут
Гиперграф: что это такое и как его построить

Гиперграф: что это такое и как его построить

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

8 ноября 20268 минут
Лемма о рукопожатиях: формула, доказательство и примеры

Лемма о рукопожатиях: формула, доказательство и примеры

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

8 ноября 20267 минут
Задача о клике: пример и поиск в графе

Задача о клике: пример и поиск в графе

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

8 ноября 20268 минут
Теорема Форда-Фалкерсона о максимальном потоке

Теорема Форда-Фалкерсона о максимальном потоке

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

8 ноября 20269 минут
Теорема Кёнига: двудольный граф, паросочетания и покрытия

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

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

24 апреля 20267 минут