Доповнення графа (зворотний граф) - граф G '. має той же безліч вершин, що і заданий граф G. але в якому дві незбіжні вершини суміжні тоді # 8197; і # 8197; тільки # 8197; тоді. коли вони не суміжні в G.
Формально, для простого графа G = (V. E) і K = P (V 2)> (V ^)> - безлічі всіх двоелементний підмножин його вершин, доповнення G 'визначається як пара (V. K ∖ E) - граф, з вихідним набором вершин, і з набором ребер, отриманим з повного графа видаленням були в заданому графі.Доповнення порожнього графа (що містить тільки вершини, але не ребра) є повним # 8197; графом. і навпаки. Незалежне # 8197; безліч графа є клікою в доповненні графа, і навпаки. Доповнення будь-якого графа # 8197; без # 8197; трикутників не містить колишній.
Самодополнітельний # 8197; граф - це граф, який ізоморфний своєму доповненню. Кографи визначаються як графи, які можна побудувати з єдиною точки непов'язаним # 8197; об'єднанням і операцією доповнення. Кографи утворюють сімейство самодополнітельних графів - доповнення будь-якого кографа є іншим (можливо, відмінним від вихідного) кографом.
література
Основа цієї сторінки знаходиться в Вікіпедії. Текст доступний на умовах ліцензії CC BY-SA 3.0 Unported License. Нетекстові медіа доступні під власними ліцензіями. Wikipedia® - зареєстрований товарний знак організації Wikimedia Foundation, Inc. WIKI 2 є незалежною компанією і не афілійована з Фондом Вікімедіа (Wikimedia Foundation).