1) In the terminology of network theory, what is a tree? A spanning tree? A minimum spanning tree?
i- tree: A tree is a connected acyclic graph, has no parallel edges and no loops. It does not have any paths that begin and end at the same node without backtracking.
ii- spanning tree: . A spanning tree is a sub graph that is a tree containing every nodes of a network. From a network, its contain more than one spanning tree. It is a tree that provides a path between every pair of nodes.
iii- minimum spanning tree: A minimal spanning tree in a connected weighted graph is a spanning tree that has the smallest ( minimum) possible sum of weights of its edges. One among all spanning trees that minimizes total cost.
2) What is an easy way to recognize a spanning tree?
i- The number of links in a spanning tree always is one less than the number of nodes.
ii- each node is directly connected by a single link to at least one other node.
3) What is the objective of a minimum spanning tree problem?
-The main objective of minimum spanning tree problem is to optimize the operation of the network.
Reference URL : http://highered.mcgrawhill.com/sites/dl/free/0073129038/449974/Chapter6Supplement.pdf
Others: Mathematic Discrete notes Chapter 6 by Pn Elissa Nadia bt Madi.
No comments:
Post a Comment