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

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

Версия от 17:22, 22 февраля 2011

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

Let [math]\displaystyle{ G = (V,E) }[/math] be a simple graph Let [math]\displaystyle{ H }[/math] be any bipartitesubgraph 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 cubicand triangle-free