назад

3.2 Унарные и бинарные операции над графами

Унарные операции

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

Удаление ребра. В графе G1 выделяют две смежные вершины u, ν. Затем из G1 удаляют ребро uν: G2=G1-uν. Говорят, что G2 получен из G1 удалением ребра uν.

Удаление вершины. В графе G1 выделяются вершина г и смежные с ней вершины νi=1,2,3, ... Говорят, что граф G2 получен из графа G1 удалением вершины u.

Добавление ребра. В графе G1 выделяют две несмежные вершины u, ν. Затем к графу G1 добавляют ребро uν. Говорят, что граф G2 получен из G1 добавлением ребра uν.

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

  1. из графа G1 удаляют вершины u, ν (H1=G1-u-ν);
  2. к графу Н1 присоединяют новую вершину z(H1=H1+z);
  3. вершину z соединяют ребром с каждой из вершин wiQ(G2=H2+zwi, i=1,2,3 ...).

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

Расщепление вершины. В графе G1 выделяется вершина ν. Окружение Q вершины ν разбивается на две части М, N (MN=Q, MN=ø). После этого над графом G1 выполняются следующие преобразования:

  1. удаляют вершину ν вместе с инцидентными ей ребрами (Н1=G1=ν-νzi, ziQ, i=1,2,3 ..);
  2. добавляют новые вершины u,w и соединяющее их ребро uw(H2=H1+u+w+uw);
  3. вершину u соединяют ребром с каждой вершиной из множества М(H3=H1+uzi, ziM);
  4. вершину w соединяют ребром с каждой вершиной из множества N(G2=H3+uzi, ziM).

Говорят, что граф G2 получен из графа G1 расщеплением вершины ν.

Бинарные операции

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

Объединение. Граф G=G1G2 называется объединением или наложением графов G1 и G2, если VG=V1V2; UG=U1U2 (рисунок 1).


Рисунок 1 - Объединение графов G1 и G2

Объединение графов G1 и G2 называется дизъюнктным, если V1V2=ø. Аналогично определяются объединение и дизъюнктное объединение любого множества графов. При дизъюнктном объединении никакие два из объединяемых графов не должны иметь общие вершины.

Пересечение. Граф G=G1G2 называется пересечением графов G1 и G2, если VG=V1V2 и UG=U1U2 (Рисунок 2).


Рисунок 2 - Пересечение графов G1, G2

Декартово произведение. Граф G называется декартовым произведением графов G1 и G2, если VG=V1 x V2 - декартово произведение множеств вершин графов G1, G2, а множество ребер UG задается следующим образом: вершины (zi, νk) и (zj, νi) смежны в графе G тогда и только тогда, когда zi=zj(i=j), a νk и νi смежны в G2 или νki(k=l), a zi и zj смежны в графе G1 (рисунок 3).


Рисунок 3 - Декартово произведение графов G1,G2

Для графов G1, G2, G=G1 x G2 выполняются следующие соотношения:
/G1 x G2/ = /G1/ ∙ /G1/
/U(G1 x G2/ = /G2/ ∙ /U2/ + /G1/ ∙ /U1/
(1)

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


Рисунок 4 - Кольцевая сумма графов G1 и G2

 

Вопросы для самоконтроля

Унарные операции

  1. Можно ли считать, что операция расщепления вершины является в определенном смысле двойственной к операции стягивания ребра.
  2. Задан неориентированный граф G. В графе удаляются вершина и два ребра. Существенна ли последовательность выполнения операций?
  3. Как выглядит колода P(G) n-вершинного графа G, если все подграфы, входящие в колоду, выписать следующим образом:
    Gi=G-νi, i=1,2, ...,n?

Бинарные операции

  1. Верно ли, что для n-вершинного графа G и подграфов Qi, Qj из его колоды P(G) справедливо соотношение:
    G=QiQj, i=1,2, ..., n, j=1,2, ..., n?
  2. Верно ли, что для n-вершинного графа G и подграфов Qi,Qj из его колоды справедливо соотношение:
    G-νij=(G-νi)(G-νj), i=1,2, .., n, j=1,2, ..n?
  3. K={{1,2};{1,2}} - полный двухвершинный граф, Q={{1,2,3,4};{1,2};{2,3};{3,4};{4,1}} - двухмерный куб. Верно ли, что граф R=K x Q - трехмерный куб?
  4. Графы H=H1H2 и Q являются подграфами полного n-вершинного графа. Выполняется ли для них соотношение
    H x Q=(H1H2) x Q = H1 x QH2 x Q?

Практические задания