Википедия

Дополнение графа: различия между версиями

Интерактивная навигация по истории
[отпатрулированная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
м Добавлена категория
→‎Свойства: орфография, пунктуация
Строка 7:
== Свойства ==
Некоторые концепции теории графов связаны между собой через дополнение графа:
*Дополнение пустого графа (содержащего только вершины, но не ребра) является [[полныйполным графграфом]], и наоборот.
*[[Задача о независимом множестве|Независимое множество]] графа является [[Клика (теория графов)|кликой]] в дополнении графа, и наоборот.
*Дополнение любого [[Граф без треугольников|графа без треугольников]] не содержит [[Граф без клешней|клешней]].
*[[Самодополнительный граф]] — это граф, который [[Изоморфизм графов|изоморфен]] своему дополнению.
*[[Кограф|Кографы]] определяются как графы, которые можно построить из единственной точки [[Операции над графами|несвязанным объединенимобъединением]] и операцией дополнения. Кографы образуют семейство самодополнительных графов — дополнение любого кографа является другим (возможно, отличным от исходного) кографом.
 
[[Категория:Теория графов]]
Источник — https://ru.wikipedia.org/wiki/Дополнение_графа