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

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

Дополнение графа (обратный граф) — граф G', имеющий то же множество вершин, что и заданный граф G, но в котором две несовпадающие вершины смежны тогда и только тогда, когда они не смежны в G.

Формально, для простого графа G=(V,E) и K=\mathcal P(V^2) — множества всех двухэлементных подмножеств его вершин, дополнение G' определяется как пара (V,K \setminus E) — граф, с исходным набором вершин, и с набором ребёр, полученным из полного графа удалением имевшихся в заданном графе.

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

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

Литература[править | править вики-текст]

  • Харари Ф. Теория графов. — 2-е издание. — М.: УРСС, 2003. — 295 с. — ISBN 5-354-00301-6.