--%>
Assignment Help - homework help

  Theory of Tree and Minimum Spanning Trees

Tree:

Tree is one of the most well-organized data structure employed in a computer program. There are many kinds of tree.

Binary tree is a tree that always has two branches, Red-Black-Trees, 2-3-4 Trees, AVL Trees, and so on. A well balanced tree can be employed to design a good searching algorithm. A Tree is an undirected graph which contains no cycles and is connected. Most of the trees are what is termed as rooted, where there is a notion of "top" node that is termed as the root. Therefore, each node has one parent, which is the adjacent node and is closer to the root, and might have any number of children, and rest of the nodes adjacent to it. The tree below was drawn as a rooted tree.

1305_t1.jpg

Minimum Spanning Trees:

Spanning trees:

A spanning tree of a graph is simply a sub-graph which contains all the vertices and is a tree. A graph might have numerous spanning trees; for example the complete graph on four vertices:

    o---o
    |\ /|
    | X |
    |/ \|
    o---o

consists of sixteen spanning trees: 

    o---o    o---o    o   o    o---o
    |   |    |        |   |        |
    |   |    |        |   |        |
    |   |    |        |   |        |
    o   o    o---o    o---o    o---o
 
    o---o    o   o    o   o    o   o
     \ /     |\ /      \ /      \ /|
      X      | X        X        X |
     / \     |/ \      / \      / \|
    o   o    o   o    o---o    o   o
 
    o   o    o---o    o   o    o---o
    |\  |       /     |  /|     \
    | \ |      /      | / |      \
    |  \|     /       |/  |       \
    o   o    o---o    o   o    o---o
 
    o---o    o   o    o   o    o---o
    |\       |  /      \  |       /|
    | \      | /        \ |      / |
    |  \     |/          \|     /  |
    o   o    o---o    o---o    o   o 

Why minimum spanning trees?

The standard application is to a trouble similar to phone network design. You encompass a business with some offices; you want to lease phone lines to join them up with each other; and the phone company charges various amounts of money to join different pairs of cities. You wish for a set of lines which connects all your offices with a minimum total cost. It must be a spanning tree, as if a network is not a tree you can always eliminate some edges and save money.

A less apparent application is that minimum spanning tree which can be employed to approximately resolve the traveling salesman problem. A convenient formal method of defining this problem is to determine the shortest path that visits each and every point at least once.

Note that if you encompass a path visiting all points precisely once, then it is a special kind of tree. For instance in the example above, twelve of sixteen spanning trees are really paths. If you encompass a path visiting various vertices more than once, you can always drop certain edges to get a tree. Therefore in general the MST weight is less than the TSP weight, since it is a minimization over a strictly bigger set.

On other hand, when you draw a path tracing around the minimum spanning tree, you trace each edge twice and visit all the points, therefore TSP weight is less than twice the MST weight. Thus this tour is in a factor of two of optimal.

How to find minimum spanning tree?

The stupid technique is to list all spanning trees, and determine minimum of list. We know how to find minima...  Although there are far too many trees for this to be proficient. It is as well not really an algorithm, since you'd still require knowing how to list all the trees.

A better thought is to find some key property of MST which lets us be sure that some edge is part of it, and utilize this property to build up MST one edge at a time.

For simplicity, we suppose that there is a unique minimum spanning tree. You can get thoughts similar to this to work without this supposition however it becomes harder to state your theorems or write your algorithms accurately.

Lemma: Assume that X be any subset of the vertices of G, and let edge e is the smallest edge connecting X to G-X. Then e is the part of minimum spanning tree.

Proof: Assume that you have a tree T not containing e; then we want to illustrate that T is not MST. Let e=(u,v), with u in X and v not  in X. Then since T is a spanning tree it comprises a unique path from u to v, which altogether with e forms a cycle in G. This path has to comprise another edge f connecting X to G-X. T+e-f is another spanning tree (that is, it has the same number of edges, and remains connected as you can substitute any path having f by one going the other way around the cycle). It has smaller weight than t as e has smaller weight than f. Therefore T was not minimum, which is what we wanted to prove.

Rooted tree:

Most of the trees are what is termed as rooted, where there is a notion of "top" node that is termed as the root. Therefore, each node has one parent that is the adjacent node which is closer to the root, and might have any number of children, which are rest of nodes adjacent to it. The tree shown above was drawn as a rooted tree.

Forest:

An undirected graph that contains no cycles is termed as forest. A directed acyclic graph is frequently termed to as a dag.

2392_t2.jpg

Latest technology based Programming Languages Online Tutoring Assistance

Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Programming Languages help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Programming Languages, project ideas and tutorials. We provide email based Programming Languages help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Programming Languages. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Programming Languages Homework help and assignment help services. They use their experience, as they have solved thousands of the Programming Languages assignments, which may help you to solve your complex issues of Programming Languages. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.