Дополнение графа

Граф Петерсена (слева) и его дополнение (справа).

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

Формальное определение

Пуcть G=(V,E) — простой граф и пусть множество K содержит все двухэлементные подмножества множества V. Тогда H=(V,K\E) является дополнением графа G.

Свойства

Дополнением пустого графа (содержащего только вершины, но не ребра) является полный граф, и наоборот.