Graph Theory Show that for every natural number t there exis

Graph Theory.

Show that for every (natural number) t, there exists a weighted, undirected graph G = (V, E) with source vertex s, where all edge weights are distinct, such that G has exactly t different shortest path trees.

Solution

Shortest path tree:- it is a tree, which has the shortest paths from root to all individual nodes (sum of all edges int the path is minimum). Shortest path tree for a graph need not be unique..

given that all edge weights are distinct (1)

for every node in graph there is shortest path tree, given that all edges are distinct, from (1) , there fore , the shortest path trees produced by each node may not be same,there exist at least one unique tree. and hence there t number of distinct shortest path trees are there for a given Graph g, t<=no of nodes in Graph, t>=1