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

Обновлено: 05.07.2024

Пусть %%G_1 = (V_1, E_1)%% и %%G_2 = (V_2, E_2)%% — какие-либо два графа.

Дополнением графа %%G_1 = (V_1, E_1)%% называется граф %%\overline = (V_1, \overline )%%, множеством вершин которого является множество %%V_1%%, а множеством ребер — %%\overline = \%%.

Объединением графов %%G_1%% и %%G_2%% при условии, что %%V_1 \cap V_2 = \varnothing%%; %%E_1 \cap E_2 = \varnothing%%, называется граф %%G_1 \cup G_2 = (V_1 \cup V_2, E_1 \cup E_2)%%.

Пересечением графов %%G_1%% и %%G_2%% называется граф %%G_1 \cap G_2 = (V_1 \cap V_2, E_1 \cap E_2)%%.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3) Кольцевая сумма двух графов GÅG¢ есть граф, не имеющий изолированных вершин и состоящий только из ребер, присутствующих либо в G, либо в G¢, но не в обоих графах одновременно. Т.о. это ЕÅЕ¢ реберно-порожденный граф. См. рис.17.

4) Относительное дополнение подграфа до графа – это граф, в который входят те ребра основного графа, которых не было в подграфе, а множество вершин совпадает с множеством вершин основного графа. См. рис.18.

5) Абсолютное дополнение – это дополнение до полного графа на том же множестве вершин. Так для графа, изображенного в правой части равенства на рис.18, абсолютное дополнение будет изображаться так, как показано на рис.19.

6) Удаление ребра – ребро удаляется из графа, а инцидентные ему вершины остаются. См.рис.20.

7) Удаление вершины – вершина удаляется из графа вместе со всеми инцидентными ей ребрами. См. рис.21.

8) Отождествление (замыкание) вершин – при замыкании двух вершин, эти вершины удаляются из графа и заменяются одной новой, при этом ребра, инцидентные исходным вершинам, теперь будут инцидентны новой вершине.

9) Стягивание ребра – ребро удаляется, а его концевые вершины отождествляются. На рисунке 23 последовательно стягиваются ребра е₁, е₃, е₂.

1) Объединение двух графов G=(V, E) и G¢=(V¢, E¢) есть граф S=(V∪V¢,E∪E¢).

На рисунке 15 показано объединение двух графов.

2) Пересечение двух графов G=(V, E) и G¢=(V¢, E¢) есть граф S=(V∩V¢,E∩E¢). См. рис.16.

6) Удаление ребра – ребро удаляется из графа, а инцидентные ему вершины остаются. См.рис.20.

7) Удаление вершины – вершина удаляется из графа вместе со всеми инцидентными ей ребрами. См. рис.21.

Определение. Дополнением графа называется такой граф , в котором две вершины смежны тогда и только тогда, когда они не смежны в .

Граф имеет те же вершины, что и граф . Граф имеет те и только те рёбра, которые добавляются в граф , чтобы он стал полным.

Например, на рис. 9 представлена диаграмма дополнения графа на рис. 1.

Рис. 9. Дополнение

Определение. Объединением графов и , не имеющих общих вершин и ребер, называется граф .

Граф содержит вершины и ребра, принадлежащие хотя бы одному из графов.

Например, на рис. 10 представлены диаграммы графов и и диаграмма их объединения .

Рис. 10. Объединение графов

Определение. Соединением Графов и , не имеющих общих вершин и ребер, называется граф .

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

Например, на рис. 11 представлены диаграммы графов и и диаграмма их соединения .

Рис. 11. Соединение графов

Определение. Удалением вершины графа называется операция, состоящая в удалении этой вершины Вместе с инцидентными ей ребрами.

Для обозначения удаления вершины графа используется символ .

Например, На рис. 12 представлен результат удаления вершины графа на рис. 1.

Рис. 12. Диаграмма графа

Определение. Удалением ребра графа называется операция удаления этого ребра при сохранении всех вершин графа.

Для обозначения удаления ребра графа используется символ .

Например, на рис. 13 представлен результат удаления ребра графа на рис. 1.

Рис. 13. Диаграмма графа

Определение. Добавлением новой вершины графа называется операция добавления этой вершины к множеству вершин , при сохранении всех ребер графа .

Для обозначения добавления новой вершины графа используется символ .

Например, на рис. 14 представлен результат добавления вершины графа на рис. 1.

Рис. 14. Диаграмма графа

Определение. Добавлением нового ребра графа называется операция добавления этого ребра к множеству ребер , при сохранении всех вершин .

Для обозначения добавления нового ребра графа используется символ .

Например, На рис. 15 представлен результат добавления ребра графа на рис. 1.

Рис. 15. Диаграмма графа

Определение. Стягиванием Подграфа графа называется операция, состоящая в следующем:

1) нахождение множества ;

2) нахождение множества ;

3) добавление к множеству новой вершины;

4) добавление к множеству новых ребер, инцидентных новой вершине и соединяющих новую вершину с оставшимися старыми вершинами.

Для обозначения стягивания подграфа графа используется символ .

Например, На рис. 16 представлены диаграммы графов и и диаграмма стягивания подграфа графа .

Рис. 16. Диаграмма графа

Определение. Размножением вершины графа называется операция, состоящая в следующем:

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

2) добавление пары новых вершин вместе с соединяющим их ребром;

3) соединение каждой из новых вершин с другими вершинами.

Для обозначения размножения вершины графа используется символ .

Например, На рис. 17 представлена диаграмма графа и диаграмма размножения его вершины.

Рис. 17. Диаграмма графа

Задачи и упражнения

30. Определите типы графов на рис. 23 и на
рис. 24.

31. Графы и заданы диаграммами:

Постройте диаграммы следующих графов, являющихся результатами операций над графами и :

1) , ;

2) , , , ;

3) , , , ;

4) , , ;

5) , ;

6) , , , ;

7) , , , ;

8) , где , , Æ;

9) .

32. Постройте диаграммы следующих графов, являющихся результатами операций над графами и задачи 4.1: