Metrization of weighted graphs

Abstract

We find a set of necessary and sufficient conditions under which the weight $w:E\to {\mathbb{R}}^{+}$ on the graph $G=(V,E)$ can be extended to a pseudometric $d:V\times V\to {\mathbb{R}}^{+}$. If these conditions hold and $G$ is a connected graph, then the set ${\mathfrak{M}}_w$ of all such extensions is nonvoid and the shortest-path pseudometric $d_w$ is the greatest element of ${\mathfrak{M}}_w$ with respect to the partial ordering $d_1⩽d_2$ if and only if $d_1(u,v)⩽d_2(u,v)$ for all $u,v\in V$. It is shown that every nonvoid poset $({\mathfrak{M}}_w,⩽)$ contains the least element ${\rho }_{0,w}$ if and only if $G$ is a complete $k$-partite graph with $k⩾2$ and in this case the explicit formula for computation of ${\rho }_{0,w}$ is obtained.

7 figures