Пополнения элементарных графов

Пополнением элементарного графа G называется его сверхграф G, являющийся полным графом. Граф G является суграфом своего пополнения G и получается из последнего при помощи операции удаления ребер. Переход от графа G к его пополнению можно осуществить при помощи обратной операции, называемой операцией добавления ребер. Каждая такая операция увеличивает количество ребер графа на единицу, не меняя числа вершин графа. Разность между количествами ребер графов G и G называется степенью неполноты графа G. Ясно, что если граф G имеет т ребер и п вершин, то степень неполноты графа G равна С^г_п — т, так как пополнение G имеет С ребер.

Пример 1. На рис. 21 представлен элементарный граф G и его пополнение G. Добавляемые ребра изображены пунктиром, их количество равно степени неполноты графа G.

Рис. 21.

Пример 2. Пусть задан полный двудольный граф G, содержащий п + т вершин (п вершин в первом подмножестве и т — во втором). Подсчитаем степень неполноты графа G. Так как G — полный граф с п+т.

(п + т-1)(п + т)

вершинами, то он имеет С_п+т =;

ребер. Исходный двудольный граф G содержит п • т ребер. Поэтому, степень неполноты графа G равна.

Пример 3. Рассмотрим полный к-долъный граф G (V, Е), т. е. элементарный граф, обладающий следующими свойствами: 1) множество вершин V графа G разделено на к непересекающихся подмножеств V/, Vz—, V*; 2) любая пара вершин из разных подмножеств инцидентна ровно одному ребру; 3) вершины из одного подмножества не смежны. Предположим, что граф G имеет и, + п₂+…+п_к

вершин, причем |к,| = и, У₂ = п₂,…, У_к = п_к. Тогда граф G имеет п₁-п₂+п₁-п₃+…+п_к__]-п_к ребер, его пополнение G имеет С*_{+ + +r|j} ребер, а степень неполноты графа G равна С* + +. -+С* . На рис. 22.

представлены полный 3-дольный граф и его пополнение при п, = п₂ = п₃ = 2.

Рис. 22.

Заметим, что операцию добавления ребер можно очевидным образом определить и для произвольного графа (псевдографа). Так, например, при помощи этой операции из произвольного элементарного графа можно получить полный граф с петлями. Аналогично, добавляя недостающие ребра к элементарному двудольному графу, соединяющие вершины из разных «долей», можно получить полный двудольный граф. При помощи этой операции можно элементарный граф превратить в мультиграф или псевдограф. Во всех случаях, когда производится операция добавления ребер, получается граф, не изоморфный исходному графу.