Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow ГЕОМЕТРИЧЕСКАЯ ТЕОРИЯ ГРАФОВ
Посмотреть оригинал

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

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

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

Рис. 21

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

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

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

2

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

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

вершин, причем |к,| = и,, У2 = п2,...,Ук = пк. Тогда граф G имеет п1-п2+п1-п3+...+пк_]-пк ребер, его пополнение G имеет С*+ + +r|j ребер, а степень

неполноты графа G равна С* + +.. -+С* . На рис. 22

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

Рис. 22

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

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы