0
$\begingroup$

This is the formal definition of a minimum spanning tree taken from Algorithms by Dasgupta, Papadimitrious and U. Vazirani.

Input: An undirected graph $G = (V,E)$; edge weights $w_e$.

Output: A tree $T = (V,E')$, with $E' \subseteq E$, that minimizes $$ \operatorname{weight}(T) = \sum_{e \in E'} w_e. $$

My confusion arises from the fact that the edges in the minimum spanning tree are an improper subset of the edges in the original graph. If the graph were cyclic, then we would have removed the cycles in the minimum spanning tree and would have had fewer edges. How is it that we have an improper subset (containing all the edges of the original graph)?

This is the example given right before the definition and the graph clearly contains cycle edges.

graph example

$\endgroup$
8
  • 2
    $\begingroup$ The formal definition is wrong. The graph should be connected. $\endgroup$ – Yuval Filmus Feb 10 at 15:39
  • 2
    $\begingroup$ I'm not sure you got the definition of subset right. A set $A$ is a subset of a set $B$ if every element of $A$ is an element of $B$. If $A \neq B$ then $A$ is a proper subset of $B$. The concept of improper subset is not standard, but it seems to be the same as subset. $\endgroup$ – Yuval Filmus Feb 10 at 15:40
  • $\begingroup$ If $G$ is already a tree, then its only spanning tree is $G$ itself. Does this answer your question? $\endgroup$ – Yuval Filmus Feb 10 at 15:42
  • $\begingroup$ If 𝐺 is already a tree, then its only spanning tree is 𝐺 itself - this would mean that set $A$ and set $B$ are one and the same? $\endgroup$ – heretoinfinity Feb 11 at 16:38
  • $\begingroup$ If $A = B$ then, in particular, $A$ is a subset of $B$. However, it is not a proper subset of $B$. $\endgroup$ – Yuval Filmus Feb 11 at 16:40
3
$\begingroup$

It looks like you misread or misunderstand the standard set notation "$E'\subseteq E$".

That notation just means $E'$ is a subset of $E$, i.e. every element of $E'$ is also an element of $E$.


We do not speak of "an improper subset", most of the time if not ever.

Why?

Suppose $A$ and $B$ are two sets. $A$ is a subset of $B$ iff every element of $A$ is also an element of $B$. If, furthermore, $A$ is not $B$, then we say $A$ is a proper (or strict) subset of $B$.

If we want to mention "an improper subset" of $B$, what would it mean?

  • It should mean $B$ itself. That is how I would understand that phrase upon first reading. Then, why do we want to say "an improper subset of $B$", a pretty long phrase, when we can just say "$B$", which is concise? The phrase "an improper subset" seems implying there are more-than-one such subsets for a given set, which is simply wrong.

  • It could just means "subset" when it is used in distinction to "proper subset" (which sounds unnatural to me, but maybe that is only me). Again, why not just use "subset", which is concise?

$\endgroup$
3
  • $\begingroup$ I think "improper subset" is used in distinction to "proper subset", and just means "subset". $\endgroup$ – Yuval Filmus Feb 10 at 15:54
  • $\begingroup$ Compare also $\subset,\subsetneq$ vs $\subseteq,\subset$ – you could argue that $\subseteq$ reflects the concept of "improper subset" (since it explicitly allows equality). $\endgroup$ – Yuval Filmus Feb 11 at 16:42
  • $\begingroup$ An "improper subset" was defined by someone as "the subset consisting of all elements of a given set". The ambiguity of that phrase together with the simpler and clearer alternative to whatever interpretation of that phrase indicates that we should just avoid using that phrase. $\endgroup$ – John L. Feb 12 at 2:50

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.