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

Пусть $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)$.