A tree having ''m'' nodes has (m-1) branches. prove., Data Structure & Algorithms

Q. Prove the hypothesis that "A tree having 'm' nodes has exactly (m-1) branches".     

Ans:

A tree having m number of nodes has exactly (m-1) branches

Proof: A root in a tree has indegree zero and all other nodes have indegree one. There must be (m-1) incoming arcs to the (m-1) non-root nodes. If there is any other arc, this arc must be terminating at any of the nodes. If the node is root, then its indegree will become one and that is in contradiction with the fact that root always indegree zero. If the end point of this extra edge

is any non-root node then its indegree will be two, which is again a contradiction. Hence there cannot be more arcs. Therefore, a tree with m vertices will have exactly (m-1) edges.

 

 

Posted Date: 7/11/2012 1:36:54 AM | Location : United States







Related Discussions:- A tree having ''m'' nodes has (m-1) branches. prove., Assignment Help, Ask Question on A tree having ''m'' nodes has (m-1) branches. prove., Get Answer, Expert's Help, A tree having ''m'' nodes has (m-1) branches. prove. Discussions

Write discussion on A tree having ''m'' nodes has (m-1) branches. prove.
Your posts are moderated
Related Questions
Q. Write down an algorithm to add an element in the end of the circular linked list.        A n s . Algo rithm to Add the Element at the End of Circular Linked Lists


Define the Carrier set of the Symbol ADT Carrier set of the Symbol ADT is the set of all finite sequences of characters over Unicode characters set (Unicode is a standard char

Q. Write a procedure to the insert a node into the linked list at a particular position and draw the same by taking an example?

A small shop sells 280 different items. Every item is identified by a 3 - digit code. All items which start with a zero (0) are cards, all items which start with a one (1) are swee

floyd warshall algorithm

What are stored and derived attributes?  Stored attributes: The attributes kept in a data base are called stored attributes.  Derived attributes: The attributes that are

What is Efficiency of algorithm? Efficiency of an algorithm can be precisely explained and investigated with mathematical rigor.  There are two types of algorithm efficiency

Q. The degree of a node is defined as the number of children it has. Shear show that in any binary tree, the total number of leaves is one more than the number of nodes of degree 2

implement multiple stacks in a single dimensional array. write algorithm for various stack operation for them