[Boards: 3 / a / aco / adv / an / asp / b / bant / biz / c / can / cgl / ck / cm / co / cock / d / diy / e / fa / fap / fit / fitlit / g / gd / gif / h / hc / his / hm / hr / i / ic / int / jp / k / lgbt / lit / m / mlp / mlpol / mo / mtv / mu / n / news / o / out / outsoc / p / po / pol / qa / qst / r / r9k / s / s4s / sci / soc / sp / spa / t / tg / toy / trash / trv / tv / u / v / vg / vint / vip / vp / vr / w / wg / wsg / wsr / x / y ] [Search | Click for more| Home]

Hello /g/ If you don't want to throw that CS degree in

This is a blue board which means that it's for everybody (Safe For Work content only). If you see any adult content, please report it.

Thread replies: 18
Thread images: 3

Hello /g/

If you don't want to throw that CS degree in the trash, prove the correctness of Kruskal's algorithm.
>>
/g/ can only into simple stuff like bubble sort

Go to /sci/
>>
>algo correctness
well shit I don't remember that one, I only got 80% in that class.
>>
>>50787180
what do you mean? its obvious
>>
>>50787274
No it's not
>>
>>50787282
sorry, it is if you aren't mentally retarded or don't have it as homework
>>
>>50787237
/thread
>>
Proof is trivial and left as an exercise to the reader.
>>
>>50787313
lol
>>
>>50787180
>do my homework for me

you first fuccboi
>>
>>50787180
Don't worry OP I got you
>>
proof by contradiction:
Say there exists a set of edges that creates a smaller minimum spanning set. the edges it would choose have 2 properties: Smallest and does not create a cycle. WHICH LITERALLY CANNOT HAPPEN AS IT IS THE ALGORITHM WITH WHICH WE CHOOSE OUR EDGES YOU FUCKING SCRUB.
>>
>>50787313
>stats class
The professor did that during the proofs as a joke but still
>>
>>50787180
OMG
>AUTISM / 8
>WIZARD SHIT
>>
Its a fucking greedy algorithm that's why its correct, are you fucking first year or why do you have to do this
>>
>>50787180
The proof consists of two parts. First, it is proved that the algorithm produces a spanning tree. Second, it is proved that the constructed spanning tree is of minimal weight.

Spanning tree Edit
Let be a connected, weighted graph and let be the subgraph of produced by the algorithm. cannot have a cycle, being within one subtree and not between two different trees. cannot be disconnected, since the first encountered edge that joins two components of would have been added by the algorithm. Thus, is a spanning tree of .

Minimality Edit
We show that the following proposition P is true by induction: If F is the set of edges chosen at any stage of the algorithm, then there is some minimum spanning tree that contains F.

Clearly P is true at the beginning, when F is empty: any minimum spanning tree will do, and there exists one because a weighted connected graph always has a minimum spanning tree.
Now assume P is true for some non-final edge set F and let T be a minimum spanning tree that contains F. If the next chosen edge e is also in T, then P is true for F + e. Otherwise, T + e has a cycle C and there is another edge f that is in C but not F. (If there were no such edge f, then e could not have been added to F, since doing so would have created the cycle C.) Then T − f + e is a tree, and it has the same weight as T, since T has minimum weight and the weight of f cannot be less than the weight of e, otherwise the algorithm would have chosen f instead of e. So T − f + e is a minimum spanning tree containing F + e and again P holds.
Therefore, by the principle of induction, P holds when F has become a spanning tree, which is only possible if F is a minimum spanning tree itself.
>>
>>50788322
>getting baited into doing some fags homework for him
goddamn /g/ you are pathetic
>>
>>50788336
This is literally wikipedia copypaste
Thread posts: 18
Thread images: 3


[Boards: 3 / a / aco / adv / an / asp / b / bant / biz / c / can / cgl / ck / cm / co / cock / d / diy / e / fa / fap / fit / fitlit / g / gd / gif / h / hc / his / hm / hr / i / ic / int / jp / k / lgbt / lit / m / mlp / mlpol / mo / mtv / mu / n / news / o / out / outsoc / p / po / pol / qa / qst / r / r9k / s / s4s / sci / soc / sp / spa / t / tg / toy / trash / trv / tv / u / v / vg / vint / vip / vp / vr / w / wg / wsg / wsr / x / y] [Search | Top | Home]
Please support this website by donating Bitcoins to 16mKtbZiwW52BLkibtCr8jUg2KVUMTxVQ5
If a post contains copyrighted or illegal content, please click on that post's [Report] button and fill out a post removal request
All trademarks and copyrights on this page are owned by their respective parties. Images uploaded are the responsibility of the Poster. Comments are owned by the Poster.
This is a 4chan archive - all of the content originated from that site. This means that 4Archive shows an archive of their content. If you need information for a Poster - contact them.