Mfcttrf

In text books, for instance in the 3rd edition of Introduction to Algorithms, Cormen, on page 625, the weights of the edge set $E$ is defined with a weight function $w:Erightarrow mathbbR$.

Why is it defined in this way? Why do we need a function? I mean, we all know when working with a graph, that the meaning is just that an edge $(u,v)$ has a weight $w$. So, why is it written with a function? I remember the first time I saw this definition I was very confused. Only after actually going through an algorithm and reading it again, I realized that it really just means that every edge has its weight.

So, I still don't fully understand why it is written in this complicated way and what exactly it means though, and it would be very nice if someone could tell me that in a understandable language.

It means that each edge has only one weight, which is defined as a real number.

So, this definition in compact form excludes many cases, for example:

• an edge doesn't have weight at all


• an edge has two (or more) weights


• an edge has weight as a complex number


• etc.

Here is the original statement in CLRS.

Assume that we have a connected, undirected graph $G$ with a weight function $w: EtoBbb R$, and we wish to find a minimum spanning tree for $G$.

It is pretty good to understand "a weight function $w:Erightarrow mathbbR$" as "an edge has a weight". In fact, that is how I would read that notation immediately. I would encourage you to keep this primitive understanding, in an attempt to form the most compact and natural representation of knowledge in your mind.

While that simple and natural understanding is probably enough to understand the setup for that section of the book, that mathematical notation has some distinct advantages.

In general, although expressive and colorful, natural languages or thoughts, are more complex and abound with ambiguity and arbitrary vagueness. If "an edge $(u,v)$ has a weight $w$", could the edge $(u,v)$ also has two different weight? Is weight something like "6 pounds", "12 dollars", or "3 miles"? If edge $(u,v')$ is not edge $(u,v)$, do I have to use the same symbol $w$ for the weight of $(u,v')$ or should I use a different symbol? While these questions may or may not pose a problem for you, it might for other readers of the book.

On the other hand, the notation "$w: EtoBbb R$" defines exactly what is the domain, codomain and the kind of correspondence of a relation. To be pedantic, it means the symbol/entity $w$ associates to every element of $E$, i.e, an edge of $G$ exactly one element of $R$, i.e, a real number. There is no room to err.

Moving down the road, page 648 of the book presents the following formula.

$beginaligned
w(T') &= w(T) - w(x,y) + w(u,v)\
&le w(T)
endaligned$

You can try to express the facts embodied in the above formula in plain English. You may need three or even ten times longer statements to express with the same rigor and clarity. You cannot be more visually appealing. That is how the notation $w:EtoBbb R$ shines.

The power of mathematics notations, including notations in computer science, is what you would like to master if you want to dive further into the mathematics, computer science and many other subjects where symbolic computations are needed and useful. In a sense, notations like this are beautiful data types. You can get familiar with them. You can become comfortable with them.

There are many problems which are solvable in the unweighted version but not for weighted version. Here they consider weighted version.