Complement of a graph, complementary graph

Complement of a graph, complementary graph — дополнение графа.

The complementary graph $\bar{G} = (V, \bar{E})$ of a graph $\,G = (V,E)$ is defined by $\bar{E} = \{(x,y): x,y \in V\mbox{ and }x \neq y\mbox{ and }(x,y) \not \in E\}$.

Given a simple digraph $\,G$, the simple digraph $\bar{G}$ is defined by

$\begin{array}{l} V(\bar{G}) = V(G), \\ E(\bar{G}) = V(G) \times V(G) - E(G). \end{array}$

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.