Complement of a graph, complementary graph: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Complement of a graph, complementary graph''' --- дополнение графа. The '''complementary graph''' <math>\bar{G} = (V, \bar{E})</math> of a graph …») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Complement of a graph, complementary graph''' | '''Complement of a graph, complementary graph''' — ''[[дополнение графа]].'' | ||
The '''complementary graph''' <math>\bar{G} = (V, \bar{E})</math> of a graph <math>G = (V,E)</math> is | The '''complementary graph''' <math>\bar{G} = (V, \bar{E})</math> of a [[graph, undirected graph, nonoriented graph|graph]] <math>\,G = (V,E)</math> is defined by <math>\bar{E} = \{(x,y): x,y \in V\mbox{ and }x \neq y\mbox{ and }(x,y) \not \in E\}</math>. | ||
defined by <math>\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>G</math>, the simple digraph <math>\bar{G}</math> is defined by | Given a [[simple graph|simple]] digraph <math>\,G</math>, the simple [[digraph]] <math>\bar{G}</math> is defined by | ||
<math> \begin{array}{l} V(\bar{G}) = V(G), \\ | <math> \begin{array}{l} V(\bar{G}) = V(G), \\ | ||
E(\bar{G}) = V(G) \times V(G) - E(G). | E(\bar{G}) = V(G) \times V(G) - E(G). \end{array}</math> | ||
\end{array}</math> | |||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Версия от 06:20, 5 ноября 2014
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.