3
$\begingroup$

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:E\rightarrow \mathbb{R}$.

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.

$\endgroup$
  • 1
    $\begingroup$ What simpler ways would you be thinking of? $\endgroup$ – Bergi Jul 21 at 14:35
  • $\begingroup$ Something like "every edge in $E$ has exactly one weight value in $\mathbb{R}$" would be much more readable for me. And then, maybe in the next sentence we could put the mathematical definition. For me a function is something else. $\endgroup$ – RichArt Jul 21 at 20:30
  • $\begingroup$ Yes, that's definitely more verbose and readable. We could also define it more rigorously as a binary relation with the desired properties - however, that very kind of relation is what we call a function :-) Also, a function provides the notation $w(e)$ when we want to "get the weight for the edge $e$" in an algorithm. $\endgroup$ – Bergi Jul 21 at 20:51
7
$\begingroup$

Here is the original statement in CLRS.

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

It is pretty good to understand "a weight function $w:E\rightarrow \mathbb{R}$" as "an edge has a weight". In fact, that is how I would interpret that notation in a rush or subconsciously. It is good enough in most situations. I would encourage you to keep this primitive understanding, as it may help forming the most compact and natural representation of knowledge in your mind.

Should we read aloud that notation, we can say "$w$ from $E$ to $\Bbb R$" or "$w$ from capital $E$ to bold $\Bbb R$" literally. Adding a bit of interpretation, we can also say, "function $w$ from edges to real numbers", "function $w$ that maps each edge to a real number", or, even more explicitly, "function $w$ whose domain is the set of edges and whose codomain is the set of real numbers".

While the simple and natural understanding, "an edge has a weight", 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$", is weight something like "2 miles", "5.0 dollars", or "approximate 7.7 pounds"? Could the edge $(u,v)$ also have an extra weight? Should I use the same symbol $w$ for the weight of edge $(u,v')$ that is not edge $(u,v)$? 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: E\to\Bbb 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.

$\begin{aligned} w(T') &= w(T) - w(x,y) + w(u,v)\\ &\le w(T) \end{aligned}$

If you try to express the facts embodied in the above formula in plain English, more than two or even five times longer statements may be needed to attain the same rigor and clarity. The result can hardly be more visually appealing. That is how the notation $w:E\to\Bbb 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.

$\endgroup$
  • $\begingroup$ So, how do you actually read in plain English $w:E\rightarrow \mathbb{R}$ ? Can you update it in your answer above? $\endgroup$ – RichArt Jul 20 at 21:49
  • $\begingroup$ @RichArt Updated. $\endgroup$ – Apass.Jack Jul 21 at 2:02
5
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.