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

Введем несколько операций над графами. Первые три операции, включающие два графа, Бинарные, а остальные четыре - Унарные, т. е. определены на одном графе. Рассмотрим графы G1=(V1, Е1) и G2=(V2, E2).

Объединение графов G1 и G2, обозначаемое как G1⋃ G2, представляет собой такой граф G3= (V1⋃ V2, E1⋃ E2), что множество его вершин является объединением V1 и V2, а множество ребер - объединением E1 и Е2. Например, графы G1 и G2 и их объединение представлены на рис. 14, а, б и 15,в.

Пересечение графов G1 и G2, обозначаемое как G1⋂ G2, представляет собой граф G3 = {V1⋂ V2, E1⋂ Е2). Таким образом, множество вершин G3 состоит только из вершин, присутствующих одновременно в графах G1 и G2, а множество ребер G3 состоит только из ребер, присутствующих одновременно в G1 и G2. Пересечение графов G1 и G2 (рис. 14, а, б) показано на рис. 15, г. Кольцевая сумма двух графов G1 и G2, обозначаемая как G1⨁ G2, представляет собой граф G3, порожденный на множестве ребер E1⨁ Е2. Другими словами, граф G3 не имеет изолированных вершин и состоит только из ребер, присутствующих либо в G1, либо в G2, но не в обоих графах одновременно. Кольцевая сумма графов (рис. 14, а, б) показана на рис. 16, д.

Легко убедиться в том, что три рассмотренные Операции Коммутативны, т. е. G1⋃ G2 = G2⋃ G1, G1⋂ G2 = G2⋂ G1, G1⨁ G2 = G2⨁Gl.

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

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

Рисунок 16 д

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

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

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

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

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

Рисунок 17

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

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

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

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

Рисунок 18

< Предыдущая		Следующая >