Xem mẫu
- v5
• ..
..
.... .......
.... .......
....
.... ....
....
....
.... ....
....
....
.... ....
25 30
....
...
... ....
.... ....
.... ....
.... ....
.... ....
.. ....
.
....
.... ....
....
..
.
.... ....
.... ....
v4
.. ....
. ....
....
....
50
....
....
..
.
....
.... ....
....
..
. ....
.... ....
v7 • • v3
....
•
.........................................................
.........................................................
....
.... .
..... .
..
.... ....
.... ... .
. .. .
. ....
.... . ..... .
.... . .....
. .... .
. ....
....
. . .
....
....
. . .
20 20
. . .
...
.... ...
..
.
....
. . .
....
....
. . .
.... ...
. ...
.... . .
..
. . . .
....
.... ....
. . .
...
....
. ...
. .
. ..
.... .
....
. . .
.... .... ...
...
. . .
....
. . .
.... ..
.
. . .
...
....
.... ...
....
. . .
....
. . .
..
. . ...
.... ...
. .
....
....
. ....
v6 . .
. . .
....
. ...
..
. ...
....
....
. . .
....
. . .
.... ...
. . .
.... ...
..
.
. . .
....
.... ....
. . .
.... ...
. ...
. .
.... ......
.... ....
.
• . .
. ...
25 30 25
. .
...
. ... . . .
. ..
. . .
...
...
. . .
.
. . .
.
. ...
. .
40
. ...
. . .
.
. . .
. ...
. ...
. .
.
. . .
.
. . .
...
. ...
. . . .
. . . .
. ...
. . .
...
. .
. . .
.
. . .
...
...
.
20
. . .
. . . .
...
. . . .
...
. . . .
. . . .
...
. ...
. . .
. . . .
. ...
.
. . .
...
.
. . ... .
.
. . ... .
. . . .
. . . ... .
. ... .
. .
. . . .
. . . ....
. ....
. .
• • • •
. . . .
.................................................................................................................................................................
. . .
. ................................................................................................................................................................
.
v8 v9 v1 v2
20 40 30
H` 3.2:
ınh
012 034
˙ng ma trˆn A ⊕ B nˆu A = 2 0 3 v` B = 5 0 4 .
’ ´
V´ du 3.3.2 T` tˆ
ı. ım o a e a
.
560 310
Ta c´
o
012 034 012
A ⊕ B = 2 0 3 + 5 0 4 = 2 0 3.
560 310 310
Chˇng han, phˆn tu. c23 x´c d .nh bo.i
˙
’ `
a˙ ’ ˙
’
a a ¯i
.
c23 = min{2 + 4, 0 + 4, 3 + 0} = 3.
01∞ 10∞
V´ du 3.3.3 T` tˆ’ng ma trˆn A ⊕ B nˆu A = 1 0 4 v` B = 1 0 4 .
˙ ´
ı. ım o a e a
.
∞40 ∞40
Ta c´
o
01∞ 10∞ 105
A ⊕ B = 1 0 4 + 1 0 4 = 1 0 4.
∞40 ∞40 540
Chˇng han, phˆn tu. c13 x´c d .nh bo.i
˙
’ `
a˙ ’ ˙
’
a a ¯i
.
c23 = min{0 + ∞, 1 + 4, ∞ + 0} = 5.
Bˆy gi`. ´p dung tˆ’ng ma trˆn Hedetniemi v`o viˆc t` d u.`.ng d i ngˇn nhˆ t. X´t v´
˙ ´ ´
a oa o a a e ım ¯ o ¯ a a eı
. . .
89
- du trong H` 3.2. K´ hiˆu W 2 := W ⊕ W, W k := W k−1 ⊕ W, k ≥ 2. Khi d o
ınh ye ¯´
. .
0 30 55 30 60 50 ∞ 60 40
30 70
0 25 40 70 60 ∞ ∞
55 25 0 50 80 70 ∞ ∞ ∞
30 40
40 50 0 30 20 40 ∞
W = 60 ∞.
2
70 80 30 0 ∞ 25 ∞
∞ 20
∞ ∞ 20 ∞ 0 20 ∞
∞ ∞
∞ ∞ ∞ 25 20 0 25
∞ ∞ ∞ ∞ ∞ ∞ 25 0 20
40 ∞ ∞ ∞ ∞ 20 ∞ 20 0
Ch´ng ta h˜y x´t c´ch x´c d inh mˆt phˆn tu. cua ma trˆn W 2 = [aij ] :
(2)
`
a˙˙ ’’
u aea a ¯. o a
. .
(2)
a13 = min{0 + ∞, 30 + 25, ∞ + 0, 30 + 50, ∞ + ∞, ∞ + ∞, ∞ + ∞, ∞ + ∞, 40 + ∞}
= 55.
Ch´ y rˇ ng gi´ tri 55 l` tˆ’ng cua 30, d o d`i cua d u.`.ng d i ngˇn nhˆ t v´.i sˆ cung mˆt t`.
˙
u´ ` ´ ´ ´
˙
’ ¯ˆ a ˙ ¯ o
’
a a. ao ¯ a aoo ou
. .
(2)
´’ ´’
¯˙’ ¯e ¯˙ a˙ ’ ¯ˆ a ˙ ’ o ¯˙ a ¯˙’
d ınh v1 dˆn d ınh v2 , v` cua 25, d o d`i cua cung nˆi d ınh v2 v` d ınh v3 . Do d o a13 l` d o d`i
¯´ a ¯ˆ a
. .
cua d u.`.ng d i ngˇn nhˆ t t`. v1 dˆn v2 v´.i sˆ cung nhiˆu nhˆ t hai. Suy ra W 2 cho ta thˆng
´ ´ ´ ´ ` ´
˙ ¯o
’ ¯ a au ¯e oo e a o
.`.ng d i ngˇn nhˆ t gi˜.a hai d ınh c´ sˆ cung nhiˆu nhˆ t hai.
´
’´’ ´u ´ ` ´
˙ a ˙ a ¯ˆ a ¯ ¯˙’
tin cua tˆ t ca c´c d o d`i d u o ¯ a a oo e a
.
Tu.o.ng tu., W 3 cho ta thˆng tin cua tˆ t ca c´c d o d`i d u.`.ng d i ngˇn nhˆ t gi˜.a hai
´
’´’ ´u
˙ a ˙ a ¯ˆ a ¯ o
o ¯ a a
. .
d ınh c´ sˆ cung nhiˆu nhˆ t ba, v` vˆn vˆn. Do d` thi c´ n d ınh nˆn c´ nhiˆu nhˆ t (n − 1)
´ ` ´ ` ´
¯˙’ ¯ˆ . o ¯˙ ’
oo e a aa a o eo e a
.`.ng d i ngˇn nhˆ t gi˜.a hai d ınh. Vˆy
´ ´u ¯˙
’
cung trˆn d u o
e¯ ¯ a a a
.
Dinh l´ 3.3.4 Trong d` thi c´ trong sˆ khˆng ˆm n d ı’nh, phˆn tu. h`ng i cˆt j cu a ma
-. ´ `
¯˙ a ˙a ’ ˙
’
y ¯ˆ . o .
o ooa o
.
.`.ng d i ngˇn nhˆ t gi˜.a d ı’nh v v` v .
´ ´
n−1
a ¯o a ˙ ¯ ’ a u ¯˙
trˆn Hedetniemi W
a l` d ˆ d`i cu a d u o ¯ a iaj
. .
V´.i d` thi trong H` 3.2 c´ ch´ d ınh, ta c´
o ın ¯˙ ’
o ¯ˆ .
o ınh o
0 30 55 30 60 50 70 60 40
30 80 90 70
0 25 40 70 60
55 25 0 50 80 70 90 110 90
30 40 60 40
40 50 0 30 20
8
W = 60 70 80 30 0 45 25 50 65 .
50 20 40 20
60 70 20 45 0
0 25 40
70 80 90 40 25 20
60 90 110 60 50 40 25 0 20
40 70 90 40 65 20 40 20 0
Do d o, d u.`.ng d i ngˇn nhˆ t t`. v1 dˆn v7 c´ d o d`i 70.
´ ´ ´
¯´ ¯ o ¯ a au ¯e o ¯ˆ a
.
90
- Diˆu l´ th´ nhˆ t trong v´ du n`y l` W 4 = W 8 . Thˆt vˆy, d ang th´.c suy tru.c tiˆp t`.
-` y u a ˙
’
´ ´
e ı.aa a a ¯ˇ u eu
.. .
.`.ng d i ngˇn nhˆ t d i qua nhiˆu nhˆ t bˆn cung. Bo.i vˆy d o d`i
´
d` thi trong H` 3.2: moi d u o ¯ ´ ` ´´ ˙ a ¯ˆ a
’.
¯o .
ˆ ınh .¯ a a¯ e ao .
.`.ng d i ngˇn nhˆ t d u.o.c x´c d inh bo.i ma trˆn W 4 thay v` phai t´ dˆn W 8 . Tˆ’ng ˙
´ ´ ´
˙¯
’ ˙’ ˙ ınh ¯e
’
cua d u o ¯ a a ¯ . a ¯. a ı o
.
qu´t ta c´
a o
-.
Dinh l´ 3.3.5 Trong d` thi c´ trong sˆ khˆng ˆm n d ı’nh, nˆu ma trˆn Hedetniemi W k =
´ ´
¯˙
y ¯ˆ . o .
o ooa e a.
˙u thi tˆp c´c d ˆ d`i cu a c´c d u.`.ng d i ngˇn nhˆ t, v` sˆ
’ ´ ´ ´
k−1 k k+1 k
. a a ¯o a ˙ a ¯ o ¯
’
W , c`n W = W , th` W biˆ
o ı e a a ao
. .
.`.ng d i ngˇn nhˆ t khˆng vu.o.t qu´ k.
˜ ´ ´
cung trˆn mˆ i d u o
e o¯ ¯ a a o a
.
Do d ´, thuˆt to´n n`y c´ thˆ’ d`.ng o. bu.´.c lˇp th´. k < (n − 1). Du.´.i d ay l` d oan
˙ ˙
’
¯o a a a o eu oa u o ¯ˆ a ¯ .
. .
.o.ng tr` minh hoa t´ ma trˆn lu˜ th`.a cua ma trˆn trong lu.o.ng W.
yu˙ ’
chu ınh . ınh a a
. . . .
void Hetdetniemi()
{
int i, j, k, t;
int Old[MAXVERTICES][MAXVERTICES], New[MAXVERTICES][MAXVERTICES];
Boolean Flag;
for (i = 1; i
- if (Flag == TRUE) break;
}
}
X´c d .nh d .`.ng d ngˇn nhˆ t
´ ´
a ¯i ¯u o ¯i a a
Bˆy gi`. ta t` d u.`.ng d i ngˇn nhˆ t t`. v1 dˆn v7 (d o d`i 70). Ta c´
´ ´ ´
a o ım ¯ o ¯ a au ¯e ¯ˆ a o
.
(4) (3)
w14 = w1k ⊕ wk7
v´.i k n`o d o. Nhu.ng c´c phˆn tu. w1k tao th`nh vector h`ng
’ (3) .
`
a˙
o a ¯´ a a a
(0, 30, 55, 30, 60, 50, 70, 60, 40)
v` c´c phˆn tu. wk7 tao th`nh vector cˆt
`
a˙ ’
aa a o
. .
(∞, ∞, ∞, ∞, 25, 20, 0, 25, ∞).
V` gi´ tri nho nhˆ t d at d u.o.c tai k = 6 u.ng v´.i 70 = 50 + 20 (v` k = 7) nˆn d u.`.ng d i ngˇn
´
´
˙ a ¯. ¯ . .
’
ıa. ´ o a e ¯o ¯ a
. v dˆn v s˜ d i qua nhiˆu nhˆ t ba cung t`. v dˆn v v` kˆt th´c v´.i cung d o d`i 20
´ ´ ` ´ ´ ´
nhˆ t t` 1 ¯e 7 e ¯
au e a u 1 ¯e 6 a e uo ¯ˆ a
.
. v dˆn v . (Thˆt ra, do gi´ tri nho nhˆ t c˜ng d at d u.o.c tai k = 7 (´.ng v´.i 70 + 0) nˆn
´ ´
˙
’ a u ¯. ¯ . .
t` 6 ¯e 7
u a a. u o e
.
` n tai d u.`.ng d i ngˇn nhˆ t t`. v1 dˆn v7 v´.i tˆ’ng sˆ cung d i qua khˆng vu.o.t qu´ ba).
˙
´ ´u ´ ´
tˆ . ¯ o
o ¯ a a ¯e oo o ¯ o a
.
Tiˆp dˆn ta t` cung tru.´.c khi dˆn d ınh v6 . Ch´ y rˇ ng w16 = 70 − 20 = 50. C´c
(4)
u´ `
´´ ´’
¯e ¯ ˙
e ¯e ım o a a
phˆn tu. wk6 tao th`nh vector cˆt
`
a˙ ’ a o
. .
(∞, ∞, ∞, 20, ∞, 0, 20, ∞, 20).
Lˆn n`y gi´ tri nho nhˆ t d at tai k = 4 (´.ng v´.i 50 = 30 + 20) nˆn d u.`.ng d i ngˇn nhˆ t d ˆ
´
` ´ ´.
˙
’ a ¯. .
aa a. u o e ¯o ¯ a a ¯o
. v dˆn v kˆt th´c v´.i cung (v , v ) d ˆ d`i 20. Cuˆi c`ng, c´c phˆn tu. w tao
´ ´ ´ `
a ˙ k4 .
’
d`i 50 t` 1 ¯e 6 e
a u uo ¯o a ou a
.
46
th`nh vector cˆt
a o
.
(30, 40, 50, 0, 30, 20, ∞, ∞, ∞),
v` gi´ tri nho nhˆ t d at tai k = 1 hoˇc k = 4 (´.ng v´.i 30 + 0 hoˇc 0 + 30) nˆn tˆn tai cung
´ e`.
˙
’ a ¯. .
aa. a u o a o
. .
. v dˆn v . Vˆy d u.`.ng d i ngˇn nhˆ t t`. v dˆn v l` v , v , v , v (c´c cung c´
´
´ ´ ´
d o d`i 30 t` 1 ¯e 4 a ¯ o
¯ˆ a u ¯ a a u 1 ¯e 7 a 1 4 6 7 a o
. .
d o d`i 30, 20, 20).
¯ˆ a
.
Do d ´ thuˆt to´n Hedetniemi cho mˆt minh hoa h` hoc trong mˆ i bu.´.c lˇp, v` su.
˜ a˙ ’
¯o a a o . ınh . o oa
. . .
˙ phuc hˆi d u.o.c d u.`.ng d i ngˇn nhˆ t. Nhu. vˆy, ch´ng ta cˆn thˆm
’ . `¯. ¯o ´ ´ `
dung c´c ma trˆn c´ thˆ
a aoe o ¯ a a a u a e
. . .
mˆt ma trˆn P lu.u tr˜. thˆng tin cua c´c d u.`.ng d i ngˇn nhˆ t. Ma trˆn n`y s˜ d u.o.c cˆp
´ ´
˙ a ¯o
’
o a uo ¯ a a a a e¯ . a
. . . .
nhˆt trong mˆ i bu.´.c lˇp khi t´ W k t`. W k−1 .
˜
a o oa ınh u
. .
92
- Thuˆt to´n Floyd (tru.`.ng ho.p ma trˆn trong lu.o.ng tu` y)
3.3.2 a a o a y´
. . . . .
Thuˆt to´n du.´.i d ay d u.o.c d u.a ra lˆn d` u tiˆn bo.i Floyd [25] v` d u.o.c l`m min ho.n bo.i
` ¯ˆ ˙
’ ˙
’
a a o ¯ˆ ¯ . ¯ a a e a¯ . a
. .
Murchland [46].
Thuˆt to´n Floyd
a a
.
1. [Kho.i tao] Dˇt k := 0.
˙ . -a
’ .
2. k := k + 1.
3. [Bu.´.c lˇp] V´.i moi i = k sao cho wik = ∞ v` v´.i moi j = k sao cho wkj = ∞, thu.c
oa o ao
. . . .
hiˆn ph´p g´n
e ea
.
wij := min{wij , (wik + wkj )}. (3.3)
4. [Diˆu kiˆn kˆt th´c] (a) Nˆu tˆn tai chı sˆ i sao cho wii < 0 th` tˆn tai mach v´.i d ˆ
-` ´ e`.
´o ’´ ı` .
˙o
e ee u o o ¯o
. . .
.a d ınh v . B`i to´n vˆ nghiˆm; thuˆt to´n d`.ng.
d`i ˆm ch´ ¯˙ ’
aa u aao e a au
. .
i
(b) Nˆu wii ≥ 0 v´.i moi i = 1, 2, . . . , n, v` k = n, b`i to´n c´ l`.i giai: ma trˆn wij cho
´ ˙
’
e o a a a oo a
. .
.`.ng d i ngˇn nhˆ t t`. v dˆn v . Thuˆt to´n d`.ng.
´ ´ ´
d ˆ d`i d u o
¯o a ¯ ¯ a a u i ¯e j a au
. .
´u wii ≥ 0 v´.i moi i = 1, 2, . . . , n, nhu.ng k < n, chuyˆ’n sang Bu.´.c 2.
˙
(c) Nˆe o e o
.
Ch´.ng minh t´ d ung d ˇn cua thuˆt to´n Floyd l` ho`n to`n d o.n gian [35], [25] v`
´ ˙
’ ˙
’
u ınh ¯´ ¯a a a aa a¯ a
.
.`.i d oc. Ph´p to´n co. ban cua Phu.o.ng tr` 3.3 trong thuˆt to´n n`y goi l`
˙
’ ˙
’
d`nh cho ngu o ¯ .
a e a ınh a a a .a
.
ph´p to´n bˆ ba v` c´ nhiˆu u.ng dung trong nh˜.ng b`i to´n tu.o.ng tu. b`i to´n t` d u.`.ng
`´
e ao ao e u aa a a ım ¯ o
. . .
´ ´
d i ngˇn nhˆ t (xem [14], [30]).
¯ a a
C´c d u.`.ng d i ngˇn nhˆ t c´ thˆ’ nhˆn d u.o.c d` ng th`.i c`ng v´.i c´c d o d`i d u.`.ng d i
˙
´ ´
a ¯o ¯ a a o e a ¯ . ¯ˆ o ou o a ¯ˆ a ¯ o ¯
. .
. dung quan hˆ dˆ qui tu.o.ng tu. Phu.o.ng tr` 3.2. Bˇ ng c´ch ´p
´ a` `
´a ˙
’
ngˇn nhˆ t bˇ ng c´ch su .
a a e ¯e ınh a aa
.. .
. chˆ cua Hu [35] dˆ’ lu.u gi˜. thˆng tin c´c d u.`.ng d i ngˇn nhˆ t c`ng v´.i d o d`i cua
˙ ´
´˙ ´u
’ o ¯ˆ a ˙ ’
dung co e ¯e uo a ¯o ¯ a a
. .
.a v`o ma trˆn vuˆng cˆ p n : P := [θ ]; v` biˆn d ˆ’i n´ d` ng th`.i v´.i viˆc
n´. Cu thˆ’ l` d u a
˙ ˙
´ ´
o . e a¯ a o a a e ¯o o ¯o ˆ ooe
. .
ij
˙i ma trˆn W. Phˆn tu. θij cua ma trˆn P s˜ chı ra d ınh d i tru.´.c vj trong d u.`.ng d i
’
´ `
a˙ ’ ˙’ e˙ ’ ¯˙ ’¯
biˆn d ˆ
e ¯o a a o ¯o ¯
. .
ngˇn nhˆ t t`. vi dˆn vj ; o. bu.´.c d` u tiˆn ta g´n cho ma trˆn P c´c gi´ tri d` u l` θij := vi
´ ´ ´ ˙
’
a au ¯e o ¯ˆ
a e a a a a . ¯a a
ˆ
.
v´.i moi d ınh vi v` vj .
¯˙
’
o a
.
C`ng v´.i viˆc biˆn d o’i ma trˆn W theo Phu.o.ng tr` 3.3 trong Bu.´.c 3, ta biˆn d o’i
˙ ˙
´ ´
u oe e ¯ˆ a ınh o e ¯ˆ
. .
´
P theo quy tˇc
a
´
θkj nˆu (wik + wkj ) < wij ,
e
θij :=
nˆu ngu.o.c lai.
´
θij e ..
.o.c s˜ gi´p cho ta viˆc t` c´c d u.`.ng d i ngˇn nhˆ t.
´
´ ´
Kˆt th´c thuˆt to´n, ma trˆn P thu d u . e u
e u a a a ¯ e ım a ¯ o ¯ a a
. . .
˙ ng han d u.`.ng d i ngˇn nhˆ t gi˜.a hai d ınh vi v` vj l`
’ ´ ´u ¯˙
’
Chˇa . ¯o ¯ a a a a
vi , v ν , . . . , v γ , v β , v α , v j
93
- ´
trong d o vα = θij , vβ = θiα , vγ = θiβ , ..., cho dˆn khi vi = θiν .
¯´ ¯e
Cˆn ch´ y o. d ˆy l` nˆu tˆ t ca c´c gi´ tri wii d u.o.c kho.i tao bˇ ng ∞ (thay cho bˇ ng
˙.` `
` ´´’
u ´ ˙ ¯a a e a ˙ a
’ ’
a a. ¯. a a
´
´ ´ ´
˙
’ a ¯o a ˙ ’
0) l´c xuˆ t ph´t thuˆt to´n, th` c´c gi´ tri cuˆi c`ng cua wii l` d ˆ d`i cua mach ngˇn nhˆ t
u a a a a ıa a.ou a a
. . .
´t ph´t t`. d ınh vi . Ngo`i ra c˜ng c´ thˆ’ dˆ d`ng x´c d inh mach c´ d o d`i ˆm khi wii < 0
˙˜a
˙
’
xuˆ a a u¯ a u o ee a ¯. o ¯ˆ a a
. .
du.a v`o ma trˆn d u.`.ng d i P.
a a ¯o ¯
. .
˙.
’
Thu tuc Floyd() sau minh hoa thuˆt to´n d a tr` b`y.
a a ¯˜ ınh a
. .
void Floyd()
{
byte i, j, k;
AdjPointer Tempt;
byte Pred[MAXVERTICES][MAXVERTICES];
int Weight[MAXVERTICES][MAXVERTICES], NewLabel;
byte Start, Terminal;
for (i = 1; i Length;
Tempt = Tempt->Next;
}
}
for (k = 1; k
- for (j = 1; j NewLabel)
{
Weight[i][j] = NewLabel;
Pred[i][j] = Pred[k][j];
}
}
if (Weight[i][i] < 0)
{
printf("Ton tai mach do dai am qua dinh %d", i);
printf(" %6d ", Weight[i][i]);
return;
}
}
}
// Vi du minh hoa
Start = 1;
Terminal = 3;
if (Weight[Start][Terminal] < +INFTY)
{
printf("Ton tai duong di tu %d", Start);
printf(" den %d", Terminal);
printf("\nDuong di qua cac dinh:");
i = Terminal;
while (i != Start)
{
printf("%3d ", i);
i = Pred[Start][i];
}
printf("%3d ", Start);
printf("\nTrong luong la %3d ", Weight[Start][Terminal]);
}
else
printf("\n Khong ton tai duong di tu %d den %d", Start, Terminal);
}
95
- 3.4 Ph´t hiˆn mach c´ d o d`i ˆm
a e o ¯ˆ a a
. . .
Vˆ n d` ph´t hiˆn c´c mach c´ d o d`i ˆm trong mˆt d` thi tˆ’ng qu´t l` quan trong khˆng
˙
´e
a ¯ˆ a ea o ¯ˆ a a o ¯o . o
.ˆ aa o
. . . .
.ng trong ch´ b`i to´n t` d u.`.ng d i ngˇn nhˆ t m` c`n l` mˆt bu.´.c co. ban trong
´ ´ ˙
’
nh˜
u ınh a a ım ¯ o ¯ a a ao a o o
.
nh˜.ng thuˆt to´n kh´c (xem Phˆn 3.4.1 v` [14]).
`
u a a a a a
.
Ta biˆt rˇ ng Thuˆt to´n Floyd t` d u.`.ng d i ngˇn nhˆ t gi˜.a c´c cˇp d ınh c´ thˆ’ ph´t ˙
´` ´ ´
a u a a ¯˙ ’
ea a a ım ¯ o ¯ a oea
. .
` thi. Ho.n n˜.a, nˆu d` thi ch´.a mˆt d ınh s m` c´ thˆ’ dˆn ˙´
´ ¯o . u ˙
’
hiˆn c´c mach d o d`i ˆm trong d o .
ea . ¯ˆ a a ¯ˆ u eˆ o¯ a o e ¯e
. . .
. d o, th` c´ thˆ’ ´p dung Thuˆt to´n Ford-Moore-Bellman (t` tˆ t ca
˙
´’ ´’
a ˙ a ¯˙ ’ ım a ˙
tˆ t ca c´c d ınh kh´c t` ¯´au ı o ea a a
. .
.`.ng d i ngˇn nhˆ t xuˆ t ph´t t`. d ınh s) dˆ’ ph´t hiˆn c´c mach c´ d o d`i ˆm nhu. d ˜
˙a
´ ´ ´ a u ¯˙ ’
c´c d u o
a¯ ¯ a a a ¯e ea o ¯ˆ a a ¯a
. . .
thu.c hiˆn trong Bu.´.c 3 cua phˆn n`y. Nˆu tˆn tai d ınh khˆng thˆ’ dˆn d u.o.c t`. s (chˇng˙´ ˙
’
` e ` . ¯˙
´o
˙
’ ’
e o aa o e ¯e ¯ . u a
. .
han, khi G l` d` thi vˆ hu.´.ng khˆng liˆn thˆng) th` Thuˆt to´n Ford-Moore-Bellman s˜ kˆt ´
a ¯o . o o
ˆ o e o ı a a ee
. .
˙ c´c d ınh c´ thˆ’ dˆn d u.o.c t`. s c´ nh˜n h˜.u han, c´c d ınh kh´c khˆng dˆn d u.o.c
˙ ¯e ¯ . u
´ ´¯.
’ a ¯˙ ’ ˙
’
th´c v` chı
ua oe oau a¯ a o ¯e
.
t`. s c´ nh˜n bˇ ng ∞. Trong tru.`.ng ho.p n`y c´ thˆ’ tˆn tai c´c mach c´ d o d`i ˆm trong
˙o
` a o e` . a
u oaa o o ¯ˆ a a
. . .
th`nh phˆn liˆn thˆng khˆng ch´.a s v` khˆng d u.o.c ph´t hiˆn. Tuy nhiˆn, nhiˆu u.ng dung
` `´
a ae o o u a o ¯. a e e e
. .
` n kiˆ’m tra c´ mach d ˆ d`i ˆm hay khˆng, d` thi d u.o.c x´t c´ d ınh s dˆn d u.o.c tˆ t ca c´c
˙ ´¯. a ˙a ´’
˙
’
cˆ
a e o . ¯o a a o ¯o . ¯ . e o ¯
ˆ ¯e
.
d ınh kh´c, v` do d o v´.i nh˜.ng tru.`.ng ho.p nhu. vˆy, dˆ’ x´c d .nh su. tˆn tai cua mach d o
˙ .` . ˙
¯˙’ ’
a a ¯´ o u o a ¯e a ¯i o ¯ˆ
. . . .
.n Thuˆt to´n
˙’
d`i ˆm, Thuˆt to´n Ford-Moore-Bellman s˜ cho ph´p t´ to´n hiˆu qua ho
aa a a e e ınh a e a a
. . .
Floyd.
C´c nguyˆn tˇc kˆt th´c cua Thuˆt to´n Ford-Moore-Bellman d u.o.c tr` b`y dˆ’ t´ ˙
´´ u˙ ’
a eae a a ¯. ınh a ¯e ınh
.
´t c´c d u.`.ng d i ngˇn nhˆ t t`. s khi khˆng c´ mach d o d`i ˆm. C´c nguyˆn tˇc
´ ´
´u
to´n ´ nhˆ a ¯ o
a ıt a ¯ a a o o. ¯ˆ a a a ea
.
.m ho.n nhu. sau.
n`y c´ thˆ’ cai biˆn dˆ’ ph´t hiˆn mach d ˆ d`i ˆm s´
˙ ’ e ¯e a ˙
a o e˙ e . ¯o a a o
. .
Sau khi g´n lai nh˜n cua d ınh vi t`. mˆt d ınh vj ∗ theo Phu.o.ng tr` 3.2 ta kiˆ’m tra ˙
˙ ¯˙
’ ’ u o ¯˙.’
a. a ınh e
.`.ng d i ngˇn nhˆ t hiˆn h`nh (m` c´ thˆ’ suy t`. c´c nh˜n hiˆn h`nh θ)
˙
´ ´ea
¯˙’
d ınh vi c´ thuˆc d u o
o o¯ ¯ a a ao e ua a ea
. . .
. s dˆn v ∗ hay khˆng. Nˆu d ung, th` d ınh v ∗ d ˜ d u.o.c g´n nh˜n thˆng qua v v` d iˆu
´ ´ i a ¯`
ı ¯˙’
t` ¯e j
u o e ¯´ j ¯a ¯ . a a o e
˜n dˆn Lk (vj ∗ ) + w(vj ∗ , vi ) < Lk (vi ); do d ´ mˆt phˆn cua d u.`.ng d i ngˇn nhˆ t hiˆn
´
´ ` ´e
˙ ¯o
’
n`y dˆ ¯e
aa ¯o o a ¯ a a
. .
h`nh t`. vi dˆn vj ∗ cˆng thˆm cung (vj ∗ , vi ) s˜ tao th`nh mach c´ d o d`i ˆm v` thuˆt to´n
´
a u ¯e o e e. a o ¯ˆ a a a a a
. . . .
kˆt th´c. Nˆu mˇt kh´c, nh˜n cua d ınh vi hoˇc khˆng thay d o’i bo.i Phu.o.ng tr` 3.2, hoˇc
˙’
´ ´ a ˙ ¯˙
’’ ¯ˆ ˙
e u e a a a o ınh a
. . .
nhˆn nh˜n m´.i t`. mˆt d ınh vj ∗ nhu.ng vi khˆng thuˆc d u.`.ng d i ngˇn nhˆ t t`. s dˆn vj ∗ , th`
´ ´ ´
o u o ¯˙ ’
a a o o ¯o ¯ a a u ¯e ı
. . .
.´.c 3 nhu. tru.´.c. Cˆn ch´ y rˇ ng, cai tiˆn trˆn ch´ l` giam nh˜.ng
u´ `
´ ` ’´
˙e ınh a ˙ ’
thuˆt to´n tiˆp tuc Bu o
a a e. o a a e u
.
. th`.a khˆng cˆn thiˆt trong Thuˆt to´n Ford-Moore-Bellman, do mˆt mach c´ d o d`i ˆm
` ´
du u o a e a a o o ¯ˆ a a
. . . .
d u.o.c x´c d .nh ngay khi n´ d u.o.c tao ra v` khˆng cˆn d o.i kˆt th´c thu tuc.
` ¯. e ´ ˙.
’
¯ . a ¯i o¯ . . ao a u
Mach tˆi u.u trong d` thi c´ hai trong lu.o.ng
´
3.4.1 o ¯ˆ . o
o
. . .
Mˆt vˆ n d` nay sinh trong nhiˆu l˜ vu.c liˆn quan dˆn mˆt d` thi c´ hu.´.ng m` mˆ i cung ˜
. ´ e’ ` ınh . e ´
o a ¯ˆ ˙ e ¯e o ¯ˆ . o o
.o ao
.o.c g´n hai trong lu.o.ng: w v` b . B`i to´n l` t` mˆt mach Φ m` cu.c tiˆ’u (hoˇc
˙
(vi , vj ) d u . a
¯ ij a ij a a a ım o a. e a
. . . . .
96
- cu.c d ai) h`m muc tiˆu
. ¯. a e
.
wij
(vi ,vj )∈Φ
z (Φ) := .
(vi ,vj )∈Φ bij
˙’ ınh ˙
’
Chˇng han, x´t h`nh tr` cua mˆt con t`u hay mˆt m´y bay trˆn mang giao thˆng
a ea o a o a e o
. . . .
. rˇ ng w l` “lo.i nhuˆn” v` b l` “th`.i gian” cˆn thiˆt dˆ’ di chuyˆ’n trˆn cung
˙ ˙
` ` ´ ¯e
a˙˙ ’’
v` gia su a ij a a a ij a o a e e e
. .
(vi , vj ). B`i to´n d at ra l` t` h`nh tr` dˆ’ tˆi d a lo.i nhuˆn v´.i th`.i gian nho nhˆ t.
˙´ ´
˙’a
a a ¯ˇ a ım a ınh ¯e o ¯ . ao o
. .
C´c vˆ n d` kh´c c´ thˆ’ ph´t biˆ’u dang b`i to´n t` c´c mach tˆi u.u trong d` thi
˙a ˙
´e ´
a a ¯ˆ a o e e a a ım a o ¯o .
ˆ
. .
.o.ng: Lˆp lich dˆ’ t´ to´n song song, tˆi u.u d a muc tiˆu trong xu. l´ cˆng
˙ ınh a ´ ˙yo
’
c´ hai trong lu .
o a . ¯e o ¯ e
. . .
nghiˆp.
e
.
B`i to´n t` mˆt mach Φ trong d` thi c´ hai trong lu.o.ng dˆ’ cu.c tiˆ’u h`m muc tiˆu
˙ ˙
a a ım o ¯o . o
ˆ ¯e . ea e
. . . . .
. thuˆt to´n ph´t hiˆn c´c mach c´ d o d`i ˆm nhu. sau. Gia su.
z (Φ) c´ thˆ’ giai quyˆt nh`
˙’ ´
oe˙ ˙˙
’’
e o a a a ea o ¯ˆ a a
. . . .
rˇ ng c´c trong lu.o.ng wij v` bij l` c´c sˆ thu.c tu` y (du.o.ng, ˆm hoˇc bˇ ng khˆng) nhu.ng
` a`
´
a a a aa o . y´ a .a o
. .
˙ m˜n r`ng buˆc (vi ,vj )∈Φ bij > 0, v´.i moi mach Φ trong G. (Trong hˆu hˆt c´c t`
` ´
’aa
thoa o o a e a ınh
. . .
.ng b ≥ 0 v´.i moi i v` j ).
˙
’
huˆng, chˇng han c´c vˆ n d` nˆu trˆn, wij ∈ R nhu
´ ´e
o a . a a ¯ˆ e e o a
.
ij
Ch´ng ta chon mˆt gi´ tri thu. z k d oi v´.i h`m muc tiˆu z (Φ) v` x´t d` thi c´ trong
´
a.˙ ’
u o ¯ˆ o a e a e ¯o . o .
ˆ
. . .
.o.ng
lu .
wij = wij − z k bij .
k
V´.i ma trˆn trong lu.o.ng wij m´.i, x´t b`i to´n d u.`.ng d i ngˇn nhˆ t trˆn G. C´ ba tru.`.ng
´ ´e
k
o a o e a a ¯o ¯ a a o o
. . .
.p xay ra:
˙
’
ho.
Tru.`.ng ho.p A. Tˆn tai mach c´ d o d`i ˆm Φ− sao cho
`.
o o o ¯ˆ a a
. . .
k
wij < 0.
)∈Φ−
(vi ,vj
Tru.`.ng ho.p B. Khˆng tˆn tai mach c´ d o d`i ˆm v`
`.
o o o o ¯ˆ a a a
. . .
k
wij > 0
(vi ,vj )∈Φ
v´.i moi mach Φ.
o . .
Tru.`.ng ho.p C. Tˆn tai mach c´ d o d`i bˇ ng khˆng (nhu.ng khˆng c´ mach d o d`i ˆm);
o ¯ˆ a `
`.
o o a o o o. ¯ˆ a a
. . . .
.c l`
t´ a
u
k
wij = 0
(vi ,vj )∈Φ0
v´.i mach Φ0 n`o d o.
o a ¯´
.
97
- Trong Tru.`.ng ho.p A ch´ng ta c´ thˆ’ n´i rˇ ng z ∗ (gi´ tri cu.c tiˆ’u cua z ) nho ho.n z k v`
˙ ˙˙
o eo` ’ ˙
’
o u a a.. e ı
.
k
wij − z k
wij ≡ bij < 0
)∈Φ− )∈Φ− )∈Φ−
(vi ,vj (vi ,vj (vi ,vj
chı c´ thˆ’ d ung nˆu
˙ ´
˙ o e ¯´
’ e
wij
(vi ,vj )∈Φ−1
< zk
−1 bij
(vi ,vj )∈Φ
m` hiˆ’n nhiˆn chı ra rˇ ng z ∗ < z k .
˙ `
˙
’
ae e a
Tu.o.ng tu., trong Tru.`.ng ho.p B ta c´ thˆ’ n´i rˇ ng z ∗ > z k ; v` trong Tru.`.ng ho.p C
˙
o eo`
o a a o
. . .
∗ k
th` z = z .
ı
Do d o thuˆt to´n t` kiˆm nhi phˆn dˆ’ giai quyˆt b`i to´n nhu. sau: Kho.i d` u v´.i
˙’
´ ´
. a ¯e ˙ ˙ ¯ˆ o
’a
¯´ a a ım e ea a
.
. z 1 ; nˆu n´ qu´ l´.n (t´.c l` Tru.`.ng ho.p A) thu. v´.i z 2 < z 1 ; nˆu n´ qu´ nho (t´.c
´ ´
a.˙ ’ ˙o
’ ˙u
’
gi´ tri thu e o ao ua o eoa
.
.`.ng ho.p B) thu. v´.i z 2 > z 1 . Khi d ˜ c´ c´c cˆn trˆn v` du.´.i (z v` z tu.o.ng u.ng) ta
˙o
’
l` Tru o
a ¯a o a a eao ual ´
. .
˙ x´c d .nh z ∗ bˇ ng c´ch thu. z k = (zu + zl )/2 v` thay zu bˇ ng z k nˆu xay ra Tru.`.ng
’ a ¯i ` ` ´˙
˙
’ ’
c´ thˆ
oe a a a a e o
ho.p A, hoˇc thay zl bˇ ng z k nˆu xay ra Tru.`.ng ho.p B. Do sˆ c´c ph´p thu. tı lˆ v´.i 1/η,
` ´˙ ´
’ ˙ ˙e o
’ ’.
a a e o oa e
. . .
1 l` sai sˆ cho tru.´.c, v` do mˆi lˆn thu. (x´c d .nh mach d ˆ d`i ˆm hoˇc
˜a
´ o` ˙ a ¯i
’
trong d o 0 < η
¯´ a o o a . ¯o a a a
. .
t´ to´n ma trˆn trong lu.o.ng) d oi hoi n3 ph´p to´n, nˆn t` nghiˆm cua b`i to´n trˆn d oi
¯` ˙ ’ ˙aa
’
ınh a a e a e ım e e ¯`
. . . .
hoi O[n3 log 1/η ] ph´p to´n.
˙
’ e a
98
- Chu.o.ng 4
ˆ
CAY
Mo. d` u
˙ ¯ˆ
’a
4.1
Cˆy l` mˆt trong nh˜.ng kh´i niˆm quan trong nhˆ t cua l´ thuyˆt d` thi, v` thu.`.ng xuˆ t
´’ ´ˆ ´
a˙y
aao u ae e ¯o . a o a
. . .
.ng l˜nh vu.c ´ c´ liˆn quan dˆn d` thi.
´ ¯ˆ .
hiˆn trong nh˜
e u a . ıt o e ¯e o
.
Trong chu.o.ng n`y, tru.´.c hˆt s˜ nghiˆn c´.u cˆy Huffman v` nh˜.ng u.ng dung cua n´
´ ˙o
’
a oee eua au´ .
. liˆu. Kˆ tiˆp ch´ng ta x´t tr` b`y c´c thuˆt to´n t` cˆy bao tr`m, cˆy
´´
trong viˆc n´n d˜ e
e e u. ee u e ınh a a a a ım a u a
. .
.o.ng nho nhˆ t khi c´c canh cua d` thi d u.o.c gˇn v´.i c´c chi ph´ (trong
´
´
˙
’a ˙ ¯ˆ . ¯ . a o a
’o
bao tr`m c´ trong lu .
u o. a. ı .
lu.o.ng). Cˆy bao tr`m nho nhˆ t cua d` thi c´ nhiˆu u.ng dung trong nh˜.ng tru.`.ng ho.p c´c
˙ a ˙ ¯ˆ . o ` ´
´’o
’
a u e u o .a
. .
.`.ng dˆ n (ˆng dˆ n ga, dˆy dˆ n trong mang d iˆn, v.v) d u.o.c su. dung dˆ’ nˆi n d iˆ’m v´.i
˙o ˙
˜o ˜ ˜
´ ´
˙.
’
du o
¯ a a aa ¯e ¯. ¯e ¯e o
. .
nhau theo c´ch tˆt nhˆ t: tˆ’ng khoang c´ch cua c´c d u.`.ng dˆ n l` nho nhˆ t. Nˆu n d iˆ’m
˙ ˙
˜
´ ´o ´ ´
˙’ ˙ a ¯o
’ ˙
’
a o a a aa a e ¯e
d u.o.c nˆi v´.i nhau trˆn mˆt mˇt phˇng, ta c´ thˆ’ biˆ’u diˆn bo.i mˆt d` thi d` y d u trong d o
˙˙
˙’ ˜
´ ˙
’ o ¯o . ¯ˆ ¯ ˙ ’
¯. o o e oa a oee e .ˆ a ¯´
. .
˙ ng c´ch gi˜.a hai d iˆ’m tu.o.ng u.ng. Khi d ´ cˆy bao tr`m v´.i trong
˙
’
c´c chi ph´ canh l` khoa
a ı. a a u ¯e ´ ¯o a u o .
lu.o.ng nho nhˆ t s˜ cho mang giao thˆng v´.i chi ph´ ´ nhˆ t. Nˆu c´ thˆ’ nˆi thˆm ngo`i n
˙´ e
´ ´ ´
˙
’ae o o ı ıt a e o eo a
. .
d iˆ’m cho ph´p, ta c´ thˆ’ thˆm ch´ xˆy du.ng d u.o.c mang v´.i ch´ ph´ re ho.n v` x´c d inh n´
˙ ˙. ı ı˙ ’
¯e e oea ıa ¯. o a a ¯. o
. .
ch´ l` giai quyˆt b`i to´n Steiner. B`i to´n sau n`y s˜ d u.o.c d` cˆp o. phˆn cuˆi chu.o.ng.
´ a e ¯ . ¯ˆ a ˙ ` ´
ınh a ˙ ’ e.’
eaa aa a o
Dinh ngh˜ 4.1.1 C´c d inh ngh˜ sau cua cˆy (vˆ hu.´.ng) l` tu.o.ng d u.o.ng:
-. ˙a
’
ıa a ¯. ıa oo a ¯
-ˆ . e
1. D` thi liˆn thˆng c´ n d ınh v` (n − 1) canh.
o ¯˙ ’
o o a .
-ˆ . e
2. D` thi liˆn thˆng khˆng c´ chu tr`
o o o o ınh.
3. D` thi m` moi cˇp d ınh d u.o.c nˆi v´.i nhau bo.i mˆt v` chı mˆt dˆy chuyˆn so. cˆ p.
- ˆ . a . a ¯˙ ¯ . o o ´ ` ´
’ ˙
’ oa˙oa ’.
o e a
. .
4. D` thi liˆn thˆng v` khi b´.t mˆt canh bˆ t k` th` mˆ t t´ liˆn thˆng.
-ˆ . e ´ ´
o o a o o. a y ı a ınh e o
.
99
- . a o ˙ ¯˙ ’ ’
H` 4.1 minh hoa cˆy c´ bay d ınh v` s´u canh.
ınh aa .
v2
• .
.
...
...
...
...
...
...
...
...
..
..
...
...
...
...
• v3
...
...
...
... .
...
...
...
.
... ...
...
...
... ...
...
..
...
... ...
... .
.
...
.
...
...
... ...
...
...
... ...
...
...
...
v1 • v4 • ..
..
.. ..
..
.... ...
..
.
..... ....
.
.. ..... . .....
.. ...... . ..
.. ...... .
. .....
.... . ..
.. .... .
.... ...
.
.. ...
.
....
.. .... ...
.
. ...
....
....
.. . ...
.. .
....
.... ...
.... .
.. ...
.... .
.. . ...
• v5
.....
• ...
.....
.. ..
.. .
.. .
..
..
v6
..
..
..
..
..
..
..
..
..
• v7
..
.
.
o ı.`a
H` 4.1: Mˆt v´ du vˆ cˆy.
ınh e
.
Kh´i niˆm vˆ cˆy nhu. mˆt thu.c thˆ’ cua to´n hoc d u.o.c d u.a ra lˆn d` u tiˆn bo.i
˙’
`a ` ¯ˆ
e˙ ˙
’
a e e o a . ¯. ¯ a a e
. . .
.i d inh ngh˜ c´c mach co. ban d u.o.c su. dung trong phˆn t´ c´c
˙ ¯. ˙ .
’ ’
Kirchhoff [37] khi liˆn hˆ v´ ¯.
e eo ıa a a ıch a
. .
˙
’
mang d iˆn. Khoang 10 nˇm sau d o, mˆt c´ch d oc lˆp, Cayley [11] d a ph´t hiˆn lai c´c cˆy
¯e a ¯´ o a ¯ˆ a ¯˜ a e.aa
. . . .. .
v` nh˜.ng t´ chˆ t cua n´ khi nghiˆn c´.u c´c t´ chˆ t ho´ hoc cua c´c chˆ t d` ng phˆn
´’o ´ ´ˆ
ıch a ˙ ˙a
’
au e u a ınh a a. a ¯o a
˙ a hydrocarbon.
’
cu
Cˆy c´ gˆc (c`n goi l` cˆy gia pha) d u.o.c d .nh ngh˜ tu.o.ng tu. nhu. sau:
´ o .aa ˙ ¯ . ¯i
’
a oo ıa .
Dinh ngh˜ 4.1.2 Cˆy c´ gˆc T l` d` thi c´ hu.´.ng khˆng mach m` moi d ınh, ngoai tr`.
-. ´ a . ¯˙ ’
ıa a oo a ¯o . o o
ˆ o u
. .
˙
’ ` ´’
o ¯˙’ ˙ ¯˙
’’ ao ˙ a
mˆt d ınh (chˇng han v1 ), c´ bˆc trong bˇ ng mˆt: bˆc trong cua d ınh v1 (goi l` gˆc cua cˆy)
a oa a o a
. . . . . .
bˇ ng khˆng; n´i c´ch kh´c, moi d ınh v ∈ T tˆn tai duy nhˆ t mˆt d u.`.ng d i t`. gˆc dˆn v.
` `. ´ o ¯o ´´
¯˙
’
a o oa a o a ¯ u o ¯e
. .
H` 4.2 minh hoa mˆt d` thi l` cˆy c´ gˆc v´.i d ınh v1 l` gˆc. T`. d .nh ngh˜ suy ra
´ ´
o ¯o . a a o o o ¯˙ ’
ınh .ˆ ao u ¯i ıa
.
.´.ng trˆn c´c
`
rˇ ng cˆy c´ gˆc n d ınh c´ (n − 1) cung v` l` d` thi liˆn thˆng (khi bo qua hu o
´ ¯˙’ ˙
’
a a oo o a a ¯ˆ . e
o o ea
cung).
Cˆn ch´ y rˇ ng, c´ thˆ’ d .nh hu.´.ng trˆn mˆt cˆy (vˆ hu.´.ng) sao cho d` thi thu d u.o.c
˙
`
`
a u´ a o e ¯i o e oa oo ¯o .
ˆ ¯.
.
.´.ng c´c
˙
’
´ ˙` ´
’a o ¯˙
.’
l` cˆy c´ gˆc: Ta chı cˆn chon mˆt d ınh tu` y, chˇng han v1 , l`m gˆc v` d .nh hu o
aa oo y´ a a o a ¯i a
. .
` n t`. v1 dˆn c´c d ınh treo. Ngu.o.c lai, nˆu bo qua c´c hu.´.ng trˆn cˆy
´ a ¯˙ ´
’ ˙
’
cung theo dˆy chuyˆ u
a e ¯e e a o ea
..
c´ gˆc ta thu d u.o.c mˆt cˆy.
´
oo ¯. oa
.
Cˆy gia pha m` trong d o mˆ i ngu.`.i d an ˆng biˆ’u thi mˆt d ınh v` c´c cung d u.o.c v˜
˙
˜
˙a
’ . o ¯˙
.’
a ¯´ o o ¯` o e aa ¯. e
. c´c cha dˆn c´c con cua ho l` mˆt v´ du quen thuˆc cua cˆy c´ gˆc, gˆc cua cˆy l` ngu.`.i
´ ´o˙aa
´’
˙
’ .a o ı . o ˙ a oo
’
t` a
u ¯e a o
. .
˙ x´c d .nh d u.o.c.
’ a ¯i
d` u tiˆn trong d`ng ho m` c´ thˆ
¯a
ˆ e o . ao e ¯.
100
- v1
• ....
....
... .....
... .....
...
... ...
...
...
... ...
...
.
.
...
... ...
...
...
... ...
...
.
. ....
... ...
.... ....
.. ....
....
... ..
..
.
... ...
... ...
. ...
... ...
... ...
. ...
...
... ...
...
.
...
...
v2 v3
...
...
.
...
... ...
...
.
...
... ...
...
.
• •
... ...
... ...
. .
........ ..
... ..... ... ...
... .....
.
... ... .....
... ...
...
... ... .
. .
.... ....
.... ....
...
... ...
. ...
.....
..
. ....
.. ... .
.... ..
...
... ...
...
... ...
...
. .
... ...
v6
... ...
...
... ...
...
. .
... ...
... ...
...
... ...
...
. .
... ...
• • • •
...
... ...
... ...
...
. .
.......
.
........
.
...
...
v4 v5 v7
...
...
.
....
.... ...
.
...
..
.. ....
.... ....
... ...
...
...
v8 ... ...
...
...
... ...
...
..
...
• • ...
... ...
.
....... .
........
..
...
...
v9
...
...
.
....
....
.. ...
...
.
.. ....
.... ...
.. ...
... ...
..
v10 ... ...
... ...
... ...
... ...
• •
... ...
... ...
.
.......
......
.
... ...
... ....
v11
.
.
...
.... ...
...
....
.... . ....
.... ..
. ...
. ...
...
... ...
...
...
... ...
...
...
...
• • ...
...
..
..
v12 v13
o ı.`a oo ´
H` 4.2: Mˆt v´ du vˆ cˆy c´ gˆc.
ınh e
.
4.2 Cˆy Huffman
a
´ ` o˙
.’
Tiˆn tr` g´n d˜y c´c bit cho c´c k´ hiˆu goi l` m˜ ho´. Trong phˆn n`y ch´ng ta mˆt ta
e ınh a a a a ye .aa a aa u
.
´t quen thuˆc-thuˆt to´n m˜ ho´ Huffman.
mˆt thuˆt to´n m˜ ho´ rˆ
o a a a aa o a a aa
. . . .
´
4.2.1 C´c bˆ m˜ “tˆt”
a oao
.
Khi ta n´i vˆ m˜ ho´ c´ ngh˜ l` g´n d˜y c´c bit cho c´c phˆn tu. cua mˆt bang ch˜. c´i.
o` a ao `
a˙˙ ’’ o˙ ’
e ıa a a a a a ua
.
˜i nhi phˆn goi l` bˆ m˜ v` c´c phˆn tu. cua ch´ng goi l` t`. m˜. Mˆt bang
` ˙˙
’’ o˙ ’
Tˆp c´c chuˆ
aa o .a .ao aaa a u . au a
. . .
. c´i l` mˆt tˆp ho.p c´c k´ hiˆu, goi l` c´c k´ tu.. Chˇng han, bang ch˜. c´i su. dung
˙
’ ˙
’ ua ˙ . ’
ch˜ a a o a
u aye .aa y. a
.. . . .
. thu.`.ng, 26 k´ tu. hoa, v` c´c dˆ u ngˇt cˆu ´
` eaa
a´ ´ ` ´
trong hˆu hˆt c´c s´ch (tiˆng Anh) gˆm 26 k´ tu
e o y. o y. aa a aa
. dˆ u phˆ’y). M˜ ASCII (viˆt tˇt cua c´c ch˜. c´i d` u tiˆn cua chuˆi American Standard
˙ ´´ ’ ˜
´ ea˙a u a ¯ˆ e ˙ ’
(nhu a a a a o
. A l` 01000001, cua k´ tu. a l` 01100001 v` k´
˙ y.
’ ˙ y.
’
Code for Information Interchange cua k´ tu a a ay
. , l` 0011010. Ch´ y rˇ ng trong m˜ ASCII sˆ c´c bit su. dung dˆ’ biˆ’u diˆn c´c k´ tu. l` ˙e ˙
` ˜ a y.a
´a ˙.
’
tu a u´ a a o ¯e e
.
bˇ ng nhau. M˜ nhu. vˆy goi l` m˜ c´ d ˆ d`i cˆ d. nh. Nˆu ta muˆn giam sˆ c´c bit d `i hoi
` ´ ´ ´ ´
˙
’ ¯o ˙ ’
a a a . a a o ¯o a o ¯i e o oa
. .
˙ biˆ’u diˆn c´c thˆng b´o kh´c nhau, ta cˆn c´c chuˆi bit biˆ’u diˆn k´ tu. c´ d o d`i (n´i
’e ˙ ˙
˜a ˜ ˜ y . o ¯ˆ a
`a
dˆ
¯e e o a a a o e e o
.
` ng nhau. Nˆu biˆ’u diˆn c´c bit d`i ho.n cho c´c k´ tu. thu.`.ng xuyˆn xuˆ t
˙ ˜a
´ ´
chung) khˆng bˇo a e e e a a y. o e a
hiˆn v` ngu.o.c lai, ch´ng ta c´ thˆ’, vˆ trung b`
˙e ınh, giam sˆ bit biˆ’u diˆn c´c k´ hiˆu. Chˇng
˙ ˜aye ˙
’
oe` ´
˙
’
ea u o e e a
. .. .
han, m˜ Morse [31] su. dung c´c t`. m˜ ngˇn ho.n cho c´c k´ tu. xuˆ t hiˆn thu.`.ng xuyˆn:
´ ´e
˙.
’
a auaa a y. a o e
. .
a˙ ’˙ ’ ˙
’ ˙
’
m˜ cua cua a l` ·−, cua e l` ·, trong khi cua z l` − − · · · · , q l` − − ·−, j l` · − − − .
a a a a a
Tuy nhiˆn d o d`i trung b` cua m˜ khˆng phai l` tiˆu chuˆ’n quan trong khi thiˆt kˆ
˙ ´´
ınh ˙
’ ˙ae
’
e ¯ˆ a ao a ee
. .
101
- mˆt bˆ m˜ “tˆt”. X´t v´ du sau. Gia su. bang ch˜. c´i gˆm bˆn k´ tu. a1 , a2 , a3 , a4 v´.i c´c
´ ua` ´
˙˙˙
’’’
ooao eı. o o y. oa
..
.o.ng u.ng l` P (a ) = 1 , P (a ) = 1 , P (a ) = 1 , P (a ) = 1 . Entropy cua
´ ´e ˙
’
x´c suˆ t xuˆ t hiˆn tu
a a a ´ a
. 1 2 3 4
2 4 8 8
m˜ nguˆn n`y l` 1.75 bit/k´ hiˆu (xem [31] dˆ’ c´ kh´i niˆm vˆ entropy). X´t c´c bˆ m˜
˙
` `
a oaa ye ¯e o a e e eaoa
. . .
` n n`y cho bo.i bang sau
˙˙
’’
trong nguˆ a
o
C´c k´ tu.
a y. M˜ C1
a M˜ C2
a M˜ C3
a M˜ C4
a
a1 1 1 1 1
a2 1 0 01 10
a3 0 11 001 100
a4 01 00 000 1000
-o a
Dˆ d`i trung b`
ınh 1.125 1.125 1.75 1.875
.
Dˆ d`i trung b` l cua mˆ i m˜ x´c d inh bo.i
-o a ˜
˙
’ ˙
’
ınh o a a ¯.
.
4
l= P (ai )n(ai ) (bit/k´ hiˆu),
ye .
i=1
trong d o n(ai ) l` sˆ c´c bit cua t`. m˜ ai .
´ ˙ua
’
¯´ aoa
Du.a trˆn d o d`i trung b` ´ ´ a` ˙o
’ ˙
’
e ¯ˆ a ınh, m˜ C1 l` tˆt nhˆ t. Tuy nhiˆn, c´c m˜ cˆn phai c´ kha
a ao a e a a
. .
.`.i nhˆn c´ thˆ’ hiˆ’u d u.o.c r˜ r`ng. Hiˆ’n nhiˆn m˜ C
˙˙ ˙
`
nˇng truyˆn thˆng tin sao cho ngu o
a e o a o e e ¯. oa e e a1
.
.o.c g´n l` 1 nˆn khi nhˆn d u.o.c
khˆng c´ t´ chˆ t n`y: V` ca hai k´ hiˆu a1 v` a2 d` u d u . a a
´ ı˙’
o o ınh a a ye a ¯ˆ ¯
e e a ¯.
. .
thˆng tin l` 1, ngu.`.i nhˆn khˆng thˆ’ phˆn biˆt d ´ l` k´ hiˆu a1 hay a2 . Ch´ng ta muˆn
˙a ´
o a o a o e e ¯o a y e u o
. . .
.o.c g´n duy nhˆ t mˆt t`. m˜.
˜ ´ oua
mˆi k´ hiˆu d u . a
oye¯ a
. .
M˜ C2 c´ c´c k´ tu. d u.o.c g´n c´c chuˆi bit kh´c nhau cho c´c k´ tu.. Tuy nhiˆn, gia
˜ ˙
’
a oa y .¯. a a o a a y. e
. m˜ ho´ d˜y a a a d u.o.c 011 v` gu.i d i chuˆi bit n`y. Ngu.`.i nhˆn chuˆ i 011 c´ mˆt sˆ
˜ ˜ .´
˙
’ a˙¯ ’
su a a a 2 1 1 ¯ . o a o a o ooo
.
- iˆu n`y c´ ngh˜ l` mˆt d˜y d u.o.c m˜ ho´ v´.i bˆ m˜ C2
c´ch giai m˜: a2 a1 a1 hoˇc a2 a3 . D `
˙
’a
a a eao ıa a o a ¯ . a ao o a
. . .
th` d˜y n`y c´ thˆ’ d u.o.c giai m˜ khˆng tr`ng v´.i thˆng b´o ban d` u. N´i chung, d ˆy khˆng
˙ ˙ao
’
ı a a o e¯ . u o o a ¯a
ˆ o ¯a o
˙ a ¯` ´ ´´ ´ ´
’ ˙
’
phai l` d iˆu ch´ng ta mong muˆn khi thiˆt kˆ c´c bˆ m˜. Ch´ng ta muˆn c´ t´ chˆ t giai
e u o e ea o a u o o ınh a
.
´t; t´.c l` moi d˜y c´c t`. m˜ chı c´ duy nhˆ t mˆt c´ch giai m˜. C´ thˆ’ ch´.ng
˙u
´oa
˙o
’ ˙
’a
m˜ duy nhˆ u a . a a u a
a a a oe
.
´
˙ a ınh a a
’
minh c´c m˜ C3 v` C4 thoa m˜n t´ chˆ t n`y.
a a a
Mˇc d` viˆc kiˆ’m tra t´ duy nhˆ t khi giai m˜ l` kh´, ta c´ thˆ’ ch´.ng minh t´
˙ ˙
´ ˙’
aue e ınh a aa o oeu ınh
. .
.a trˆn thuˆc t´ cua bˆ m˜: khˆng c´ t`. m˜ n`o trong m˜ C
´t n`y cho bˆ m˜ C3 du ˙oa
’
chˆ a
a oa e o ınh o ou aa a3
. . . .
l` “tiˆn tˆ” cua t`. m˜ kh´c. Bˆ m˜ nhu. vˆy goi l` m˜ tiˆn tˆ. Mˆt c´ch d o.n gian dˆ’ kiˆ’m
˙˙
a`o˙uaa
e´’ a .a a` o e´ ˙ ¯e e
’
oa oa¯
. . .
tra mˆt bˆ m˜ c´ phai l` tiˆn tˆ hay khˆng ta v˜ cˆy nhi phˆn (mˆi d ınh c´ bˆc ≤ 2) tu.o.ng
˜’
˙a` o e´
’ o ¯˙
o o ao o ea .a oa
.. .
u.ng v´.i bˆ m˜. Cˆy d u.o.c v˜ xuˆ t ph´t t`. mˆt n´t d o.n (n´t gˆc) v` mˆ i n´t trong c´ bˆc
˜
´ ´
´ o o a a¯. e a a u o u¯ uo aou oa
. . .
.n hoˇc bˇ ng hai. Mˆt trong hai nh´nh con tu.o.ng u.ng bit 1 v` nh´nh c`n lai
a`
˙
’
ngo`i nho ho
a a o a ´ aa o.
. .
102
- tu.o.ng u.ng bit 0. Dˆ’ thuˆt tiˆn, ta quy u.´.c nh´nh con bˆn phai tu.o.ng u.ng 0 v` nh´nh con
-e˙ ˙
’
´ ae o a e ´ aa
. .
.o.ng u.ng 1. Theo c´ch n`y, c´c cˆy nhi phˆn tu.o.ng u.ng c´c m˜ C , C v` C cho
bˆn tr´i tu
e a ´ a aaa a ´ a a2 3a4
.
trong H` 4.3. (Dˆ’ d o.n gian, ta s˜ khˆng v˜ c´c m˜i tˆn trong c´c cˆy nhi phˆn).
-e ¯
˙ ˙
’
ınh eo ea ue aa .a
•
...
...
...
...
1....................
.
.
...
..
...
...
• •...............
..
.
.. .
...... .
... .....
... .....
...
a1 ................0
1 0
...
...
... ...
...
...
... ...
...
.
.
...
... ...
... ...
...
...
... ...
... ...
...
.
... ...
... ... ...
• • • •
...
.. .
.. . ...
...
. .....
...... ......
... ... ...
...
... .....
... ..... ... .....
... .....
a1 a2 0...
...
1 0 1 ...
0
... ...
... ... ...
... ... ...
... .
... ...
... ... ... ...
... ... ...
...
. .
. .
... ...
... ... ... ...
... ... ...
...
... ...
... ... ... ...
... ... ...
... .
.
... ...
... ...
... ... ...
... ...
...
• • • • •
... ...
. ...
... .. ..
... ...
...
... ....
... .. ...
...
. ...
...
... ... .....
... .. ..... ...
...
1 a1 a2 0 a2 a3 0 ...
...
.
... ...
1 0
... ... ...
... ... ...
... ...
. .
... ...
... ... ...
... ... ...
... ...
.
. .
... ... ...
... ... ...
... ...
... ...
.
... ...
... ... ...
... ...
... ... ...
. ...
. ... ...
... ...
... ... ...
...
...
• • • • • ...
... ... ...
...
... ...
... ..
..
a3 a4 a3 a4 a4
M˜ C2
a M˜ C3
a M˜ C4
a
H` 4.3:
ınh
u´ ` `
´
Ch´ y rˇ ng ngo`i n´t gˆc, cˆy nhi phˆn c´ hai loai n´t: c´c n´t l´ c´ bˆc ngo`i bˇ ng
a auo a .ao .u a uaoa aa
.
. m˜ chı tu.o.ng
o a` o a u
e´
khˆng; v` c´c n´t trong c´ bˆc ngo`i kh´c khˆng. Trong bˆ m˜ tiˆn tˆ, c´c t` a ˙ ’
o aa u oa a a o
. .
.ng c´c n´t l´. M˜ C khˆng phai l` m˜ tiˆn tˆ do tˆn tai t`. m˜ tu.o.ng u.ng n´t trong.
˙a a` o ´ `
’
u
´ a ua a4 o e o.ua ´ u
Duyˆt cˆy t`. gˆc dˆn c´c n´t l´ cho ta biˆ’u diˆn chuˆi bit tu.o.ng u.ng k´ hiˆu. Mˆ i nh´nh
˙ ˜ ˜ ˜
´´
e a u o ¯e a u a e e o ´ ye o a
. .
. m˜ cua n´: bit 1 cho nh´nh tr´i v` bit 0 cho nh´nh phai.
d ong g´p mˆt bit v`o t` a ˙ o ’ ˙
’
¯´ o o au a aa a
.
M˜ tiˆn tˆ luˆn luˆn d u.o.c giai m˜ duy nhˆ t nhu.ng ngu.o.c lai khˆng d ung (chˇng han
˙
’
a` o o
e´ ´
˙a
’
o¯. a o ¯´ a
.. .
.ng minh rˇ ng bˆ m˜ c´ thˆ’ giai m˜ duy nhˆ t tu.o.ng d u.o.ng
m˜ C4 ). Tuy nhiˆn c´ thˆ’ ch´
˙ ˙’
` ´
o ao e ˙
a eoeu a a a ¯
.
v´.i m˜ tiˆn tˆ theo ngh˜ sˆ trung b` c´c bit biˆ’u diˆn c´c k´ hiˆu bˇ ng nhau.
˙ ˜aye`
o a` o e´ ´
ıa: o ınh a e e .a
4.2.2 M˜ Huffman
a
M˜ Huffman l` m˜ tiˆn tˆ v` tˆi u.u v´.i c´c x´c xuˆ t cho tru.´.c. Phu.o.ng ph´p xˆy du.ng
a a` oaoe´ ´ ´
a oaa a o aa .
m˜ Huffman du.a trˆn hai quan s´t sau:
a e a
.
1. Trong mˆt bˆ m˜ tˆt u.u, c´c k´ hiˆu xuˆ t hiˆn thu.`.ng xuyˆn (c´ x´c suˆ t hay tˆn sˆ
´ ´e ´ `o
a´
o o ao aye a o e oa a
.. . .
´t hiˆn l´.n) s˜ c´ c´c t`. m˜ ngˇn ho.n c´c k´ hiˆu ´ xuˆ t hiˆn.
´ ´e
xuˆ
a eo eoa u a a a y e ıt a
. . .
2. Trong mˆt bˆ m˜ tˆt u.u, hai k´ hiˆu xuˆ t hiˆn ´ nhˆ t s˜ c´ c´c t`. m˜ c`ng d o d`i.
´ ´ e ıt a e o a u a u ¯ˆ a
´
o o ao ye a
.. . . .
Dˆ’ xˆy du.ng m˜ Huffman, ch´ng ta c´ thˆ’ biˆ’u diˆn qua cˆy nhi phˆn m` c´c n´t l´
-e a
˙ ˙˙ ˜
a u oee e a .a aa ua
.
.o.ng u.ng c´c k´ hiˆu. Duyˆt cˆy nhi phˆn s˜ cho ta c´c t`. m˜ cua bˆ m˜: xuˆ t ph´t t`.
´
aua˙ oa ’
tu ´ aye ea .ae a au
. . .
103
- nut gˆc v` d i dˆn c´c n´t l´, thˆm bit 1 v`o t`. m˜ mˆi lˆn qua nh´nh tr´i v` bit 0 mˆ i lˆn
˜a ˜a
´ ´ a u a o` o`
´ o a ¯ ¯e a u a e a aa
.i cˆy trong H` 4.4, ta c´ biˆ’u diˆn c´c k´ tu. qua c´c t`. m˜ nhu. sau:
˙ ˜ a y.
˙
’
qua nh´nh phai. V´ a
a o ınh oe e aua
K´ tu.
y. M˜ ho´
aa
A 1
O 00
R 010
S 0110
T 0111
•
.....
......
... .....
... .....
1................... 0
...
...
...
...
...
...
.
. . ...
... ...
... ...
. ...
...
...
• • ...
..
..
.
.....
......
... ....
... ....
1 0
...
...
A ...
...
.
...
... ...
...
.
. ...
... ...
... ...
... ...
... ...
. ...
...
...
• • ...
...
.
....
.....
.
..
.
... ...
... ....
.
1 0
...
...
O
...
...
..
.. ...
...
...
... ...
...
...
... ...
...
...
... ...
...
...
...
• • ...
...
.
....
.....
..
.
.
... ...
... ....
.
...
1 0
...
R
...
...
..
.. ...
...
...
... ...
...
...
... ...
...
...
... ...
...
...
...
• •
...
...
...
.. .
T S
H` 4.4:
ınh
Dˆ’ giai m˜ mˆt chuˆi bit, ch´ng ta bˇt d` u t`. gˆc v` di chuyˆ’n doc theo cˆy cho dˆn
-e ˙ a o
˙’ ˙.
˜ ´ˆ ´ ´
o u a ¯a u o a e a ¯e
.
.: d i theo nh´nh tr´i nˆu d ´ l` bit 1, ngu.o.c lai d i theo nh´nh phai. Chˇng ˙
’
´ ˙
’
khi gˇp k´ tu ¯
a y. a a e ¯o a . .¯ a a
.
˜
han, chuˆi bit
o
.
01010111
.o.ng u.ng t`. RAT. V´.i mˆt cˆy x´c d inh m˜ Huffman nhu. H` 4.4, chuˆi bit bˆ t k` d u.o.c
˜ ´
tu ´ u o o a a ¯. a ınh o a y¯ .
.
. tu.o.ng u.ng v´.i nh˜.ng chuˆi bit c´ d ˆ d`i thay d o’i.
˙
˜
´ a ua y.
˙’a
giai m˜ duy nhˆ t mˇc d` c´c k´ tu
a ´ o u o o ¯o a ¯ˆ
. .
Huffman d a chı ra thuˆt to´n xˆy du.ng m˜ Huffman t`. bang c´c tˆn sˆ xuˆ t hiˆn cua
a` o a
a´´e˙
¯˜ ˙ ’ u˙ ’ ’
a aa a
. . .
. nhu. sau:
c´c k´ tu
a y.
Thuˆt to´n xˆy du.ng m˜ Huffman
a a a a
. .
X´t chuˆ i cˆn m˜ ho´ s t`. n k´ tu. v´.i n ≥ 2.
˜a
o`
e aau y.o
1. Xˆy du.ng d˜y tˆn sˆ fi , i = 1, 2, . . . , n, xuˆ t hiˆn cua c´c k´ tu. trong chuˆi s.
˜
a`o a´ ´ e ˙ a y.’
a a o
. .
104
- 2. Nˆu n = 2 (gia su. f1 ≤ f2 ), xuˆ t cˆy nhu. trong H` 4.5 v` d`.ng.
´ ´
˙˙
’’
e aa ınh au
• .
..
... ...
... .....
... .....
... ...
...
... ...
...
...
... ...
1 0
...
.
.
...
... ...
...
...
... ...
...
.
... ...
... ...
. ...
...
... ...
...
.
... ...
... ...
...
.
...
... ...
...
.
• •
...
... ..
..
f1 f2
H` 4.5:
ınh
3. Gia su. f v` f l` hai tˆn sˆ nho nhˆ t v` f ≤ f . Tao mˆt danh s´ch tˆn sˆ m´.i bˇ ng
`oo`
`o
a´˙aa ´ a´
˙˙
’’ ’
a a o a a
. .
.i f + f . Goi thuˆt to´n n`y su. dung danh s´ch tˆn sˆ m´.i dˆ’ tao
˙
` o o ¯e .
a´
˙
’ aa˙. ’
c´ch thay f v` f bo
a a a a
. .
cˆy T . Thay d ınh d u.o.c g´n nh˜n f + f dˆ’ nhˆn d u.o.c cˆy T trong H` 4.6. Xuˆ t T.
˙. ´
¯˙ ¯ . a
’
a a ¯e a ¯ . a ınh a
• ..
..
... .....
... .....
...
... ...
...
...
... ...
...
...
... ...
1 0
...
.
.
...
... ...
...
...
... ...
...
.
... ...
... ...
. ...
... ...
... ...
. ...
...
... ...
...
.
...
... ...
...
• •
.
...
... ..
.
f f
H` 4.6:
ınh
`o
a´
˙
’
V´ du 4.2.1 Cho bang tˆn sˆ
ı.
K´ tu. `o
a´
y. tˆn sˆ
A 2
B 3
C 7
D 8
E 12
Khi d o cˆy Huffman tu.o.ng u.ng cho trong H` 4.7.
¯´ a ´ ınh
4.3 Cˆy bao tr` m
a u
Ch´ng ta d a nghiˆn c´.u riˆng biˆt c´c t´ chˆ t cua mˆt cˆy, trong muc n`y ch´ng ta s˜
´’
e a ınh a ˙
u ¯˜ eu e oa .a u e
. .
.u cˆy khi gˇn n´ nhu. mˆt d` thi con cua mˆt d` thi kh´c. Ch´ng ta biˆt rˇ ng
´ e`
´a
˙
’
nghiˆn c´ a
eu ao o ¯o .
ˆ o ¯o . a
ˆ u
. .
cho d` thi c´ m canh, c´ thˆ’ xˆy du.ng d u.o.c 2m d` thi con kh´c nhau; r˜ r`ng l` trong sˆ
˙ ´
¯ˆ . o
o o ea ¯. ¯o .
ˆ a oa a o
. .
105
- • ....
....
.. ....
.. ....
...
... ...
...
...
... ...
...
...
... ...
...
.
...
... ...
...
.
... ...
... ...
1 0
. ...
... ...
... ...
. ...
...
... ...
...
.
...
... ...
...
.
...
... ...
...
.
...
... ...
...
.
... ...
... ...
...
. ...
...
... ...
...
.
...
...
• • ..
..
.
.
....... .
...... ......
... ...
.
... ...
... .... ... .....
... .....
.
1 0 1 0
... ...
... ...
...
... ...
...
. .
... ...
... ...
...
... ...
...
.
. .
. ... ...
... ... ... ...
... ...
... ...
... ... ... ...
... ...
...
. .
... ...
... ... ...
... ...
• • • •
...
.. ..
. .. ..
..... .
......
.
.
.
... ...
... ....
.
1 0
...
7 8 12
... ...
...
.
...
... ...
...
..
. ...
...
...
... ...
...
...
... ...
C D E
...
...
...
• •
...
..
..
..
2 3
A B
H` 4.7:
ınh
d o c´ mˆt v`i d` thi con l` mˆt cˆy. Ch´ng ta quan tˆm dˆn mˆt loai cˆy d ac biˆt: “cˆy
´
¯´ o o a ¯ˆ . o aoa u a ¯e o . a ¯ˇ e a
. . . . .
` n d` u tiˆn d u.o.c su. dung v` ph´t triˆ’n l´ thuyˆt vˆ
˙y ´`
˙.
’
bao tr`m”. Kh´i niˆm cˆy bao tr`m lˆ ¯a
u ae a uaˆ e¯. aa e ee
.
cˆy bo.i nh` vˆt l´ ngu.`.i Du.c Kirchoff nˇm 1847. Kirchoff d a su. dung cˆy bao tr`m nhˇ m
o -´ `
˙
’ ¯˜ ˙ .
’
a aay a a u a
.
.o.ng tr` tuyˆn t´ dˆ’ x´c d inh cu.`.ng d o d`ng d iˆn trong mˆ i nh´nh v`
˙ a ¯. ˜
´
˙ ea
’.
giai hˆ c´c phu ınh e ınh ¯e o ¯ˆ o ¯ e o a a
. .
˙ a mˆt mang d iˆn.
’
xung quanh mach cu o ¯e
. . . .
-ˆ .
V´ du 4.3.1 D` thi trong H` 4.8(a) c´ cˆy bao tr`m trong H` 4.8(b).
ı. o ınh oa u ınh
e e
b b
• • • •
................................................
............................................
. ...
. ...............................................
............................................
...... ...
..
... .... ...
.
... .... ... . ...
.. .
... ... . ...
... ... . ...
.
...
...
... ... ...
... ... ...
.
...
... .
.
... ... ...
...
... ... ...
.
... .
.
... ... ...
...
... ... ...
.
... .
.
...
... ... ...
...
... ... ...
.
.
.
...
... ... ...
...
... ... . ...
.
.
...
...
... . ...
.
... ... ...
... .... .
.
... ..
... ...
.
... ..
.
.
... .. .
...
a• •c a• •c
..
............................................... ...
................................................ .
.
...
..
. .. ...............................................
...............................................
..
.
.
...
... .
... ....
. ... ...
. ...
...
.
... ...
...
... .
... ... ...
... . ...
...
... ...
.
...
... .
... ... ...
... ...
. ...
... ...
.
...
... ... .
... ...
... ...
...
.
... ...
... .
... ...
... ...
.
... ...
...
.
... ...
... .
... ... ...
... ... . ...
...
... ...
.
... .
...
... ...
...
... ...
. ...
... ...
.
... ... .
... ...
... ...
... ...
.
... ...
... ... .
... . ...
... .... ...
...
... .
... ...
... .
... . ...
...
...
... ... ...
.
... ... ...
• • • •
... ...
..
..
.............................................. ..
..............................................
.
f f
d d
(a) (b)
H` 4.8:
ınh
Dinh ngh˜ 4.3.2 Cˆy T d u.o.c goi l` cˆy bao tr`m cua d` thi liˆn thˆng G nˆu T l` d`
-. ´
˙ ¯o . e
’ˆ
ıa a ¯. .aa u o e a ¯o
ˆ
.a tˆ t ca c´c d ınh cua G.
u´’
thi con cua G v` T ch´ a ˙ a ¯˙
˙
’ ’ ˙
’
a
.
-. -ˆ .
Dinh l´ 4.3.3 D` thi G = (V, E ) c´ d` thi bˆ phˆn l` mˆt cˆy nˆu v` chı’ nˆu G liˆn
´ ´
o ¯ˆ . o a a o a e a ˙ e
y o o e
. . .
.´.c mˆt d` thi liˆn thˆng v` c´ n d ı’nh, bao gi`. ta c˜ng c´ thˆ’ ˙
a o ¯˙
thˆng. N´i c´ch kh´c, cho tru o
o oa a o ¯ˆ . e
o o o u oe
.
˙ d u.o.c mˆt cˆy ch´.a tˆ t ca c´c d ı’nh cu a G (cˆy c´ n d ı’nh).
’¯ .
.´ ´’
˙¯ o o .
’ ˙
’ u a ˙ a ¯˙ ˙
’ a o ¯˙
bo d i mˆt sˆ canh cu a G dˆ
¯e oa
.
106
- Ch´.ng minh. Diˆu kiˆn cˆn. Nˆu G liˆn thˆng th` ta thu. t` xem c´ canh n`o m` khi x´a
-` e` ´ ˙ ım
’
u e .a e e o ı o. a a o
d i khˆng l`m cho d` thi mˆ t t´ liˆn thˆng khˆng. Nˆu khˆng c´ mˆt canh n`o nhu. vˆy
´ ´
¯ o a ¯ˆ . a ınh e
o o o e o oo. a a
. .
th` G l` mˆt cˆy; nˆu c´ mˆt canh nhu. vˆy th` x´a n´ d i, v` ta lai d i t` mˆt canh m´.i dˆ’ ˙
´
ı aoa eoo. a ı o o¯ a ¯ ım o . o ¯e
. . . . .
.i khi khˆng thˆ’ x´a mˆt canh n`o d u.o.c n˜.a th` ta c´ mˆt cˆy m` tˆp ho.p c´c
˙o
x´a... Cho t´
o o o e o. a¯. u ı ooa aa .a
. . .
`
¯˙’ ˙ o ¯´
’
d ınh cua n´ d ung bˇ ng V.
a
Diˆu kiˆn d u. Gia su. a, b l` hai d ınh trong G v` do d o thuˆc cˆy bao tr`m T cua G. Khi
-` e ¯˙ ’ ˙˙
’’ ¯˙’ ˙
’
e a a ¯´ oa u
. .
d o tˆn tai dˆy chuyˆn µ trong T t`. a dˆn b. Suy ra µ c˜ng thuˆc G. Vˆy G liˆn thˆng.
¯´ ` . a ` ´
o e u ¯e u o a e o
. .
Ch´ng ta s˜ su. dung thuˆt to´n t` kiˆm theo chiˆu rˆng dˆ’ xˆy du.ng cˆy bao tr`m
˙
´ ` o ¯e a
e˙ .
’
u a a ım e e. a u
. .
cua d` thi liˆn thˆng.
˙ ¯ˆ . e
’o o
´ `
4.3.1 Thuˆt to´n t` kiˆm theo chiˆu rˆng x´c d .nh cˆy bao tr` m
a a ım e eo a ¯i a u
. .
Trong thuˆt to´n n`y, S k´ hiˆu l` mˆt d˜y.
a aa yeaoa
. . .
Nhˆp: D` thi liˆn thˆng G := (V, E ) v´.i c´c d ınh d u.o.c d ´nh sˆ th´. tu.
a -ˆ . e ´
o a ¯ ˙ ¯ . ¯a
’
o o o u.
.
v1 , v 2 , . . . , v n .
´
Xuˆ t: Cˆy bao tr`m T.
a a u
1. [Kho.i tao] Dˇt S := [v1 ] v` T l` d` thi gˆm d ınh v1 v` khˆng c´ canh. K´ hiˆu v1 l`
˙ . -a a ¯ˆ . ` ¯˙
’ ’
a o o ao o. ye a
. .
´c.
¯˙’
d ınh gˆ
o
2. [Thˆm canh] V´.i mˆ i x ∈ S, theo th´. tu., thˆm canh (x, y ) ∈ E v` d ınh y (theo th´.
˜ a ¯˙’
e o o u. e u
. .
.) v`o T nˆu T ∪ (x, y ) khˆng tao th`nh chu tr` ınh. Nˆu khˆng c´ canh nhu. vˆy,
´ ´
tu a e o a e o o. a
. . .
d`.ng. T l` cˆy bao tr`m.
u aa u
3. [Cˆp nhˆt S ] Thay S bo.i con (trong T ) cua S theo th´. tu.. Chuyˆ’n sang Bu.´.c 2.
˙
˙
’ ˙
’
a a u. e o
. .
- e ım a
Dˆ’ t` cˆy bao tr`m cua d` thi liˆn thˆng ta c`n c´ thˆ’ d`ng thuˆt to´n t` kiˆm
˙ ˙ ´
˙ ¯o . e
’
u ˆ o o o eu a a ım e
.
. sau:
` u sˆu (c`n goi l` quay lui) nhu
theo chiˆ a
e o .a
´ `
4.3.2 Thuˆt to´n t` kiˆm theo chiˆu sˆu x´c d .nh cˆy bao tr` m
a a ım e ea a ¯i a u
.
Nhˆp: D` thi liˆn thˆng G := (V, E ) v´.i c´c d ınh d u.o.c d ´nh sˆ th´. tu.
a -ˆ . e ´
o a ¯ ˙ ¯ . ¯a
’
o o o u.
.
v1 , v 2 , . . . , v n .
´
Xuˆ t: Cˆy bao tr`m T.
a a u
107
- 1. [Kho.i tao] Dˇt w := v1 v` T l` d` thi gˆm d ınh v1 v` khˆng c´ canh. K´ hiˆu v1 l`
˙ . -a a ¯ˆ . ` ¯˙
’ ’
a o o ao o. ye a
. .
´
¯˙’
d ınh gˆc.
o
2. [Thˆm canh] Chon canh (w, vk ) v´.i chı sˆ k nho nhˆ t sao cho viˆc thˆm canh n`y v`o
’´ ´
˙o ˙a
’
e o e e aa
. . . . .
˙n sang Bu.´.c 3. Ngu.o.c lai, thˆm
’
´ `.
T khˆng tao ra chu tr`
o ınh. Nˆu khˆng tˆn tai, chuyˆ
e o o e o e
. ..
canh (w, vk ) v` d ınh vk v`o T ; d at w := vk v` chuyˆ’n sang Bu.´.c 2.
˙
a ¯˙’ a ¯ˇ a e o
. .
3. [Kˆt th´c?] Nˆu w = v1 , thuˆt to´n d`.ng, T l` cˆy bao tr`m.
´ ´
e u e a au aa u
.
4. [Quay lui] Dˇt x l` cha cua w (trong T ); g´n w := x v` chuyˆ’n sang Bu.´.c 2.
-a ˙
˙
’
a a a e o
.
V´ du 4.3.4 D` thi trong H` 4.9(a) c´ c´c cˆy bao tr`m, H` 4.9(b) v` 4.9(c), d u.o.c
-ˆ .
ı. o ınh oa a u ınh a ¯.
.ng theo c´c thuˆt to´n t` kiˆm theo chiˆu rˆng v` chiˆu sˆu tu.o.ng u.ng.
´ `o a`a
xˆy du
a a a a ım e e. e ´
. .
a a a
• • •
....
... ....
... ..
.
... .... ... .... ...
... .... ... .... ...
... ... ...
... ... ...
... ...
... ...
... ... ...
... ...
... ... ...
... ...
... ... ...
... ... ... ... ...
... ...
... ... ...
... ...
... ... ...
... ...
... ... ... ... ...
... ... ... ... ..
•c •c •c
b• b• b• ...............................
. .. . ... ................................
.................................... .. ...
..
..................................... ..
...
.. ..... ..
.
....
.. ....
. .
. .....
.... .. .... . .... .. ...
. .
... . ... ... . ... ...
.
.. . .. . ..
. . . ..
... . ... ... . ..... ... . ... ...
... . .... ... . ..... ... . .... ...
. . ..
. ..
. . .
. ...
... . ... . ... . ...
... . ... . ... . ...
. . ....
... ...
... ... ...
...
... ... ... ... ...
. . .
... ... ... ...
.
... ...
. . .
... ... ... ...
. ...
. . .
. ...
... ... ... ...
. . .
... ... ... ...
.
... ...
... ...
... ...
. . .
. ...
. . .
. ...
... ... ... ... ...
. . .
... ... ... ... ... ...
.
. . .
... ... ...
...
.
. . .
d• • •f d• • •f d• • •f
...
.
. . .
... ... ...
....
.... ..
... .. ...
. . . .
.. .. ..
. .
.. . . . . ... ..
.... . ... .
. . . .
.. . .
... ... ... ... ...
. . .
.
... ... ..... ... ... ...
. . .
. ...
... ...
. . . .
... ... ... ...
. . .
...
e e e
.
... ... ... ...
. . . ...
.
...
... ...
...
. . . .
... ... ... ... ...
. . .
... ... ... ...
. ...
. . .
... ... . ...
...
. . . .
...
... . .... ... . .... ... ...
. . .
. ... . .... ... ...
. ...
... . .... . . ...
. . .. ...
. . . ..
... ...
.
... . .. ... . ..
... . ... ...
... . ... . .
... ....
... ....
. . ..
....... . .
... . ... . . .. ...
.
... . ..
. . .
.....................................
..................................... . .
• • • • • •
... ............................... .....
.. . .
. ................................
. .
....
. ... . . ..
...
...
...
... ...
. ... ..
...
... .
...
... ...
... ...
j j j
...
i i i
...
...
...
... ...
... ...
...
...
...
...
... ...
... ...
...
...
...
...
... ...
... ...
...
...
...
...
... .... ...
... .... ... ...
...
• • • ...
...
...
..
....
...
k k k
(a) (b) (c)
H` 4.9: (a) D` thi G. (b) Cˆy bao tr`m sinh bo.i thuˆt to´n t` kiˆm theo chiˆu rˆng. (c)
-ˆ . ´ `o
˙
’
ınh o a u a a ım e e.
.
.i thuˆt to´n t` kiˆm theo chiˆu sˆu.
´ `a
˙
’
Cˆy bao tr`m sinh bo
a u a a ım e e
.
T` cˆy bao tr` m du.a trˆn hai ma ng tuyˆn t´
´
˙
’
4.3.3 ım a u e e ınh
.
- e a ¯a a
Dˆ’ c`i d ˇt c´c thuˆt to´n t` kiˆm theo chiˆu rˆng v` chiˆu sˆu trˆn d` thi liˆn thˆng G
˙ ´ `o a`a
a a ım e e. e e ¯o . e
ˆ o
. .
. liˆu ma trˆn kˆ hay cai biˆn, mang c´c danh
t` cˆy bao tr`m T ta c´ thˆ’ d`ng cˆ u tr´c d˜ e
˙ ´ a` ˙e
’ ˙
’
ım a u o eu a u u. .e a
` Vout []. Tuy nhiˆn, trong tru.`.ng ho.p d` thi d u.o.c biˆ’u diˆn bo.i hai mang tuyˆn t´
˙ ˜ ´
˙
’ ˙
’
s´ch kˆ
a e e o . ¯o . ¯ .
ˆ e e e ınh
.n. Ngo`i ra, phu.o.ng ph´p sau n`y c˜ng cho ta
´. ˙
’
α v` β th` c´ch tiˆp cˆn sau s˜ hiˆu qua ho
a ıa ea ee a a au
.
.ng” (tˆp c´c cˆy bao tr`m) ch´.a (n − p) canh trong tru.`.ng ho.p d` thi c´ p > 1
mˆt “r`
o u aaa u u o . ¯o . o
ˆ
. . .
` n liˆn thˆng. Hiˆ’n nhiˆn, v´.i nh˜.ng thuˆt to´n xˆy du.ng cˆy bao tr`m ta c´ thˆ’
˙ ˙
th`nh phˆ e
a a o e e o u a aa a u oe
. .
kiˆ’m tra d` thi c´ liˆn thˆng hay khˆng, v` nˆu n´ khˆng liˆn thˆng th` c´ thˆ’ x´c d .nh c´c
˙ ˙
´
e ¯o . o e
ˆ o o ae o o e o ı o e a ¯i a
` n liˆn thˆng. Nˆu mˇt kh´c, d` thi c´ trong sˆ th` ch´ng ta c´ thˆ’ t` cˆy bao ˙ ım a
´ ´ıu
th`nh phˆ e
a a o e a a ¯o . o .
ˆ o oe
.
tr`m c´ tˆ’ng trong lu.o.ng nho nhˆ t (xem Phˆn 4.4). Ho.n n˜.a ch´ng ta c˜ng c´ thˆ’ xˆy
˙ ˙
´ `
˙
’
u oo a a u u u o ea
. .
.ng hˆ c´c chu tr` d oc lˆp du.a trˆn cˆy bao tr`m cua d` thi nhu. trong Phˆn 4.3.4. `
˙ ¯o .
’ˆ
du ea ınh ¯ˆ a ea u a
. . .. .
108
nguon tai.lieu . vn
