четвер, 6 листопада 2008 р.

Повний граф, доповнення графа

Граф називається повним, якщо кожні дві різні його вершини з’єднані одним і тільки одним ребром.

На малюнку показаний повний граф з 4 вершинамиАле графи також можуть бути неповними, наприклад граф, показаний нижче


Граф, який не є повним, можна перетворити в повний з тими ж вершинами, прибавивши ребра, яких не вистачає. Позначимо даний граф Г, він неповний. Провівши потрібні ребра, ми отримуємо повний граф з такою ж кількістю вершин . Вершини графа Г і прибавлені ребра також утворюють граф, який називається доповненням графа.


Доповненням графа Г називається граф Г2 з тими ж вершинами, що і граф Г, і з тими і тільки тими ребрами, які необхідно додати до графа Г, щоб отримати повний граф.


Завдання
Намалюйте граф, який є доповненням графа Г, зображеного на малюнку


Немає коментарів: