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
This notation bounds a function to in constant factors. We say f(n) = Θ(g(n)) if there presents positive constants n 0 , c 1 and c 2 such that to the right of n 0 the value of f

Explain Division Method Division Method: - In this method, key K to be mapped into single of the m states in the hash table is divided by m and the remainder of this division


A stack is a last in, first out (LIFO) abstract data type and sequential data structure. A stack may have any abstract data type as a component, but is characterized by two fundame

ESO207: Programming Assignment 1 Due on 6 Sept, 2015. To be submitted online. Problem In this assignment you are required to implement k-way Merge Sort algorithm. In this version p

It offers an effective way to organize data while there is a requirement to access individual records directly. To access a record directly (or random access) a relationship is

how to learn about time complexity of a particular algorithm

Approximating smooth surfaces with Polygon nets Networks of polygons are used to represent smooth surfaces. They are, of course, only an approximation to the true surface, but

Given the following search tree, state the order in which the nodes will be searched for breadth first, depth first, hill climbing and best first search, until a solution is reache

Postorder traversal of a binary tree struct NODE { struct NODE *left; int value;     /* can take any data type */ struct NODE *right; }; postorder(struct NODE