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

Занятие 29. Тема «Операции над графами»

План лекции:

1. Полный граф

2. Бинарные операции над графами

3. Унарные операции над графами

Полный граф

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

Бинарные операции над графами

Бинарные операции включают два графа.

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

1. Объединение. Граф G=(X,А) называется объединением (или наложением) графов G₁₌ (Х₁, А₁) и G₂ = (Х₂, А₂), если множество его вершин является объединением Х₁ и Х₂, а множество ребер - объединением А₁ и А₂: Другими словами, в один граф добавляются все вершины и ребра одного и второго графа (одинаковые остаются по одному).

G = G₁ G₂ = (X₁ X₂, А₁ А₂).

В матрице смежности объединенного графа работает операция дизъюнкция по таблице истинности. Матрицы смежности графов G₁ и G₂ имеют вид

А₁= А₂=

Объединение графов G₁ G₂ выглядит так

1. Пересечение. Граф G=(X,А) называется пересечением графов G₁=(Х₁,А₁) и G₂=(Х₂,А₂), если множество его вершин является пересечением Х₁ и Х₂, а множество ребер - пересечением А₁ и A₂: G = G₁ G₂ =(X₁ X₂, A₁ А₂). Другими словами, в один граф добавляются только те вершины и ребра, которые одинаковые и у одного и у второго графа.

G

G₁

G₂

Матрица смежности пересеченного графа G₁ G₂ составляется по конъюнкции и выглядит так

3. Кольцевая сумма. Граф G=(X,А)=G₁ G₂, порожденный на множестве ребер A₁ A₂, представляет собой кольцевую сумму двух графов G₁=(Х₁,А₁) и G₂ =(Х₂, А₂). Другими словами, в кольцевой граф добавляются те ребра, которые разные у обоих графов, а одинаковые убираются (вершины остаются все). Кольцевая сумма графов G₁ и G₂ по­казана на рисунке:

G₂

Матрица смежности кольцевого графа G₁ G₂ составляется по сложению по модулю два и выглядит так

4. Разность. Граф G=(X,А) называется разностью графов G₁=(Х₁,А₁) и G₂=(Х₂,А₂), если множество его вершин является раз­ностью Х₁ и Х₂, а множество ребер - разностью А₁ и. A₂: G = G₁ G₂ = (X₁ X₂, А₁ А₂). Операция разности некоммутативна, то есть G₁ G₂ G₂ G_1. Другими словами, в разностный граф добавляются только те ребра, которые есть у первого графа, но нет у второго (вершины остаются все).

G

G₁

G₂

Матрица смежности разностного графа G₁ G₂ составляется по вычитанию (1-1=0, 1-0=1, 0-1=0, 0-0=0) и выглядит так

5. Дополнением графа G=(X,А₁) является граф =(X,А₂) , у которого множество вершин совпадает с множеством вершин графа G, а множество ребер, не принадлежит графу G, то есть в любые две вершины смежны, если только они не смежны в G. Другими словами, в дополненный граф добавляются только те ребра, которых не хватает до полного графа (вершины остаются все).

Матрица смежности полного графа, состоит из всех 1, кроме главной диагонали. Матрица смежности дополненного графа G₁ G₂ составляется инверсии и выглядит так

G:

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

Унарные операции определены на одном графе. Рассмотрим их.

1. Удаление вершины. Если x_i - вершина графа G=(X,А), то G-i является графом, получившимся после удаления из графа G вер­шимы i и всех ребер, инцидентных этой вершине. Удаление из гра­фа вершины влечет удаление всех ребер, входящих в эту вершину. Удаление вершины 2 показано на рисунке:

- исходный граф G - граф G-2

1. Удаление ребра или удаление дуги. Если а_i - ребро графа G = (X, А), то G-а_i является графом, полу­чающимся после удаления из G ребра а_i. Заметим, что концевые вершины ребра а_i, не удаляются. После удаления всех ребер граф оказывается без ребер. Удаление ребер (5,4) и (1,2) показано на рисунке:

- исходный граф G - граф G-(5,4),(1,2)

1. Замыкание или отождествление. Говорят, что пара вершин х_i и х_j в графе G замыкается (или отождествляется), если они замыкаются такой новой вершиной, что все дуги в графе G, инцидентные х_i и х_j, становятся инцидентными новой вершине. После замыкания, дуга или ребро, находящееся между вершинами, станет петлей. Например, результат замыкания вершин 2 и 3 показан на рисунке:

2,3?

4

5

1

- исходный граф G

1. Стягивание. Под стягиванием подразумевают операцию удаления дуги или ребра и отождествление его концевых вершин. После стягивания, две вершины совмещаются в одну, а ребро или дуга, находящаяся между ними, удаляется. Граф, изображенный на следующем рисунке, получен стягиванием ребра (1,5):

2

- исходный граф G

Самостоятельная работа студентов

1. Переписать лекцию в тетрадь и прислать фото

2. Выполнить все бинарные операции (кроме дополнения) двумя способами для следующих графов:

G1: G2:

1. Выполнить все унарные операции для следующего графа по следующим параметрам (удаление вершины 3, удаление дуги (46), замыкание вершин 1 и 3, стягивание дуги (46)).

Выполненные задания отправить на адрес электронной почты преподавателя в виде фото, сделанное из тетради.