BIGtheme.net http://bigtheme.net/ecommerce/opencart OpenCart Templates
Friday , July 28 2017
Home / Discrete mathematics / Trees-brance node-terminal node-edge-vertex

Trees-brance node-terminal node-edge-vertex

Definition: A tree to be a connected group that contains no simple circuit. A collection of disjoint trees is called a forest. A vertex of degree 1 in a tree is called a half or terminal node and a vertex of degree larger than 1 is called a branch node or on terminal node.

Screenshot_4

Some properties of a tree:

  1. There is a unique path between every two vertices in a tree.
  2. The number of vertices is one more than the number of vertices.
  3. A tree with two or more vertices has at least two leaves.

Proof: 1

Since a tree is a connected graph, there at least one path between every two vertices. However if there were two or more paths between a pair of vertices. Then there would be a circuit in the tree, which contradict. So by the definition of the tree we conclude that “There is a unique path between every two vertices in a tree.”

Proof:2

We prove it by induction method. If there is one vertex, there cannot form a tree because in a tree no vertex can be isolated.

If there were two vertices it obvious that there is one edge. Otherwise there form a circuit.

Let there be a tree T with v vertices and edges. Let {a,b} be an edge in T. Suppose we remove the edge {a,b} from T, we claim that the remaining edges from a forest of two trees. Let C be a vertex such that the path between a and c in T does not include the edge {a,b}. Then the path between b and c in T must include the edge {a,b}, because, otherwise there is circuit in T. Thus after the removal of the edge {a,b}, there is a path a between a and c but no path between b and c. Similarly let do be a vertex such that the path between a and d in T includes the edges           {a,b}. Then the path between b and d does not include the edge {a,b}. Thus after the removal of the edge {a,b}. There is a path between b and d but no path between a and d. Consequently, the removal of the edge {a,b} divides T into two disjoint trees T/ and T// where T/ contains a and all the vertices whose paths to a in T do not contain the edge {a,b} and T// contains b and all the vertices whose path to b in T do not contain the edge {a,b}. Since both T/ and T// have most v-1 vertices by hypothesis of induction.

e/=v/-1 and e//=v//-1

Where e/ and e// are the number of edges and v/ and v// are the number of vertices in T/ and T//.

Thus e/+e//=v/-1+v//-1= v/+v//-2

Since the tree T,

e = e/+e//+1 and v=v/+v//

= v/+v//-2+1

= v/+v//-1

=v-1

e = v-1.

Definition: A directed graph is said to be a directed tree when the direction of the edges are ignored.

Screenshot_5

Fig-1

Fig-1 shows a directed tree. A directed tree is called a rooted tree if there is exactly one vertex whose incoming degree is 0 and the incoming degree of all the other vertices are 1. The vertex with incoming degree 0 is called the root of the rooted tree.

Screenshot_6

 

In a rooted tree, a vertex whose outgoing degree is nonzero is called a branch or internal node.

Let a be branch node in a rooted tree. A vertex is said to be son of a if there is an edge from a to b. Also a is said to be father of b. Two vertices are said to brother if they are the son of same vertex. A vertex c is said to be a descendent of a if there is a directed path from a to c. Also a is said to be an ancestor of c. These terms indeed remind us that what we commonly call family trees are indeed rooted trees.

Some result on the characterization of trees. All of there characterizations can be considered as the equivalent definitions of trees.

  1. A graph in which there is a unique path between every pair of vertices is a tree.
  2. A connected graph with e = v-1 is a tree.
  3. A graph with e = v-1 that has no circuit is a tree.

Proof:1

We note first that a graph in which there is a path between every pair of vertices is connected. Moreover the graph cannot contain a circuit if these paths are unique. Since the existence of a circuit implies that the existence of two distinct paths between a certain pair of vertices. Thus we can conclude that a graph in which there is a unique path between every pair of vertices is a tree.

Proof:2

Let G be connected graph with e = v-1. Suppose G has a simple circuit C. Let v denote the number of vertices in c, clearly the number edge in c is equal v/. Since G is a connected, every vertex of G that is not C must be connected to the vertices in c. Now each edge of G that is not in c can connected only one addition vertex to the vertices in c. There are v-v/ vertices are not in c. So G must contain at least v-v/ edges that are not in c. Thus we must have e≥ v/+v-v/. which is contradict.

It follows that G does not connected any circuit.

Proof:3

Let G be a graph with e = v-1 that tress has no circuit. Suppose G is not connected. Let G/ ,G//, ………. Denote the connected components of G. Since each of G/ ,G//, ………. Is connected and has no circuits, they are all trees. Then

We have

e/ = v/-1

e//=v//-1

…………………………….

Where e/ ,e// ,……… are the number of edges and v/ ,v// ,……….are the number of vertices in G/,G//, …………..

We have,

e/+e//+…………….= v/-1+ v//-1+……………..

= v/+ v//+…………-1-1……………..

Since,

e = e/+e//+e///+……………….

v = v/+v//+v///+………………

Then e = v-1. (proved)

 

Check Also

Procedure for computing shortest distance| Discrete Mathematics

Solution: The procedure for computing the shortest distance/path from a to any vertex G. Initially, ...

Leave a Reply

Your email address will not be published. Required fields are marked *