Операции над графами

Общепринятыми унарными операциями над графами являются следующие операции:

1. Удаление вершины. Обозначение H = G - v, где H и G результирующий и исходный графы соответственно, v – удаляемая вершина.

2. Удаление ребра. Обозначение H = G - e, где e – удаляемое ребро.

3. Стягивание ребра.

В определённом смысле двойственными к этим операциям являются операции:

4. Добавление вершины. Обозначение H = G + v, где v – добавляемая вершина.

5. Добавление ребра. Обозначение H = G + e, где e – добавляемое ребро.

6. Расщепление вершины.

Смысл 1,2,4,5 операций очевиден. Рассмотрим подробнее 3 и 6 операции.

Стягивание ребра { u, v } обозначает отождествление смежных вершин u и v.

Для отождествления вершин u и v графа G необходимо выполнить следующие действия:

1) H=G - u - v + v ¢ - получить граф H путем удаления из исходного графа G отождествляемых вершин u, v и добавления новой вершины v ¢.

2) в графе H соединить вершину v ¢ ребром с каждой вершиной, смежной с вершиной u, а затем с каждой вершиной, смежной с вершиной v, в графе G.

Примеры отождествления вершин и cтягивания ребра представлены на рис. 4.1.

Отметим, что в общем случае при выполнении операции отождествления вершин графа могут образоваться кратные рёбра, то есть результатом такой операции будет мультиграф. Один из таких случаев проиллюстрирован на рис. 4.2.

Пусть v - одна из вершин графа G. Разобьём множество смежных ей вершин (её окружение) на два произвольных подмножества M и N и выполним следующее преобразование графа G:

1) удалим вершину v вместе с инцидентными ей рёбрами;

2) добавим новые вершины u и w и ребро { u, w };

3) вершину u соединим ребром с каждой вершиной из множества M, а вершину w - с каждой вершиной из множества N.

Теперь рассмотрим две бинарные графовые операции: объединение и произведения графов.

Граф H =(V, E) называется объединением графов F =(V ₁, E ₁)и G =(V ₂, E ₂),если V = V ₁È V ₂, E = E ₁È E ₂.

Для обозначения операции объединения графов используется запись H = F È G. Пример операции объединения графов показан на рис. 4.3.

Объединение графов F =(V ₁, E ₁)и G =(V ₂, E ₂) называется дизъюнктивным, если V ₁Ç V ₂=Æ.

Аналогично определяется объединение и дизъюнктивное объединение любого множества графов, причём в последнем случае никакие два из объединяемых графов не должны иметь общих вершин.

Пусть G_i =(V_i, E_i), (i =1,2) – два графа. Произведением графов G ₁´ G ₂ называется граф G =(V, E), где V = V ₁´ V ₂ – декартово произведение множеств вершин исходных графов, а множество E формируется по правилу: вершины (u ₁, u ₂) и (v ₁, v ₂) смежные в графе G тогда и только тогда, когда или u ₁= v ₁, а u ₂ и v ₂ смежные в G ₂, или u ₂= v ₂, а u ₁ и v ₁ смежные в G ₂ (рис. 4.4.)

Очевидно, что число вершин графа G =(V, E), полученного в результате произведения графов G ₁=(V ₁, E ₁) и G ₂=(V ₂, E ₂), равно произведению числа вершин графов G ₁ и G ₂, то есть | V |=| V ₁|×| V ₂|, а число рёбер определяется так: | E |=| V ₁|×| E ₂|+| V ₂|×| E ₁|.

С помощью операции произведения вводится понятие n - мерного куба, n -мерный куб Q_n определяется рекуррентно:

1) Q ₁= K ₂, где K ₂ – полный граф порядка 2,

2) Q_n = K ₂´ Q_{n -1}, n >1.

Очевидно, что Q_n – граф порядка 2 ⁿ, вершины которого можно представить (0,1)-векторами длины n таким образом, что две вершины будут смежные тогда и только тогда, когда соответствующие векторы различаются ровно в одной координате.

Упражнения:

1. Нарисуйте кубы Q ₁, Q ₂ и Q ₃. Определите число рёбер n-мерного куба.

2. Постройте алгоритмы, реализующие операции над графами. Какие структуры данных для хранения графов удобнее при реализации тех или иных операций?