Bài giảng Toán rời rạc - Phạm Tiến Sơn

˙ˇ’ng caˆ´u), moˆ˜i caˆy co´ sa´u d¯ı˙’nh. Ve˜ ca´c
caˆy na`y.
5. (a) Ve˜ hai caˆy butane C4H10 kha´c nhau.
(b) Co´ bao nhieˆu chaˆ´t d¯o`ˆng phaˆn cu˙’a hydrocarbon ba˙’o hoa` C6H14?
6. Chu´.ng minh ra`ˇng soˆ´ ca´c caˆy co´ goˆ´c d¯u.o.. c ga´n nha˜n n d¯ı˙’nh kha´c nhau la` n
n−1. Ve˜ taˆ´t
ca˙’ ca´c caˆy co´ goˆ´c d¯u.o.. c ga´n nha˜n trong tru
.`o.ng ho.. p n = 1, 2 va` 3.
207
7. Vo´.i moˆ˜i caˆy sau, xa´c d¯i.nh ca´c vector trong chu´
.ng minh cu˙’a D- i.nh ly´ Caylay.
.....................................
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
....
.........................................................................
............................................................................. .....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
.....
...
v1
v2
v3
v4v5
v6
v7
• •
•
•
•
•
• .......................
.........
.........
.........
.........
.........
.........
................................................................................................................................................
............
............
............
............
............
............
..........
............
............
.......
....
....
....
....
....
....
....
..............................................................................
v1
v2
v3
v4v5
v6
v7
• •
•
•
•
•
•
8. Vo´.i moˆ˜i vector sau, xa´c d¯i.nh ca´c caˆy bao tru`m cu˙’a K7 trong chu´
.ng minh cu˙’a D- i.nh ly´
Caylay:
(a) (7, 2, 4, 4, 1).
(b) (2, 2, 2, 4, 6).
6.5 Caˆy nhi. phaˆn
“Caˆy nhi. phaˆn” (binary tree) la` moˆ. t trong nhu˜
.ng lo´.p quan tro.ng nhaˆ´t cu˙’a caˆy co´ goˆ´c. Moˆ˜i
d¯ı˙’nh trong caˆy nhi. phaˆn co´ nhie`ˆu nhaˆ´t hai con (xem Hı`nh 6.13). Ho
.n nu˜.a, moˆ˜i d¯ı˙’nh con
d¯u.o.. c ky´ hieˆ.u hoaˇ.c la` “con tra´i” hoaˇ.c la` “con pha˙’i”. Khi ve˜ caˆy nhi. phaˆn, d¯ı˙’nh con tra´i
d¯u.o.. c ve˜ beˆn tra´i va` d¯ı˙’nh con pha˙’i d¯u
.o.. c ve˜ beˆn pha˙’i.
.................................................................................................................................................. ..
.
................................................................................................................................................
...................................
......
................................. ..
..
a
b c
d
e
f g
•
•
•
•
•
• •
Hı`nh 6.13:
D- i.nh ngh˜ıa 6.5.1 Caˆy nhi. phaˆn la` moˆ. t caˆy co´ goˆ´c trong d¯o´ moˆ˜i d¯ı˙’nh hoaˇ.c khoˆng co´ con,
hoaˇ.c co´ moˆ. t con, hoaˇ.c co´ hai con. Neˆ´u d¯ı˙’nh co´ moˆ. t con, th`ı con na`y d¯u
.o.. c xem la` con tra´i
hoaˇ.c con pha˙’i; neˆ´u moˆ.t d¯ı˙’nh co´ hai con, th`ı moˆ. t con beˆn tra´i va` moˆ. t con beˆn pha˙’i.
Vı´ du. 6.5.1 Trong caˆy nhi. phaˆn Hı`nh 6.13, d¯ı˙’nh b la` con tra´i cu˙’a a va` d¯ı˙’nh c la` con pha˙’i
cu˙’a a. D- ı˙’nh d la` con pha˙’i cu˙’a b; d¯ı˙’nh b khoˆng co´ con tra´i. D- ı˙’nh e la` con tra´i cu˙’a c; d¯ı˙’nh c
khoˆng co´ con pha˙’i.
208
Vı´ du. 6.5.2 Moˆ.t caˆy xa´c d¯i.nh bo
.’˙ i ma˜ Huffman la` caˆy nhi. phaˆn. Cha˙ˇ’ng ha.n, vo´
.i caˆy
Huffman trong Hı`nh 6.3, di chuyeˆ˙’n tu`. moˆ. t d¯ı˙’nh d¯eˆ´n d¯ı˙’nh con beˆn tra´i tu
.o.ng u´.ng su.’˙ du.ng
bit 1 va` di chuyeˆ˙’n tu`. moˆ. t d¯ı˙’nh d¯eˆ´n d¯ı˙’nh con beˆn pha˙’i tu
.o.ng u´.ng su.’˙ du.ng bit 0.
Caˆy nhi. phaˆn d¯a`ˆy d¯u˙’ la` caˆy nhi. phaˆn ma` moˆ˜i d¯ı˙’nh hoaˇ.c co´ hai con hoaˇ.c khoˆng co´ con.
D- i.nh ly´ 6.5.2 Neˆ´u T la` caˆy nhi. phaˆn d¯a`ˆy d¯u˙’ vo´
.i i d¯ı˙’nh trong th`ı T co´ i + 1 d¯ı˙’nh treo va`
co´ taˆ´t ca˙’ 2i+ 1 d¯ı˙’nh.
Chu´.ng minh Taˆ.p ca´c d¯ı˙’nh cu˙’a T go`ˆm nhu˜
.ng d¯ı˙’nh la` ca´c d¯ı˙’nh con (moˆ.t va`i d¯ı˙’nh la` cha)
va` nhu˜.ng d¯ı˙’nh khoˆng pha˙’i la` d¯ı˙’nh con. To`ˆn ta. i duy nhaˆ´t moˆ.t d¯ı˙’nh khoˆng pha˙’i la` con-d¯ı˙’nh
goˆ´c. Do co´ i d¯ı˙’nh trong va` moˆ˜i d¯ı˙’nh co´ hai con neˆn to`ˆn ta. i 2i d¯ı˙’nh con. Vaˆ.y soˆ´ ca´c d¯ı˙’nh
cu˙’a T la` 2i+ 1 va` soˆ´ ca´c d¯ı˙’nh treo ba`ˇng
(2i+ 1)− i = i+ 1.
2
D- i.nh ly´ 6.5.3 Neˆ´u T la` caˆy nhi. phaˆn co´ d¯oˆ. cao h va` t d¯ı˙’nh treo th`ı
log t ≤ h. (6.1)
Chu´.ng minh Ta se˜ chu´.ng minh quy na.p theo h baˆ´t d¯a˙ˇ’ng thu´
.c tu.o.ng d¯u.o.ng:
t ≤ 2h. (6.2)
Neˆ´u h = 0 th`ı caˆy T go`ˆm moˆ.t d¯ı˙’nh; suy ra t = 1. Do d¯o´ (6.2) d¯u´ng.
Gia˙’ su.’˙ kha˙ˇ’ng d¯i.nh d¯u´ng vo´
.i mo. i caˆy nhi. phaˆn co´ d¯oˆ. cao nho˙’ ho
.n h. Gia˙’ su.’˙ T la` caˆy nhi.
phaˆn co´ d¯oˆ. cao h > 0 vo´
.i t d¯ı˙’nh treo. Xe´t tru.`o.ng ho.. p d¯ı˙’nh goˆ´c cu˙’a T chı˙’ co´ moˆ. t con. Neˆ´u
ta khu.’˙ goˆ´c va` ca.nh lieˆn thuoˆ.c vo´
.i goˆ´c th`ı ta d¯u.o.. c caˆy nhi. phaˆn co´ d¯oˆ. cao h− 1 va` cu`ng soˆ´
d¯ı˙’nh treo nhu. T. Theo quy na.p, t ≤ 2h−1 < 2h va` do vaˆ.y (6.2) d¯u´ng.
Baˆy gio`. gia˙’ su.’˙ goˆ´c cu˙’a T co´ hai con la` v1 va` v2. Ky´ hieˆ.u Ti, i = 1, 2, la` caˆy con vo´
.i goˆ´c ta. i
vi va` gia˙’ su
.’˙ Ti co´ d¯oˆ. cao hi va` ti d¯ı˙’nh treo. Theo gia˙’ thieˆ´t quy na.p
ti ≤ 2hi , i = 1, 2. (6.3)
Nhaˆ.n xe´t ra`ˇng ca´c d¯ı˙’nh treo cu˙’a T go`ˆm ca´c nu´t la´ cu˙’a T1 va` T2. Do d¯o´
t = t1 + t2. (6.4)
Tu`. (6.3) va` (6.4) ta co´
t = t1 + t2 ≤ 2h1 + 2h2 ≤ 2h−1 + 2h−1 = 2h.
2
209
................................................................................................................. ........................................................................................
.
.......................................
.....
.........................................
...
...........................................................................................................................
.....
.........................................
...
..................................................................................................................... ............................................................................... .
...........................................
.....
.........................................
...
.................................................................................. .. .........................................
...
.......................................
.....
•
• •
• • • •
• • • • • • •
Hı`nh 6.14:
Vı´ du. 6.5.3 Caˆy nhi. phaˆn trong Hı`nh 6.14 co´ d¯oˆ. cao h = 3 va` soˆ´ ca´c nu´t la´ la` t = 8. Trong
tru.`o.ng ho.. p na`y, (6.1) tro
.’˙ tha`nh d¯a˙ˇ’ng thu´.c.
Gia˙’ su.’˙ ta co´ moˆ. t taˆ.p S ma` ca´c pha`ˆn tu
.’˙ cu˙’a no´ d¯u.o.. c saˇ´p thu´
. tu.. . Cha˙ˇ’ng ha.n, neˆ´u S ⊂ R
vo´.i thu´. tu.. thoˆng thu
.`o.ng; neˆ´u S la` ca´c chuoˆ˜i ky´ tu.. , ta co´ theˆ˙’ su
.’˙ du.ng thu´
. tu.. tu`
. d¯ieˆ˙’n. Caˆy
nhi. phaˆn d¯u
.o.. c su
.’˙ du.ng raˆ´t nhie`ˆu trong tin ho.c nha`ˇm lu
.u tru˜. ca´c pha`ˆn tu.’˙ cu˙’a moˆ.t taˆ.p d¯u
.o.. c
saˇ´p thu´. tu.. . Gia˙’ su
.’˙ ta. i moˆ˜i d¯ı˙’nh v ta lu
.u tru˜. du˜. lieˆ.u d(v). Khi d¯o´ neˆ´u v la` con tra´i (hoaˇ.c
con pha˙’i) cu˙’a w th`ı se˜ co´ moˆ. t moˆ´i quan heˆ. thu´
. tu.. giu˜
.a d(v) va` d(w).
D- i.nh ngh˜ıa 6.5.4 Caˆy t`ım kieˆ´m nhi. phaˆn (binary seach tree) la` moˆ. t caˆy nhi. phaˆn trong
d¯o´ du˜. lieˆ.u lieˆn keˆ´t vo´
.i moˆ˜i d¯ı˙’nh. Du˜. lieˆ.u d¯u
.o.. c saˇ´p xeˆ´p sao cho vo´
.i moˆ˜i d¯ı˙’nh v du˜. lieˆ.u trong
caˆy con beˆn tra´i cu˙’a v nho˙’ ho.n du˜. lieˆ.u trong v; va` moˆ˜i du˜
. lieˆ.u trong caˆy con beˆn pha˙’i cu˙’a
v lo´.n ho.n du˜. lieˆ.u trong v.
Vı´ du. 6.5.4 Chuoˆ˜i S
OLD PROGRAMMERS NEVER DIE
THEY JUST LOSE THEIR MEMORIES
co´ theˆ˙’ d¯aˇ. t trong moˆ.t caˆy t`ım kieˆ´m nhi. phaˆn nhu
. Hı`nh 6.15.
No´i chung, co´ nhie`ˆu ca´ch d¯aˇ. t du˜
. lieˆ.u va`o caˆy t`ım kieˆ´m nhi. phaˆn. Hı`nh 6.16 minh ho.a caˆy
nhi. phaˆn kha´c lu
.u tru˜. ca´c tu`. trong chuoˆ˜i S.
Du.´o.i d¯aˆy la` thuaˆ. t toa´n xaˆy du
.
. ng caˆy t`ım kieˆ´m nhi. phaˆn.
6.5.1 Thuaˆ.t toa´n xaˆy du
.
. ng caˆy t`ım kieˆ´m nhi. phaˆn
Nhaˆ.p: Da˜y ca´c tu`
. phaˆn bieˆ.t: S.
Xuaˆ´t: Caˆy t`ım kieˆ´m nhi. phaˆn T.
210
OLD
................................................................................................................................................... .....
NEVER
.....................................................................................
.....
DIE
...................................................................................... .
..
JUST
....................................................................................... ..
.
LOSE
....................................................................................... .
..
MEMORIES
.......................................................................................................................................................
PROGRAMMERS
....................................................................................... .
..
THEY
......................................................................................
....
THEIR
Hı`nh 6.15:
Bu.´o.c 1. [Xaˆy du.. ng nu´t goˆ´c] Gia˙’ su
.’˙ w la` tu`. d¯a`ˆu tieˆn trong da˜y S. Neˆ´u S = ∅, d¯aˇ. t T la` caˆy
khoˆng d¯ı˙’nh va` ca.nh va` du`
.ng; ngu.o.. c la. i, thieˆ´t laˆ.p T la` caˆy co´ d¯u´ng moˆ.t d¯ı˙’nh (la` goˆ´c)
va` lu.u tru˜. w trong goˆ´c.
Bu.´o.c 2. [Laˆ´y ky´ tu.. tieˆ´p] Gia˙’ su
.’˙ w la` ky´ tu.. keˆ´ tieˆ´p trong S. Neˆ´u khoˆng to`ˆn ta. i, du`
.ng.
Bu.´o.c 3. [Baˇ´t d¯a`ˆu t`ım kieˆ´m d¯eˆ˙’ lu.u tru˜. vi. tr´ı] Gia˙’ su
.’˙ v la` goˆ´c cu˙’a T.
Bu.´o.c 4. [Keˆ´t thu´c?] Neˆ´u w nho˙’ ho.n tu`. trong v va` v khoˆng co´ caˆy con beˆn tra´i th`ı theˆm
d¯ı˙’nh con beˆn tra´i va`o v va` lu.u w va`o caˆy con tra´i sau d¯o´ chuyeˆ˙’n sang Bu.´o.c 2. Neˆ´u w
lo´.n ho.n tu`. trong v va` v khoˆng co´ caˆy con beˆn pha˙’i, theˆm d¯ı˙’nh con beˆn pha˙’i va`o v va`
lu.u w va`o sau d¯o´ chuyeˆ˙’n sang Bu.´o.c 2.
Bu.´o.c 5. [Tieˆ´p tu. c t`ım] Neˆ´u w nho˙’ ho
.n tu`. trong v d¯aˇ. t v la` con beˆn tra´i cu˙’a v va` chuyeˆ˙’n
sang Bu.´o.c 4. Neˆ´u w lo´.n ho.n tu`. trong v d¯aˇ. t v la` con beˆn pha˙’i cu˙’a v va` chuyeˆ˙’n sang
Bu.´o.c 4.
Caˆy t`ım kieˆ´m nhi. phaˆn raˆ´t tieˆ.n lo
.
. i trong vieˆ.c t`ım kieˆ´m du˜
. lieˆ.u. Tu´
.c la` neˆ´u cho du˜. lieˆ.u
D ta co´ theˆ˙’ xa´c d¯i.nh vi. tr´ı cu˙’a no´ D trong caˆy t`ım kieˆ´m nhi. phaˆn (neˆ´u co´). D- eˆ˙’ xa´c d¯i.nh
du˜. lieˆ.u D trong caˆy t`ım kieˆ´m nhi. phaˆn, chu´ng ta baˇ´t d¯a`ˆu tu`
. goˆ´c. Sau d¯o´ ta laˇ.p la. i tieˆ´n
tr`ınh so sa´nh D vo´.i du˜. lieˆ.u ta. i nu´t hieˆ.n ha`nh. Neˆ´u D ba`ˇng du˜
. lieˆ.u ta. i nu´t hieˆ.n ha`nh, tu´
.c
d¯a˜ t`ım thaˆ´y D va` thuaˆ. t toa´n du`
.ng. Neˆ´u D nho˙’ ho.n (tu.o.ng u´.ng, lo´.n ho.n) du˜. lieˆ.u ta. i nu´t
hieˆ.n ha`nh v ta di chuyeˆ˙’n xuoˆ´ng nu´t con beˆn tra´i (tu
.o.ng u´.ng, beˆn pha˙’i) cu˙’a v va` laˇ.p la. i qua´
tr`ınh na`y. Ta. i tho`
.i d¯ieˆ˙’m na`o d¯o´, ta khoˆng theˆ˙’ di chuyeˆ˙’n d¯u.o.. c nu˜
.a th`ı keˆ´t luaˆ.n D khoˆng
co´ trong caˆy.
211
NEVER
................................................................................................................................................... .....
JUST
.....................................................................................
.....
DIE
...................................................................................... .
..
LOSE
....................................................................................... .
..
MEMORIES
.......................................................................................................................................................
PROGRAMMERS
....................................................................................... .
..
THEIR
....................................................................................
.....
OLD
....................................................................................... .
..
THEY
Hı`nh 6.16:
Tho`.i gian t`ım kieˆ´m du˜. lieˆ.u trong caˆy t`ım kieˆ´m nhi. phaˆn la` toˆ´i d¯a khi du˜
. lieˆ.u khoˆng na`ˇm
trong caˆy va` theo d¯o´ ta co´ daˆy chuye`ˆn da`i nhaˆ´t tu`. nu´t goˆ´c. Do d¯o´ tho`.i gian toˆ´i d¯a d¯eˆ˙’ t`ım
kieˆ´m tı˙’ leˆ. vo´
.i chie`ˆu cao cu˙’a caˆy. Heˆ. qua˙’ la` d¯oˆ. cao cu˙’a caˆy t`ım kieˆ´m nhi. phaˆn ca`ng nho˙’ th`ı
tho`.i gian t`ım kieˆ´m ca`ng ı´t. Co´ nhie`ˆu ca´ch d¯eˆ˙’ cu.. c tieˆ˙’u hoa´ d¯oˆ. cao cu˙’a caˆy (xem [9]).
D- eˆ˙’ phaˆn t´ıch tru.`o.ng ho.. p xaˆ´u nhaˆ´t trong caˆy t`ım kieˆ´m nhi. phaˆn T (co´ n d¯ı˙’nh, t d¯ı˙’nh
treo va` d¯oˆ. cao h) ta go. i T
∗ la` caˆy nhi. phaˆn d¯a`ˆy d¯u˙’ nhaˆ.n d¯u.o.. c tu`. T ba`ˇng ca´ch theˆm ca´c
nu´t con beˆn tra´i va` beˆn pha˙’i (neˆ´u ca`ˆn). Cha˙ˇ’ng ha.n, Hı`nh 6.17 la` caˆy nhi. phaˆn d¯a`ˆy d¯u˙’ tu`
.
caˆy T trong Hı`nh 6.15. Ca´c d¯ı˙’nh theˆm va`o d¯u.o.. c d¯a´nh daˆ´u ∗. Vieˆ.c t`ım kieˆ´m khoˆng tha`nh
coˆng trong T tu.o.ng u´.ng d¯eˆ´n ca´c d¯ı˙’nh d¯a´nh daˆ´u ∗ trong T ∗. Theo D- i.nh ly´ 6.5.3, log t ≤ h.
Nhu.ng theo ca´ch xaˆy du.. ng, caˆy nhi. phaˆn d¯a`ˆy d¯u˙’ T
∗ co´ n d¯ı˙’nh trong va` t d¯ı˙’nh treo, neˆn
theo D- i.nh ly´ 6.5.2, t = n+ 1. Do d¯o´ trong tru
.`o.ng ho.. p xaˆ´u nhaˆ´t tho`
.i gian t`ım kieˆ´m ı´t nhaˆ´t
la` log t = log(n + 1). Ba`i taˆ.p 3 chı˙’ ra ra`ˇng neˆ´u d¯oˆ. cao cu˙’a T toˆ´i thieˆ˙’u th`ı tru
.`o.ng ho.. p xaˆ´u
nhaˆ´t tho`.i gian t`ım kieˆ´m ba`ˇng [log(n+ 1)].
Ba`i taˆ.p
1. D- aˇ. t ca´c tu`
. FOUR SCORE AND SEVEN YEARS AGOOUR FOREFATHERS BROUGHT
FORTH theo thu´. tu.. xuaˆ´t hieˆ.n cu˙’a chu´ng va`o caˆy t`ım kieˆ´m nhi. phaˆn.
2. Vieˆ´t thuaˆ. t toa´n t`ım kieˆ´m treˆn caˆy t`ım kieˆ´m nhi. phaˆn.
3. Vieˆ´t thuaˆ. t toa´n lu
.u tru˜. n tu`. kha´c nhau va`o caˆy t`ım kieˆ´m nhi. phaˆn T vo´
.i tro.ng lu
.o.. ng
toˆ´i thieˆ˙’u. Chu´.ng minh raˇ`ng caˆy d¯a`ˆy d¯u˙’ T ∗ nhaˆ.n d¯u.o.. c tu`. caˆy T ba`ˇng ca´ch theˆm ca´c
nu´t con beˆn tra´i va` beˆn pha˙’i (neˆ´u ca`ˆn thieˆ´t) co´ tro.ng lu
.o.. ng [log(n+ 1)].
4. Kha˙ˇ’ng d¯i.nh sau d¯u´ng hay sai: Gia˙’ su
.’˙ T la` caˆy nhi. phaˆn. Vo´
.i moˆ˜i d¯ı˙’nh v trong T,
212
................................................................................................................. ............................................................................................................................
......
..................................... ..
..
...................................
.....
..................................... ..
..
...................................
.....
..................................... ..
..
...................................
.....
..................................... ..
..
...................................................................................
.
..................................................................................................................... ............................................................................... .
....
.................................................................................. .. ...................................
......
..................................... ..
..
......................................
..
...................................
......
∗ ∗
∗
∗
∗
∗ ∗
∗ ∗
∗
•
Hı`nh 6.17:
du˜. lieˆ.u trong v lo´
.n ho.n (tu.o.ng u´.ng, nho˙’ ho.n) du˜. lieˆ.u trong con tra´i (tu
.o.ng u´.ng, con
pha˙’i) cu˙’a v th`ı T la` caˆy t`ım kieˆ´m nhi. phaˆn. Gia˙’i th´ıch.
5. Ve˜ ca´c graph (neˆ´u to`ˆn ta. i) tu
.o.ng u´.ng vo´.i nhu˜.ng t´ınh chaˆ´t d¯a˜ neˆu:
(a) Caˆy nhi. phaˆn d¯a`ˆy d¯u˙’ co´ boˆ´n d¯ı˙’nh trong va` naˇm d¯ı˙’nh treo.
(b) Caˆy nhi. phaˆn d¯a`ˆy d¯u˙’ co´ d¯oˆ. cao 3 va` ch´ın d¯ı˙’nh treo.
(c) Caˆy nhi. phaˆn d¯a`ˆy d¯u˙’ co´ d¯oˆ. cao 4 va` ch´ın d¯ı˙’nh treo.
6. Caˆy m-phaˆn d¯a`ˆy d¯u˙’ la` caˆy co´ goˆ´c sao cho moˆ˜i d¯ı˙’nh trong co´ m d¯ı˙’nh con co´ thu´. tu.. .
Caˆy m-phaˆn d¯a`ˆy d¯u˙’ T vo´.i i d¯ı˙’nh trong th`ı co´ bao nhieˆu d¯ı˙’nh? Co´ bao nhieˆu d¯ı˙’nh
treo? Gia˙’i th´ıch.
7. T`ım thuaˆ. t toa´n xaˆy du
.
. ng caˆy nhi. phaˆn d¯a`ˆy d¯u˙’ vo´
.i n > 1 d¯ı˙’nh treo.
8. Vieˆ´t thuaˆ. t toa´n d¯eˆ. quy xaˆy du
.
. ng caˆy t`ım kieˆ´m nhi. phaˆn.
9. T`ım d¯oˆ. cao cu
.
. c d¯a. i cu˙’a caˆy nhi. phaˆn d¯a`ˆy d¯u˙’ co´ t d¯ı˙’nh treo.
10. Vieˆ´t thuaˆ. t toa´n kieˆ˙’m tra moˆ.t caˆy nhi. phaˆn vo´
.i ca´c du˜. lieˆ.u d¯u
.o.. c lu
.u tru˜. ta. i moˆ˜i d¯ı˙’nh
la` caˆy t`ım kieˆ´m nhi. phaˆn.
11. Gia˙’ su.’˙ T la` caˆy nhi. phaˆn d¯a`ˆy d¯u˙’; I la` toˆ˙’ng ca´c d¯oˆ. da`i cu˙’a ca´c daˆy chuye`ˆn d¯o
.n gia˙’n
tu`. goˆ´c d¯eˆ´n ca´c d¯ı˙’nh trong va` E la` toˆ˙’ng ca´c d¯oˆ. da`i cu˙’a ca´c daˆy chuye`ˆn d¯o
.n gia˙’n tu`.
goˆ´c d¯eˆ´n ca´c d¯ı˙’nh treo. Chu´.ng minh ra`ˇng neˆ´u T co´ n d¯ı˙’nh trong th`ı E = I + 2n.
12. Caˆy nhi. phaˆn T go. i la` caˆn ba`ˇng neˆ´u vo´
.i moˆ˜i d¯ı˙’nh v, d¯oˆ. cao cu˙’a ca´c caˆy con beˆn tra´i
va` beˆn pha˙’i sai kha´c nhau nhie`ˆu nhaˆ´t la` 1. (D- oˆ. cao caˆy roˆ˜ng d¯i.nh ngh˜ıa la` −1). Ky´
hieˆ.u Nh la` soˆ´ toˆ´i thieˆ˙’u ca´c d¯ı˙’nh trong caˆy nhi. phaˆn caˆn baˇ`ng vo´
.i d¯oˆ. cao h va` f1, f2, . . .
la` da˜y Fibonacci.
(a) Chu´.ng minh ra`ˇng N0 = 1, N1 = 2, va` N2 = 4.
213
(b) Chu´.ng minh ra`ˇng Nh = 1 +Nh−1 +Nh−2 vo´.i mo. i h ≥ 0.
(c) Chu´.ng minh ra`ˇng Nh = fh+2 − 1 vo´.i mo. i h ≥ 0.
13. Chu´.ng minh ra`ˇng d¯oˆ. cao h cu˙’a caˆy nhi. phaˆn caˆn baˇ`ng thoa˙’ ma˜n h = O(log 2). D- ie`ˆu
na`y chı˙’ ra ra`ˇng trong tru.`o.ng ho.. p xaˆ´u nhaˆ´t, tho`
.i gian t`ım kieˆ´m trong caˆy nhi. phaˆn
caˆn ba`ˇng n d¯ı˙’nh la` O(log 2).
14. Chu´.ng minh raˇ`ng neˆ´u caˆy nhi. phaˆn caˆn baˇ`ng d¯oˆ. cao h co´ n ≥ 1 d¯ı˙’nh th`ı log n < h+1.
214
Ta`i lieˆ.u tham kha˙’o
[1] C. Berge, Ly´ thuyeˆ´t d¯o`ˆ thi. va` u´
.ng du. ng, NXB Khoa ho.c va` ky˜ thuaˆ. t Ha` Noˆ. i, 1971.
[2] A. Cayley, Collected papers, Quart. Jl. of Mathematics, 13 Cambridge, 26 (1897).
[3] N. Biggs, Discrete mathematic, Clarendon Press Oxford, 1989.
[4] Dijkstra, E. W., A note on two problems in connection with graphs, Numerische Math-
ematik, 1, 269 (1959).
[5] P. J. Cameron, Combinatorics: topics, techniques, algorithms, Cambridge University
Press, 1994.
[6] N. Deo, Graph theory with applications to engineering and computer science, Prentice-
Hall Inc., 1974.
[7] R. J. MC Eliece, M. Kac, The theory of information and coding, Addison-Wesley, 1977.
[8] C. M. Goldie, R. G. E. Pinch, Communication theory, Cambridge University Press,
1991.
[9] R. W. Hamming, Coding and information theory, Prentice Hall, 1980.
[10] R. Hill, A first course in coding theory, Clarendon Press Oxford, 1985.
[11] R. Johnsonbaugh, An introduction to discrete mathematic, Macmillan Publishing Com-
pany, 1992.
[12] A. R. Kenneth, C. R.B. Wright, Discrete mathematics, Prentice-Hall International Edi-
tions, 1978.
[13] Kirchhoff G., in “Annalen der Physik and Chemie” 72, 497 (1847).
[14] S. Lipschutz, Essential computer mathematic, McGraw-Hill, 1992.
[15] S. Lipschutz, M. L. Lipson,2000 sloved problems in discrete mathematics, McGraw-Hill,
1992.
[16] C. L. Liu, Introduction to combinationnal mathematic, McGraw-Hill, 1985.
215
[17] F. J. MacWilliams, N. J. A. Soane, The theory of error-correcting codes, North-Holland,
1981.
[18] A. A. Michael, A. J. Kfoury, R. N. Moll, D. Gries, A basis for theoretical computer
science, Springer-Verlag NewYork Inc., 1981.
[19] J. G. Michaels, K. H. Rosen, Applications of discrete mathematics, McGraw-Hill, 1991.
[20] Prim R. C., Shortest connection networks and some generalizations, Bell Syst. Tech.
Jl., 36, 1389 (1957).
[21] S. Roman, An introduction to discrete mathematic, Saunders College, 1982.
[22] K. H. Rosen, Discrete mathematics and its applications, McGraw-Hill, 1995.
[23] B. M. Stephen, A. Ralston, Discrete algorithmic mathematics, Addision-Wesley Pub-
lishing Company, 1991.
[24] D. Welsh, Codes and cryptography, Clarendon Press Oxford, 1987.
216