1
$\begingroup$

I got confused about minimal and minimum in context of graph theory. Although, I have understanding that minimal means more than one minimum i.e. none qualifies as actual minimum so we say them minimal.

What exactly does minimal spanning tree mean? Also, what exactly does 'minimal edge' mean?

How do they differ from minimum spanning tree? How are 'minimal edge' different from minimum edge?

This doubt arose due to the statement:

S: There exists a minimum weight edge in G, which exists in every minimum spanning tree of G.

Can we say on using word 'minimum' it's implied that there is only one minimum weight edge. Besides, statement used "exists" which is singular.

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ Where did you encounter "minimal spanning tree" and "minimal edge"? This statement doesn't mention them. Minimum here means a global minimum: a tree/edge with the smallest weight (there is no other tree/edge with a smaller weight). $\endgroup$
    – user114966
    Mar 2, 2021 at 22:44
  • $\begingroup$ Today, here: link. Although, someone else pointed out too, but he seem to have deleted his comment. $\endgroup$
    – sgoel
    Mar 2, 2021 at 22:47
  • $\begingroup$ @Dmitry, Sir, Does all edges with minimum weight qualifies as Global Minimum, or Do we say Global minimum in that case don't exist? $\endgroup$
    – sgoel
    Mar 2, 2021 at 22:55
  • 1
    $\begingroup$ I agree with this answer: math.stackexchange.com/a/2142655/743044 . Note that "minimum" implies "minimal". So it's not incorrect to use "minimal" instead of "minimum", but no reason to do that. $\endgroup$
    – user114966
    Mar 2, 2021 at 22:55
  • $\begingroup$ All such edges are global minima. (I use word "global" only to stress that they are minima across the set of all edges) $\endgroup$
    – user114966
    Mar 2, 2021 at 22:57

1 Answer 1

Reset to default
1
$\begingroup$

A minimum weight edge is an edge whose weight is minimal among all edges. There can be more than one minimum weight edge. All minimum weight edges have the same weight.

Similarly, a minimum spanning tree is a spanning tree whose weight is minimal among all spanning trees. There can be more than one minimum spanning tree. All minimum spanning trees have the same weight.

In some cases, there is a distinction between minimum and minimal. For example, a minimum vertex cover is a vertex cover whose weight is minimal among all vertex covers. In contrast, a minimal vertex cover is a vertex cover, any proper subset of which isn't a vertex cover. Finding a minimal vertex cover is easy – start with the set of all vertices, and repeatedly remove a vertex as long as it is possible to do so while maintaining the property of covering all edges. In contrast, finding a minimum vertex cover is expected to be hard (the corresponding decision problem is NP-hard).

The same property of being minimal doesn't make much sense for edges and spanning trees. When people say minimal edge or minimal spanning tree, they probably mean minimum (weight) edge and minimum spanning tree.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Sir, I have a confusion, saying something is "minimum" only if it's unique minimal, Is that incorrect?link If graph have all edge weights same, it's bit inconvenient to say graph have all minimum weight edges. $\endgroup$
    – sgoel
    Mar 3, 2021 at 12:07
  • $\begingroup$ You can use a word in any way you like, as long as everybody understands what you mean by the word. The standard definition of minimum doesn't imply uniqueness. $\endgroup$
    – Yuval Filmus
    Mar 3, 2021 at 12:08
  • $\begingroup$ For example, the minimum value attained by the sine function is $-1$. It is not attained uniquely. $\endgroup$
    – Yuval Filmus
    Mar 3, 2021 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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