CMIS 160

Discrete Mathematics

Erich Prisner

UMUC SG

Spring 2002

#
Minimum spanning tree

Now here you can generate random edge costs,
and find a minimum weight spanning tree either using single steps
or all steps at once.
White,
yellow,
orange,
red,
purple, and
blue
indicate weights of
0,
1,
2,
3,
4, and
5 or larger.
With fixed names (edge weights),
obviously several maximum weight spanning trees are possible.
Given some (partial) tree, clicking on a yet unchosen edge
may convince the computer to include it, and delete another
previously chosen edge instead. But for some edges, the computer
denies taking them. What does that mean for that edge?
How can we find such edges?
The following stuff is only for test purposes: