W-Density

Материал из WikiGrapp

[math]\displaystyle{ w }[/math]-Density --- [math]\displaystyle{ w }[/math]-плотность.

The [math]\displaystyle{ w }[/math]-density of [math]\displaystyle{ G }[/math] is defined by

[math]\displaystyle{ wd(G) = \frac{w^{E}(G)}{w^{V}(G)}. }[/math]

(See Weighted graph.3.) A weighted graph is called [math]\displaystyle{ w }[/math]-balanced, if for each subgraph [math]\displaystyle{ H }[/math] of [math]\displaystyle{ G }[/math], we have [math]\displaystyle{ wd(H) \leq wd(G) }[/math], where [math]\displaystyle{ V(H) }[/math] is assumed to be nonempty. If [math]\displaystyle{ G }[/math] is not [math]\displaystyle{ w }[/math]-balanced, then there exists a subgraph with greater [math]\displaystyle{ w }[/math]-density than that of [math]\displaystyle{ G }[/math]. Let [math]\displaystyle{ wm(G) }[/math] denote the maximum [math]\displaystyle{ w }[/math]-density of a subgraph of [math]\displaystyle{ G }[/math], i.e.

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

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