aoa presentation mst
Post on 03-Apr-2018
228 Views
Preview:
TRANSCRIPT
-
7/28/2019 AoA Presentation MST
1/32
BY: GHULAM ABBAS
MS-III(CCN)
SUKKUR IBA
-
7/28/2019 AoA Presentation MST
2/32
TopicsDefinitions & Networking Basics
MST Algorithms
KruskalReverse Delete
Prim
Brief History
Importance
-
7/28/2019 AoA Presentation MST
3/32
Definitions & Networking
BasicsNetwork models are created from two major
building blocks:arcs (sometimes called edges), which are
connecting lines, and
nodes, which are the connecting points for the
arcs.Agraph is a structure that is built byinterconnecting nodes and arcs.
Adirected graph (often called a digraph) is agraph in which the arcs have specified
directions, as shown by arrowheads.Finally, a network is a graph (or more commonly
a digraph) in which the arcs have an associatedflow.
Practical Optimization: A Gentle Introduction,John W. Chinneck, 2010http: / /www.sce.car leton .ca/faculty/chinneck/po.htm l
-
7/28/2019 AoA Presentation MST
4/32
Networking Basics
Practical Optimization: A Gentle Introduction,John W. Chinneck, 2010http: / /www.sce.car leton.ca/faculty/chinneck/po.htm l
A networkis an arrangement of paths
connected at various points, through whichitems move.
Introduction to Management Science, 9th ed, Bernard W. Taylor III, 2006
-
7/28/2019 AoA Presentation MST
5/32
Definitions & Networking BasicsSome further definitions associated with graphs and networks:
chain: a sequence of arcs connecting two nodes i and j.For example, in Figure 8.1(a), we might connect nodes
A and E via the chains ABCE or ADCE.
path: a sequence of directed arcs connecting two
nodes. In this case, you must respect the arc
directions. For example, in Figure 8.1(b), a path from A
to E might be ABDE, but the chain ABCE is not a path
because it traverses arc BC in the wrong direction.
cycle: a chain that connects a node to itself without any
retracing.
Practical Optimization: A Gentle Introduction,John W. Chinneck, 2010http: / /www.sce.car leton .ca/faculty/chinneck/po.htm l
-
7/28/2019 AoA Presentation MST
6/32
Definitions & Networking
Basicsconnected graph (or connected network): has
just one part. In other words you can reach anynode in the graph or network via a chain from
any other node.
Practical Optimization: A Gentle Introduction,John W. Chinneck, 2010http: / /www.sce.car leton.ca/faculty/chinneck/po.htm l
-
7/28/2019 AoA Presentation MST
7/32
Practical Optimization: A Gentle Introduction,John W. Chinneck, 2010http: / /www.sce.car leton.ca/faculty/chinneck/po.htm l
tree: a connected graph having no cycles.
Some examples are shown in Figure 8.2(a).
-
7/28/2019 AoA Presentation MST
8/32
Definitionsspanning tree: normally a tree selected from among thearcs in a graph or network so that all of the nodes in thetree are connected.
Practical Optimization: A Gentle Introduction,John W. Chinneck, 2010http: / /www.sce.car leton .ca/faculty/chinneck/po.htm l
-
7/28/2019 AoA Presentation MST
9/32
Definitionsflow capacity: an upper (and sometimes lower) limit on
the amount of flow in an arc in a network. For example,the maximum flow rate of water in a pipe, or themaximum simultaneous number of calls on atelephone connection.
source (or source node): a node which introduces flow
into a network. This happens at the boundary betweenthe network under study and the external world.
sink (or sink node): a node which removes flow from anetwork. This happens at the boundary between thenetwork under study and the external world.
Practical Optimization: A Gentle Introduction,John W. Chinneck, 2010http: / /www.sce.car leton.ca/faculty/chinneck/po.htm l
-
7/28/2019 AoA Presentation MST
10/32
The Minimum Spanning Tree
ProblemGiven a graph in which the arcs are labeled with the
distances between the nodes that they connect,find a spanning tree which has the minimum total
length.
NO CYCLES ALLOWED!!ALGORITHMS a problem solving procedure
following a set of rulesCycle- the nodes are connected by more than
one edge.
Practical Optimization: A Gentle Introduction,John W. Chinneck, 2010http: / /www.sce.car leton.ca/faculty/chinneck/po.htm l
-
7/28/2019 AoA Presentation MST
11/32
Steps of the minimal spanning tree solutionmethod:
1. Select any starting node (conventionally, node 1 isselected).
2. Select the node closest to the starting node to jointhe spanning tree.
3. Select the closest node not presently in the spanningtree.
4. Repeat step 3 until all nodes have joined the
spanning tree.
Introduction to Management Science, 9th ed, Bernard W. Taylor III, 2006
-
7/28/2019 AoA Presentation MST
12/32
Practical Optimization: A Gentle Introduction,John W. Chinneck, 2010http: / /www.sce.car leton.ca/faculty/chinneck/po.htm l
-
7/28/2019 AoA Presentation MST
13/32
What is an MST AlgorithmAn MST algorithm is a way to show theshortest distance
There are many different algorithms:
KruskalReverse Delete
Prim
Introduction to Management Science, 9th
ed, Bernard W. Taylor III, 2006
-
7/28/2019 AoA Presentation MST
14/32
KRUSKALS ALGORITHM1. Pick out the smallest edges
2. Repeat Step 1 as long as the edges selected does not
create a cycle3. When all nodes have been connected, you are done
http://www.slideshare.net/zhaokatherine/minimum-spanning-tree
http://www.slideshare.net/zhaokatherine/minimum-spanning-treehttp://www.slideshare.net/zhaokatherine/minimum-spanning-treehttp://www.slideshare.net/zhaokatherine/minimum-spanning-treehttp://www.slideshare.net/zhaokatherine/minimum-spanning-treehttp://www.slideshare.net/zhaokatherine/minimum-spanning-treehttp://www.slideshare.net/zhaokatherine/minimum-spanning-tree -
7/28/2019 AoA Presentation MST
15/32
REVERSE-DELETE ALGORITHMThis is the opposite of Kruskals algorithm
1. Start with all edges
2. Delete the longest edge3. Continue deleting longest edges as long as all nodes
are connected and no cycles are formed
http://www.slideshare.net/zhaokatherine/minimum-spanning-tree
http://www.slideshare.net/zhaokatherine/minimum-spanning-treehttp://www.slideshare.net/zhaokatherine/minimum-spanning-treehttp://www.slideshare.net/zhaokatherine/minimum-spanning-treehttp://www.slideshare.net/zhaokatherine/minimum-spanning-treehttp://www.slideshare.net/zhaokatherine/minimum-spanning-treehttp://www.slideshare.net/zhaokatherine/minimum-spanning-tree -
7/28/2019 AoA Presentation MST
16/32
PRIMS ALGORITHM1. Pick out a node
2. Pick out the shortest edge that is connected to your
tree so far, as long as it doesnt create a cycle3. Continue this until all nodes are covered
http://www.slideshare.net/zhaokatherine/minimum-spanning-tree
http://www.slideshare.net/zhaokatherine/minimum-spanning-treehttp://www.slideshare.net/zhaokatherine/minimum-spanning-treehttp://www.slideshare.net/zhaokatherine/minimum-spanning-treehttp://www.slideshare.net/zhaokatherine/minimum-spanning-treehttp://www.slideshare.net/zhaokatherine/minimum-spanning-treehttp://www.slideshare.net/zhaokatherine/minimum-spanning-tree -
7/28/2019 AoA Presentation MST
17/32
17
a
b
h
c d
e
fg
i
4
8 7
9
10
144
2
2
6
1
7
11
8
The execution of Kruskal's algorithm
The edges are considered by the algorithm insorted order by weight.
The edge under consideration at each step isshown with a red weight number.
-
7/28/2019 AoA Presentation MST
18/32
18
a
b
h
c d
e
fg
i
4
8 7
9
10
144
2
2
6
1
711
8
a
b
h
c d
e
fg
i
4
8 7
9
10
144
2
2
6
1
7
11
8
-
7/28/2019 AoA Presentation MST
19/32
19
a
b
h
c d
e
fg
i
4
8 7
9
10
144
2
2
6
1
7
11
8
a
b
h
c d
e
fg
i
4
8 7
9
10
144
2
2
6
1
7
11
8
-
7/28/2019 AoA Presentation MST
20/32
20
a
b
h
c d
e
fg
i
4
8 7
9
10
144
2
2
6
1
711
8
a
b
h
c d
e
fg
i
4
8 7
9
10
144
2
2
6
1
7
11
8
-
7/28/2019 AoA Presentation MST
21/32
21
a
b
h
c d
e
fg
i
4
8 7
9
10
144
2
2
6
1
711
8
a
b
h
c d
e
fg
i
4
8 7
9
10
144
2
2
6
1
711
8
-
7/28/2019 AoA Presentation MST
22/32
22
a
b
h
c d
e
fg
i
4
8 7
9
10
144
2
2
6
1
711
8
a
b
h
c d
e
fg
i
4
8 7
9
10
144
2
2
6
1
7
11
8
-
7/28/2019 AoA Presentation MST
23/32
Grow the minimum spanning tree from theroot vertex r.
Q is a priority queue, holding all verticesthat are not in the tree now.
key[v] is the minimum weight of any edgeconnecting v to a vertex in the tree.
parent[v] names the parent of v in the tree.When the algorithm terminates, Q is empty;
the minimum spanning tree A for G is thus
A={(v,parent[v]):v
V-{r}}.Running time: O(||E||lg |V|).
23
-
7/28/2019 AoA Presentation MST
24/32
24
a
b
h
c d
e
fg
i
4
8 7
9
10
144
2
2
6
1
7
11
8
a
b
h
c d
e
fg
i
4
8 7
9
10
144
2
2
6
1
7
11
8
The execution of Prim's algorithm(moderatepart)
the rootvertex
-
7/28/2019 AoA Presentation MST
25/32
25
a
b
h
c d
e
fg
i
4
8 7
9
10
144
2
2
6
1
7
11
8
a
b
h
c d
e
fg
i
4
8 7
9
10
144
2
2
6
1
711
8
-
7/28/2019 AoA Presentation MST
26/32
26
a
b
h
c d
e
fg
i
4
8 7
9
10
144
2
2
6
1
711
8
a
b
h
c d
e
fg
i
4
8 7
9
10
144
2
2
6
1
711
8
-
7/28/2019 AoA Presentation MST
27/32
27
a
b
h
c d
e
fg
i
4
8 7
9
10
144
2
2
6
1
7
11
8
a
b
h
c d
e
fg
i
4
8 7
9
10
144
2
2
6
1
711
8
-
7/28/2019 AoA Presentation MST
28/32
28
a
b
h
c d
e
fg
i
4
8 7
9
10
144
2
2
6
1
7
11
8
Bottleneck spanning tree: A spanning tree of Gwhose largest edge weight is minimum over allspanning trees of G. The value of the bottleneckspanning tree is the weight of the maximum-weightedge in T.
Theorem: A minimum spanning tree is also abottleneck spanning tree. (Challenge problem)
-
7/28/2019 AoA Presentation MST
29/32
MSTsKruskal (1956) and Prim (1957)
MSTs makes our life easier and we save money byusing short paths
MSTs was first seen in Poland, France, the CzechRepublic Slovakia, and Czechoslovakia
-
7/28/2019 AoA Presentation MST
30/32
IMPORTANCE OF MSTS1. We need it in computer science because it preventloops in a switched network with redundant paths
2. It is one of the oldest and most basic graphs intheoritical computer science
http://www.slideshare.net/zhaokatherine/minimum-spanning-tree
http://www.slideshare.net/zhaokatherine/minimum-spanning-treehttp://www.slideshare.net/zhaokatherine/minimum-spanning-treehttp://www.slideshare.net/zhaokatherine/minimum-spanning-treehttp://www.slideshare.net/zhaokatherine/minimum-spanning-treehttp://www.slideshare.net/zhaokatherine/minimum-spanning-treehttp://www.slideshare.net/zhaokatherine/minimum-spanning-tree -
7/28/2019 AoA Presentation MST
31/32
Why we like MSTs1. MSTs are fun to work with2. It helps us find the shortest route
Theshortestdistance between two people is asMILE.
-
7/28/2019 AoA Presentation MST
32/32
THANKS FOR PATIENCE
top related