Metrization of weighted graphs

Abstract: We find a set of necessary and sufficient conditions under which the weight

w : E o m a t h b b R^{+}

on the graph

G = (V, E)

can be extended to a pseudometric

d : V i m e s V o m a t h b b R^{+}

. If these conditions hold and

G

is a connected graph, then the set

m a t h f r a k M_{w}

of all such extensions is nonvoid and the shortest-path pseudometric

d_{w}

is the greatest element of

m a t h f r a k M_{w}

with respect to the partial ordering

d_{1} l e q s l a n t d_{2}

if and only if

d_{1} (u, v) l e q s l a n t d_{2} (u, v)

for all

u, v i n V

. It is shown that every nonvoid poset

(m a t h f r a k M_{w}, l e q s l a n t)

contains the least element

h o_{0, w}

if and only if

G

is a complete

k

-partite graph with

k g e q s l a n t 2

and in this case the explicit formula for computation of

h o_{0, w}

is obtained.

Recommendations

Cites Work

Cited In (12)

This page was built for publication: Metrization of weighted graphs