I want to show that the output spanning tree $S$ of Kruskal's algorithm is a minimum spanning tree, so it is of minimum weight, by contradiction.
We suppose that $S$ is not a minimum spanning tree.
Let $T$ be a spanning tree which has the minimum weight.
How can I go on to get a contradicti...
I want to write an algorithm that finds an optimal vertex cover of a tree in linear time O(n), where n is the number of the vertices of the tree.
A vertex cover of a graph G=(V,E) is a subset W of V such that for every edge (a,b) in E, a is in W or b is in W.
In a vertex cover we need to have ...
I'm trying find where the common proof by contradiction that $\sqrt 2$ is irrational breaks down when trying to prove $\sqrt 4$ is irrational.
Assume $(\frac pq)^2=4$ and $\gcd(p,q)=1$. I guess I could just let $p=2, q=1$ and be done, but why is that an adequate failure of the proof? If it's not...
@user159870 First, I hope you didn't think I knew the answer. I'm guessing. I learned about K's algorithm a few minutes ago when I watched the video I posted. :D
@user159870 Second, I think that's already a contradiction. I mean, we know K's algo always selects the smallest weighted edge.
I don't think so. That is what we have supposed, that there is an other spanning tree with the smallest weight. We have to find something that cannot be true to conclude that our assumption, that $S$ is not a minimum spanning tree, is false. But I don't know how. @Jeff
I want to show that the output spanning tree $S$ of Kruskal's algorithm is a minimum spanning tree, so it is of minimum weight, by contradiction.
We suppose that $S$ is not a minimum spanning tree.
Let $T$ be a spanning tree which has the minimum weight.
How can I go on to get a contradicti...
I want to write an algorithm that finds an optimal vertex cover of a tree in linear time O(n), where n is the number of the vertices of the tree.
A vertex cover of a graph G=(V,E) is a subset W of V such that for every edge (a,b) in E, a is in W or b is in W.
In a vertex cover we need to have ...
