Tree

1.Definition of tree??

1. A tree is a connected undirected graph with no simple circuits.(Chuck Allison, Discrete Mathematics and Its Applications (5^th Edition))

2. An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.( Chih-Wei Yi, Discrete mathematics(spring 2009))

3. A tree is a connected undirected graph with no simple circuits.

Because a tree cannot have a simple circuit, a tree cannot contain

multiple edges or loops. Therefore any tree must be a simple

graph.( Julien Dompierre, Discrete Mathematics II — MATH/COSC 2056E)

4. A tree is a mathematical structure that can be viewed as either a graph or as a data structure. The two views are equivalent, since a tree data structure contains not only a set of elements, but also connections between elements, giving a tree graph

2.How to determine a tree??

-a tree is  a connected undirected graph with no simple circuit

-an undirected graph is a tree if and only if there is a unique simple path between any two of its vertices

 

3.Rooted tree??

Definition

-A rooted tree is a tree in which one vertex has been designated as

the root and every edge is directed away from the root.

We usually draw a rooted tree with its root at the top of the graph.

-The arrows indicating the directions of the edges can be omitted

because the choice of root determines the direction of the edges.

-In many applications of trees, a particular vertex of the tree is

designated as the root.

-The choice of the root is arbitrary.

characteristics

-If v is a vertex in T other than the root, the parent of v is the

unique vertex u such that there is a directed edge from u to v.

-If u is the parent of v, v is called a child of u.

Vertices with the same parent are called siblings.

 

4.Describe the characteristics and properties of trees.

properties of tree??

theorem 1

A tree with n vertices has n - 1 edges.

theorem 2

A full m-ary tree with i internal vertices contains n = mi + 1

vertices.

theorem 3

A full m-ary tree with

1 n vertices has i = (n - 1) /m internal vertices and

l = [(m - 1) n + 1] /m leaves,

2 i internal vertices has n = mi + 1 vertices and

l = (m - 1) i + 1 leaves,

3 l leaves has n = (ml - 1) / (m - 1) vertices and

i = (l -1) / (m - 1) internal vertices.

theorem 4

There are at most m^h leaves in an m-ary tree of height h.

5.0.3 Application of tree??

-binary search trees

-decision trees

-game trees

  

5.1.Explain how tree are used in modeling??

representing organization

the structure of a large organization can be modeled using a rooted tree. each vertex in this tree represent a position in organization. an edge from one vertex to another indicates that the person represented by the initial vertex is the(direct) boss of the person represented by the terminal vertex

6.Definition of tree traversal??

General Definition: to traverse a data structure is to process, however you like, every node in the data structure exactly once.

Note: You may ``pass through'' a node as many times as you like but you must only process the node once.

preorder traversal

Let T be an ordered rooted tree with root r . If T consists only of

r , then r is the preorder traversal of T. Otherwise, suppose that

T1,T2, _ _ _ ,Tn are the subtrees at r from left to right in T. The

preorder traversal begins by visiting r . It continues by traversing

T1 in preorder, then T2 in preorder, and so on, until Tn is

traversed in preorder.

inorder traversal

Let T be an ordered rooted tree with root r . If T consists only of

r , then r is the inorder traversal of T. Otherwise, suppose that

T1,T2, _ _ _ ,Tn are the subtrees at r from left to right. The inorder

traversal begins by traversing T1 in inorder, then visiting r . It

continues by traversing T2 in inorder, then T3 in inorder, ..., and

.nally Tn in inorder.

postorder traversal

Let T be an ordered rooted tree with root r . If T consists only of

r , then r is the postorder traversal of T. Otherwise, suppose that

T1,T2, _ _ _ ,Tn are the subtrees at r from left to right in T. The

postorder traversal begins by traversing T1 in postorder, then T2 in

postorder, ..., then Tn in postorder, and end by visiting r .

7.Spanning tree??

-Let G be a simple graph. A spanning tree of G is a subgraph of G

that is a tree containing every vertex of G.

theorem

 -A simple graph is connected if and only if it has a spanning tree.

application of spanning tree

ip multicast

-IP multicast is a method of sending internet protocol (IP) datagrams to a group of interested receivers in a single transmission. It is often employed for streaming media applications on the internet and private networks. The method is the IP-specific version of the general concept of multicast networking. It uses specially reserved multicast address blocks in IPV4 and IPV^. In IPv6, IP multicast addressing replaces broadcast addressing as implemented in IPv4.

 8.Minimum spanning tree??

-A minimum spanning tree in a connected weighted graph

is a spanning tree that has the smallest possible sum of weights of its edges

9.Kruskal algorithm??

Kruskal’s algorithm begins by choosing an edge in the graph with

minimum weight

− successively add edges with minimum weight that

_ do not form a simple circuit with those edges already chosen

− Stop after n − 1 edges have been selected

Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component)

note:Kruskal's algorithm is used to find the minimum/maximum spanning tree in an undirected graph (a spanning tree, in which is the sum of its edges weights minimal/maximal). The algorithm was devised by Joseph Kruskal in 1956.

 application of kruskal algorithm

example1:

-Minimum spanning trees have also been used to generate maze. Both Kruskal's and Prim's algorithm have been used this way, often creating high-quality mazes.

 

 example 2:

-One example would be a cable TV company laying cable to a new neighborhood. If it is constrained to bury the cable only along certain paths, then there would be a graph representing which points are connected by those paths. Some of those paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weights. A spanning tree for that graph would be a subset of those paths that has no cycles but still connects to every house. There might be several spanning trees possible. A minimum spanning tree would be one with the lowest total cost.