3
$\begingroup$

As my title points out, I don't understand how do you show that, in general, the diameter of a MST (minimal spanning tree) can be bigger than the diameter of G, by the factor $\Omega(n)$. $(n:= |V|, G =(V,E)) $.

And I don't understand, how big is $\Omega(n)$ and why $\Omega$?

I made a example where the distance of two nodes in $G$ is smaller than the distance of the two nodes in the MST.

diamter of G and the MST of G

Is it correct to write,

  • $D_{MST} = D_{G} \cdot \Omega(n)$ ?
  • $\Omega(n) = D_{MST}/D_{G}$ ?

$D_{G} =$ diameter of graph $G$ and $D_{MST} =$ diameter of MST.

$\endgroup$
1
$\begingroup$

You say that you don't understand how to show that the diameter of a MST can be $\Omega(n)$ larger than the diameter of the underlying graph.

However, it seems that what you don't understand is what it means that the diameter of a MST can be $\Omega(n)$ larger than the diameter of the underlying graph.

It is impossible to prove a theorem if you don't understand its statement.

Here is what you are asked to do. Given a weighted graph $G$, we will use the following notation:

  • $n(G)$ is the number of vertices in $G$.
  • $D(G)$ is the diameter of $G$.
  • $D_{MST}(G)$ is the minimum diameter of a minimum spanning tree of $G$.

Give a sequence of graphs $G_i$ such that $n(G_i) \to \infty$ and $D_{MST}(G) = \Omega(n(G)) \cdot D(G)$.

It seems that you are not familiar with the notation $\Omega(\cdot)$. It is the counterpart of big O, and described in the answers to this question.

Unpacking the big $\Omega$ notation, we can rephrase the question:

Give a sequence of graphs $G_i$ such that $n(G_i) \to \infty$ and there exists a constant $C>0$ such that $D_{MST}(G_i) \geq C n(G_i) D(G_i)$.

The question is somewhat ambiguous – it's not clear if you need to provide an example for every $n$ or just for infinitely many $n$. I assumed the latter, but in fact in your case there is a sequence $G_i$ with $n(G_i) = i$, so you can try proving this stronger statement instead.

$\endgroup$
  • $\begingroup$ I see! Using the other writing for $\Omega$ makes it clear! $\endgroup$ – M.Mac Nov 17 '16 at 18:18

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.