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

Для графов и их объединение определяется как граф , а пересечение – как граф .

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

Под суммой двух абстрактных графов понимают объединение графов с непересекающимися множествами вершин. Точнее говоря, имеется в виду следующее. Сначала вершинам графов-слагаемых присваиваются имена (пометки, номера) так, чтобы множества вершин не пересекались, затем полученные графы объединяются и пометки стираются (т.е. результат операции – тоже абстрактный граф). Операция сложения ассоциативна, то есть для любых трех графов. Поэтому можно образовывать сумму любого числа графов, не указывая порядка действий с помощью скобок. Если складываются k экземпляров одного и того же графа G, то полученный граф обозначается через . Например, .

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

Рис. 1.

Произведение графов и определяется следующим образом. Множеством вершин графа является декартово произведение множеств и , то есть вершины этого графа – упорядоченные пары , где , . Вершины и в графе смежны тогда и только тогда, когда и смежна с в графе , или и смежна с в графе . С помощью операции произведения можно выразить некоторые важные графы через простейшие. Например, произведение двух путей дает прямоугольную решетку – см. рисунок 2.

Рис. 2.

Другой пример – k- мерный куб , определяемый следующим образом. Вершинами его являются всевозможные упорядоченные двоичные наборы длины k. Всего, таким образом, в этом графе вершин. Вершины и смежны в нем тогда и только тогда, когда наборы x и y различаются точно в одной координате. С помощью операции произведения граф можно определить рекурсивно: