Answer for question 1
Tree
In telecommunication networks, a tree network is a combination of two or more star networks connected together. Each star network is a local area network (LAN) in which there is a central computer or server to which all the workstation nodes are directly linked. The central computers of the star networks are connected to a main cable called the bus. Thus, a tree network is a bus network of star networks.
The illustration shows a tree network with five star networks connected to a common bus. The workstations are shown as small spheres, the central computers of the star networks are shown as larger spheres, connections within star networks are shown as short lines, and the bus is shown as a long, heavy line. The connections can consist of wire cables, optical fiber cables, or wireless links.
Spanning Tree
Spanning trees are a standard technique used in local area network (LAN) switching. Spanning tree algorithms were developed to prevent redundant transmission of data along intermediate hops between a source and destination host on a mesh network topology. Without spanning trees, a mesh network can be flooded and rendered unusable by messages circulating in an infinite loop between hosts.
The primary Spanning Tree Protocol (STP) is IEEE standard 802.1D, an algorithm commonly used on Ethernet networks. This algorithm works by limiting the paths messages can travel at any given time to a fully connected tree rather than a mesh. As hosts join and leave the network, this protocol dynamically updates the tree accordingly.
Minimum spanning tree
minimum spanning tree (MST) or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree. More generally, any undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of minimum spanning trees for its connected components.
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.
Minimum spanning tree objectives
• They can be computed quickly and easily, and they create a sparse subgraph that reflects a lot about the original graph.
• They provide a way to identify clusters in sets of points. Deleting the long edges from a minimum spanning tree leaves connected components that define natural clusters in the data set, as shown in the output figure above.
• They can be used to give approximate solutions to hard problems such as Steiner tree and traveling salesman.
• As an educational tool, minimum spanning tree algorithms provide graphic evidence that greedy algorithms can give provably optimal solutions.
Method to solve minimum spanning tree
there are 4 method to solve minimum spanning tree...
Kruskal's algorithm
We'll start with Kruskal's algorithm, which is easiest to understand and probably the best one for solving problems by hand.
Kruskal's algorithm:
sort the edges of G in increasing order by length
keep a subgraph S of G, initially empty
for each edge e in sorted order
if the endpoints of e are disconnected in S
add e to S
return S
Note that, whenever you add an edge (u,v), it's always the smallest connecting the part of S reachable from u with the rest of G, so by the lemma it must be part of the MST.
This algorithm is known as a greedy algorithm, because it chooses at each step the cheapest edge to add to S. You should be very careful when trying to use greedy algorithms to solve other problems, since it usually doesn't work. E.g. if you want to find a shortest path from a to b, it might be a bad idea to keep taking the shortest edges. The greedy idea only works in Kruskal's algorithm because of the key property we proved.
Analysis: The line testing whether two endpoints are disconnected looks like it should be slow (linear time per iteration, or O(mn) total). But actually there are some complicated data structures that let us perform each test in close to constant time; this is known as the union-find problem and is discussed in Baase section 8.5 (I won't get to it in this class, though). The slowest part turns out to be the sorting step, which takes O(m log n) time.
Prim's algorithm
Rather than build a subgraph one edge at a time, Prim's algorithm builds a tree one vertex at a time.
Prim's algorithm:
let T be a single vertex x
while (T has fewer than n vertices)
{
find the smallest edge connecting T to G-T
add it to T
}
Since each edge added is the smallest connecting T to G-T, the lemma we proved shows that we only add edges that should be part of the MST.
Again, it looks like the loop has a slow step in it. But again, some data structures can be used to speed this up. The idea is to use a heap to remember, for each vertex, the smallest edge connecting T with that vertex.
Prim with heaps:
make a heap of values (vertex,edge,weight(edge))
initially (v,-,infinity) for each vertex
let tree T be empty
while (T has fewer than n vertices)
{
let (v,e,weight(e)) have the smallest weight in the heap
remove (v,e,weight(e)) from the heap
add v and e to T
for each edge f=(u,v)
if u is not already in T
find value (u,g,weight(g)) in heap
if weight(f) < weight(g) replace (u,g,weight(g)) with (u,f,weight(f)) } Analysis: We perform n steps in which we remove the smallest element in the heap, and at most 2m steps in which we examine an edge f=(u,v). For each of those steps, we might replace a value on the heap, reducing it's weight. (You also have to find the right value on the heap, but that can be done easily enough by keeping a pointer from the vertices to the corresponding values.) I haven't described how to reduce the weight of an element of a binary heap, but it's easy to do in O(log n) time. Alternately by using a more complicated data structure known as a Fibonacci heap, you can reduce the weight of an element in constant time. The result is a total time bound of O(m + n log n).
Boruvka's algorithm
(Actually Boruvka should be spelled with a small raised circle accent over the "u".) Although this seems a little complicated to explain, it's probably the easiest one for computer implementation since it doesn't require any complicated data structures. The idea is to do steps like Prim's algorithm, in parallel all over the graph at the same time.
Boruvka's algorithm:
make a list L of n trees, each a single vertex
while (L has more than one tree)
for each T in L, find the smallest edge connecting T to G-T
add all those edges to the MST
(causing pairs of trees in L to merge)
As we saw in Prim's algorithm, each edge you add must be part of the MST, so it must be ok to add them all at once.
Analysis: This is similar to merge sort. Each pass reduces the number of trees by a factor of two, so there are O(log n) passes. Each pass takes time O(m) (first figure out which tree each vertex is in, then for each edge test whether it connects two trees and is better than the ones seen before for the trees on either endpoint) so the total is O(m log n).
A hybrid algorithm
This isn't really a separate algorithm, but you can combine two of the classical algorithms and do better than either one alone. The idea is to do O(log log n) passes of Boruvka's algorithm, then switch to Prim's algorithm. Prim's algorithm then builds one large tree by connecting it with the small trees in the list L built by Boruvka's algorithm, keeping a heap which stores, for each tree in L, the best edge that can be used to connect it to the large tree. Alternately, you can think of collapsing the trees found by Boruvka's algorithm into "supervertices" and running Prim's algorithm on the resulting smaller graph. The point is that this reduces the number of remove min operations in the heap used by Prim's algorithm, to equal the number of trees left in L after Boruvka's algorithm, which is O(n / log n).
Applications of Minimum Spanning Tree Problem
Network design.
– telephone, electrical, hydraulic, TV cable, computer, road
The standard application is to a problem like phone network design. You have a business with several offices; you want to lease phone lines to connect them up with each other; and the phone company charges different amounts of money to connect different pairs of cities. You want a set of lines that connects all your offices with a minimum total cost. It should be a spanning tree, since if a network isn’t a tree you can always remove some edges and save money.
Approximation algorithms for NP-hard problems.
– traveling salesperson problem, Steiner tree
A less obvious application is that the minimum spanning tree can be used to approximately solve the traveling salesman problem. A convenient formal way of defining this problem is to find the shortest path that visits each point at least once.
Note that if you have a path visiting all points exactly once, it’s a special kind of tree. For instance in the example above, twelve of sixteen spanning trees are actually paths. If you have a path visiting some vertices more than once, you can always drop some edges to get a tree. So in general the MST weight is less than the TSP weight, because it’s a minimization over a strictly larger set.
On the other hand, if you draw a path tracing around the minimum spanning tree, you trace each edge twice and visit all points, so the TSP weight is less than twice the MST weight. Therefore this tour is within a factor of two of optimal.
Indirect applications.
– max bottleneck paths
– LDPC codes for error correction
– image registration with Renyi entropy
– learning salient features for real-time face verification
– reducing data storage in sequencing amino acids in a protein
– model locality of particle interactions in turbulent fluid flows
– autoconfig protocol for Ethernet bridging to avoid cycles in a network
Cluster analysis
k clustering problem can be viewed as finding an MST and deleting the k-1 most
expensive edges. See this for more details.
no of vertice : 7
no of edges : 6
total weight : = 1 + 1 + 2 + 4 + 4 + 6
= 18
03:59
smskpp2
