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

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

Объединение графов G1 и G2 , обозначаемое как $$G_{1} \cup G_{2}$$, представляет такой граф $$G_{3} = (Х_{1} \cup Х_{2}, A_{1} \cup A_{2})$$, что множество его вершин является объединением Х1 и Х2 , а множество ребер – объединением A1 и A2 . Граф G3 , полученный операцией объединения графов G1 и G2 , показан на ,д, а его матрица смежности – на ,е. Матрица смежности результирующего графа получается операцией поэлементного логического сложения матриц смежности исходных графов G1 и G2 .

Пересечение графов G1 и G2 , обозначаемое как $$G_{1} \cap G_{2}$$, представляет собой граф $$G_{4} = (Х_{1} \cap Х_{2}, A_{1} \cap A_{2})$$. Таким образом, множество вершин графа G4 состоит из вершин, присутствующих одновременно в G1 и G2 . Операция пересечения графов $$G_{1} \cap G_{2}$$ показана на ,в, а результирующая матрица смежности получается операцией поэлементного логического умножения матриц смежности исходных графов G1 и G2 . показана на .г.

Рис.2.2. Операция пересечения и кольцевой суммы: а – граф G1 ; б – граф G2 ; в – граф $$G_{1} \cap G_{2}$$ ; г – матрица смежности графа $$G_{1} \cap G_{2}$$ ; д – граф $$G_{1} \oplus G_{2 }$$ ; е – матрица смежности графа $$G_{1} \oplus G_{2 }$$

Кольцевая сумма двух графов G1 и G2 , обозначаемая как $$G_{1} \oplus G_{2}$$, представляет собой граф G5 , порожденный на множестве ребер $$A_{1} \oplus A_{2}$$. Другими словами, граф G5 не имеет изолированных вершин и состоит только из ребер, присутствующих либо в G1 , либо в G2 , но не в обоих одновременно. Кольцевая сумма графов G1 и G2 показана на ,д, а результирующая матрица смежности получается операцией поэлементного логического сложения по mod 2 матриц смежности исходных графов G1 и G2 . показана на .е.

Легко убедиться в том, что три рассмотренные операции коммутативны т. е. $$G_{1} \cup G_{2} = G_{2} \cup G_{1}, G_{1} \cap G_{2} = G_{2} \cap G_{1}, G_{1} \oplus G_{2} = G_{2} \oplus G_{1}$$, и многоместны, т. е. $$G_{1} \cup G_{2} \cup G_{3} \cup G_{4} \cup \dots , G_{1} \cap G_{2} \cap G_{3} \cap G_{4} \cap ..$$. и так далее.

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

Удаление вершины. Если хi -вершина графа G = (X, A), то G–хi -порожденный подграф графа G на множестве вершин X–хi , т. е. G–хi является графом, получившимся после удаления из графа G вершины хi и всех ребер, инцидентных этой вершине. Удаление вершины х3 показано на ,б (для исходного графа, изображенного на ,а). Матрица смежности исходного графа представлена на таблице 2.1а). Результирующая матрица смежности графа после выполнения операции удаления вершины хi получается путем удаления соответствующего ). В дальнейшем элементы графа могут быть переобозначены.

Удаление ребра или удаление дуги. Если ai - дуга графа G = (X, A), то G-ai – подграф графа G, получающийся после удаления из G дуги ai . Заметим, что концевые вершины дуги ai не удаляются. Удаление из графа множества вершин или дуг определяется как последовательное удаление определенных вершин или дуг. Удаление дуг a4 и a7 показано на ,в. Результирующая матрица смежности графа после выполнения операции удаления дуги ai получается путем удаления соответствующих элементов из исходной матрицы ().

Замыкание или отождествление. Говорят, что пара вершин хi и xj в графе G замыкается (или отождествляется), если они заменяются такой новой вершиной, что все дуги в графе G, инцидентные хi и xj , становятся инцидентными новой вершине. Например, результат замыкания вершины х1 и х2 показан на ,г для графа ,а). Матрица смежности графа после выполнения операции замыкания вершин хi и xj получается путем поэлементного логического сложения ).

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