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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Новая страница: «'''Bipartite density''' --- двудольная плотность. Let <math>G = (V,E)</math> be a ''simple graph'' Let <math>H</math> be any ''bipartite''subgra…»)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 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.

Текущая версия от 11:54, 29 февраля 2012

Bipartite densityдвудольная плотность.

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

[math]\displaystyle{ b(G) = \frac{\varepsilon(H)}{\varepsilon(G)} }[/math]

is called the bipartite density of [math]\displaystyle{ \,G }[/math]. The problem of determining the bipartite density of a graph is NP-complete problem even if [math]\displaystyle{ \,G }[/math] is cubic and triangle-free

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.