Complement of a graph, complementary graph: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Complement of a graph, complementary graph''' --- дополнение графа. The '''complementary graph''' <math>\bar{G} = (V, \bar{E})</math> of a graph …»)
 
Нет описания правки
 
Строка 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.

Текущая версия от 10:48, 24 октября 2018

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.