операции над графами. Занятие 29. Тема Операции над графами План лекции Полный граф Бинарные операции над графами

• Название: Занятие 29. Тема Операции над графами План лекции Полный граф Бинарные операции над графами
• Дата: 25.06.2021
• Размер: 0.51 Mb.
• Имя файла: операции над графами.docx
• Тип: Занятие; #221422

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

План лекции:

1. 
   Полный граф
   
2. 
   Бинарные операции над графами
   
3. 
   Унарные операции над графами
   

Полный граф

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

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

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

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

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

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












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



А₁= А₂=


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

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

G

G₁

G₂

3. 
   
   
4. 
   
   

Матрица смежности пересеченного графа 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

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

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

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

2,3?

4

5

1

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

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

2

- исходный граф G
Самостоятельная работа студентов

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

G1: G2:

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