2015-05-14
1362
В композиции графов, как и в произведении графов, вершины обозначаются парами ab, где символы a и b – обозначения вершин в G 1 и G 2 соответственно.
Разность графов G 1(V 1, E 1)\ G 2(V 2, E 2) = G (V 1\ V 2, E), где E = {[ x 1, x 2]| x 1, x 2 
V 1\ V 2 
[ x 1, x 2] E 1 [ x 1, x 2] 
E 2}
Удаление вершины G (V, E)\{ xi }. Из графа удаляется вершина вместе с инцидентными ребрами. В результате получается подграф, содержащий все ребра инцидентные множеству V \{ xi }.
Удаление ребра G \{ ei }. Удаляется ребро, но при этом сохраняются концевые вершины, получается часть графа.
Добавление вершины К заданному множеству вершин { х 1, x 2, ..., xk } добавляется новая вершина x, смежная с х 1, x 2, ..., xk.
G (V 1, E 1) + { x } = G (V 1 
{ x }, E = E 1 (x, xi), xi V 1), { x } V 1.
Добавление ребра Для заданной пары вершин х, у добавляется ребро e.
G (V 1, E 1) + { e } = G (V 1, E = E 1 { e }), { e } E 1.
Стягивание подграфа A в вершину В результате выполнения этой операции получается граф G (V 1, E 1) = G (V, E)/ A, A 
V , V 1 = V \ A { x }, E 1 = E \{ e = [ x 1, x 2]| x 1, x 2 A } { e = [ x, u ]| u Г(A)\ A }. Г(А) – множество вершин, смежных с вершинами А.
Замыкание или отождествление вершин Вершины xi и xj отождествляются (рис. 2.17), т.е. они заменяются одной новой вершиной, при этом все ребра, инцидентные xi и xj, становятся инцидентны новой вершине.
|
|
|
Рисунок 2.17
Подразбиение ребра, удаляется заданное ребро u = [ х, у ] и добавляется вершина z и цепь (x, u 1, z, u 2, у).
