Операция дополнения графа

Пусть дан граф и . Дополнением графа называется граф с множеством верши , в котором две вершины смежные тогда и только тогда, когда они несмежные в графе . Из этого определения получается правило построения графа , для чего необходимо построить полный граф и удалить из него все ребра, принадлежащие графу . Очевидно, что, например, дополнением полного графа является пустой граф, и наоборот – дополнением пустого графа является полный граф. На рис. 2.11 Приведен граф , являющейся дополнением графа .

Рис. 2.11