Введение

Граф с теми же вершинами, но противоположными связями, в математической области теории графов, называется комплементом или инверсией графа G. Это граф H, построенный на тех же вершинах, такой что две различные вершины H смежны тогда и только тогда, когда они не смежны в G. Иными словами, для получения комплемента графа необходимо добавить все недостающие ребра, чтобы сформировать полный граф, и удалить все существующие ребра. Комплемент – это не дополнение множества вершин графа; дополняются только ребра.

Определение

Пусть G = (V, E) будет простым графом, и пусть K состоит из всех 2-элементных подмножеств V. Тогда H = (V, K \ E) является дополнением к G, где K \ E – разность множеств K и E. Для ориентированных графов дополнение можно определить аналогичным образом, как ориентированный граф на том же множестве вершин, используя множество всех упорядоченных пар из V вместо множества K в указанной выше формуле. В терминах матрицы смежности A графа, если Q – матрица смежности полного графа с тем же числом вершин (то есть все элементы равны единице, за исключением диагональных элементов, которые равны нулю), то матрица смежности дополнения к A равна Q - A. Дополнение не определено для мультиграфов. В графах, допускающих петли (но не кратные ребра), дополнение к G можно определить, добавив петлю к каждой вершине, которой нет в G, и в противном случае используя ту же формулу, что и выше. Однако эта операция отличается от операции для простых графов, поскольку применение её к графу без петель приведёт к графу с петлями на всех вершинах.

Самодополняющие графики и классы графиков

Самодополняющийся график — это график, изоморфный своему дополнению. Кографы определяются как графики, которые можно построить из отдельных вершин с помощью операций дизъюнктного объединения и взятия дополнения. Они образуют самодополняющее семейство графов: дополнение любого кографа является другим кографом. Для кографов, состоящих более чем из одной вершины, ровно один граф в каждой комплементарной паре связный, и одно эквивалентное определение кографов заключается в том, что каждый их связный индуцированный подграф имеет несвязное дополнение. Другое, самодополняющее определение состоит в том, что они не содержат индуцированного подграфа в виде пути из четырех вершин. Другой самодополняющий класс графов — класс расщепленных графов, графов, в которых вершины можно разбить на клику и независимое множество. Такое же разбиение дает независимое множество и клику в комплементарном графе. Пороговые графы — это графы, формируемые путем многократного добавления либо изолированной вершины (без соседей), либо универсальной вершины (смежной со всеми ранее добавленными вершинами). Эти две операции являются взаимно дополняющими, и они генерируют самодополняющее семейство графов.

Алгоритмические аспекты

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