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