Complement of a graph, complementary graph
Перейти к навигации
Перейти к поиску
Complement of a graph, complementary graph — дополнение графа.
The complementary graph [math]\displaystyle{ \bar{G} = (V, \bar{E}) }[/math] of a graph [math]\displaystyle{ \,G = (V,E) }[/math] is defined by [math]\displaystyle{ \bar{E} = \{(x,y): x,y \in V\mbox{ and }x \neq y\mbox{ and }(x,y) \not \in E\} }[/math].
Given a simple digraph [math]\displaystyle{ \,G }[/math], the simple digraph [math]\displaystyle{ \bar{G} }[/math] is defined by
[math]\displaystyle{ \begin{array}{l} V(\bar{G}) = V(G), \\ E(\bar{G}) = V(G) \times V(G) - E(G). \end{array} }[/math]
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.