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

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

Граф Петерсена (ліворуч) і його доповнення (праворуч)

Формальна побудова

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

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

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

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

Посилання

• Bondy, John Adrian; Murty, U. S. R. (1976). Graph Theory with Applications. North-Holland. ISBN 0-444-19451-7. Процитовано 30 травня 2013. , pages 6 and 29.
• Diestel, Reinhard (2005). Graph Theory (вид. 3rd). Springer. ISBN 3-540-26182-6. . Electronic edition [Архівовано 8 лютого 2012 у Wayback Machine.], page 4.