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

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

Let G be a graph with a vertex set V(G) and an edge set E(G). The density of G is defined by

d(G) = \frac{|E(G)|}{|V(G)|}.

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

m(G) = \max_{H \subseteq G} d(H).

m(G) is called the global density of G.