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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Граф Петерсена (слева) и его дополнение (справа).

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

Формальное определение[править | править исходный текст]

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

Свойства[править | править исходный текст]

Некоторые концепции теории графов связаны между собой через дополнение графа: