logo search
КЛ

§ 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 .