§ 2. Операции над графами. Способы задания графов Операции над графами
Объединением
графов
и
называется граф
,
у которого
и
.
Пример.
Заданы граф
,
у которого
,
и граф
,
у которого
,
Найти
объединение
этих графов.
□ По определению
,
где
и
,
следовательно,
Зная V и U, всегда можно построить граф G (рис. 4.5) :
Рис. 4.5 ■
Суммой
(соединением)
графов
и
называется граф
,
представляющий собой объединение графов
G1
, G2
и полного двудольного графа Кт,п
, построенного на носителях
и
.
Другими
словами, при построении суммы
графов G1
и G2
определяется их объединение и каждая
вершина
,
не вошедшая в пересечение
,
соединяется со всеми вершинами
,
не вошедшими в пересечение
,
и наоборот.
Пример. Найти сумму G1 + G2 графов G1 и G2 , рассмотренных в предыдущем примере.
□ По определению
,
где
.
Тогда
,
где Vk
и Uk
– множество вершин и множество ребер
полного двудольного графа Кт,п
соответственно. В двудольном графе
множество вершин разбито на два
непересекающихся подмножества
и
,
т.е.
,
причем
и
.
Определяем
:
.
Тогда
,
.
Полный двудольный граф имеет вид
Объединяя три
графа
,
получим искомый граф G
(рис. 4.6):
Рис. 4.6
В графе G тонкими линиями выделены ребра графа, который является объединением графов G1 и G2 (ср. с рис. 4.5 ), толстыми линиями – ребра полного двудольного графа К1,2 . ■
Произведением
графов G1
= < V1,
U1
> и G2
= < V2,
U2
> называется граф G=<V,U>,
у которого
,
а множество ребер U
получается
следующим образом : вершины
и
смежны в графе G
тогда и только тогда, когда или v1m=
v1p,
а v2n
и v2k
смежны в G2
, или v1m
и v1p
смежны в G1,
а v2n
= v2k
.
Пример. Найти
произведение
графов G1
и G2
, у которых
,
,
,
.
□ Согласно определению произведения графов :
.
Учитывая правило построения множества ребер U графа G , получим :
Рис. 4.7 ■
С помощью операции произведения можно ввести единичные п – мерные кубы – один из классов графов. Указанный п – мерный куб Нп вводится рекуррентно:
,
где К2 – полный граф с числом вершин, равным двум.
Таким образом, Нn – граф порядка 2п, вершины которого можно представить векторами длины п , причем такими, что векторы , соответствующие двум смежным вершинам, будут различаться ровно в одной координате. На рис. 4.8 представлены кубы Н2 и Н3 :
Рис. 4.8
Из рисунка видно, что каждая вершина п – мерного куба инцидентна п ребрам . Следовательно, число ребер п – мерного куба равно п·2п-1 .