- Дополнение графа
-
В теории графов дополнением или обратным к графу G называется такой граф H, имеющий то же множество вершин, что и G, но в котором две несовпадающие вершины смежны тогда и только тогда, когда они не смежны в G. Чтобы найти обратный граф, дополните данный граф до полного и удалите все ребра, которые уже были до этого.
Формальное определение
Пуcть G=(V,E) — простой граф и пусть множество K содержит все двухэлементные подмножества множества V. Тогда H=(V,K\E) является дополнением графа G.
Свойства
Дополнением пустого графа (содержащего только вершины, но не ребра) является полный граф, и наоборот.
Категория:- Теория графов
Wikimedia Foundation. 2010.