Bipartite density

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.