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