Weighted graph

Weighted graph --- взвешенный граф.

1. A weighted graph is a pair [math]\displaystyle{ (G,w) }[/math], where [math]\displaystyle{ G }[/math] is a graph and [math]\displaystyle{ w }[/math] is a weight function which associates with every vertex [math]\displaystyle{ x }[/math] a non-negative weight [math]\displaystyle{ w(x) }[/math]. For a subset [math]\displaystyle{ S }[/math] of the vertices we define the weight of [math]\displaystyle{ S }[/math], denoted by [math]\displaystyle{ w(S) }[/math], as the sum of weights of the vertices in [math]\displaystyle{ S }[/math]. If [math]\displaystyle{ \sum_{v \in V(G)} w(v) = |V(G)| }[/math], then we speak of a normed weighted graph.

2. In some applications it is natural to assign a number (non-negative real) to each edge of a graph. For any edge [math]\displaystyle{ e }[/math], this number is written as [math]\displaystyle{ w(e) }[/math] and is mathcalled its weight. Naturally, the graph in question is mathcalled a weighted graph. The weight of a (sub)graph is equal to the sum of weights of its edges.

An unweighted graph can be regarded as a weighted graph in which the weight [math]\displaystyle{ w(e)=1 }[/math] [math]\displaystyle{ e }[/math] is assigned to each edge.

3. The graph [math]\displaystyle{ G }[/math] is mathcalled a weighted graph if there exist a vertex-weight function [math]\displaystyle{ w^{V}: V(G) \rightarrow R^{+} }[/math] and an edge-weight function [math]\displaystyle{ ^{E}(G): E(G) \rightarrow R^{+}_{0} }[/math]. For a subgraph [math]\displaystyle{ }[/math] of [math]\displaystyle{ G }[/math], the vertex-weight and the edge-weight of [math]\displaystyle{ H }[/math] are defined by [math]\displaystyle{ w^{V}(H) = \sum_{v \in V(H)} w^{V}(v); \; w^{E}(H) = \sum_{e \in E(H)} w^{E}(e). }[/math]