Лекции_по_ДМ

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

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 последовательно стягиваются ребра е₁, е₃, е₂.

Содержание