Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Доповнення графа



Граф Петерсена (ліворуч) і його доповнення (праворуч).

В теорії графів доповненням або зворотним до графу G називається такий граф H, має ту ж безліч вершин, що і G, але в якому дві незбіжні вершини суміжні тоді і тільки тоді, коли вони не суміжні в G. Щоб знайти зворотний граф, доповніть даний граф до повного і видаліть всі ребра, які вже були до цього.


Формальне визначення

Пуcть G = (V, E) - простий граф і нехай безліч K містить всі двоелементний підмножини безлічі V. Тоді H = (V, K \ E) є доповненням графа G.

Властивості

Доповненням порожнього графа (який містить тільки вершини, але не ребра) є повний граф, і навпаки.


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Доповнення
Методика доповнення
Алгебраїчне доповнення
Доповнення (лінгвістика)
Інваріант графа
Розгортка графа
Розбиття графа
Доповнення (комп'ютерні ігри)
Компонента зв'язності графа
© Усі права захищені
написати до нас
Рейтинг@Mail.ru