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

Рассмотрим некоторые основные операции, позволяющие из уже имеющихся графов получать новые графы.

1. Объединение (сумма) графов. Объединением G₁ È G₂ графов G₁ = (S₁, U₁) и G₂ = (S₂, U₂) называется граф (S₁ È S₂, U₁ È U₂).

2. Пересечение (произведение) графов. Пересечением G₁ Ç G₂ графов

G₁ = (S₁, U₁) и G₂ = (S₂, U₂), где S₁ Ç S₂ ¹ Æ, называется граф (S₁ Ç S₂, U₁ Ç U₂).

3. Дополнение простого графа. Дополнением простого графа G = (S, U) называется простой граф , имеющий те же вершины, что и граф G, причëмлюбые две различные вершины смежны в тогда и только тогда, когда они не смежны в G.

4. Прямое произведение графов. Граф G = (S, U) называется произведением G₁ ´ G₂ графов G₁ = (S₁, U₁) и G₂ = (S₂, U₂), если S = S₁ ´ S₂, а множество рëбер U образуется следующим образом: вершины (x₁, x₂) и (y₁, y₂) смежны в графе G тогда и только тогда, когда либо вершины x₁ и y₁ совпадают, а вершины x₂ и y₂ смежны в G₂, либо вершины x₂ и y₂ совпадают, а вершины x₁ и y₁ смежны в G₁.

5. Удаление вершины. Операция, заключающаяся в удалении из графа

G = (S, U) вершины x и всех инцидентных ей рëбер (дуг), называется операцией удаления вершины x из графа G. В результате получается подграф G (S \{ x }).

6. Удаление ребра (дуги). Операция, заключающаяся в удалении ребра (дуги) u из множества рëбер (дуг) U графа G = (S, U), называется операцией удаления ребра (дуги) u из графа G. Концы ребра (дуги) u не удаляются.

7. Добавление вершины. Операция, которая из графа G = (S, U) порождает граф G ¢ = (S È{ x }, U), называется операцией добавления вершины x к графу G.

8. Добавление ребра (дуги). Операция, которая из графа G = (S, U) порождает граф G ¢= (S È{ x, y }, U È{(x, y)}, называется операция добавления ребра (дуги)

(x, y)к графу G.

9. Отождествление вершин. Пусть x и y – две произвольные вершины графа

G = (S, U). Операцией отождествления вершин x и y называется операция, заключающаяся в удалении из графа G вершин x и y и присоединении к полученному графу новой вершины z, соединив еë ребром (дугой) с каждой из вершин, входящих в объединение M множеств вершин, смежных с вершинами x и y в графе G. Если G – орграф, то для любой вершины a Î M присоединяется дуга

(a, z), если (a, x)Î U или (a, y)Î U, и дуга (z, a), если (x, a)Î U или (y, a)Î U.

10. Стягивание ребра (дуги). Операцией стягивания ребра (дуги) называется отождествление двух смежных вершин. Граф G называется стягиваемым к графу G₁, если G₁ получается из G в результате некоторой последовательности стягиваний рëбер (дуг).

11. Операция подразбиения ребра (дуги). Операцией подразбиения ребра (дуги) (x, y) графа G = (S, U) называется операция, заключающаяся в удалении из U ребра (дуги) (x, y), добавлении к S новой вершины z и добавлении к

U \ {(x, y)} двух рëбер (x, z) и (z, y).