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

Даны два графа: G1=(N1,U1) и G2=(N2,U2)

Бинарные операции.

1.Объеденением графов G1 и G2 назыв граф D=G1∪G2, множество вершин которого=(N1∪N2)

D=G1∪G2=(N1∪N2, U1∪U2)

2.Пересечением рёбер графов G1 и G2 назыв граф Д, множество вершин которого является пересечением множества вершин G1 и G2: Д=G1∩G2=(N1∩N2,U1∩U2)

3.Произведением графов G1 и G2 называется граф, множество вершин которого объеденены множеством вершин исходных графов.

G1xG2=(N1∪N2, U1∪U2∪W)

W={(i,j):іЄN1, jЄN2}

Унарные операции

Дан исходный граф G=(N,U)

1.Дополнение до полного графа назыв граф дополнения графа ¬G с множеством рёбер W(W={(i,j):(i,j)∉U}.

2.Удаление вершины G∖{e}. Удаление вершины е из графа G: удаляется вершина и инцидентные ей рёбра

3.Удаление ребра G∖{i,j}

Удаляются вершины, а концевые вершины этого ребра остаются

4.Стягивание вершин по ребру, соединяющему эти вершины(N∖{i,j}∪{k},W)

Состоит из множества рёбер: из всех рёбер исходного графа, которые не были инциденты в вершине i или в вершине j, а также рёбер (k,l), где k-новая вершина, а l≠i,j и в исходном графе были рёбра(l.i) или (l,j).