Bipartite density

Материал из WikiGrapp
Перейти к:навигация, поиск

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

Let \,G = (V,E) be a simple graph. Let \,H be any bipartite subgraph of \,G with the maximum number of edges. Then (\varepsilon(G) =
|E(G)|)

b(G) = \frac{\varepsilon(H)}{\varepsilon(G)}

is called the bipartite density of \,G. The problem of determining the bipartite density of a graph is NP-complete problem even if \,G is cubic and triangle-free

Литература

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