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

Введем несколько операций над графами. Первые три операции, включающие два графа, бинарные, а остальные четыре - унарные, т. е. определены на одном графе. Рассмотрим графы G₁=(V₁, Е₁) и G₂=(V₂, E₂).

Объединение графов G₁ и G₂, обозначаемое как G₁⋃ G₂, представляет собой такой граф G₃= (V₁⋃ V₂, E₁⋃ E₂), что множество его вершин является объединением V₁ и V₂, а множество ребер - объединением E₁ и Е₂. Например, графы G₁ и G₂ и их объединение представлены на рис. 14, а, б и 15,в.

Пересечение графов G₁ и G₂, обозначаемое как G₁⋂ G₂, представляет собой граф G₃ = {V₁⋂ V₂, E₁⋂ Е₂). Таким образом, множество вершин G₃ состоит только из вершин, присутствующих одновременно в графах G₁ и G₂, а множество ребер G₃ состоит только из ребер, присутствующих одновременно в G₁ и G₂. Пересечение графов G₁ и G₂ (рис. 14, а, б) показано на рис. 15, г. Кольцевая сумма двух графов G₁ и G₂, обозначаемая как G₁⨁ G₂, представляет собой граф G₃, порожденный на множестве ребер E₁⨁ Е₂. Другими словами, граф G₃ не имеет изолированных вершин и состоит только из ребер, присутствующих либо в G₁, либо в G₂, но не в обоих графах одновременно. Кольцевая сумма графов (рис. 14, а, б) показана на рис. 16, д.

Легко убедиться в том, что три рассмотренные операции коммутативны, т.е. G₁⋃ G₂ = G₂⋃ G₁, G₁⋂ G₂ = G₂⋂ G₁, G₁⨁ G₂ = G₂⨁G_l.

Рисунок 14 (а,б)

Рисунок 15 (в,г)

Рисунок 16 д

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

Теперь рассмотрим унарные операции на графе.

Удаление вершины. Если v_i - вершина графа G = (V, E), то G - v_i - порожденный подграф графа G на множестве вершин V - v_i, т. е. G - v_i является графом, получившимся после удаления из графа G вершины v_i и всех ребер, инцидентных этой вершине.

Удаление ребра. Если е_i - ребро графа G = (V, E), то G - e_i - подграф графа G, получающийся после удаления из G ребра e_i. Заметим, что концевые вершины ребра e_i не удаляются из G. Удаление из графа множества вершин или ребер определяется как последовательное удаление отдельных вершин или ребер.

Если G₁ = (V', Е') - подграф графа G = (V, Е), то через G - G₁ будем обозначать граф G' = (V, Е - Е'). Таким образом, G - G₁ - дополнение подграфа G₁ в G. Удаление вершины показано на рис. 17 (а – исходный граф, б – вершина удалена).

Рисунок 17

Замыкание или отождествление. Говорят, что пара вершин v_i и v_j в графе G замыкается (или отождествляется), если они заменяются такой новой вершиной, что все ребра в графе G, инцидентные v_i и v_j, становятся инцидентными новой вершине.

Например, результат замыкания вершин v₃ и v₄ в графе рис. 18, а представлен на рис. 18, б.

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

Граф, изображенный на рис. 18, в, получен стягиванием ребер е₁ и е₅ в графе G (рис. 18, а).

Рисунок 18