n
C = [cij]n×n cij e" 0 i, j = 1, . . . , n
i j
(i1, i2, . . . , in, i1)
ci i2 + ci i3 + . . . + ci in + ci i1
1 2 n-1 n
n (ij, ij+1)
(i, i) i = 1, . . . , n
cii = +", i = 1, . . . , n.
n (n-1)!
1
(1, i2), (i2, i3), . . . , (in-1, in), (in, 1), i2, i3, . . . , in " {2, 3, , . . . , n}
n - 1 (n - 1)!
c1i + ci i3 + . . . + ci in + ci 1
2 2 n-1 n
ci i3 + . . . + ci in + ci 1 + c1i
2 n-1 n 2
(i2, i3), . . . , (in-1, in), (in, 1), (1, i2)
n (n - 1)! n
8! = 4032
2n n = 9 n = 13
213 = 8192
 X = [xij]1d"i,jd"n
1, (i, j)
xij =
0, .
Å„Å‚
n n
ôÅ‚
ôÅ‚
ôÅ‚
cijxij min
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
i=1 j=1
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚ n
ôÅ‚
ôÅ‚
òÅ‚
xij = 1, i = 1, . . . , n,
ôÅ‚j=1
ôÅ‚ n
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
xij = 1, j = 1, . . . , n,
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
i=1
ôÅ‚
ôÅ‚x e" 0, xij " Z, i, j = 1, . . . , n,
ôÅ‚
ôÅ‚
ij
ôÅ‚
ôÅ‚
ół {(i, j) : xij = 1} {(i1, i2), . . . , (in-1, in), (in, i1)}.
n
xij = 1, i = 1, . . . , n xij e" 0, xij " Z, i, j = 1, . . . , n,
j=1
n
xij = 1, j = 1, . . . , n xij e" 0, xij " Z, i, j = 1, . . . , n,
i=1
{(i, j) : xij = 1} {(i1, i2), . . . , (in-1, in), (in, i1)},
 C = [cij] = [cij - ui - vj]
X = [xij]
n n n n n n
cijxij = cijxij + ui + vj.
i=1 j=1 i=1 j=1 i=1 j=1
X = [xij]
n n n n n n n n n n
cijxij = (cij + ui + vj)xij = cijxij + ( xij)ui + ( xij)vj =
i=1 j=1 i=1 j=1 i=1 j=1 i=1 j=1 j=1 i=1
n n n n
= cijxij + 1 · ui + 1 · vj.
i=1 j=1 i=1 j=1
C = [cij]
C = [cij] = [cij - ui - vj]
C = [cij]n×n
C = [cij] C = [cij]
C1 = [c1 ] C = [cij]
ij
c1 = cij - ui, ui = min cij
ij
j=1,...,n
C1
C2 = [c2 ] C = [cij]
ij
c2 = c2 - vj, vj = min c1 .
ij ij ij
j=1,...,n
C2 C
n n
ui + vj
i=1 j=1
 C = [cij] = [cij - ui - vj]
n n n n
cijxij e" ui + vj.
i=1 j=1 i=1 j=1
X = [xij] X e" 0
n n n n n n
0 d" cijxij = cijxij - ui - vj.
i=1 j=1 i=1 j=1 i=1 j=1
C
n-1
n
n - 1
îÅ‚ Å‚Å‚
" 8 7 5
ïÅ‚ śł
2 " 6 4
ïÅ‚ śł
C = .
ðÅ‚ ûÅ‚
3 10 " 4
7 5 4 "
(k, l) (k, l)
(k, l) (k, l)
(k, l) (k, l)
G
Õ(G)
" 3 2 0
C1 =
0 " 4 2
0 7 " 1
3 1 0 "
 ui i = 1, 2, 3, 4
" 2 2 0
0 " 4 2
C2 =
0 6 " 1
3 0 0 "
vj j = 1, 2, 3, 4
4 4
R = ui+ vj = 15 Õ(G) = 15
i=1 j=1
cii = " i = 1, . . . , n
0 · (+") =: 0
xii = 0 i = 1, . . . , n
4
cijxij = 8x12 + 7x13 + 5x14 + 2x21 + 6x23 + 4x24 + 3x31 + 10x32 + 4x34+
i,j=1
7x41 + 5x42 + 4x43 = 5(x11(= 0) + x12 + x13 + x14) + 3x12 + 2x13+
+ 2(x21 + x22(= 0) + x23 + x24) + 4x23 + 2x24 + 3(x31 + x32 + x33(= 0) + x34)+
7x32 + x43 + 4(x41 + x42 + x43 + x44(= 0)) + 3x41 + x42 =
14 + (x21 + x22(= 0) + x32 + x42) + 2x12 + 2x13 + 4x32 + 2x42 + 6x32 + x43 + 3x41
e" 15 + 0.
(k, l) (k, l) (k, l)
(1, 4), (2, 1), (3, 1), (4, 2), (4, 3)
(2, 1)
 (2, 1)
(1, 4)
(3, 1)
(4, 2)
(4, 3)
1 2 3 4
1 " 2 2 0(3)
C2 =
2 0(2) " 4 2
3 0(1) 6 " 1
4 3 0(2) 0(2) "
(k, l)
(1, 4)
G
(1, 4)
x14 = 1
4 4
xij = 1, i = 1, 2, 3, 4 xij = 1, j = 1, 2, 3, 4
j=1 i=1
i = 1 j = 4
(1, 4)
(4, 1) "
1 2 3
2 0 " 4
C(1,4) =
3 0 6 "
4 " 0 0
R(1,4) = 15 + 0 = 15
Õ((1, 4)) = 15
(1, 4)
(1, 4)
R(1,4) = 15 + 3 = 18
Õ((1, 4)) = 18
min{Õ((1, 4)), Õ((1, 4))} = Õ((1, 4)) = 15.
G
((1, 4)) A, B A *" B = (1, 4) A )" B = "
(1, 4)
 (2, 1) (3, 1) (4, 2) (4, 3)
1 2 3
2 0(4) " 4
C(1,4) =
3 0(6) 6 "
4 " 0(6) 0(4)
(3, 1) (4, 2)
(3, 1)
(1, 4) (3, 1)
c13 (1, 4) (3, 1)
(4, 3) c43 = "
2 3
C(1,4)(3,1) =
2 " 4
4 0 "
2 3
C(1,4)(3,1) =
2 " 0 4
4 0 " 0
R(1,4),(3,1) = 15 + 4 = 19 Õ((1, 4)
(3, 1)) = 19
(1, 4)
(3, 1) ((1, 4), (3, 1))
R(1,4),(3,1) = 15 +
6 = 21 Õ((1, 4), (3, 1)) = 21
min{Õ((1, 4)) = 18, Õ((1, 4), (3, 1)) = 19, Õ((1, 4), (3, 1)) = 21} = Õ((1, 4)) = 18.
(3, 1)
(4, 2)
Õ((1, 4), (4, 2)) = 19, Õ((1, 4), (4, 2)) = 21.
(1, 4) (3, 1) Õ((1, 4), (3, 1)) = 19
(1, 4) (3, 1)
Õ((1, 4), (3, 1)) = 21 A, B A *" B = (1, 4) A )" B = "
 (1, 4)
c14 = "
(1, 4)
1 2 3 4
1 " 2 2 "
C(1,4) =
2 0 " 4 2
3 0 6 " 1
4 3 0 0 "
1 2 3 4
1 " 0 0 " 2
1
C(1,4) =
2 0 " 4 2 0
3 0 6 " 1 0
4 3 0 0 " 0
1 2 3 4
1 " 0 0 "
2 0 " 4 1
C(1,4) =
3 0 6 " 0
4 3 0 0 "
0 0 0 1
(1, 4) R(1,4) = 15 + 3 = 18
(1, 4)
(1, 2), (1, 3), (2, 1) (3, 1) (3, 4) (4, 2) (4, 3)
1 2 3 4
1 " 0(0) 0(0) "
C(1,4) =
2 0(1) " 4 1
3 0(0) 6 " 0(1)
4 3 0(0) 0(0) "
(2, 1) (3, 4)
(2, 1) 18+1 = 19 Õ((1, 4), (2, 1)) =
19
 (1, 4) (2, 1)
c12 = "
(2, 1) (1, 2)
2 3 4
1 " 0 "
C(1,4),(2,1) =
3 6 " 0
4 0 0 "
Õ((1, 4), (2, 1)) = Õ((1, 4)) = 18
min{Õ((1, 4), (2, 1)), Õ((1, 4), (2, 1)), Õ((1, 4), (3, 1)), Õ((1, 4), (3, 1))} = Õ((1, 4), (2, 1)) = 18.
(1, 4) (2, 1)
(1, 4) (3, 1)
Õ((1, 4), (3, 1)) = 19 (1, 4)
(3, 1) Õ((1, 4), (3, 1)) = 21
(1, 4), (2, 1) Õ((1, 4), (2, 1)) = 19 A, B
A *" B = ((1, 4), (2, 1)) A )" B = "
(1, 4) (2, 1)
(1, 3) (3, 4) (4, 2) (4, 3)
2 3 4
1 " 0(") "
C(1,4),(2,1) =
3 6 " 0(")
4 0(6) 0(0) "
(1, 3) (3, 4) "
(3, 4)
18 + " = " Õ((1, 4), (2, 1), (3, 4)) = "
(1, 4)
(2, 1), (3, 4)
c43 = " (3, 4)
(4, 3)
2 3
C(1,4),(2,1)(3,4) =
1 " 0
4 0 "
Õ((1, 4), (2, 1), (3, 4)) = 18
min{Õ((1, 4), (2, 1), (3, 4)) = 18, Õ((1, 4), (2, 1), (3, 4)) = ", Õ((1, 4), (2, 1)) = 19,
Õ((1, 4), (3, 1)) = 19, Õ((1, 4), (3, 1))} = 21} = Õ((1, 4), (2, 1), (3, 4)) = 18.
(1, 4) (2, 1) (3, 4)
(1, 4) (3, 1)
Õ((1, 4), (3, 1)) = 19 (1, 4)
(3, 1) Õ((1, 4), (3, 1)) = 21
(1, 4), (2, 1) Õ((1, 4), (2, 1)) = 19
(1, 4) (3, 4) (2, 1)
Õ((1, 4), (2, 1), (3, 4)) = " A, B A*"B = ((1, 4), (2, 1), (3, 4)) A)"B = "
(1, 4) (2, 1) (3, 4)
(1, 3) (4, 2)
2 3
C(1,4),(2,1)(3,4) =
1 " 0(")
4 0(") "
" (1, 3)
Õ((1, 4), (2, 1), (3, 4), (1, 3)) = "
(1, 4)
(2, 1), (3, 4), (1, 3)
2
C(1,4),(2,1),(3,4),(4,2) =
4 0
Õ((1, 4), (2, 1), (3, 4), (1, 3)) = 18 + 0 = 18.
(1, 4) (2, 1), (3, 4), (1, 3)
(2, 1), (3, 4), (1, 3), (4, 2)
c21 + c34 + c13 + c42 = 18 = Õ((1, 4), (2, 1), (3, 4), (1, 3)) = min{Õ((1, 4), (2, 1), (3, 4)),
Õ((1, 4), (2, 1), (3, 4)), Õ((1, 4), (2, 1)), Õ((1, 4), (3, 1)), Õ((1, 4), (3, 1))}},
(2, 1), (3, 4), (1, 3), (4, 2)
(1, 3, 4, 2, 1) (3, 4, 2, 1, 3) (4, 2, 1, 3, 4) (2, 1, 3, 4, 2)
 n - 1
îÅ‚ Å‚Å‚
" 27 43 16 30 26
ïÅ‚ śł
7 " 16 1 30 25
ïÅ‚ śł
ïÅ‚ śł
20 13 " 35 5 0
ïÅ‚ śł
C = .
ïÅ‚ śł
21 16 25 " 18 18
ïÅ‚ śł
ðÅ‚ ûÅ‚
12 46 27 48 " 5
23 5 5 9 5 "
(6 - 1)! = 120 C
1 2 3 4 5 6
1 2 3 4 5 6
1 " 11 27 0 14 10
1 " 11 27 0 14 10 16
2 1 " 15 0 29 24
2 6 " 15 0 29 24 1
3 15 13 " 35 5 0
C1 = C2 =
3 20 13 " 35 5 0 0
4 0 0 9 " 2 2
4 5 0 9 " 2 2 16
5 2 41 22 43 " 0
5 7 41 22 43 " 0 5
6 13 0 0 4 0 "
6 18 0 0 4 0 " 5
5 0 0 0 0 0
Õ( ) = 48
1 2 3 4 5 6
1 " 11 27 0(10) 14 10
2 1 " 15 0(1) 29 24
C2 =
3 15 13 " 35 5 0(5)
4 0(1) 0(0) 9 " 2 2
5 2 41 22 43 " 0(2)
6 13 0(0) 0(9) 4 0(2) "
(1, 4)
Õ((1, 4)) = 58.
 Õ((1, 4))
c41 = "
1 2 3 5 6
2 1 " 15 29 24
3 15 13 " 5 0
C(1,4) =
4 " 0 9 2 2
5 2 41 22 " 0
6 13 0 0 0 "
1 2 3 5 6
2 0 " 14 28 23 1
3 15 13 " 5 0 0
C(1,4) =
4 " 0 9 2 2 0
5 2 41 22 " 0 0
6 13 0 0 0 " 0
Õ((1, 4)) = 48 + 1 = 49.
min{Õ((1, 4)), Õ((1, 4))} = Õ((1, 4)) = 49,
(1, 4)
1 2 3 5 6
2 0(16) " 14 28 23
3 15 13 " 5 0(5)
C(1,4) =
4 " 0(2) 9 2 2
5 2 41 22 " 0(2)
6 13 0(0) 0(9) 0(2) "
(1, 4)
((1, 4), (2, 1)) ((1, 4), (2, 1)) Õ((1, 4)) = 58
Õ((1, 4), (2, 1)) = 49 + 16 = 65.
(1, 4), (2, 1)
(1, 2)
(1, 4) (2, 1)
(4, 2)
c42 = "
2 3 5 6
3 13 " 5 0
C(1,4),(2,1) =
4 " 9 2 2
5 41 22 " 0
6 0 0 0 "
2 3 5 6
3 13 " 5 0 0
C(1,4),(2,1) =
4 " 7 0 0 2
5 41 22 " 0 0
6 0 0 0 " 0
Õ((1, 4), (2, 1)) = 49 + 2 = 51.
min{Õ((1, 4), (2, 1)), Õ((1, 4), (2, 1)), Õ((1, 4))} = Õ((1, 4), (2, 1)) = 51,
(1, 4)
(2, 1)
2 3 5 6
3 13 " 5 0(5)
C(1,4),(2,1) =
4 " 7 0(0) 0(0)
5 41 22 " 0(22)
6 0(13) 0(7) 0(0) "
(1, 4), (2, 1)
((1, 4), (2, 1), (5, 6)) ((1, 4), (2, 1), (5, 6)) Õ((1, 4), (2, 1)) = 65
Õ((1, 4)) = 58
Õ((1, 4), (2, 1), (5, 6)) = 51 + 22 = 73.
(1, 4), (2, 1), (5, 6)
c65 = "
2 3 5
3 13 " 5
C(1,4),(2,1),(5,6) =
4 " 7 0
6 0 0 "
2 3 5
3 8 " 0 5
C(1,4),(2,1),(5,6) =
4 " 7 0 0
6 0 0 " 0
Õ((1, 4), (2, 1), (5, 6)) = 51 + 5 = 56.
min{Õ((1, 4), (2, 1), (5, 6)), Õ((1, 4), (2, 1), (5, 6)), Õ((1, 4), (2, 1)), Õ((1, 4), (2, 1)), Õ((1, 4))}
= Õ((1, 4), (2, 1), (5, 6)) = 56,
(1, 4)
(2, 1) (5, 6)
2 3 5
3 8 " 0(8)
C(1,4),(2,1),(5,6) =
4 " 7 0(7)
6 0(8) 0(7) "
(1, 4), (2, 1), (5, 6)
(3, 5) (6, 2) (6, 2)
((1, 4), (2, 1), (5, 6)) ((1, 4), (2, 1), (5, 6), (6, 2))
((1, 4), (2, 1), (5, 6), (6, 2)) Õ((1, 4), (2, 1), (5, 6)) = 73 Õ((1, 4), (2, 1)) =
65 Õ((1, 4)) = 58
Õ((1, 4), (2, 1), (5, 6), (6, 2)) = 56 + 8 = 64.
(1, 4), (2, 1), (5, 6), (6, 2)
3 5
C(1,4),(2,1),(5,6),(6,2) =
3 " 0
4 7 0
3 5
3 " 0
C(1,4),(2,1),(5,6),(6,2) =
4 0 0
7 0
Õ((1, 4), (2, 1), (5, 6), (6, 2)) = 56 + 7 = 63.
min{Õ((1, 4), (2, 1), (5, 6), (6, 2)), Õ((1, 4), (2, 1), (5, 6), (6, 2)), Õ((1, 4), (2, 1), (5, 6)),
Õ((1, 4), (2, 1), (5, 6)), Õ((1, 4), (2, 1)), Õ((1, 4), (2, 1)), Õ((1, 4))} = Õ((1, 4)) = 58
(1, 4)
(1, 4) c14 = "
1 2 3 4 5 6
1 " 11 27 " 14 10
2 1 " 15 0 29 24
C(1,4) =
3 15 13 " 35 5 0
4 0 0 9 " 2 2
5 2 41 22 43 " 0
6 13 0 0 4 0 "
1 2 3 4 5 6
1 " 1 17 " 4 0 10
2 1 " 15 0 29 24 0
C(1,4) =
3 15 13 " 35 5 0 0
4 0 0 9 " 2 2 0
5 2 41 22 43 " 0 0
6 13 0 0 4 0 " 0
Õ((1, 4)) = 58
1 2 3 4 5 6
1 " 1 17 " 4 0(1)
2 1 " 15 0(5) 29 24
C(1,4) =
3 15 13 " 35 5 0(5)
4 0(1) 0(0) 9 " 2 2
5 2 41 22 43 " 0(2)
6 13 0(0) 0(9) 4 0(2) "
(1, 4)
(6, 3)
Õ((1, 4), (6, 3)) = 58 + 9 = 67.
 Õ((1, 4), (6, 3))
c36 = "
1 2 4 5 6
1 " 1 " 4 0
2 1 " 0 29 24
C(1,4),(6,3) =
3 15 13 35 5 "
4 0 0 " 2 2
5 2 41 43 " 0
1 2 4 5 6
1 " 1 " 4 0 0
2 1 " 0 29 24 0
C(1,4),(6,3) =
3 10 8 30 0 " 5
4 0 0 " 2 2 0
5 2 41 43 " 0 0
Õ((1, 4), (6, 3)) = 58 + 5 = 63.
min{Õ((1, 4), (2, 1), (5, 6), (6, 2)), Õ((1, 4), (2, 1), (5, 6), (6, 2)), Õ((1, 4), (2, 1), (5, 6)),
Õ((1, 4), (2, 1), (5, 6)), Õ((1, 4), (2, 1)), Õ((1, 4), (2, 1)), Õ((1, 4), (6, 3)),
Õ((1, 4), (6, 3))} = Õ((1, 4), (2, 1), (5, 6), (6, 2)) = Õ((1, 4), (6, 3)) = 63
(1, 4) (2, 1) (5, 6) (6, 2) (1, 4)
(6, 3)
(1, 4) (2, 1) (5, 6) (6, 2)
3 5
C(1,4),(2,1),(5,6),(6,2) =
3 " 0(")
4 0(") 0(0)
(1, 4) (2, 1) (5, 6) (6, 2)
(3, 5) (4, 3) (3, 5)
((1, 4) (2, 1) (5, 6) (6, 2))
((1, 4) (2, 1) (5, 6) (6, 2) (3, 5)) ((1, 4) (2, 1) (5, 6) (6, 2) (3, 5))
Õ((1, 4), (2, 1), (5, 6), (6, 2)) = 64 Õ((1, 4), (2, 1), (5, 6)) = 73 Õ((1, 4), (2, 1)) =
65 Õ((1, 4), (6, 3)) = 63 Õ((1, 4), (6, 3)) = 67
Õ((1, 4), (2, 1), (5, 6), (6, 2), (3, 5)) = 64 + " = ".
 (1, 4) (2, 1) (5, 6) (6, 2)
(3, 5)
3
C(1,4),(2,1),(5,6),(6,2),(3,5) =
4 0
Õ((1, 4), (2, 1), (5, 6), (6, 2), (3, 5)) = 63 + 0 = 63.
(4, 3)
min{Õ((1, 4), (2, 1), (5, 6), (6, 2)), Õ((1, 4), (2, 1), (5, 6)), Õ((1, 4), (2, 1)), Õ((1, 4), (6, 3)),
Õ((1, 4), (6, 3)), Õ((1, 4), (2, 1), (5, 6), (6, 2), (3, 5)), Õ((1, 4), (2, 1), (5, 6), (6, 2), (3, 5))} =
= Õ((1, 4), (6, 3)) = Õ((1, 4), (2, 1), (5, 6), (6, 2), (3, 5)) = 63 = c14 + c43 + c35 + c56 + c62 + c21,
(1, 4, 3, 5, 6, 2, 1)
Õ((1, 4), (6, 3)) = Õ((1, 4), (2, 1), (5, 6), (6, 2), (3, 5)) = 63,
(1, 4, 3, 5, 6, 2, 1)
(1, 4) (6, 3)
1 2 4 5 6
1 " 1 " 4 0(1)
2 1 " 0(31) 29 24
C(1,4),(6,3) =
3 10 8 30 0(10) "
4 0(1) 0(1) " 2 2
5 2 41 43 " 0(2)
((1, 4), (6, 3))
(2, 4)
Õ((1, 4), (6, 3), (2, 4)) = 63 + 31 = 94 > 63
 Õ((1, 4), (6, 3), (2, 4))
c42 = "
1 2 5 6
1 " 1 4 0
C(1,4),(6,3),(2,4) =
3 10 8 0 "
4 0 " 2 2
5 2 41 " 0
Õ((1, 4), (6, 3), (2, 4)) > 63,
(1, 4, 3, 5, 6, 2, 1)