Bipartite density: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
(Новая страница: «'''Bipartite density''' --- двудольная плотность. Let <math>G = (V,E)</math> be a ''simple graph'' Let <math>H</math> be any ''bipartite''subgra…»)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Bipartite density''' --- двудольная плотность.  
'''Bipartite density''' — ''[[двудольная плотность]].''


Let <math>G = (V,E)</math> be a ''simple graph'' Let <math>H</math> be any ''bipartite''subgraph
Let <math>\,G = (V,E)</math> be a ''[[simple graph]]''. Let <math>\,H</math> be any ''[[bipartite graph|bipartite]]'' [[subgraph]]
of <math>G</math> with the maximum number of edges. Then (<math>\varepsilon(G) =
of <math>\,G</math> with the maximum number of [[edge|edges]]. Then (<math>\varepsilon(G) =
|E(G)|</math>)
|E(G)|</math>)
<math>b(G) = \frac{\varepsilon(H)}{\varepsilon(G)}</math>


is called the '''bipartite density''' of <math>G</math>. The problem of
:::::<math>b(G) = \frac{\varepsilon(H)}{\varepsilon(G)}</math>
determining the bipartite density of a graph is ''NP-complete problem''
 
even if <math>G</math> is ''cubic''and ''triangle-free''
is called the '''bipartite density''' of <math>\,G</math>. The problem of
determining the bipartite density of a [[graph, undirected graph, nonoriented graph|graph]] is ''[[NP-complete problem]]''
even if <math>\,G</math> is ''[[cubic graph|cubic]]'' and ''[[triangle-free graph|triangle-free]]''
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Навигация