Вікіпедія

Доповнення графа: відмінності між версіями

Інтерактивний перегляд історії
[перевірена версія][перевірена версія]
← Попереднє редагуванняНаступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
м Lxlalexlxl перейменував сторінку з Доповнення графа на Доповнення графу
Немає опису редагування
Рядок 1:
[[FileФайл:Petersen graph complement.svg|thumb|300px|[[Граф Петерсена]] (ліворуч) і його доповнення (праворуч)]]
В [[теорія графів|теорії графів]], '''доповнення''' або '''обернений''' до графаграфу ''G'' — граф ''H'' на тих самих вершинах, поєднаних ребрами тоді і тільки тоді, коли вони несуміжні в ''G''. Тобто, для побудови доповнення графаграфу, потрібно додати всі ребра, необхідні для отримання [[повний граф|повного графаграфу]] і видалити всі ребра, які були присутні до того. Однак, це не [[доповнення множин]]и графаграфу; доповнені тільки ребра.
 
== Формальна побудова ==
Нехай ''G'' = (''V'', ''E'') буде [[простий граф|простим графом]] і нехай ''K'' складається з усіх 2-елементних підмножин ''V''. Тоді ''H'' = (''V'', ''K'' \ ''E'') — доповнення ''G''.
 
== Застосування і приклади ==
Декілька концепцій теорії графів стосуються одна одної через доповнення графів:
* Доповнення безреберного графаграфу це повний граф і навпаки.
* [[Незалежна множина (теорія графів)|Незалежна множина]] в графі це [[кліка (теорія графів)|кліка]] в доповненні графаграфу і навпаки.
* Доповнення будь-якого графу без трикутників це граф без кігтів.
* [[Самодоповняльний граф]] це граф, який [[Ізоморфізм графів|ізоморфний]] до свого доповнення.
* [[Кограф]]и визначені як графи, які можна утворити з [[Диз'юнктне об'єднання|диз'юнктного об'єднання]] і операцій доповнення, і які формують сім'ю самодоповнювальних графів: доповнення будь-якого кографакографу є інший (можливо інший) кограф.
 
== Посилання ==
* {{citation
| last1=Bondy
Рядок 28:
| url-access=registration
}}, pages 6 and 29.
* {{Citation
| last=Diestel | first=Reinhard
| title=Graph Theory
Отримано з https://uk.wikipedia.org/wiki/Доповнення_графа