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

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.

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

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

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

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

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

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

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