Cutting Algorithm
Páginas: 2 (384 palabras)
Publicado: 26 de noviembre de 2012
Network Optimization
1.
2.
3.
4.
Introduction.
Description.
Example.
Bibliography.
30/10/2012
2
Goal: I have a set of cities and I want join all
cities withthe minimum kilometres of roads.
Cutting algorithm is a procedure to obtain a
minimum or maximum spanning tree.
I have several possibilities.
15
Madrid
Valencia
5
2
8
20
Toledo
10Albacete
30/10/2012
3
Let G a non-directed graph with N = {1, 2,…,n}
nodes and E = {a1, a2,… ,ae} edges.
Steps:
While (e > n-1) do:
To sort E high to low with respectto weight. (If we
have 2 edges with the same weight, the order,
between them, are indifferent).
ai = The edge with greater weight.
If (G – {ai}) is a connected graph then:
G = G – {ai}. Else
ai = Next element in the set.
Go to if.
30/10/2012
4
30/10/2012
5
(or, des)
Weight
(2,8)
7
(9,10)
18
(1,5)
6
(8, 10)
10
(2,7)
5
(1,2)9
(1,6)
4
(2, 4)
9
(2,3)
4
(5,9)
9
(3, 10)
4
(6,8)
9
(5,6)
3
(6,9)
9
(7,10)
3
(7,8)
9
(1,4)
2
(4,8)
8
(4,6)
2
(8,9)8
(3,7)
1
30/10/2012
6
(or, des)
Weight
(2,8)
7
(8, 10)
10
(1,5)
6
(1,2)
9
(2,7)
5
(2, 4)
9
(1,6)
4
(5,9)
9
(2,3)
4
(6,8)9
(3, 10)
4
(6,9)
9
(5,6)
3
(7,8)
9
(7,10)
3
(4,8)
8
(1,4)
2
(8,9)
8
(4,6)
2
(3,7)
1
30/10/2012
7
(or, des)
Weight
(4,8)8
(8,9)
8
(2,8)
7
(1,5)
6
(2,7)
5
(1,6)
4
(2,3)
4
(3, 10)
4
(5,6)
3
(7,10)
3
(1,4)
2
(4,6)
2
(3,7)
1
30/10/2012
8 (or, des)
Weight
(4,8)
8
(8,9)
8
(2,8)
7
(2,3)
4
(5,6)
3
(7,10)
3
(1,4)
2
(4,6)
2
(3,7)
1
30/10/2012
9
1.
2.
Lesson 3, Network...
1.
2.
3.
4.
Introduction.
Description.
Example.
Bibliography.
30/10/2012
2
Goal: I have a set of cities and I want join all
cities withthe minimum kilometres of roads.
Cutting algorithm is a procedure to obtain a
minimum or maximum spanning tree.
I have several possibilities.
15
Madrid
Valencia
5
2
8
20
Toledo
10Albacete
30/10/2012
3
Let G a non-directed graph with N = {1, 2,…,n}
nodes and E = {a1, a2,… ,ae} edges.
Steps:
While (e > n-1) do:
To sort E high to low with respectto weight. (If we
have 2 edges with the same weight, the order,
between them, are indifferent).
ai = The edge with greater weight.
If (G – {ai}) is a connected graph then:
G = G – {ai}. Else
ai = Next element in the set.
Go to if.
30/10/2012
4
30/10/2012
5
(or, des)
Weight
(2,8)
7
(9,10)
18
(1,5)
6
(8, 10)
10
(2,7)
5
(1,2)9
(1,6)
4
(2, 4)
9
(2,3)
4
(5,9)
9
(3, 10)
4
(6,8)
9
(5,6)
3
(6,9)
9
(7,10)
3
(7,8)
9
(1,4)
2
(4,8)
8
(4,6)
2
(8,9)8
(3,7)
1
30/10/2012
6
(or, des)
Weight
(2,8)
7
(8, 10)
10
(1,5)
6
(1,2)
9
(2,7)
5
(2, 4)
9
(1,6)
4
(5,9)
9
(2,3)
4
(6,8)9
(3, 10)
4
(6,9)
9
(5,6)
3
(7,8)
9
(7,10)
3
(4,8)
8
(1,4)
2
(8,9)
8
(4,6)
2
(3,7)
1
30/10/2012
7
(or, des)
Weight
(4,8)8
(8,9)
8
(2,8)
7
(1,5)
6
(2,7)
5
(1,6)
4
(2,3)
4
(3, 10)
4
(5,6)
3
(7,10)
3
(1,4)
2
(4,6)
2
(3,7)
1
30/10/2012
8 (or, des)
Weight
(4,8)
8
(8,9)
8
(2,8)
7
(2,3)
4
(5,6)
3
(7,10)
3
(1,4)
2
(4,6)
2
(3,7)
1
30/10/2012
9
1.
2.
Lesson 3, Network...
Leer documento completo
Regístrate para leer el documento completo.