УНАРНЫЕ И БИНАРНЫЕ ОПЕРАЦИИ НАД ГРАФАМИ

Цель работы — исследование унарных, бинарных операций над графами и приобретение практических навыков решения задач с использованием основ теории графов.

Основные понятия и определения

Все унарные операции над графами можно объединить в две группы. Первую группу составляют операции, с помощью которых из исходного графа G₁, можно построить граф G₂ с меньшим числом элементов. В группу входят операции удаления ребра или вершины, отождествления вершин, стягивание ребра. Вторую группу составляют операции, позволяющие строить графы с большим числом элементов. В группу входят операции расщепления вершин, добавления ребра.

Отождествление вершин. В графе G₁ выделяются вершины и, v . Определяют окружение Q₁ вершины u,и окружение Q₂ вершины v , вычисляют их объединение Q = Q ₁ Q ₂ . Затем над графом G₁ выполняются следующие преобразования:

— из графа G₁ удаляют вершины u , v ( H₁ = G₁ - u - v);

— к графу Н₁присоединяют новую вершину z ( H₁ = H₁ + z );

— вершину z соединяют ребром с каждой из вершин w₁ Q

(G₂ = H₁ + zw_i, i = 1,2,3,…).

Стягивание ребра. Данная операция является операцией отождествления смежных вершин и, v в графе G₁.

Наиболее важными бинарными операциями являются: объединение, пересечение, декартово произведение и кольцевая сумма.

Объединение. Граф G называется объединением или наложением графов G₁ и G₂, если V_G = V₁ V₂; U_G = U₁ U₂ (рис. 1).

Рис. 1. Объединение графов G₁, G₂

Объединение графов G₁ и G₂ называется дизъюнктным, если V₁ V₂ = . При дизъюнктном объединении никакие два из объединяемых графов не должны иметь общих вершин.

Пересечение. Граф G называется пересечением графов G₁, G₂,если V_G = V₁ V₂и U_G = U₁ U₂ (риc.2). Операция "пересечения" записывается следующим образом: G = G₁ G₂.

Рис.2. Пересечение графов G₁, G₂.

Декартово произведение. Граф G называется декартовым произведением графов G₁ и G₂ если V_G = V₁ V₂ —декартово произведение множеств вершин графов G₁, G₂, а множество ребер U_c задается следующим образом: вершины (z_i, v_k) и (z_j, v_l) смежны в графе G тогда и только тогда, когда z_i = z_j(i = j), a v_k и v_l смежны в G₂ или v_k = v_l(k = l), смежны в графе G₁ (см. рис.3).

Рис. 3. Декартово произведение графов G₁, G₂

Кольцевая сумма графов представляет граф, который не имеет изолированных вершин и состоит из ребер, присутствующих либо в первом исходном графе, либо во втором. Кольцевая сумма определяется следующим соотношением: G = G₁  G₂ (рис.4).

Рис.4. Кольцевая сумма графов G₁, G₂

Лабораторное задание

1. Выполните генерацию матриц M₁, М₂ смежности неориентированных помеченных графой G₁, G₂. Метки вершин выберите из подмножества натуральных чисел {1, 2, …, n}. Порядок графов, определяется преподавателем. Вычислите матрицу смежности дополнительного графа (дополнения) G₁. Порядок графа п определяется преподавателем.

2. Вычислите матрицы смежности подграфов Н, Q графа G₁( G₁).

Например:

H = G₁ - v_i, i = 1, 2,..., n;

Q = G₁ - v_i - v_j, i = 1, 2,..., n, i  j.

3. Выполните операцию отождествления вершин (стягивания ребра, расщепления вершины) в графе G₁( G₁), Номера выбираемых для выполнения операции двух вершин (вершины) согласуйте с преподавателем.

4. Выполните операцию объединения (пересечения, кольцевой суммы) графов G = G₁  G₂ (G = G₁  G₂, G = G₁  G₂).

5. Выполните операцию декартова произведения графов G = G₁X G₂, i = 1,2

Содержание отчета

1. Матричные и графические представления графов G₁( G₁),Н, Q,, G₂, G₃.

2. Протоколы и результаты выполнения операций отождествления вершин (стягивания ребра), расщепления вершины объединения, пересечения, кольцевой суммы, декартова произведения графов в матричной и графической формах.

Контрольные вопросы

1. Задан неориентированный граф G. В графе удаляются вершина и два ребра. Существенна ли последовательность выполнения операций?

2. Как выглядит колода P( G) п — вершинного графа G, если все подграфы, входящие в колоду, выписать следующим образом:

G₁ = G - v_i, i = 1, 2, ..., n?

3. К = {{1, 2}; {1, 2}} — полный двухвершинный граф, Q = ({{1,2,3,4}; {{1, 2}; {2, 3}; {3, 4}; {4, 1}} - двумерный куб. Верно ли, что граф R = К Q - трехмерный куб?

4. Графы H = H₁ H₂и Q являются подграфами полного n-вершинного графа. Выполняется ли для них соотношение

H Q = (H₁ H₂) Q = H₁ Q H₂ Q?