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

Объединение графов и , обозначаемое как , представляет такой граф , что множество его вершин является объединением и , а множество ребер – объединением и . Граф , полученный операцией объединения графов и . Пересечение графов и , обозначаемое как , представляет собой граф . Таким образом, множество вершин графа G4 состоит из вершин, присутствующих одновременно в и .

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

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

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

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

Стягивание: Под стягиванием подразумевают операцию удаления дуги или ребра и отождествление его концевых вершин.(а->д)