Density

Density --- плотность.

Let [math]\displaystyle{ G }[/math] be a graph with a vertex set [math]\displaystyle{ V(G) }[/math] and an edge set [math]\displaystyle{ E(G) }[/math]. The density of [math]\displaystyle{ G }[/math] is defined by

[math]\displaystyle{ d(G) = \frac{|E(G)|}{|V(G)|}. }[/math]

[math]\displaystyle{ G }[/math] is said to be balanced if for each subgraph [math]\displaystyle{ H }[/math] of [math]\displaystyle{ G }[/math] we have [math]\displaystyle{ d(H) \leq d(G) }[/math], where V(H) is assumed to be nonempty. If [math]\displaystyle{ G }[/math] is not balanced, then it contains a subgraph with greater density than that of [math]\displaystyle{ G }[/math]. In particular, we use [math]\displaystyle{ m(G) }[/math] to denote the maximum density of a subgraph of [math]\displaystyle{ G }[/math], i.e.

[math]\displaystyle{ m(G) = \max_{H \subseteq G} d(H). }[/math]

[math]\displaystyle{ m(G) }[/math] is called the global density of [math]\displaystyle{ G }[/math].