Hi
The following questions i need help on:
1) Consider a graph containing n cities (nodes), where n is an integer greater than 1.
a) Give a formula for the number of links (lines in the complete graph.
b) Give a formula for the number of links (lines) in the minimal spanning tree.
P.S
(a) Hint: If you draw an edge (link) from each node (n choices) to every other node (n - 1 choices), then you will draw every edge in the complete graph twice.
(b) Any tree with n nodes has n - 1 edges. By the way, it does not make sense to talk about a "minimal spanning tree" unless the graph has weights (or distances) assigned to edges. This is because any tree is minimal by definition: it ceases to be connected when any edge is removed. A spanning tree can be defined as a minimal set of edges that connect all vertices in a graph.
The number of links (edges)
Example 10 nodes -
Node Links
1 9 Node 1 links to 9 nodes (and not to its self)
2 8 Node 2 is already linked to bode 1 - so it links to 8 more.
3 7 Node 3 is already linked to 1 and 2 - so it links to 7 more
This continues
4 6
5 5
6 4
7 3
8 2
9 1
10 is already linked to all the others
So with n nodes - a fully connected graph will have (n^2 - n) / 2 edges.
thanks for the help