Все унарные операции над графами можно объединить в две группы. Первую группу составляют операции, с помощью которых из исходного графа 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 выполняются следующие преобразования:
Стягивание ребра. Данная операция является операцией отождествления смежных вершин u, ν в графе G1.
Расщепление вершины. В графе G1 выделяется вершина ν. Окружение Q вершины ν разбивается на две части
М, N (MN=Q, M
N=ø). После этого над графом G1
выполняются следующие преобразования:
Говорят, что граф G2 получен из графа G1 расщеплением вершины ν.
Наиболее важными бинарными операциями являются: объединение, пересечение, декартово произведение и кольцевая сумма.
Объединение. Граф G=G1G2 называется объединением или наложением графов
G1 и G2, если VG=V1
V2; UG=U1
U2
(рисунок 1).
Объединение графов G1 и G2 называется дизъюнктным, если V1V2=ø.
Аналогично определяются объединение и дизъюнктное объединение любого множества графов. При дизъюнктном объединении никакие два из
объединяемых графов не должны иметь общие вершины.
Пересечение. Граф G=G1G2 называется пересечением графов G1 и G2,
если VG=V1
V2 и UG=U1
U2 (Рисунок 2).
Декартово произведение. Граф G называется декартовым произведением графов G1 и G2, если VG=V1 x V2 - декартово произведение множеств вершин графов G1, G2, а множество ребер UG задается следующим образом: вершины (zi, νk) и (zj, νi) смежны в графе G тогда и только тогда, когда zi=zj(i=j), a νk и νi смежны в G2 или νk=νi(k=l), a zi и zj смежны в графе G1 (рисунок 3).
/G1 x G2/ = /G1/ ∙ /G1/ /U(G1 x G2/ = /G2/ ∙ /U2/ + /G1/ ∙ /U1/ | (1) |
Кольцевая сумма графов представляет граф, который не имеет изолированных вершин и состоит из ребер, присутствующих либо
в первом исходном графе, либо во втором. Кольцевая сумма определяется следующим соотношением: G = G1 G1
(рисунок 4).
![]() |
Практические задания |