В теорії графів, доповнення або обернений до графа 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 , процитовано 30 травня 2013
{{}}
: Обслуговування CS1: Сторінки з параметром url-status, але без параметра archive-url (), pages 6 and 29. - Diestel, Reinhard (2005), Graph Theory (вид. 3rd), , ISBN . Electronic edition [ 8 лютого 2012 у Wayback Machine.], page 4.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет