New answers tagged minimum-spanning-tree
3
Interesting question.
The right intuition should probably be along the guideline that two random subsets of cardinality $n$ drawn from some $cn$ elements for some constant $c$ differ from each other significantly with a probability very close to 1 and, hence, the weight of the minimum spanning tree of the graph $G$ should be $\mathcal\Theta(n^2)$ on average. ...
2
You can't. Consider the following sets for some $k$, with $m=k^2$ (they both are powers of $2$):
$\{1..k\}$, $\{k+1..2k\}$, $\ldots$, $\{m-k+1..m\}$
$\{1, 3, 5, \ldots, 2k-1\}$, $\{2, 4, 6, \ldots, 2k\}$, $\{2k+1, 2k+3, \ldots, 4k - 1\}$, $\{2k+2, 2k+4, \ldots, 4k\}$, $\ldots$
$\{1, 5, 9, \ldots, 4k - 3\}$, $\{2, 6, 10, \ldots, 4k-2\}$ $\ldots$.
Each ...
0
I have a proposal for a proof that doesn't involve "coloring" since it sounds vague.
Let $T' = (V,F')$ be a spanning tree but not a MST of $G=(V,E)$. Let $T = (V,F)$ be a MST of $G$.
You already did the following:
Now go through all $e \in F-F'$ and add $e$ to $T'$. Resulting graph contains a cycle if there is another edge $e'$ on the cycle such ...
0
After long hours facing this problem, with my advisor help, we could solve this problem in $O(|E(G^{'})| log\text{ }C)$ time complexity by using one iteration of the Boruvka's algorithm, where $C$ is the number of connected components of $G^{''} (V(G^{'}), T\backslash \{(v_k, v_i): v_k \in V(G^{'})\})$, i.e., the number of connected components of the MST $T$ ...
Top 50 recent answers are included
