Доповнення графа

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Граф Петерсена (ліворуч) і його доповнення (праворуч)

В теорії графів, доповнення або обернений до графа G — граф H на тих самих вершинах, поєднаних ребрами тоді і тільки тоді, коли вони несуміжні в G. Тобто, для побудови доповнення графа, потрібно додати всі ребра, необхідні для отримання повного графа і видалити всі ребра, які були присутні до того. Однак, це не доповнення множини графа; доповнені тільки ребра.

Формальна побудова[ред.ред. код]

Нехай G = (VE) буде простим графом і нехай K складається з усіх 2-елементних підмножин V. Тоді H = (VK \ E) — доповнення G.

Застосування і приклади[ред.ред. код]

Декілька концепцій теорії графів стосуються одна одної через доповнення графів:

  • Доповнення безреберного графа це повний граф і навпаки.
  • Незалежна множина в графі це кліка в доповненні графа і навпаки.
  • Доповнення будь-якого графу без трикутників це граф без кігтів.
  • Самодоповняльний граф це граф, який ізоморфний до свого доповнення.
  • Кографи визначені як графи, які можна утворити з диз'юнктного об'єднання і операцій доповнення, і які формують сім'ю самодоповнювальних графів: доповнення будь-якого кографа є інший (можливо інший) кограф.

Посилання[ред.ред. код]