Дополнение графа: определение и построение

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

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

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

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

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

Количество путей в ориентированном графе
Как найти количество путей в ориентированном графе: подсчёт в DAG, динамическое программирование, матрица смежности, заданная длина и влияние циклов на ответ.

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

Ориентированный ациклический граф: что такое DAG
Ориентированный ациклический граф простыми словами: как читать вершины, рёбра и пути, проверить отсутствие циклов и рассчитать сроки работ на примере DAG.