Does edge weight of a undirected weighted graph must be a metric?

249 Views Asked by At

In a undirected weighted graph, each edge is assigned with a weight $w: E\rightarrow R$. Does $w(\cdot)$ must be a metric ? That is, $w$ satisfies the following three conditions

(1) $w(x, y) > 0 $ for any edges pair $x$ and $y$;

(2) $w(x, y) = w(y, x)$;

(3) $w(x, y) + w(y, z) \geq w(x, z)$.

2

There are 2 best solutions below

0
On BEST ANSWER

It's obvious that $w$ cannot be a metric in general, because $w(x,y)$ is undefined if $(x,y)$ is not an edge. But:

Suppose $(V,E)$ is a connected undirected graph and $w(x,y)>0$ for every $(x,y)\in E$ with $x\ne y$; if edges of the form $(x,x)$ are allowed, assume $w(x,x)=0$ whenever $(x,x)\in E$. For $x,y\in V$ define $d(x,y)=0$ if $x=y$ and otherwise say $d(x,y)$ is the infimum of $\sum w(x_j,x_{j-1})$ over all paths $x=x_0,\dots, x_n=y$ (such that each $(x_j,x_{j-1})$ is an edge). Then it's easy to show $d$ is a metric. (Here I'm assuming that "undirected" means that if $(x,y)\in E$ then $(y,x)\in E$ and $w(y,x)=w(x,y)$.)

0
On

No, it doesn't have to be a metric.

I haven't found a complete and fully explicit definition of a weighted graph anywhere, but I've found several informal descriptions of weighted graphs, and none of them say that the weight function has to be a metric.

In particular, none of the descriptions I've found say that the weight function has to satisfy the triangle inequality $w(x, y) + w(y, z) \geq w(x, z)$. For example, these lecture notes by William D McQuain of Virginia Tech show a weighted graph which includes three vertices $b$, $h$ and $i$, such that $w(b,h) = 5$ and $w(h,i) = 15$, but $w(b,i) = 25$.