В теорії графів, доповнення або обернений до графа 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, Інтернет
V teoriyi grafiv dopovnennya abo obernenij do grafa G graf H na tih samih vershinah poyednanih rebrami todi i tilki todi koli voni nesumizhni v G Tobto dlya pobudovi dopovnennya grafa potribno dodati vsi rebra neobhidni dlya otrimannya povnogo grafa i vidaliti vsi rebra yaki buli prisutni do togo Odnak ce ne dopovnennya mnozhini grafa dopovneni tilki rebra Graf Petersena livoruch i jogo dopovnennya pravoruch Formalna pobudovaNehaj G V E bude i nehaj K skladayetsya z usih 2 elementnih pidmnozhin V Todi H V K E dopovnennya G Zastosuvannya i prikladiDekilka koncepcij teoriyi grafiv stosuyutsya odna odnoyi cherez dopovnennya grafiv Dopovnennya bezrebernogo grafa ce povnij graf i navpaki v grafi ce klika v dopovnenni grafa i navpaki Dopovnennya bud yakogo grafa bez trikutnikiv ce graf bez kigtiv Samodopovnyalnij graf ce graf yakij izomorfnij do svogo dopovnennya Kografi viznacheni yak grafi yaki mozhna utvoriti z diz yunktnogo ob yednannya i operacij dopovnennya i yaki formuyut sim yu samodopovnyuvalnih grafiv dopovnennyam bud yakogo kografa ye inshij mozhlivo vidminnij vid pochatkovogo kograf PosilannyaBondy John Adrian Murty U S R 1976 Graph Theory with Applications North Holland ISBN 0 444 19451 7 procitovano 30 travnya 2013 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Citation title Shablon Citation citation a Obslugovuvannya CS1 Storinki z parametrom url status ale bez parametra archive url posilannya pages 6 and 29 Diestel Reinhard 2005 Graph Theory vid 3rd Springer ISBN 3 540 26182 6 Electronic edition 8 lyutogo 2012 u Wayback Machine page 4