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

В этом разделе мы введем несколько операций над графами. Первые три операции, включающие два графа, бинарные, а осталь четыре — унарные, т. е. определены на одном графе. Рассмотрим графы

(см. скан)

Рис. 1.9. Объединение, пересечение и кольцевая сумма графов. а — граф б — граф

Объединение графов обозначаемое как представляет собой такой граф , что множество его вершин является объединением , а множество ребер — объединением Например, графы и их объединение представлены на рис. 1.9, а, б, в.

Пересечение графов обозначаемое как представляет собой граф Таким образом, множество вершин состоит только из вершин, присутствующих одновременно в графах а множество ребер состоит только из ребер, присутствующих одновременно в Пересечение графов (рис. 1.9, а, б) показано на рис. 1.9, г. Кольцевая сумма двух графов обозначаемая как представляет собой граф порожденный на множестве ребер . Другими словами, граф не имеет изолированных вершин и состоит только из ребер, присутствующих либо в либо в но не в обоих графах одновременно. Кольцевая сумма графов (рис. 1.9, а, б) показана на рис. 1.9, д.

Легко убедиться в том, что три рассмотренные операции коммутативны, т. е.

Рис. 1.10. Удаление ребра и удаление вершины. а — граф G; б —

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

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

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

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

Если — подграф графа , то через будем обозначать граф . Таким образом, — дополнение подграфа

Удаление вершины и удаление ребра показано на рис. 1.10.

Рассматриваемая далее операция замыкания, или отождествления, хорошо знакома инженерам-электрикам.

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

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

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

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

Рис. 1.11. Операции отождествления и стягивания в графе, а — граф G; б — граф G после отождествления в — граф G после стягивания и