![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/2/2f/Petersen_graph_complement.svg/langru-640px-Petersen_graph_complement.svg.png&w=640&q=50)
Дополнение графа
Материал из Википедии — свободной encyclopedia
Дополнение графа (обратный граф) — граф , имеющий то же множество вершин, что и заданный граф
, но в котором две несовпадающие вершины смежны тогда и только тогда, когда они не смежны в
.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2f/Petersen_graph_complement.svg/320px-Petersen_graph_complement.svg.png)
Формально для простого графа и
— множества всех двухэлементных подмножеств его вершин — дополнение
определяется как пара
— граф с исходным набором вершин и с набором ребёр, полученным из полного графа удалением имевшихся в заданном графе.
Дополнение пустого графа (содержащего только вершины, но не рёбра) является полным графом, и наоборот. Независимое множество графа является кликой в дополнении графа, и наоборот. Дополнение любого графа без треугольников не содержит клешней.
Самодополнительный граф — это граф, который изоморфен своему дополнению. Кографы определяются как графы, которые можно построить из единственной точки несвязанным объединением и операцией дополнения. Кографы образуют семейство самодополнительных графов — дополнение любого кографа является другим (возможно, отличным от исходного) кографом.