Question

Graph Theory
Can someone check my work?
Define a graph G with V(G) = {a, b, c, d, e, f, g} and E(G) = {(a,b), (a,e), (b,c), (b,g),
(c,d), (c,g), (d,e), (d,f), (e,f), (f,g)} and corresponding weights W(E) = {1, 9, 7, 8, 4, 10, 3,
5, 2, 6} respectively. Use Kruskal’s algorithm to find a minimum spanning tree for G.

Answer 1

The minimum spanning tree is in blue

Answer 2

@KingGeorge can you check this please. Thank you!

Answer 3

I'm sorry, but I'm only on for just a minute. I'll be back in 45 minutes for a closer look if you can wait that long :/

Answer 4

ok

Answer 5

I have a feeling it's really simple, and I just don't remember/didn't learn anything from GT

Answer 6

After a quick refresher, I think I have it. Start with the graph given (the one with the red lines). Kruskal's algorithm says to choose the one with the least weight to it. That is (ab). So add the edge (ab) to the minimum spanning tree. Next largest is (fe), so add that to the minimum spanning tree. Continue with this pattern, you'll also get (de) and (cd) in the tree.

Now, look at (df), the edge with weight 5. Notice that this would form a cycle in the minimum spanning tree. So we ignore it.

After that, we're free to continue. we add the edges (fg) and (bc) in the same manner as before. For the remaining edges, Kruskal's algorithm says that we throw them out since they would form cycles. Hence, the graph colored in blue is the minimum spanning tree.

Answer 7

oh so that was right.. Thanks a lot KG

Answer 8

You should add a B somewhere at the end of your username so that we can call you KGB

Answer 9

I like it :P

But I'm not Russian, so we'll see.

Answer 10

Sorry that took so long, I'm a bit out of practice with graph theory.

Answer 11

lol it's fine