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

Пусть %%G_1 = (V_1, E_1)%% и %%G_2 = (V_2, E_2)%% — какие-либо два графа.

Дополнением графа %%G_1 = (V_1, E_1)%% называется граф %%\overline {G} = (V_1, \overline {E_1})%%, множеством вершин которого является множество %%V_1%%, а множеством ребер — %%\overline {E_1} = \{e \in V_1 \times V_1~ |~ e \notin E_1\}%%.

Объединением графов %%G_1%% и %%G_2%% при условии, что %%V_1 \cap V_2 = \varnothing%%; %%E_1 \cap E_2 = \varnothing%%, называется граф %%G_1 \cup G_2 = (V_1 \cup V_2, E_1 \cup E_2)%%.

Пересечением графов %%G_1%% и %%G_2%% называется граф %%G_1 \cap G_2 = (V_1 \cap V_2, E_1 \cap E_2)%%.