4624
правки
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]]'' | |||