Minimum spanning trees

after i found a minimum spanning tree, the second part of the question says which two edges will be included in any spanning tree. how do i find them?

edit: i have used kruskal's algorithm btw, and i know how to use prim's.

Reply 1

DFranklin

18

I'm not sure, but I suspect we would need to see the tree in question.

OP

shall i put it up?

Do

OP

part ii)

OK, well you can answer this one by common sense.

First, can you see one edge you have to have if you're going to have a spanning tree?

OP

EI (lenght 1)?

I assume you mean EG (there is no edge EI that I can see).

That's not right, anyhow. There's one edge that, if removed, would leave the network divided into two disconnected regions. That edge therefore must be in any spanning tree (even a non-minimal spanning tree).

Reply 8

ghostwalker

17

Prokaryotic_crap

EI (lenght 1)?

Assuming you meant EG (length 1).

There are two paths that must be there, and each has a different reason for being there.

Although EG is not the answer to Franklin's question, it is the other path, since it is the unique minimum length path in any minimal spanning tree.

So you are right on this one, but for the wrong reason.

You still need to address Franklin's question however for the other path.

Reply 9

DFranklin

18

Well, I had a different 2nd edge in mind. My reasoning:

Spoiler

It looks to me like there are more than 2 required edges.

Reply 10

Prokaryotic_crap

OP

18

DFranklin

I assume you mean EG (there is no edge EI that I can see).

That's not right, anyhow. There's one edge that, if removed, would leave the network divided into two disconnected regions. That edge therefore must be in any spanning tree (even a non-minimal spanning tree).