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

План
1. Бинарные операции.
2. Унарные операции.

ПОВТОРЕНИЕ
Геометрическое представление графа — это схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых
Графом G(V, E) называется совокупность двух множеств — непустого множества V (множества вершин) и множества E (множество рѐбер)
вершина
ребро
дуга

СПОСОБЫ ОПИСАНИЯ ГРАФОВ
Способы описания графов
Перечисление элементов
Изображение
Матрица смежности
Матрица инциденций
Списки смежности

ОПЕРАЦИИ НАД ГРАФАМИ
Исходные графы
Различают бинарные и унарные операции

ОБЪЕДИНЕНИЕ ГРАФОВ
Объединением (суммой) множеств А и В называется множество А ∪ В, элементы которого принадлежат хотя бы одному из этих множеств. Например, если А={1,2,4}, B={3,4,5,6}, то А ∪ B = {1,2,3,4,5,6}

ОБЪЕДИНЕНИЕ ГРАФОВ
При объединении графов матрица смежности результата получается операцией поэлементного логического сложения матриц смежности исходных графов G1 и G2 .

ПЕРЕСЕЧЕНИЕ ГРАФОВ
Пересечением (произведением) множеств А и В называется множество А ∩ В, элементы которого принадлежат как множеству А, так и множеству В. Например, если А={1,2,4}, B={3,4,5,2}, то А ∩ В = {2,4}

ПЕРЕСЕЧЕНИЕ ГРАФОВ
результирующая матрица смежности получается операцией поэлементного логического умножения матриц смежности исходных графов G1 и G2

КОЛЬЦЕВАЯ СУММА ГРАФОВ
Кольцевой суммой множеств А и В называют множество, состоящее из тех и только тех элементов, которые принадлежат множеству А, но не принадлежат множеству В или принадлежат множеству В, но не принадлежат множеству А.

КОЛЬЦЕВАЯ СУММА ГРАФОВ
результирующая матрица смежности получается операцией поэлементного логического сложения матриц
смежности исходных графов

УДАЛЕНИЕ ВЕРШИНЫ
Результат - граф, получившимся после удаления из графа G вершины хi и всех ребер, инцидентных этой вершине
Удалена вершина x3, в матрице смежности удалены строка 3 и столбец 3

УДАЛЕНИЕ РЕБРА ИЛИ ДУГИ
Концевые вершины удаляемого ребра НЕ УДАЛЯЮТСЯ
Удалены дуги a4 и a7, в матрице смежности элементы A23, A43

ЗАМЫКАНИЕ (ОТОЖДЕСТВЛЕНИЕ)
пара вершин хi и xj в графе G замыкается (или отождествляется), если они заменяются такой новой вершиной, что все дуги в графе G, инцидентные хi и xj , становятся инцидентными новой вершине
Замкнуты вершины x1 и x2. Матрица смежности графа после выполнения операции замыкания вершин хi и xj получается путем поэлементного логического сложения i-го и j-го столбцов и i-ой и j-ой строк в исходной матрице и "сжимания" матрицы по вертикали и горизонтали

СТЯГИВАНИЕ
вверху – стягивание дуги a1, внизу – дуг a1 , a6 и a7
Под стягиванием подразумевают операцию удаления дуги или ребра и отождествление его концевых вершин

Контрольные вопросы
Выполнить операцию пересечения для графов, показанных на рисунке.

Контрольные вопросы
Выполнить операцию пересечения для графов, представленных матрицами смежности смежности.

Источники информации
Программирование, компьютеры и сети https://progr-system.ru/