Term Paper

qwertyuiopasdfghjklzxcvbnmqwe rtyuiopasdfghjklzxcvbnmqwertyui opasdfghjklzxcvbnmqwertyuiopa sdfghjklzxcvbnmqwertyuiopasdfg hjklzxcvbnmqwertyuiopasdfghjklz xcvbnmqwertyuiopasdfghjklzxcvb nmqwertyuiopasdfghjklzxcvbnmq wertyuiopasdfghjklzxcvbnmqwert Term Paper of Graph Theory and Probability yuiopasdfghjklzxcvbnmqwertyuio Importance of Spanning pasdfghjklzxcvbnmqwertyuiopas Trees in Data Transfer dfghjklzxcvbnmqwertyuiopasdfgh jklzxcvbnmqwertyuiopasdfghjklzx cvbnmqwertyuiopasdfghjklzxcvb nmqwertyuiopasdfghjklzxcvbnmq wertyuiopasdfghjklzxcvbnmqwert yuiopasdfghjklzxcvbnmrtyuiopas dfghjklzxcvbnmqwertyuiopasdfgh jklzxcvbnmqwertyuiopasdfghjklzx cvbnmqwertyuiopasdfghjklzxcvb

Importance of Spanning Tree in Data Transfer

Acknowledgement I would like to express my gratitude to all those who gave me helping hand in completing this term paper. I want to thank my mathematics teacher Miss Manjit for helping me whenever I needed it the most. My friends have also supported me in my work. I want to thank them all for their help, support, interest and valuable hints.

Term Paper

Page 2

Importance of Spanning Tree in Data Transfer

Contents S. no.

Title

Page

1.

Introduction

4

2

Spanning Trees & Data Transfer

7

3.

References

12

Term Paper

Page 3

Importance of Spanning Tree in Data Transfer

S

Introduction panning tree T of a connected, undirected graph G is a tree composed of all the vertices and some (or perhaps all) of the edges of G. Informally, a spanning tree of G is a selection of edges of G that form a tree spanning every

vertex.

Spanning trees • Suppose you have a connected undirected graph – Connected: every node is reachable from every other node – Undirected: edges do not have an associated direction • ...then a spanning tree of the graph is a connected sub graph in which there are no cycles

Fig. 1

Fig. 2

Finding a spanning tree •

To find a spanning tree of a graph, pick an initial node and call it part of the spanning tree do a search from the initial node: each time you find a node that is not in the spanning tree, add to the spanning tree both the new node and the edge you followed to get to it

Fig.3 Term Paper

Fig.4

Fig.5 Page 4

Importance of Spanning Tree in Data Transfer Minimum-weight spanning trees • • •

Suppose you have a connected undirected graph with a weight (or cost) associated with each edge The cost of a spanning tree would be the sum of the weight of its edges A minimum-weight spanning tree is a spanning tree that has the lowest cost

Fig.6

Fig.7

Kruskal’s algorithm

• •

T = empty spanning tree; E = set of edges; N = number of nodes in graph; while T has fewer than N - 1 edges { remove an edge (v, w) of lowest cost from E if adding (v, w) to T would create a cycle then discard (v, w) else add (v, w) to T } Finding an edge of lowest cost can be done just by sorting the edges Efficient testing for a cycle requires a fairly complex algorithm (UNIONFIND) which we don’t cover in this course

Prim’s algorithm T = a spanning tree containing a single node s; E = set of edges adjacent to s; while T does not contain all the nodes { remove an edge (v, w) of lowest cost from E if w is already in T then discard edge (v, w) Term Paper

Page 5

Importance of Spanning Tree in Data Transfer else { add edge (v, w) and node w to T add to E the edges adjacent to w } • •

} An edge of lowest cost can be found with a priority queue Testing for a cycle is automatic

Example of Spanning Tree: Mazes • • • •

Typically, – Every location in a maze is reachable from the starting location – There is only one path from start to finish If the cells are “vertices” and the open doors between cells are “edges,” this describes a spanning tree Since there is exactly one path between any pair of cells, any cells can be used as “start” and “finish” This describes a spanning tree

Mazes as spanning trees • • •

While not every maze is a spanning tree, most can be represented as such The nodes are “places” within the maze There is exactly one cycle-free path from any node to any other node

Term Paper

Page 6

Importance of Spanning Tree in Data Transfer

Spanning Trees & Data Transfer A company plans to build communication network connecting its five computer centers. Any pair of these centers can be linked with a leased telephone line. Which links should be made to ensure that there is a path between any two computer centers so that the total cost of the network is minimized? We can model this problem using the weighted graph shown in fig.9, where vertices represents the computer centers, edges represent possible leased lines, and the weights on edges are the monthly lease rates of lines represented by the edges. We can solve this problem by finding a spanning tree so that the sum of the weights of edges of the tree is minimized. Such a spanning tree is called a minimum spanning tree.

$2000

NEW YORK CHICAGO $1000

$1200 SAN FRANCISCO

$1300 $1600

$800

$900 $700 DENVER $1400 ATLANTA $2200

Fig.9

 Example: Use Prim’s algorithm design a minimum-cost cost communication network connecting all the computers represented by the graph in Fig.9 Solution: We solve this problem by finding a minimum spanning tree in the graph in fig.10. Prim’s Algorithm is carried out by choosing an initial edge of minimum weight and successively adding edges of minimum weight that are incident to a vertex in the tree and that do not form simple circuits. The edges in color in fig.10 show minimum spanning tree produced by Prim’s algorithm, with the choice made at each step displayed. Term Paper

Page 7

Importance of Spanning Tree in Data Transfer

$2000

NEW YORK CHICAGO $1000

$1200 SAN FRANCISCO

$1300 $1600

$800

$900 $700 DENVER $1400 ATLANTA $2200

Fig.10 Choice 1. 2. 3. 4.

a

Edge [Chicago, Atlanta] [Atlanta, New York] [Chicago, San Francisco] [San Francisco, Denver] Total: 2

b

3

3

c

1 4

Cost $ 700 $ 800 $1200 $ 900 $3600 1

d

2

f

3

5

g

3

h

e 4

2

f

3

4

j

3

k

3

1

l

fig.11 

Example:

Use Prim’s algorithm to find a minimum spanning tree in the graph shown in fig.11 Term Paper

Page 8

Importance of Spanning Tree in Data Transfer Solution: A minimum spanning tree constructed using Prim’s algorithm is shown in fig.11. The successive edges chosen are displayed. a

2

3

b

3

1 4

c

1

d

2

f

3

5

g

3

h

e 4

2

f

3

j

4

3

k

3

1

l

Fig.12 Choice 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.

Edge [b, f] [a, b] [f, j] [a, e] [i, j] [f, g] [c, g] [c, d] [g ,h] [h, l] [k, l] Total:



Weight 1 2 2 3 3 3 2 1 3 3 1 24

Example:

Use Kruskal’s algorithm to find a minimum spanning tree in the weighted graph shown in fig.10. Term Paper

Page 9

Importance of Spanning Tree in Data Transfer Solution: A minimum spanning tree and the choices of edge at each stage of Kruskal’s algorithm are shown in fig.13.

a

2

b

3

3

c

1 4

1

d

2

f

3

5

g

3

h

e 4

2

f

3

Choice 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.

j

4

3 Fig.13.

k

Edge [c, d] [k, l] [b, f] [c, g] [a, b] [f, j] [b, c] [j, k] [g, h] [i, j] [a, e] Total:

3

1

l Weight 1 1 1 2 2 2 3 3 3 3 3 24

IP MULTICASTING: Spanning trees play an important role in multicasting our Internet Protocol (IP) networks. To send data from a source computer to multiple receiving computers, each of which is a subnetwork, data could be sent separately to each computer. This type of networking, called unicasting, is insufficient, because many copies of the same data are transmitted over the network. To make the transmission of data to Term Paper

Page 10

Importance of Spanning Tree in Data Transfer multiple receiving computers more efficient IP multicasting is used. With IP multicasting, a computer sends a single copy of data over the network, and as data reaches intermediate routers, the data are forwarded to one or more other routers so that ultimately all receiving computers in their various subnetworks receive these data. For data to reach receiving computers as quickly as possible there should be no loops (which in graph theory terminology are circuits and cycles) in that path that data takes through the network. That is once data have reached a particular router, data should never return to their router. To avoid loops, the multicast router use network algorithms to construct a spanning tree in the graph that has the multicast source, the routers and the subnetworks containing receiving computers as vertices, with edges representing the links between computers and/or routers. The root of this spanning tree is the multicast source. The subnetworks containing receiving computers are leaves of the tree. (Note that subnetworks not containing receiving stations are not included in the graph.) This is illustrated in Fig.14.

IP Network

Multicast spanning tree

SOURCE SOURCE

(a)

(b)

- Router - Subnetwork - Subnetwork with receiving stations Fig.14. Multicast Spanning Tree

Term Paper

Page 11

Importance of Spanning Tree in Data Transfer

REFERENCES Book: Discrete Mathematics & Its Applications By: Kenneth H Rosen Tata Mc Graw-Hill Companies http://www.google.com/search?hl=en&q=spanning+trees

Term Paper

Page 12