Discrete Mathematics, data structure question concerning Trees and BFS.

Question

1)Without drawing them all, calculate how many spanning trees the graph has.

2)Which spanning tree would result from doing a breadth first search from the vertex A, using the natural alphabetical ordering of vertices?

Answer 1

well we need some data !!!

how about some random numbers generated from MS EXcel?...

32, 33, 97, 70, 2, 58, 26, 84, 30, 64, 7, 23

with a parent node of 50.....

that is level 5, 5 levels deep from the parent...

Now, lets rearrange the order of the nodes so that under

the parent node are 2 child nodes containing the 26 and the 70...

watch what happens next...

that is BARELY level 4, and the tree is more balanced..

why... is because the MEDIANS are at the parent node

positions: 25, 50 75 which balances the tree

I uploaded the pictures for you and they are in the RESOURCES section under this link

titled BINARY TREES