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