Density

Материал из WikiGrapp
Версия от 14:54, 24 марта 2011; Glk (обсуждение | вклад) (Новая страница: «'''Density''' --- плотность. Let <math>G</math> be a graph with a vertex set <math>V(G)</math> and an edge set <math>E(G)</math>. The '''density''' of <ma…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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].