Complement of a graph, complementary graph

Материал из WikiGrapp
Версия от 13:20, 5 ноября 2014; KEV (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

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.