Gio trnh l thuyt th

Bin tp bi:
Thc s Nguyn Thanh Hng

Gio trnh l thuyt th

Bin tp bi:
Thc s Nguyn Thanh Hng
Cc tc gi:
Thc s Nguyn Thanh Hng

Phin bn trc tuyn:

http://voer.edu.vn/c/9c021e14

MC LC
1. Cc khi nim c bn ca l thuyt th
2. Cc thut ng c bn
3. ng i,chu trnh, lin thng
4. Mt s dng th c bit
5. Biu din th trn my vi tnh
6. Danh sch cnh(cung)
7. Danh sch k
8. Cc thut ton tm kim trn th v ng dng
9. Tm kim theo chiu rng trn th
10. Tm ng i v kim tra tnh lin thng
11. th Euler v th Hamiton
12. th Hamilton
13. Cy v cy khung ca th
14. Cy khung ca th
15. Xy dng tp cc chu trnh c bn ca th
16. Bi ton cy khung nh nht
17. Bi ton ng i ngn nht
18. ng i ngn nht xut pht t mt nh
19. Trng hp ma trn trng s khng m-Thut ton Dijkstra
20. th trong th khng c chu trnh
21. ng i ngn nht gia tt c cc cp nh
22. Bi ton lung cc i trong mng
23. Lt ct.ng tng lung.nh l Ford_Fulkerson
24. Thut ton tm lung cc i
25. Mt s bi ton lung tng qut
26. Mt s ng dng trong t hp
27. Bi tp chng 3
28. Bi tp chng 4
29. Bi tp chng 5
30. Bi tp chng 6
31. Bi tp chng 7
32. Cc bi tp khc
Tham gia ng gp

1/164

Cc khi nim c bn ca l thuyt th

L thuyt th l mt lnh vc c t lu v c nhiu ng dng hin i. Nhng t
tng c bn ca l thuyt th c xut vo nhng nm u ca th k 18 bi
nh ton hc li lc ngi Thy S Lenhard Eurler. Chnh ng l ngi s dng
th gii bi ton ni ting v cc ci cu thnh ph Konigsberg.
th c s dng gii cc bi ton trong nhiu lnh vc khc nhau. Chng hn,
th c th s dng xc nh cc mch vng trong vn gii tch mch in. Chng
ta c th phn bit cc hp cht ha hc hu c khc nhau vi cng cng thc phn t
nhng khc nhau v cu trc phn t nh th. Chng ta c th xc nh hai my tnh
trong mng c th trao i thng tin c vi nhau hay khng nh m hnh th ca
mng my tnh. th c trng s trn cc cnh c th s dng gii cc bi ton nh:
Tm ng i ngn nht gia hai thnh ph trong mng giao thng. Chng ta cng cn
s dng th gii cc bi ton v lp lch, thi kha biu, v phn b tn s cho cc
trm pht thanh v truyn hnh

NH NGHA TH
th l mt cu trc ri rc bao gm cc nh v cc cnh ni cc nh ny. Chng ta
phn bit cc loi th khc nhau bi kiu v s lng cnh ni hai nh no ca
th. c th hnh dung c ti sao li cn n cc loi th khc nhau, chng ta s
nu v d s dng chng m t mt mng my tnh. Gi s ta c mt mng gm cc
my tnh v cc knh in thoi (gi tt l knh thoi) ni cc my tnh ny. Chng ta
c th biu din cc v tr t ny tnh bi cc im v cc knh thoi ni chng bi cc
on ni, xem hnh 1.

Hnh 1. S mng my tnh.

2/164

Nhn thy rng trong mng hnh 1, gia hai my bt k ch c nhiu nht l mt knh
thoi ni chng, knh thoi na cho php lin lc c hai chiu v khng c my tnh no
li c ni vi chnh n. S mng my cho trong hnh 1 c gi l n th v
hng. Ta i n nh ngha sau
nh ngha 1.
n th v hng G = (V,E) bao gm V l tp cc nh, v E l tp cc cp khng c
th t gm hai phn t khc nhau ca V gi l cc cnh.
Trong trng hp gia hai my tnh no thng xuyn phi truyn ti nhiu thng
tin ngi ta phi ni hai my nu bi nhiu knh thoi. Mng vi a knh thoi gia cc
my c cho trong hnh 2.

Hnh 2. S mng my tnh vi a knh thoi.

nh ngha 2.
a th v hng G= (V, E) bao gm V l tp cc nh, v E l tp cc cp khng c
th t gm hai phn t khc nhau ca V gi l cc cnh. Hai cnh e1 v e2 c gi l
cnh lp nu chng cng tng ng vi mt cp nh.

Hnh 3. S mng my tnh vi knh thoi thng bo.

3/164

R rng mi n th u l a th, nhng khng phi a th no cng l n

th, v trong a th c th c hai (hoc nhiu hn) cnh ni mt cp nh no .Trong
mng my tnh c th c nhng knh thoi ni mt ny no vi chnh n (chng hn
vi mc nh thng bo). Mng nh vy c cho trong hnh 3.Khi a th khng
th m t c mng nh vy, bi v c nhng khuyn(cnh ni mt nh vi chnh n).
Trong trng hp nychng ta cn s dng n khi nim gi th v hng, c
nh ngha nh sau:
nh ngha 3.
Gi th v hng G = (V, E) bao gm V l tp cc nh v E l tp cc cp khng
c th t gm hai phn t (khng nht thit phi khc nhau) ca V gi l cnh. Cnh e
c gi l khuyn nu n c dng e = (u, u).

Hnh 4. Mng my tnh vi knh thoi mt chiu

Cc knh thoi trong mng my tnh c th ch cho php truyn tin theo mt chiu.
Chng hn, trong hnh 4 my ch H Ni ch c th nhn tin t cc my a phng,
c mt s my ch c th gi tin i, cn cc knh thoi cho php truyn tin theo c hai
chiu c thay th bi hai cnh c hng ngc chiu nhau.
Ta i n nh ngha sau.
nh ngha 4.
n th c hng G = (V, E) bao gm V l tp cc nh v E l tp cc cp c th t
gm hai phn t khc nhau ca V gi l cc cung.
Nu trong mng c th c a knh thoi mt chiu, ta s phi s dng n khi nim a
th c hng

4/164

nh ngha 5.
a th c hng G = (V, E) bao gm V l tp cc nh v E l tp cc cp c th t
gm hai phn t khc nhau ca V gi l cc cung. Hai cung e1, e2 tng ng vi cng
mt cp nh c gi l cung lp.
Trong cc phn tip theo ch yu chng ta s lm vic vi n th v hng v n
th c hng. V vy, cho ngn gn, ta s b qua tnh t n khi nhc n chng.

5/164

Cc thut ng c bn
Trong mc ny chng ta s trnh by mt s thut ng c bn ca l thuyt th. Trc
tin, ta xt cc thut ng m t cc nh v cnh ca th v hng.

nh ngha 1.
Hai nh u v v ca th v hng G c gi l k nhau nu (u,v) l cnh ca th
G. Nu e = (u, v) l cnh ca th ta ni cnh ny l lin thuc vi hai nh u v v,
hoc cng ni l ni nh u v nh v, ng thi cc nh u v v s c gi l cc nh
u ca cnh (u, v).
c th bit c vao nhiu cnh lin thuc vi mt nh, ta a vo nh ngha sau

nh ngha 2.
Ta gi bc ca nh v trong th v hng l s cnh lin thuc vi n v s k hiu
l deg(v).

Hnh 1. th v hng
Th d 1. Xt th cho trong hnh 1, ta c
deg(a) = 1, deg(b) = 4, deg(c) = 4, deg(f) = 3,
deg(d) = 1, deg(e) = 3, deg(g) = 0
nh bc 0 gi l nh c lp. nh bc 1 c gi l nh treo. Trong v d trn nh g
l nh c lp, a v d l cc nh treo. Bc ca nh c tnh cht sau:
nh l 1. Gi s G = (V, E) l th v hng vi m cnh. Khi tng bc ca tt c
cc nh bng hai ln s cung.

6/164

Chng minh. R rng mi cnh e = (u, v) c tnh mt ln trong deg(u) v mt ln

trong deg(v). T suy ra tng tt c cc bc ca cc nh bng hai ln s cnh.
Th d 2. th vi n nh c bc l 6 c bao nhiu cnh?
Gii: Theo nh l 1 ta c 2m = 6n. T suy ra tng cc cnh ca th l 3n.
H qu. Trong th v hng, s nh bc l (ngha l c bc l s l) l mt s chn.
Chng minh. Thc vy, gi O v U tng ng l tp nh bc l v tp nh bc chn
ca th. Ta c
2m = ? deg(v) + ? deg(v)

v U

v O

Do deg(v) l chn vi v l nh trong U nn tng th nht trn l s chn. T suy

ra tng th hai (chnh l tng bc ca cc nh bc l) cng phi l s chn, do tt c cc
s hng ca n l s l, nn tng ny phi gm mt s chn cc s hng. V vy, s nh
bc l phi l s chn.
Ta xt cc thut ng tng t cho th v hng.

nh ngha 3.
Nu e = (u, v) l cung ca th c hng G th ta ni hai nh u v v l k nhau, v
ni cung (u, v) ni nh u vi nh v hoc cng ni cung ny l i ra khi nh u v vo
nh v. nh u(v) s c g l nh u (cui) ca cung (u,v).
Tng t nh khi nim bc, i vi th c hng ta c khi nim bn bc ra v bn
bc vo ca mt nh.

nh ngha 4.
Ta gi bn bc ra (bn bc vo) ca nh v trong th c hng l s cung ca th
i ra khi n (i vo n) v k hiu l deg + (v) (deg - (v))

7/164

Hnh 2. th c hng
Th d 3. Xt th cho trong hnh 2. Ta c
deg - (a)=1, deg - (b)=2, deg - (c)=2, deg - (d)=2, deg - (e) = 2.
deg + (a)=3, deg + (b)=1, deg + (c)=1, deg + (d)=2, deg + (e)=2.
Do mi cung (u, v) s c tnh mt ln trong bn bc vo ca nh v v mt ln trong
bn bc ra ca nh u nn ta c:
nh l 2. Gi s G = (V, E) l th c hng. Khi
2m = ? deg+(v) + ? deg-(v)
v V v V
Rt nhiu tnh cht ca th c hng khng ph thuc vo hng trn cc cung ca
n. V vy, trong nhiu trng hp s thun tin hn nu ta b qua hng trn cc cung
ca th. th v hng thu c bng cch b qua hng trn cc cung c gi l
th v hng tng ng vi th c hng cho.

8/164

ng i,chu trnh, lin thng

nh ngha 1.
ng i di n t nh u n nh v, trong n l s nguyn dng, trn th v
hng G = (V, E) l dy
x 0 , x 1 ,, x n-1 , x n
trong u = x 0 , v = x n , (x i , x i+1 ) E, i = 0, 1, 2,, n-1.
ng i ni trn cn c th biu din di dng dy cc cnh:
(x 0 , x 1 ), (x 1 , x 2 ), , (x n-1 , x n )
nh u gi l nh u, cn nh v gi l nh cui ca ng i. ng i c nh u
trng vi nh cui (tc l u = v) c gi l chu trnh . ng i hay chu trnh c
gi l n nu nh khng c cnh no b lp li.
Th d 1. Trn th v hng cho trong hnh 1: a, d, c, f, e l ng i n di 4.
Cn d, e, c, a khng l ng i, do (c,e) khng phi l cnh ca th. Dy b, c, f, e, b
l chu trnh di 4. ng i a, b, e, d, a, b c di l 5 khng phi l ng i n,
do cnh (a, b) c mt trong n 2 ln.

Hnh 1. ng i trn th
Khi nim ng i v chu trnh trn th c hng c nh ngha hon ton tng
t nh trong trng hp th v hng, ch khc l ta c ch n hng trn cc
cung.

nh ngha 2.
ng i di n t nh u n nh v, trong , n l s nguyn dng, trn th c
hng G = (V, A) l dy
9/164

x 0 , x 1 ,, x n-1 , x n
trong u = x 0 , v = x n , (xi, x i+1 ) E, i = 0, 1, 2,, n-1.
ng i ni trn cn c th biu din di dng dy cc cung:
(x 0 , x 1 ), (x 1 , x 2 ), , (x n-1 , x n )
nh u gi l nh u, cn nh v gi l nh cui ca ng i. ng i c nh u
trng vi nh cui (tc l u = v) c gi l chu trnh . ng i hay chu trnh c
gi l n nu nh khng c cnh no b lp li.
Th d 2. Trn th c hng cho trong hnh 1: a, d, c, f, e l ng i n di 4.
Cn d, e, c, a khng l ng i, do (c,e) khng phi l cnh ca th. Dy b, c, f, e, b
l chu trnh di 4. ng i a, b, e, d, a, b c di l 5 khng phi l ng i n,
do cnh (a, b) c mt trong n 2 ln.
Xt mt mng my tnh. Mt cu hi t ra l hai my tnh bt k trong mng ny c th
trao i thng tin c vi nhau hoc l trc tip qua knh ni chng hoc thng qua
mt hoc vi my tnh trung gian trong mng? Nu s dng th biu din mng
my tnh ny (trong cc nh ca th tng ng vi cc my tnh, cn cc cnh
tng ng vi cc knh ni) cu hi c pht biu trong ngn ng th nh sau:
Tn ti hay khng ng i gia mi cp nh ca th.

nh ngha 3.
th v hng G = (V, E) c gi l lin thng nu lun tm c ng i gia hai
nh bt k ca n.
Nh vy hai my tnh bt k trong mng c th trao i thng tin c vi nhau khi v
ch khi th tng ng vi mng ny l th lin thng.
Th d 3. Trong hnh 2 : th G l lin thng, cn th H l khng lin thng.

10/164

Hnh 2. th G v H

nh ngha 4.
Ta gi th con ca th G = (V, E) l th H = (W, F), trong W V v F E.
Trong trng hp th l khng lin thng, n s r ra thnh mt s th con lin
thng i mt khng c nh chung. Nhng th con lin thng nh vy ta s gi l
cc thnh phn lin thng ca th.
Th d 4. th H trong hnh 2 gm 3 thnh phn lin thng H1, H2, H3.
Trong mng my tnh c th c nhng my (Nhng knh ni) m s hng hc ca n
s nh hng n vic trao i thng tin trong mng. Cc khi nim tng ng vi tnh
hung ny c a ra trong nh ngha sau.

nh ngha 5.
nh v c gi l nh r nhnh nu vic loi b v cng vi cc cnh lin thuc vi n
khi th lm tng s thnh phn lin thng ca th. Cnh e c gi l cu nu
vic loi b n khi th lm tng s thnh phn lin thng ca th.
Th d 5. Trong th G hnh2, nh d v e l nh r nhnh, cn cc cnh (d,g) v
(e,f) l cu.
i vi th c hng c hai khi nim lin thng ph thuc vo vic ta c xt n
hng trn cc cung hay khng.

nh ngha 6.
th c hng G = (V, A) c gi l lin thng mnh nu lun tm c ng i
gia hai nh bt k ca n.

nh ngha 7.
th c hng G = (V, A) c gi l lin thng yu nu th v hng tng ng
vi n l v hng lin thng.
R rng nu th l lin thng mnh th n cng l lin thng yu, nhng iu ngc
li l khng lun ng, nh ch ra trong v dn di y.
Th d 6. Trong hnh 3 th G l lin thng mnh, cn H l lin thng yu nhng
khng l lin thng mnh.
11/164

Hnh 3. th lin thng mnh G v th lin thng yu H

Mt cu hi t ra l khi no c th nh hng cc cnh ca mt th v hng lin
thng c th thu c th c hng lin thng mnh? Ta s gi th nh vy l
th nh hng c. nh l di y cho ta tiu chun nhn bit mt th c l
nh hng c hay khng.
nh l 1.
th v hng lin thng l nh hng c khi v ch khi mi cnh ca n nm trn
t nht mt chu trnh.
Chng minh.
iu kin cn. Gi s (u,v) l mt cnh ca mt th. T s tn ti ng i c hng
t u n v v ngc li suy ra (u, v) phi nm trn t nht mt chu trnh.
iu kin . Th tc sau y cho php nh hng cc cnh ca th thu c
th c hng lin thng mnh. Gi s C l mt chu trnh no trong th. nh hng
cc cnh trn chu trnh ny theo mt hng i vng theo n. Nu tt c cc cnh ca
th l c nh hng th kt thc th tc. Ngc li, chn e l mt cnh cha nh
hng c chung nh vi t nht mt trong s cc cnh nh hng. Theo gi thit tm
c chu trnh C cha cnh e. nh hng cc cnh cha c nh hng ca C theo
mt hng dc theo chu trnh ny (khng nh hng li cc cnh c nh hng).
Th tc trn s c lp li cho n khi tt c cc cnh ca th c nh hng. Khi
ta thu c th c hng lin thng mnh.

12/164

Mt s dng th c bit
Trong mc ny ta xt mt s n th v hng dng c bit xut hin trong nhiu
vn ng dng thc t.

th y .
th y n nh, k hiu bi Kn, l n th v hngm gia hai nh bt k ca
n lun c cnh ni.
Cc th K3, K4, K5 cho trong hnh di y.

Hnh 1. th y
th y Kn c tt c n(n-1)/2 cnh, n l n th c nhiu cnh nht.

th vng.
th vng Cn, n3. gm n nh v1, v2,. . . .vn v cc cnh (v1,v2), (v2,v3) . . . (vn-1,vn),
(vn,v1).
th vng C3, C4, C5, C6 cho trong hnh 2.

13/164

Hnh 2. th vng C3, C4, C5, C6

th bnh xe.
th Wn thu c t Cn bng cch b sung vo mt nh mi ni vi tt c cc nh
ca Cn (xem hnh 3).

Hnh 3. th bnh xe W3, W4, W5, W6

th lp phng.
th lp phng n nh Qn l th vi cc nh biu din 2n xu nh phn di n.
Hai nh ca n gi l k nhau nu nh hai xu nh phn tng ng ch khc nhau 1 bit.
Hnh 4 cho thy Qn vi n=1,2,3.

Hnh 4. th lp phng Q1, Q2, Q3

th hai pha.
n th G=(V,E) c gi l hai pha nu nh tp nh V ca n c th phn hoch
thnh hai tp X v Y sao cho mi cnh ca th ch ni mt nh no trong X vi
mt nh no trong Y. Khi ta s s dng k hiu G=(X? Y, E) ch th hai
pha vi tp nh X? Y.

14/164

nh l sau y cho php nhn bit mt n th c phi l hai pha hay khng.
nh l 1. n th l th hai pha khi v ch khi n khng cha chu trnh di
l.
kim tra xem mt th lin thng c phi l hai pha hay khng c th p dng th
tc sau. Cho v l mt nh bt k ca th. t X={v}, cn Y l tp cc nh k ca v.
Khi cc nh k ca cc nh trong Y phi thuc vo X. K hiu tp cc nh nh vy
l T. V th nu pht hin T ? Y # th th khng phi l hai pha, kt thc. ngc
li, t X=X ? T. Tip tc xt nh vy i vi T l tp cc nh k ca T,. . .
th hai pha G=(X ? Y, E) vi ? X?= m,?Y? = n c gi l th hai pha y v
k hiu l K2,3, K3,3, K3,4 c cho trong hnh 5. Khi E

Hnh 5. th hai pha

th phng.
th c gi l th phng nu ta c th v n trn mt phng sao cho cc cnh ca
n khng ct nhau ngoi nh. Cch v nh vy s c gi l biu din phng ca
th.
Th d th K4 l phng, v c th v n trn mt phng sao cho cc cnh ca n khng
ct nhau ngoi nh (xem hnh 6).

Hnh 6. th K4 l th phng

15/164

Mt iu ng lu nu th l phng th lun c th v n trn mt phng vi cc

cnh ni l cc on thng khng ct nhau ngoi nh (v d xem cch v K4 trong
hnh 6).
nhn bit xem mt th c phi l th phng c th s dng nh l Kuratovski,
m pht biu n ta cn mt s khi nim sau: Ta gi mt php chia cnh (u,v) ca
th l vic loi b cnh ny khi th v thm vo th mt nh mi w cng vi hai
cnh (u,w), (w, u) . Hai th G(V,E) v H=(W,F) c gi l ng cu nu chng c
th thu c t cng mt th no nh php chia cnh.
nh l 2 (Kuratovski). th l phng khi v ch khi n khng cha th con ng
cu vi K 3,3 hoc K 5 .
Trong trng hp ring, th K3,3 hoc K5 khng phi l th phng. Bi ton v tnh
phng ca th K3,3 l bi ton ni ting v ba cn h v ba h thng cung cp nng
lng cho chng: Cn xy dng h thng ng cung cp nng lng vi mi mt cn
h ni trn sao cho chng khng ct nhau. th phng cn tm c nhng ng dng
quan trng trong cng ngh ch to mch in.
Biu din phng ca th s chia mt phng ra thnh cc min, trong c th c
c min khng b chng. Th d, biu din phng ca th cho trong hnh 7 chia mt
phng ra thnh 6 min R1, R2,. . . .R6.

Hnh 7. Cc min tng ng vi biu din phng ca th

Euler chng minh c rng cc cch biu din phng khc nhau ca mt th u
chia mt phng ra thnh cng mt s min. chng minh iu , Euler tm c
mi lin h gia s min, s nh ca th v s cnh ca th phng sau y.
nh l 3 (Cng thc Euler). Gi s G l th phng lin thng vi n nh, m cnh.
Gi r l s min ca mt phng b chia bi biu din phng ca G. Khi
r = m-n + 2
C th chng minh nh l bng qui np. Xt th d minh ho cho p dng cng thc
Euler.

16/164

Th d. Cho G l th phng lin thng vi 20 nh, mi nh u c bc l 3. Hi mt

phng b chia lm bao nhiu phn bi biu din phng ca th G?
Gii. Do mi nh ca th u c bc l 3, nn tng bc ca cc nh l 3x20=60. T
suy ra s cnh ca th m=60/20=30. V vy, theo cng thc Euler, s min cn tm
l r=30-20+2=12.

17/164

Biu din th trn my vi tnh

lu tr th v thc hin cc thut ton khc nhau vi th trn my tnh cn phi
tm nhng cu trc d liu thch hp m t th. Vic chn cu trc d liu no
biu din th c tc ng rt ln n hiu qu ca thut ton. V vy, vic chn
la cu trc d liu biu din th ph thuc vo tng tnh hung c th (bi ton
v thut ton c th). Trong mc ny chng ta s xt mt s phng php c bn c
s dng biu din th trn my tnh, ng thi cng phn tch mt cch ngn gn
nhng u im cng nh nhng nhc im ca chng.

MA TRN K. MA TRN TRNG S

Xt n th v hng G=(V,E), vi tp nh V={ 1, 2,. . . ,n? , tp cnh E={ e1, e2,. .
.,em }. Ta gi ma trn k ca th G l ma trn.
A={ ai,j : i,j=1, 2,. . . ,n }
Vi cc phn t c xc nh theo qui tc sau y:
ai, j = 0, nu (i,j) E v
ai,j = 1 , nu (i,j) E, i, j=1, 2,. . .,n.
Th d 1. Ma trn trn k ca th v hng cho trong hnh 1 l:

18/164

Hnh 1. th v hng G v th c hng G 1

Cc tnh cht ca ma trn k:
1) R rng ma trn k ca th v hng l ma trn i xng, tc l
a[i,j]=a[j,i], i,j=1,2,. . .,n.
ngc li, mi (0,1)-ma trn i xng cp n s tng ng, chnh xc n cch nh s
nh (cn ni l: chnh xc n ng cu), vi mt n th v hng n nh.
2) Tng cc phn t trn dng i (ct j) ca ma trn k chnh bng bc ca nh i (nh j).
3) nu k hiu
ajp , i,j=1, 2,. . . ,n
l phn t ca ma trn
Ap =A.A. . .A
19/164

p tha s
Khi
ajp , i,j=1, 2,. . . ,n
cho ta s ng i khc nhau t nh i n nh j qua p-1 nh trung gian.
Ma trn k ca th c hng c nh ngha mt cch hon ton tng t.
Th d 2. th c hng G1 cho trong hnh 1 c ma trn k l ma trn sau:

Lu rng ma trn k ca th c hng khng phi l ma trn i xng.

Ch : Trn y chng ta ch xt n th. Ma trn k ca a th c th xy dng
hon ton tng t, ch khc l thay v ghi 1 vo v tr a[i,j] nu (i,j) l cnh ca th,
chng ta s ghi k l s cnh ni hai nh i, j.
Trong rt nhiu vn ng dng ca l thuyt th, mi cnh e=(u,v) ca th c
gn vi mt con s c(e) (cn vit l c(u,v) gi l trng s ca cnh e. th trong trng
hp nh vy c gi l th c trng s. Trong trng hp th c trng s, thay v
m trn k, biu din th ta s dng ma trn trng s.
C= {c[i,j], i,j=1, 2,. . .,n}
vi
c[i,j]=c(i,j) nu (i,j) E
v c[i,j]= nu (i,j) E

20/164

trong s , tu tng trng hp c th, c th c t bng mt trong cc gi tr

sau: 0, + , - .
u im ln nht ca phng php biu din th bng ma trn k (hoc ma trn trng
s) l tr li cu hi: Hai nh u,v c k nhau trn th hay khng, chng ta ch phi
thc hin mt php so snh. nhc im ln nht ca phng php ny l: khng ph
thuc vo s cnh ca th, ta lun phi s dng n2 n v b nh lu tr ma trn
k ca n.

DANH SCH CNH (CUNG)

Trong trng hp th tha ( th c s cnh m tho mn bt dng thc: m<6n) ngi
ta thng dng cch biu din th di dng danh sch cnh.
Trong cch biu din th bi danh sch cnh (cung) chng ta s lu tr danh sch tt
c cc cnh (cung) ca th v hng (c hng). Mt cnh (cung) e=(x,y) ca th
s tng ng vi hai bin Dau[e], Cuoi[e]. nh vy, lu tr th ta cn s dng 2m
n v b nh. Nhc im ca cch biu din ny l xc nh nhng nh no ca
th l k vi mt nh cho trc chng ta phi lm c m php so snh (khi duyt qua
danh sch tt c cc cnh ca th).
Ch : Trong trng hp th c trng s ta cn thm m n v b nh lu tr trng
s ca cc cnh.
Th d 3. Danh sch cnh (cung) ca th G (G1) cho trong hnh 1 l:

21/164

DANH SCH K
Trong rt nhiu vn ng dng ca l thuyt th, cch biu din th di dng
danh sch k l cch biu din thch hp nht c s dng.
Trong cch biu din ny, vi mi nh v ca th chng ta lu tr danh sch cc nh
k vi n, m ta s k hiu l
Ke(v)= ? u V: (v,u) E?
Khi vng lp thc hin vi mi mt phn t trong danh sch ny theo th t cc phn
t c sp xp trong n s c vit nh sau:
for u Ke(v) do. . .
Chng hn, trn PASCAL c th m t danh sch ny nh sau (Gi l cu trc Forward
Star):
22/164

Const
m=1000; ? m-so canh ?
n= 100; ? n-so dinh ?
var
Ke:array[1..m] of integer;
Tro:array[1..n+1] of integer;
Trong Tro[i] ghi nhn v tr bt u ca danh sch k ca nh i, i=1, 2,. . .,n,
Tro[n+1]=2m+1.
Khi dng lnh qui c
for u Ke(v) do
begin
....
end.
C th thay th bi cu trc lnh c th trn PASCAL nh sau
For i:=Tro[v] to Tro[v+1]-1 do
Begin
U:=Ke[i];
....
End;
Trong rt nhiu thut ton lm vic vi th chng ta thng xuyn phi thc hin cc
thao tc: Thm hoc bt mt s cnh. Trong trng hp ny cu trc d liu dng
trn l khng thun tin. Khi nn chuyn sang s dng danh sch k lin kt (Linked
Adjancency List) nh m t trong chng trnh nhp danh sch k ca th t bn
phm v a danh sch ra mn hnh sau y:
Program AdjList;

23/164

Const
maxV=100;
Type
link=^node;
node=record
v:integer;
next:link;
End;
Var
j,x,y,m,n,u,v:integer;
t:link;
Ke:array[1. .Vmax] of link;
Begin
Write(Cho so canh va dinh cua do thi:); readln(m,n);
(*Khoi tao*)
for j:=1 to n do Ke[j]:=nil;
for j:=1 to m do
begin
write(Cho dinh dau va cuoi cua canh ,j,:);
readln(x,y);
new(t); t^.v:=x, t^.next:=Ke[y]; Ke[y]:=t;
new(t); t^.v:=y, t^.next:=Ke[x]; Ke[x]:=t;

24/164

end;
writeln(Danh sach ke cua cac dinh cua do thi:);
for J:=1 to m do
begin
writeln(Danh sachcac dinh ke cua dinh ,j,:);
t:=Ke[j];
while t^.next<>nil do
begin
write(t^.v:4);
t:=t^.next;
end;
end;
readln;
End.
Th d 4. Danh sch k ca cc th trong hnh 1 c m t trong hnh sau:
nh u

25/164

nh u

Hnh 2. Danh sch k ca th v hng G v c hng G1 cho trong hnh 1

rng trong cch biu din ny chng ta cn phi s dng c m+n n v b
nh.Trong cc thut ton m t cc phn tip theo hai cu trc danh sch k v ma
trn trng s c s dng thng xuyn.

26/164

Danh sch cnh(cung)

Trong trng hp th tha ( th c s cnh m tho mn bt dng thc: m<6n) ngi
ta thng dng cch biu din th di dng danh sch cnh.
Trong cch biu din th bi danh sch cnh (cung) chng ta s lu tr danh sch tt
c cc cnh (cung) ca th v hng (c hng). Mt cnh (cung) e=(x,y) ca th
s tng ng vi hai bin Dau[e], Cuoi[e]. nh vy, lu tr th ta cn s dng 2m
n v b nh. Nhc im ca cch biu din ny l xc nh nhng nh no ca
th l k vi mt nh cho trc chng ta phi lm c m php so snh (khi duyt qua
danh sch tt c cc cnh ca th).
Ch : Trong trng hp th c trng s ta cn thm m n v b nh lu tr trng
s ca cc cnh.
Th d 3. Danh sch cnh (cung) ca th G (G1) cho trong hnh 1 l:

27/164

Danh sch k
Trong rt nhiu vn ng dng ca l thuyt th, cch biu din th di dng
danh sch k l cch biu din thch hp nht c s dng.
Trong cch biu din ny, vi mi nh v ca th chng ta lu tr danh sch cc nh
k vi n, m ta s k hiu l
Ke(v)= ? u V: (v,u) E?
Khi vng lp thc hin vi mi mt phn t trong danh sch ny theo th t cc phn
t c sp xp trong n s c vit nh sau:
for u Ke(v) do. . .
Chng hn, trn PASCAL c th m t danh sch ny nh sau (Gi l cu trc Forward
Star):
Const
m=1000; ? m-so canh ?
n= 100; ? n-so dinh ?
var
Ke:array[1..m] of integer;
Tro:array[1..n+1] of integer;
Trong Tro[i] ghi nhn v tr bt u ca danh sch k ca nh i, i=1, 2,. . .,n,
Tro[n+1]=2m+1.
Khi dng lnh qui c
for u Ke(v) do
begin
....
end.
28/164

C th thay th bi cu trc lnh c th trn PASCAL nh sau

For i:=Tro[v] to Tro[v+1]-1 do
Begin
U:=Ke[i];
....
End;
Trong rt nhiu thut ton lm vic vi th chng ta thng xuyn phi thc hin cc
thao tc: Thm hoc bt mt s cnh. Trong trng hp ny cu trc d liu dng
trn l khng thun tin. Khi nn chuyn sang s dng danh sch k lin kt (Linked
Adjancency List) nh m t trong chng trnh nhp danh sch k ca th t bn
phm v a danh sch ra mn hnh sau y:
Program AdjList;
Const
maxV=100;
Type
link=^node;
node=record
v:integer;
next:link;
End;
Var
j,x,y,m,n,u,v:integer;
t:link;
Ke:array[1. .Vmax] of link;

29/164

Begin
Write(Cho so canh va dinh cua do thi:); readln(m,n);
(*Khoi tao*)
for j:=1 to n do Ke[j]:=nil;
for j:=1 to m do
begin
write(Cho dinh dau va cuoi cua canh ,j,:);
readln(x,y);
new(t); t^.v:=x, t^.next:=Ke[y]; Ke[y]:=t;
new(t); t^.v:=y, t^.next:=Ke[x]; Ke[x]:=t;
end;
writeln(Danh sach ke cua cac dinh cua do thi:);
for J:=1 to m do
begin
writeln(Danh sachcac dinh ke cua dinh ,j,:);
t:=Ke[j];
while t^.next<>nil do
begin
write(t^.v:4);
t:=t^.next;
end;
end;

30/164

readln;
End.
Th d 4. Danh sch k ca cc th trong hnh 1 c m t trong hnh sau:
nh u

nh u

Hnh 2. Danh sch k ca th v hng G v c hng G1 cho trong hnh 1

rng trong cch biu din ny chng ta cn phi s dng c m+n n v b
nh.Trong cc thut ton m t cc phn tip theo hai cu trc danh sch k v ma
trn trng s c s dng thng xuyn.

31/164

Cc thut ton tm kim trn th v ng

dng
Rt nhiu thun ton trn th c xy dng trn c s duyt tt c cc nh ca
th sao cho mi nh ca n c ving thm ng mt ln. V vy, vic xy dng
nhng thut ton cho php duyt mt cch h thng tt c cc nh ca th l mt
vn quan trng thu ht s quan tm nghin cu ca nhiu tc gi. Nhng thut ton
nh vy chng ta s gi l thut ton tm kim trn th. Trong mc ny chng ta s
gii thiu hai thut ton tm kim c bn trn th: Thut ton tm kim theo chiu su
(Depth Firt Search) v Thut ton tm kim theo chiu rng (Breadth First Search) v
ng dng ca chng vo vic gii mt s bi ton trn th.
Trong mc ny chng ta s xt th v hng G=(V,E), vi nh n v m cnh.
Chng ta s quan tm n vic nh gi hiu qu ca cc thut ton trn th, mmt
trong nhng c trng quan trng nht l phc tp tnh ton, tc l s php ton m
thut ton cn phi thc hin trong tnh hung xu nht c biu din nh hm ca kch
thc u vo ca bi ton. Trong cc thut ton trn th, u vo l th G=(V,E),
v vy, kch thc ca bi ton l s nh n v s cnh m ca th. Khi phc tp
tnh ton ca thut ton s c biu din nh l hm ca hai bin s f(n,m) l s php
ton nhiu nht cn phi thc hin theo thut ton i vi mi th n nh v m cnh.
Khi so snh tc tng ca hai hm nhn gi tr khng m f(n) v g(n) chng ta s s
dng k hiu sau:
f(n)=O(g(n))

tm c cc hng s C, N 0 sao cho

f(n) C g(n) vi mi n N.
Tng t nh vy nu f(n1, n2,. . . ,nk), g(n1, n2,. . . ,nk) l cc hm nhiu bin ta vit
f(n 1 , n 2 ,. . . ,nk) = O(g(n 1 , n 2 ,. . . ,nk))

tm c cc hng s C,N >0 sao cho

f(n 1 , n 2 ,. . . ,nk) C g(n 1 , n 2 ,. . . ,nk) vi mi n 1 , n 2 ,. . . ,nk N.

32/164

Nu phc tp tnh ton ca thut ton l O(g(n)) th ta s cn ni l n i hi thi

gian tnh c O(g(n)).

TM KIM THEO CHIU SU TRN TH

tng chnh ca thut ton c th trnh by nh sau. Ta s bt u tm kim t mt
nh v0 no ca th. Sau chn u l mt nh tu k vi v0 v lp li qu trnh
i vi u. bc tng qut, gi s ta ang xt nh v. Nu nh trong s cc nh k vi
v tm c nh w l cha c xt th ta s xt nh ny (n s tr thnh xt) v bt
u t n ta s bt u qu trnh tm kim cn nu nh khng cn nh no k vi v l
cha xt th ta ni rng nh ny duyt xong v quay tr li tip tc tm kim t nh
m trc ta n c nh v (nu v=v0, th kt thc tm kim). C th ni nm na l
tm kim theo chiu su bt u t nh v c thc hin trn c s tm kim theo chiu
su t tt c cc nh cha xt k vi v. Qu trnh ny c th m t bi th tc qui
sau y:
Procedure DFS(v);
(*tim kiem theo chieu sau bat dau tu dinh v; cac bien Chuaxet, Ke la bien toan cuc*)
Begin
Tham_dinh(v);
Chuaxet[v]:=false;
For u Ke(v) do
If Chuaxet[u] then DFS(u);
End; (*dinh v da duyet xong*)
Khi , tm kim theo chiu su trn th c thc hin nh thut ton sau:
Begin
(*Initialization*)
for v V do Chuaxet[v]:=true;
for v V do

33/164

if Chuaxet[v] then DFS(v);

End.
R rng lnh gi SFS(v) s cho php n thm tt c cc nh thuc cng thnh phn
lin thng vi nh v, bi v sau khi thm nh l lnh gi n th tc DFS i vi tt
c cc nh k vi n. Mt khc, do mi khi thm nh v xong, bi?n Chuaxet[v] c
t li gi tr false nn mi nh s c thm ng mt ln. Thut ton ln lt s tin
hnh tm kim t cc nh cha c thm , v vy, n s xt qua tt c cc nh ca
th (khng nht thit phi l lin thng).
nh gi phc tp tnh ton ca th tc, trc ht nhn thy rng s php ton cn
thc hin trong hai chu trnh ca thut ton (hai vng for chng trnh chnh) l c
n. Th tc DFS phi thc hin khng qu n ln. Tng s php ton cn pha thc hin
trong cc th tc ny l O(n+m), do trong cc th tc ny ta phi xt qua tt c cc cnh
v cc nh ca th. Vy phc tp tnh ton ca thut ton l O(n+m).
Th d 1. Xt th cho trong hnh 1 gm 13 nh, cc nh c nh s t 1 n 13
nh sau:

Hnh 1
Khi cc nh ca th c nh s li theo th t chng c thm theo th tc
tm kim theo chiu su m t trn nh hnh 2. Gi thit rng cc nh trong danh sch
k ca nh v (Ke(v)) c sp xp theo th t tng dn ca ch s.

34/164

Hnh 2. Ch s mi (trong ngoc) ca cc nh c nh li theo th t chng c

thm trong thut ton tm kim theo chiu su.
Thut ton tm kim theo chiu su trn th v hng trnh by trn d dng c th
m t li cho th c hng. Trong trng hp th c hng, th tc DFS(v) s cho
php thm tt c cc nh u no m t v c ng i n u. phc tp tnh ton ca
htut ton l O(n+m).

35/164

Tm kim theo chiu rng trn th

rng trong thut ton tm kim theo chiu su nh c thm cng mun s cng
sm tr thnh duyt xong. iu l h qu tt yu ca vic cc nh c thm s
c kt np vo trong ngn xp (STACK). Tm kim theo chiu rng trn th, nu
ni mt cch ngn gn, c xy dng trn c s thay th ngn xp (STACK) bi hng
i (QUEUE). Vi s ci bin nh vy, nh c thm cng sm s cng sm tr thnh
duyt xong (tc l cng sm di khi hng i). Mt nh s tr thnh duyt xong
ngay sau khi ta xt xong tt c cc nh k (cha c thm) vi n. Th tc c th m
t nh sau:
Procedure BFS(v);
(*Tim kiem theo chieu rong bat dau tu dinh v, cac bien Chuaxet, Ke la bien cuc bo*)
begin
QUEUE:= ;
QUEUE v; (*ket qua nap vao QUEUE*)
Chuaxet[v]:=false;
While QUEUE<> do
Begin
p QUEUE:; (*lay p tu QUEUE:*)
Tham_dinh(p);
For u Ke(v) do
If Chuaxet[u] them
Begin
QUEUE u;
Chuaxet[u]:=false;
End;
36/164

End;
end;
Khi , tm kim theo chiu rng trn th c thc hin nh thut ton sau:
Begin
(*Initialization*)
for f V do Chuaxet[v]:=true;
for v V do
if Chuaxet[v] then BFS(v);
End.
Lp lun tng t nh trong th tc tm kim theo chiu su, c th ch ra c rng
lnh gi BFS(v) s cho php thm n tt c cc nh thuc cng thnh phn lin thng
vi nh v, v mi nh ca th s c thm ng mt ln. phc tp tnh ton
ca thut ton l O(m+n).
Th d 2. Xt th xt trong hnh 1. Th t thm nh ca th theo thut ton tm
kim theo chiu rng c ghi trong ngoc.

37/164

Hnh3. Ch s mi (trong ngoc) ca cc nh c nh li theo th t chng c

thm trong thut ton tm kim theo chiu su.

38/164

Tm ng i v kim tra tnh lin thng

Trong mc ny ta xt ng dng cc thut ton tm kim m t trong cc mc trc vo
vic gii bi ton c bn trn th: bi ton v tm ng i v bi ton v xc nh
tnh lin thng ca th.7

Bi ton tm ng i gia hai nh:

Gi s s v t l hai nh no ca th. Hy tm ng i t s n t.Nh trn phn
tch, th tc DFS(s) (BS(s)) s cho thm tt c cc nh thuc cng mt thnh phn lin
thng vi s. v vy, sau khi thc hin xong th tc, nu Chuaxet[t]=true, th iu c
ngha l khng c ng i t s n t, cn nu Chuaxet[t]=false th t thuc cng thnh
phn lin thng vi s, hay ni mt cch khc: tn ti ng i t s n t. Trong trng
hp tn ti ng i, ghi nhn ng i, ta dng thm biu thc Truoc[v] ghi nhn
nh i trc nh v trong ng i tm kim t s n v. Khi , i vi th tc DFS(v)
cn sa i cu lnh trong n nh sau:
If Chuaxet[u] then
Begin
Truoc[u]:=v;
DFS(u);
End;
Cn i vi th tc BFS(v) cn sa i cu ln if trong n nh sau:
If Chuaxet [u] then
Begin
QUEUE u;
Chuaxet[u]:=false;
Truoc[u]:=p;
End;

39/164

Ch : ng i tm c theo thut ton tm kim theo chiu rng l ng i ngn

nht (theo s cnh) t s n t. iu ny suy trc tip t th t thm nh theo thut ton
tm kim theo chiu rng.

Tm cc thnh phn lin thng ca th:

Hy cho bit th gm bao nhiu thnh phn lin thng v tng thnh phn lin thng
ca n l gm nhng nh no.
Do th tc DFS(v) (BFS(s)) cho php thm tt c cc nh thuc cng mt thnh phn
lin thng vi s, nn s thnh phn lin thng ca th bng s ln gi n th tc ny.
Vn cn li l cch ghi nhn cc nh trong tng thnh phn lin thng. Ta dng thm
bin Index[v] ghi nhn ch s ca thnh phn lin thng cha nh v, v dng thm
bin Inconnect m s thnh phn lin thng (bin ny cn khi to gi tr 0). Th tc
Tham_dinh(v) trong cc th tc DFS(v) v BFS(v) c nhim v gn: Index[v]:=connect,
cn cu ln if trong cc chng trnh chnh gi n cc th tc ny cn c sa li nh
sau:
Inconnect:=0;
If Chuaxet[v] then
Begin
Inconnect:=Inconnect+1;
DFS(v); (*BFS(v)*)
End;
Kt thc vng lp th hai trong chng trnh chnh, Inconnect cho s thnh phn lin
thng ca th, cn bin mng Index[v], v V cho php lit k cc nh thuc cng
mt thnh phn lin thng.
Chng trnh PASCAL gii bi ton trn c th vit nh sau:
? CHUONG TRINH TIM DUONG DI VA KIEM TRA TINH LIEN THONG THEO
CAC THUAT TOAN TIM KIEM TREN DO THI?
uses crt;
var
a:array[1..20,1..20] fo byte;
40/164

QUEUE, Chuaxet, Truoc: array[1..20] of byte;

i,j,n,solt,k,s,t: integer;
Stop: boolean;
Ch: char;
Procedure Nhapsolieu;
Begin
Write(Cho so dinh cua do thi:); readln(n);
Writeln(Nhap so lieu ma tran ke:);
For i:= 1 to n do
Begin
For j:= i+1 to n do
Begin
Write(a[,i,,,j,]=); readln(a[i,j]);
End;
a[i,j}:=0; writeln;
End;
End;
{===========================}
Procedure readfile;
Var f:text; fn:string;
Begin
Write( Cho ten file du lieu:); readln (fn);

41/164

Assign(fnfn); reset(f); readln(f,n);

Writeln(Nhap so lieu ma tran ke:);
For i:= 1 to n do
For j:=1 to n do read(f, a[i,j});
Close(f);
End;
{===========================}
Procedure Insolieu;
Begin
Writeln(Ma tran ke:);
For i:= 1 to n do
Begin
For j:=1 to n do write(a[i,j]:3);
Writeln;
End;
End;
{===============================}
Procedure Ketqualienthon;
Begin
Insolieu;
If solt=1 then writeln(Do thi la lien thong)
Else

42/164

Begin
Wriyeln(Thanh phan lien thon thu ,i, gom cac dinh:);
For j:=1 to n do if Chuaxet[j]=i then write(j:3); writeln;
End;
Write(Go Enter de tiep tuc#7); readln;
End;
{========================================}
Procedure BFS(i:integer);
(*tim kiem theo chieu rong bat dau tu dinh i*);
var u, dauQ, CuoiQ,: integer;
begin
dauQ=1; cuoiQ:=1;
QUEUE[cuoiQ]:=i; Chuaxet[i]:=Solt;
While dauQ<=cuoiQ do
Begin
U:= QUEUE[sauQ]; dauQ:=dauQ+1;
For j:=1 to n do
If a[u,j]=1) and (Chuaxet[j]=0) then
Begin
cuoiQ:=cuoiQ+1; QUEUE:[cuoiQ]:=j;
Chuaxet[j]:=Solt; Truoc[j]:=u;
End;

43/164

End;
End; ? of procedure BFS ?
{==================================}
Procedure DFS(v:integer);
(*Tim kiem theo chieu sau bat dau tu dinh v*);
var U: integer;
begin
Chuaxet[v]:=solt;
For u:=1 to n do
If (a[v,u]=1) and (Chuaxet[u]=0) then
Begin
Truoc[u]:=v;
DFS9(u);
End;
End;
{=================================}
Procedure Lienthong;
Begin
? Khoi toa so lieu ?
for j:=1 to n do Chuaxet[j]:=0;
solt:=0;
for i:=1 to n do

44/164

if Chuaxet[i]=0 then
begin
solt:=solt+1;
? BFS(i); ? DFS(i);
end;
Ketqualienthong;
End;
{===============================}
Procedure Ketquaduongdi;
Begin
If Truoc[t]=0 then writeln(Khong co duong di tu , s, den ,t)
Else
Begin
Writeln(Duong di tu ,s, den ,t, la:);
J:=t;
Write(t,<==);
While Truoc[j]<>s do
Begin
Write(Truoc[g], <==);
J:=Truoc[j];
End;
Writeln(s);

45/164

End;
Write(Go Enter de tiep tuc#7); readln;
End;
{============================}
Procedure duongdi;
Begin
Insolieu;
Write(Tim duon di tu dinh:); readln(s);
Write( den dinh:); readln(t);
For j:=1 to n do ? Khoi tao so lieu ?
Begin
Truoc[j[:=0;
Chuaxet[j]:=0;
End;
Silt:=1; BFS(s); ? DFS(s); ?
Ketquaduondi;
End;
{============================}
Procedure menu;
Begin
Clrscr;
Writeln(TIM DUONG DI VA KIEM TRA TINH LIEN THONG);

46/164

Writeln(CUA DO THIJ THEO THUAT TOAN TIM KIEM TREN DO THI);

Writeln(===============================================);
Writeln( 1. Nhap so lieu tu ban phim);
Writeln( 2. Nhap so lieu tu file);
Writeln( 3. Kiem tra tinh lien thong);
Writeln( 4. Tim duong di giua hai dinh);
Writeln( 5. Thoat);
Writeln(--------------------------------------------------------------);
Write(Hay go phim so de chon chuc nang#7);
Ch:=readkey;
Writeln(ch);
End;
{===================================}
? Main program ?
Begin
repeat
menu;
case ch of
1:Nhapsolieu;
2:Readfile;
3:Lienthong;
4:Duongdi;

47/164

until (ch=5) or (upcase (ch)=Q);

End.

48/164

 th Euler v th Hamiton
Trong chng ny chng ra s nghin cu hai dng th c bit l th Euler v
th Hamilton. Di y, nu khng c gii thch b sung, thut ng th c dng
ch chung a th v hng v c hng, v thut ng cnh s dng ch chung cnh
ca th v hng cng nh cung ca th c hng.

TH EULER
nh ngha 1. Chu trnh n trong th G i qua mi cnh ca n mt ln c gi
l chu trnh Euler. ng i n trong G i qua mi cnh ca n mt ln c gi l
ng i Euler. th c gi l th Euler nu n c chu trnh Euler, v gi l
th na Euler nu n c ng i Euler.
R rng mi th Euler lun l na Euler, nhng iu ngc li khng lun ng.
Th d 1. th G1 trong hnh 1 l th Euler v n c chu trnh Euler a, e, c, d, e, b,
a. th G3 khng c chu trnh Euler nhng n c ng i Euler a, c, d, e, b, d, a, b,
v th G3 l th ca Euler. th G2 khng c chu trnh cng nh ng i Euler.

Hnh 1. th G 1 , G 2 , G 3
Th d 2. th H2 trong hnh 2 l th Euler v n c chu trnh Euler a, b, c, d, e, a.
th H3 khng c chu trnh Euler nhng n c ng i Euler c, a, b, c, d, b v th H3
l th na Euler. th H1 khng c chu trnh cng nh ng i Euler.

49/164

Hnh 2. th H 1 , H 2 , H 3
iu kin cn v mt th l mt th Euler c Euler tm ra vo nm 1736
khi ng gii quyt bi ton hc ba ni ting th gii thi v by ci cu thnh ph
Konigsberg v y l nh l u tin ca l thuyt th.
nh l 1 (Euler). th v hng lin thng G l th Euler khi v ch khi mi nh
ca G u c bc chn.
chng minh nh l trc ht ta chng minh b :
B . Nu bc ca mi nh ca th G khng nh hn 2 th G cha chu trnh.
Chng minh.
Nu G c cnh lp th khng nh ca b l hin nhin. V vy gi s G l n th.
Gi v l mt nh no ca G. Ta s xy dng theo qui np ng i
v v1 v2 . . .
trong v1 l nh k vi v, cn vi i1 chn vi+1 # vi-l (c th chn vi+1 nh vy l v
deg(vi) 2). Do tp nh ca G l hu hn , nn sau mt s hu hn bc ta phi quay
li mt nh xut hin trc . Gi nh u tin nh th l vk. Khi , on ca
ng i xy dng nm gia hai nh vk l 1 chu trnh cn tm.
Chng minh nh l:
Cn. Gi s G l th Euler tc l tn ti chu trnh Euler P trong G. Khi c mi ln
chu trnh P i qua mt nh no ca G bc ca nh tng ln 2. mt khc mi cnh
ca th xut hin trong P ng mt ln, suy ra mi nh ca th iu c bc chn.
.Quy np theo s nh v s cnh ca G. Do G lin thng v deg(v) l s chn nn
bc ca mi nh ca n khng nh hn 2. T theo b G phi cha chu trnh C.
Nu C i qua tt c cc cnh ca G th n chnh l chu trnh Euler. Gi s C khng i

50/164

qua tt c cc cnh ca G. Khi loi b khi G tt c cc cnh thuc C ta thu c

mt th mi H vn c bc l chn. Theo gi thit qui np, trong mi thnh phn lin
thng ca H iu tm c chu trnh Euler. Do G l lin thng nn trong mi thnh phn
ca H c t nht mt nh chung vi chu trnh C. V vy, ta c th xy dng chu trnh
Euler trong G nh sau: bt u t mt nh no ca chu trnh C, i theo cc cnh ca
C chng no cha gp phi nh khng c lp ca H. Nu gp phi nh nh vy ta s
i theo chu trnh Euler ca thnh phn lin thng ca H cha nh . Sau li tip tc
i theo cnh ca C cho n khi gp phi nh khng c lp ca H th li theo chu trnh
Euler ca thnh phn lin thng tng ng trong Hv.v (xem hnh 3). Qu trnh s kt
thc khi ta tr v nh xut pht , tc l thu c chu trnh i qua mi cnh ca th
ng mt ln.

Hnh 3. Minh ho cho chng minh nh l 1.

H qu 2. th v hng lin thng G l na Euler khi v ch khi n c khng qu 2
nh bc l.
Chng minh. Thc vy , nu G c khng qu 2 nh bc l th s nh bc l ca n ch
c th l 0 hoc 2. Nu G khng c nh bc l th theo nh l 1, n l th Euler. Gi
s G c 2 nh bc l l u v v. Gi H l th thu c t G bng cch thm vo G mt
nh mi w v hai cnh (w,u) v(w,v). Khi tt c cc nh ca H iu c bc chn,
v th theo nh l 1, n c chu trnh Euler C. Xo b khi chu trnh ny nh w v hai
cnh k n ta thu c ng i Euler trong th G.
Gi s G l th Euler, t chng minh nh l ta c th tc sau tm chu trnh Euler
trong G.
Procedure Euler_Cycle;
Begin
51/164

STACK:= ; CE:= ;
Chon u la mot dinh nao do cua do thi;
STACK u;
While STACK<> do
Begin
X:=top(STACK); (* x la phan tu dau STACK)
If Ke(x)<> then
Begin
Y:=dinh dau tien trong danh sach Ke(x);
STACK y;
(* loai bo canh (x,y) khoi do thi *)
Ke(x):=Ke(x)\ ? y ? ;
Ke(y):=Ke(y)\ ? x ? ;
End
Else
Begin
x STACK; CE x;
End;
End;
End;

Gi s G l th Euler, thut ton n gin sau y cho php xc nh chu trnh Euler
khi lm bng tay.

52/164

Thut ton Flor

Xut pht t mt nh u no ca G ta i theo cc cnh ca n mt cch tu ch cn
tun th 2 qui tc sau:
(1) Xo b cnh i qua ng thi xo b c nhng nh c lp to thnh.
(2) mi bc ta ch i qua cu khi khng cn cch la chon no khc.
Chng minh tnh ng n ca thut ton.
Trc tin ta ch ra rng th tc trn c th thc hin mi bc. Gi s ta i n mt
nh v no , khi nu v#u th th con cn li H l lin thng v cha ng hai
nh bc l l v v u. Theo h qu trong H c ng i Euler P t v ti u. Do vic xo
b cnh u tin ca ng i P khng lm mt tnh lin thng ca H, t suy ra th
tc c th thc hin mi bc. Nu v=u th lp lun trn s vn ng chng no vn
cn cnh k vi u.
Nh vy ch cn phi ch ra th tc trn dn n ng i Euler. Thc vy trong G
khng th cn cnh cha i qua khi m ta s dng cnh cui cng k vi u (trong trng
hp ngc li, vic loi b mt cnh no k vi mt trong s nhng cnh cn li
cha i qua s dn n mt th khng lin thng, v iu l mu thun vi gi
thit ii).
Chng minh tng t nh trong nh l 1 ta thu c kt qu sau y cho th c
hng.
nh l 2. th c hng lin thng mnh l th Euler khi v ch khi
Deg+(v)=deg- (v), v V.

53/164

 th Hamilton
Trong mc ny chng ta xt bi ton tng t nh trong mc trc ch khc l ta quan
tm n ng i qua tt c cc nh ca th, mi nh ng mt ln. S thay i
tng chng nh l khng ng k ny trn thc t dn n s phc tp ho vn
cn gii quyt.
nh ngha 2. ng i qua tt c cc nh ca th mi nh ng mt ln c gi
l ng i Hamilton. Chu trnh bt u t mt nh v no qua tt c cc nh cn li
mi nh ng mt ln ri quay tr v v c gi l chu trnh Hamilton. th G c
gi l th Hamilton nu n cha chu trnh Hamilton v gi l th na Hamilton nu
n c ng i Hamilton.
R rng th Hamilton l na Hamilton, nhng iu ngc li khng cn ng.
Th d 3. Trong hnh 4: G3 l Hamilton, G2 l na Hamilton cn G1 khng l na
Hamilton.

Hnh 4. th Hamilton G3, na Hamilton G2 , v G1.

Cho n nay vic tm mt tiu chun nhn bit th Hamilton vn cn l m, mc d
y l mt vn trung tm ca l thuyt th. Hn th na, cho n nay cng cha
c thut ton hiu qu kim tra mt th c l Hamilton hay khng. Cc kt qu thu
c phn ln l iu kin mt th l th Hamilton. Phn ln chng iu c
dng "nu G c s cnh ln th G l Hamilton". Mt kt qu nh vy c pht biu
trong nh l sau y.
nh l 3 (Dirak 1952). n th v hng G vi n>2 nh, mi nh c bc khng
nh hn n/2 l th Hamilton.
Chng minh:
Thm vo th G k nh mi v ni chng vi tt c cc nh ca G. gi s k l s
nh nht cc nh cn thm vo cho th thu c G l th Hamilton. Ta s ch
54/164

ra rng k=0. Thc vy, gi s ngc li l k >0. K hiu v, p, w, . . ., v l chu trnh

Hamilton trong G, trong v, w l nh ca G cn p l mt trong s cc nh mi. Khi
w khng k vi v v nu ngc li, ta khng cn s dng p v iu l mu thun
vi gi thit k nh nht. Hn th na nh (w chng hn) k vi w khng th i lin sau
nh v (k vi v) v rng khi c th thay
v p w . . . v w . . . v
bi v v . . . w w . . . v
bng cch o ngc on ca chu trnh nm gia w v v. T suy ra l s nh ca
th G khng k vi w l khng nh hn s nh k vi v (tc l t nht cng l bng
n/2+k), ng thi s nh ca G k vi w t ra l phi bng n/2+k. Do khng c nh
no ca G va khng k, li va k vi w, cho nn tng s nh ca th G (G c
n+k nh) khng t hn n+2k. Mu thun thu c chng minh nh l.
nh l sau l tng qut ho ca nh l Dirak cho th c hng:
nh l 4.
Gi s G l c hng lin thng vi n nh. Nu
deg+ (v)n/2, deg (v) n/2, v
th G l Hamilton.
C mt s dng th m ta c th bit khi no l th Hamilton. Mt v d nh vy
l th u loi. th u loi l th c hng m trong hai nh bt k ca n
c ni vi nhau bi ng mt cung. Tn u loi xut hin nh vy v th nh vy
c th dng biu din kt qu thi u bng chuyn, bng bn hay bt c mt tr chi
no m khng cho php ho. Ta c nh l sau:
nh l 5.
i) Mi th u loi l na Hamilton.
ii) Mi th u loi lin thng mnh l Hamilton.
Th d 4. th u loi D5, D6 c cho trong hnh 5.

55/164

Hnh 5. th u loi D5, u loi lin thng mnh D6

Thut ton lit k tt c cc chu trnh Hamilton ca th
Thut ton sau y c xy dng da trn c s thut ton quay lui cho php lit k tt
c cc chu trnh Hamilton ca th.
Procedure Hamilton(k);
(* liet ke cac chu trinh Hamilton thu duoc bang viec phat trien day dinh (X[1],. . . ,
X[k-1]) cua do thi G=(V,E) cho boi danh sach ke: Ke(v), v V *)
begin
for y Ke(X[k-1]) do
if (k =N+1) and (y=v0) then Ghinhan(X[1],. . . , X[n], v0)
else
if Chuaxet[y] then
begin
X[k]:=y;
Chuaxet[y]:=false;
Hamilton(k+1);
Chuaxet[y]:=true;

56/164

end;
end;
(* Main program*)
begin
for v V do Chuaxet[v]:=true;
X[1]:=0; (* v0 la mot dinh nao do cua do thi *)
Chuaxet[v0]:=false;
Hamilton(2);
end.
Th d 5. Hnh 6 di y m t cy tm kim theo thut ton va m t.

Hnh 6. th v cy lit k chu trnh Hamilton ca n theo thut ton quay lui
Trong trng hp th c khng qu nhiu cnh thut ton trn c th s dng kim
tra th c phi l Hamilton hay khng.

57/164

Cy v cy khung ca th
th v hng lin thng khng c chu trnh gi l cy. Khi nim cy ln u tin
c Cayley a ra vo nm 1857, khi ng s dng chng m mt dng cu trc
phn t ca cc hp cht ho hc trong ho hc hu c. Cy cn c s dng rng ri
trong rt nhiu lnh vc khc nhau, c bit trong tin hc, cy c s dng xy dng
cc thut ton t chc cc th mc, cc thut ton ct gi, truyn d liu v tm kim

CY V CC TNH CHT C BN CA CY
nh ngha1.
Ta gi cy l th v hng lin thng khng c chu trnh. th khng c chu trnh
c gi l rng.
Nh vy, rng l th m mi thnh phn lin thng ca n l mt cy.
Th d 1. Trong hnh 1 l mt rng gm 3 cy T1, T2, T3.

Hnh 1. Rng gm 3 cy T1, T2, T3.

C th ni cy l th v hng n gin nht. nh l sau y cho ta mt s tnh cht
ca cy.
nh l 1. Gi s G=(V,E) l th v hng n nh. Khi cc mnh sau y l
tng ng:
(1) T l cy;
(2) T khng cha chu trnh v c n-1 cnh;
(3) T lin thng v c n-1 cnh;

58/164

(4) T lin thng v mi cnh ca n iu l cu;

(5) Hai nh bt k ca T c ni vi nhau bi ng mt ng i n;
(6) T khng cha chu trnh nhng h c thm vo mt cnh ta thu c ng mt chu
trnh.
Chng minh. Ta s chng minh nh l theo s sau:
(1) (2) (3) (4) (5) (6) (1)
(1) (2) Theo nh ngha T khng cha chu trnh. Ta s chng minh bng qui np theo
s nh n cho khng nh: S cnh ca cy vi n nh l n-1. R rng khng nh ng
vi n=1. Gi s n>1. Trc ht nhn rng trong mi cy T c n nh u tm c t nht
mt nh l nh treo (tc l nh c bc l 1). Thc vy, gi v1, v2 , . . .,vk l ng
i di nht (theo scnh) trong T. Khi r rng v1 v vk l cc nh treo, v t v1 (vk)
khng c cnh ni vi bt c nh no trong s cc nh v2, v3 , . . .,vk (do th khng
cha chu trnh), cng nh vi bt c nh no khc ca th (do ng i ang xt di
nht). Loi b v1 v cnh (v1 , v2) khi T ta thu c cy T1 vi n-1 nh, m theo gi
thit qui np c n-2 cnh. Vy cy T c n-2+1 = n-1 cnh.
(2) (3) Ta chng minh bng phn chng. Gi s T khng lin thng. Khi T phn r
thnh k2 phn lin thng T1, T2,. . . Tk. Do T khng cha chu trnh nn mi Ti (i=1,2,.
. .,k) cng khng cha chu trnh, v th mi Ti l cy. Do nu gi n(Ti) v e(Ti) theo
th t l s nh v cnh ca Ti, ta c:
e(Ti) = n(Ti) 1, i= 1, 2, . . ., k,
suy ra
n-1 = e(T) = e(T1) + . . . + e(Tk)
= n(T1) + . . . n(Tk) k
= n(T) k < n-1
Mu thun thu c chng t l T lin thng.
(3) (4) Vic loi b mt cnh bt k khi T dn n th vi n nh v n-2 cnh r
rng l th khng lin thng. Vy mi cnh trong T u l cu.

59/164

(4) (5) Do T l lin thng nn hai nh bt k ca n c ni vi nhau bi mt ng

i n. Nu c cp nh no ca T c hai ng i n khc nhau ni chng, th t
suy ra th cha chu trnh, v v th cc cnh trn chu trnh ny khng phi l cu.
(5) (6) T khng cha chu trnh, bi v th nu c chu trnh th ho ra tm c cp
nh ca T c ni vi nhau bi hai ng i n. By gi, nu thm vo T mt cnh e
ni hai nh u v v no ca T. Khi cnh ny cng vi ng i n ni u vi v s
to thnh chu trnh trong T. Chu trnh thu c ny l duy nht, v nu thu c nhiu
hn mt chu trnh th suy ra trong T trc phi c sn chu trnh.
(6) (1) Gi s T khng lin thng. Khi gm t ra l 2 thnh phn lin thng. V
vy, nu thm vo T mt cnh ni hai nh thuc hai thnh phn lin thng khc nhau
ta khng thu c thm mt chu trnh no c. iu mu thun vi gi thit (6).
nh l c chng minh.

60/164

Cy khung ca th
nh ngha 2. th G v cy khung ca n c cho trong hnh 2

Hnh 2. th v cc cy khung ca n
nh l sau y cho bit s lng cy khung ca th y Kn:
nh l 2 (Cayley). S lng cy khung ca th K n l n n-2 .
nh l 2 cho thy s lng cy khung ca th l mt s rt ln. By gi ta xt
p dng ca thut ton tm kim theo chiu su v theo chiu rng trn th xy
dng cy khung ca th v hng lin thng. Trong c hai trng hp mi khi ta n
c nh mi u (tc Chuaxet[u]=true) t nh v th cnh (v, u) s c kt np vo cy
khung. Hai thut ton tng ng c trnh by trong hai th tc sau y.
Procedure stree_DFS(v);
(* tim kiem theo chieu sau ap dung vao tim tap canh cua cay khung T cua do thi vo
huong lien thong G cho boi danh sach ke. Cac bien Chuaxet, Ke, T la toan cuc*)
begin
Chuaxet[v]:=false;
For u Ke(v) do
If Chuaxet[u] then
Begin
T:=T ? (u,v);
STREE_DFS(u);

61/164

End;
end;
(* Main Program *)
begin
(* Initialition *)
for u V do Chuaxet[u]:=true;
T := ; (* T la tap canh cua cay khung *)
STREE_DFS(root); ( root la dinh nao do cua do thi *)
end.
Procedure Stree_BFS(v);
(* tim kiem theo chieu rong ap dung tim tap canh cua cau khung T cua do thi vo huong
lien thong G cho boi danh sach Ke *)
begin
Queue:= ;
Queue r;
Chuaxet[r]:=false;
While queue <> do
Begin
V queue;
For r Ke(v) do
If Chuaxet[u] then
Begin
Queue u;
62/164

Chuaxet[u]:=false;
T:= T ? (u,v);
End;
End;
end;
(* Main Program *);
begin
for u V do Chuaxet[u]:=true;
T := ; (* T la tap canh cua cay khung *)
Stree_BFS(root); (* root la mot dinh tuy y cua do thi *)
end.

Ch :
1. Lp lun tng t nh trong phn trc c th ch ra c rng cc thut ton m t
trn c phc tp tnh ton O(m+n).
2. Cy khung tm c theo th tc Stree_BFS() l cy ng i ngn nht t gc r n
tt c cc nh cn li ca th.

63/164

Xy dng tp cc chu trnh c bn ca

th
Bi ton xy dng cy khung ca th lin quan cht ch n mt s bi ton ng dng
khc ca l thuyt th: bi ton xy dng tp cc chu trnh c bn ca th m ta s
xt trong mc ny.
Gi s G=(V,E) l n th v hng lin thng, H=(V,T) l cy khung ca n. Cc
cnh ca th thuc cy khung ta s gi l cc cnh trong, cn cc cnh cn li s gi
l cnh ngoi.
nh ngha 3.
Nu thm mt cnh ngoi e E\T vo cy khung H chng ta s thu c ng mt chu
trnh trong H, k hiu chu trnh ny l Ce. Tp cc chu trnh
? = ? Ce : e E\T ?
c gi l tp cc chu trnh c bn ca th G.
Gi s A v B l hai tp hp, ta a vo php ton sau
A ? B = ( A ? B) \ ( A ? B).
Tp A ? B c gi l hiu i xng ca hai tp A v B.
Tn gi chu trnh c bn gn lin vi s kin l mi chu trnh ca th u c th thu
c t cc chu trnh c bn nh ch ra trong nh l sau y:
nh l 3.
Gi s G=(V,E) l th v hng lin thng, H=(V,T) l cy khung ca n. Khi
mi chu trnh ca th G iu c th biu din nh l hiu i xng ca mt s cc
chu trnh c bn.
Vic tm tp hp chu trnh c bn gi mt vai tr quan trng trong vn gii tch mng
in. C th hn, theo mi chu trnh c bn ca th tng ng vi mng in cn
phn tch ta s thit lp c mt phng trnh tuyn tnh theo nh lut Kirchoff: tng
hiu in th dc theo mt mch vng l bng khng. H thng phng trnh tuyn tnh
thu c cho php tnh ton hiu in th trn mi ng dy ca li in.

64/164

Ta s xy dng thut ton xy dng cc chu trnh c bn da trn th tc tm kim theo

chiu su trn th. Thut ton c cu trc tng t nh thut ton xy dng cy khung
theo th tc tm kim theo chiu su m t trong mc trc.
Thut ton xy dng tp cc chu trnh c bn.
Gi thit rng th G=(V,E) c m t bng danh sch Ke(v),v V.
Procedure Cycle(v);
(* tim kiem cac chu trinh co ban cua thanh phan lien thong chua dinh v; cac bien d, num
, stack, index la bien toan cuc *)
begin
d:=d+1; stack[d]:=v; num:=num+1;index[v]:=num;
for u Ke(v) do
if index[u]=0 then cycle(u)
else
if (u <> stack[d-1]) and (index[v]>index[u]) then
<Ghi nhan chu trinh voi cac dinh:
stack[d], stack[d-1],. . ., stack[c], voi stack[c]=u>
d:=d-1;
end;
(* Main Program *)
begin
for v V do Index[v]:=0;
num:=0; d:=0; stack[0]:=0;
for v V do
if Index[v]=0 then cycle(v);

65/164

end.
Ch : phc tp tnh ton ca thut ton va m t l O(? E? ? V? ).

66/164

Bi ton cy khung nh nht

Bi ton cy khung nh nht ca th l mt trong s nhng bi ton ti u trn th
tm c ng dng trong nhiu lnh vc khc nhau ca i sng. Trong mc ny chng
ta trnh by nhng thut ton c bn gii bi ton no. Trc ht chng ta pht biu
ni dung bi ton.
Cho G=(V,E) l th v hng lin thng vi tp nh V=? 1, 2, . . . ,n? v tp cnh E
gm m cnh. Mi cnh E ca th G c gn vi mt s khng m c(e), gi l di
ca n. Gi s H=(V,T) l cy khung ca th G. Ta gi di c(H) ca cy khung H
l tng di cc cnh ca n:
C(H) = ? c(e).

e T

Bi ton t ra l trong tt c cy khung ca th G hy tm cy khung vi di nh

nht. Cy khung nh vy nh vy c gi l cy khung nh nht ca th v bi ton
t ra c gi l bi ton cy khung nh nht.
minh ho cho nhng ng dng bi ton cy khung nh nht, di y, ta pht biu
hai m hnh thc t tiu biu ca n.
Bi ton xy dng h thng ng st. Gi s ta mun xy dng mt h thng ng
st ni n thnh ph sao cho hnh khch c th i t bt k mt thnh ph no n bt
k mt trong cc thnh ph cn li. Mt khc trn quan im kinh t i hi l chi ph
xy dng h thng ng phi nh nht. R rng th m nh l cc thnh ph cn
cc cnh l cc tuyn ng st ni cc thnh ph tng ng vi phng n xy dng
ti u phi l cy. V vy, bi ton t ra dn v bi ton tm cy khung nh nht trn
th y n nh, mi nh tng ng vi mt thnh ph, vi di trn cc cc cnh
chnh l chi ph xy dng ng ray ni hai thnh ph tng ng (ch l trong bi
ton ny ta gi thit l khng xy dng tuyn ng st c cc nh ga phn tuyn nm
ngoi cc thnh ph).
Bi ton ni mng my tnh. Cn ni mng mt h thng gm n my tnh nh s t 1
n n. Bit chi ph ni my i vi my j l c[i,j], i,j = 1, 2, . . . ,n ( thng thng chi ph
ny ph thuc vo di cp ni cn s dng). Hy tm cch ni mng sao cho tng chi
ph ni mng l nh nht.
gii bi ton cy khung nh nht, tt nhin c th lit k tt c cc cy khung ca
th v chn trong s cy khung y cy khung nh nht. Phng php nh vy, trong
trng hp th y , s i hi thi gian c nn-2 , v r rng khng th thc hin
c ngay c vi nhng th vi s nh c hng chc. Rt may l i vi bi ton

67/164

cy khung nh nht chng ta c nhng thut ton rt hiu qu gii chng. Chng
ta xt hai trong s nhng thut ton nh vy: Thut ton Kruskal v Thut ton Prim.

Thut ton Kruskal

Thut ton s xy dng tp cnh T ca cy khung nh nht H=(V,T) theo tng bc.
Trc ht sp xp cc cnh ca th G theo th t khng gim ca di. Bt u t
tp T= , mi bc ta s ln lt duyt trong danh sch cnh sp xp, t cnh c
di nh n cnh c di ln hn, tm ra cnh m vic b sung n vo tp T gm
n-1 cnh. C th, thut ton c th m t nh sau:
Procedure Kruskal;
Begin
T:= ;
While ? T ? < (n-1) and (E<> ) do
Begin
E:=E\ ? e ? ;
if (T ? ? e ? khng cha chu trnh) then T:= T ? ? e ? ;
End;
if ( ? T ? < n-1) then th khng lin thng;
End;
Th d 3.Tm cy khung nh nht ca th cho trong hnh 3 di.
Bc khi to. t T:= . Sp xp cc cnh ca th theo th t khng gim ca
di ta c dy:
(3,5) , (4,6) , (4,5) , (5,6) , (3,4) , (1,3) , (2,3) , (2,4) , (1,2)
dy di tng ng ca chng
4, 8, 9, 14, 16, 17, 18, 20, 23.

68/164

Hnh 3. th v cy khung nh nht

ba ln gp u tin ta ln lt b sung vo tp T cc cnh (3,5) , (4,6) , (4,5). R rng
nu thm cnh (5,6) vo T th s to thnh 2 cnh (4,5), (4,6) c trong T chu trnh.
Tnh hung tng t cng xy ra i vi cnh (3,4) l cnh tip theo ca dy. Tip theo
ta b sung cnh (1,3), (2,3) vo T v thu c tp T gm 5 cnh:
T = ? (3,5) , (4,6) , (4,5) , (1,3) , (2,3) ?
Chnh l tp cnh ca cy khung nh nht cn tm.
Chng minh tnh ng n ca thut ton.
R rng th thu c theo thut ton c n-1 cnh v khng c chu trnh, v vy theo
nh l 1 n l cy khung ca th G. Nh vy, ch cn phi ch ra rng T c di
nh nht. Gi s tn ti cy S ca th G m c(S) < c(T). K hiu ek l cnh u tin
trong dy cc cnh ca T xy dng theo thut ton va m t khng thuc S. khi
th con ca G sinh bi cy S c b sung cnh ek s cha mt chu trnh C duy nht i
qua ek. Do chu trnh C phi cha cnh e thuc S nhng khng thuc T nn th con
thu c t S bng cch thay cnh e ca n bi cnh ek (k hiu th l S) s l cy
khung. Theo cch xy dng c(ek) c(e) do c(S) c(S), ng thi s cnh chung ca
S v T tng thm 1 so vi s cnh chung ca S v T. Lp li qu trnh trn tng bc
mt ta c th bin i S thnh T v trong mi bc tng di khng tng, tc l c(T)
c(S). Mu thun thu c chng t T l cy khung nh nht.
V vic lp trnh thc hin thut ton.
Khi lng tnh ton nhiu nht ca thut ton chnh l bc sp xp cc cnh ca
th theo th t khng gim ca di la chn cnh b sung. i vi th m cnh
cn phi thc hin m log m php ton sp xp cc cnh ca th thnh dy khng
gim theo di. Tuy nhin, xy dng cy khung nh nht vi n-1 cnh, ni chung
ta khng cn phi sp th t ton b cc cnh m ch cn xt phn trn ca dy cha
r < m cnh. lm vic ta c th s dng cc th tc sp xp dng Vun ng (Heap
69/164

Sort). Trong th tc ny, to ng u tin ta mt c O(m) php ton, mi phn t

tip theo trong ng c th tm sau thi gian O(log m). V vy, vi ci tin ny thut
ton s mt thi gian c O(m+p) log m) cho vic sp xp cc cnh. Trong thc t tnh
ton s p nh hn rt nhiu so vi m.
Vn th hai trong vic th hin thut ton Kruskal l vic la chn cnh b sung
i hi phi c mt th tc hiu qu kim tra tp cnh T ? ? e} c cha chu trnh hay
khng. rng, cc cnh trong T cc bc lp trung gian s to thnh mt rng.
Cnh e cn kho st s to thnh chu trnh vi cc cnh trong T khi v ch khi c hai
nh u ca n thuc vo cng mt cy con ca rng ni trn. Do , nu cnh e khng
to thnh chu trnh vi cc cnh trong T, th n phi ni hai cy khc nhau trong T. v
th, kim tra xem c th b sung cnh e vo T ta ch cn kim tra xem n c ni hai
cy khc nhau trong T hay khng. Mt trong cc phng php hiu qu thc hin
vic kim tra ny l ta s phn hoch tp cc nh ca th ra thnh cc tp con khng
giao nhau, mi tp xc nh bi mt cy con trong T(c hnh thnh cc bc do
vic b sung cnh vo T). chng hn, i vi th trong v d 3, u tin ta c su tp
con 1 phn t: ? 1} , ? 2} , ? 3} , ? 4} , ? 5} , ? 6} . Sau khi b sung cnh (3,5), ta c
cc tp con ?1} , ?2} , ? 3,5} , ? 4} , ? 6} . bc th 3, ta chn cnh (4,5), khi hai
tp con c ni li v danh sch cc tp con l ? 1} , ?2} , ? 3,4,5,6} . Cnh c di
tip theo l (4,6), do hai u ca n thuc vo cng mt tp con?3,4,5,6} , nn n s to
thnh chu trnh trong tp ny. V vy cnh ny khng c chn. V thut ton s tip
tc chn cnh tip theo kho st
Nh vy, gii quyt vn th hai ny ta phi xy dng hai th tc: Kim tra xem
hai u u, v ca cnh e=(u,v) c thuc vo hai tp con khc nhau hay khng, v trong
trng hp cu tr li l khng nh, ni hai tp con tng ng thnh mt tp. Ch
rng mi tp con trong phn hoch c th lu tr nh l mt cy c gc, v khi mi
gc s c s dng lm nhn nhn bit tp con tng ng.Chng trnh trn Pascal
thc hin thut ton Kruskal vi nhng nhn xt va nu c th vit nh sau:
(* TM CY KHUNG NH NHT THEO THUT TON KRUSKAL CA TH
CHO BI DANH SCH CNH *)
uses crt;
type
arrn=array[1. .50] of integer;
arrm= array[1...50] of integer;
var
n,m, minL:integer;
70/164

Dau, cuoi, W:arrm;

DauT, CuoiT, Father:arrn;
Connect:boolean;
Procedure Nhapdl;
Var
i:integer;
Fanme:string;
F:text;
Begin
Write(Cho ten file du lieu:) readln(fname);
Assign(f,fname); reset(f);
Readln(f,n,m);
For i:=1 to m do readln(f, Dau[i], Cuoi[i], W[i]);
Close(f);
End;
Procedure Indulieu;
Var i:integer;
Begin
Writeln(So dinh ,n,. So canh ,m);
Writeln(Dinh dau Dinh cuoi Do dai);
For i:=1 to m do
Writeln(Dau[i]:4, Cuoi[i}:10, W[i]:12);

71/164

End;
Procedure Heap(First, Last:integer);
Var j,k,t1,t2,t3 : integer;
Begin
J:=first;
While (j<=trunc(last/2)) do
Begin
If (2*j<last) and W[2*j+1]<W[2*j]) then K:= 2*j+1
Else k"=2*j;
If W[k]<W[j} then
Begin
T1:=Dau[j]; t1:=Cuoi[j]; t3:=W[j];
Dau[j]:=Dau[k];Cuoi[j]:=Cuoi[k]; W[j]:=W[k];
Dau[k]:=t1; Cuoi[k]:=t2; W[k]:=t3;
J:=k;
End
Else j:=Last;
End;
End;
Function Find(i:integer):integer;
Var Tro:integer;
Begin

72/164

Tro:=i;
While Father[Tro]>0 do Tro:=Father[Tro];
Find:=Tro;
End;
Procedure Union(i,j:integer);
Var x:integer;
Begin
x:=father[i]+father[j];
if father[i]>father[j] then
begin
father[i]:=f;
father[j]:=x;
end
else
begin
father[j]:=i;
father[i]:=x;
end;
End;
Procedure Kruskal;
Var
I, Last, u,v,r1,r2, Ncanh, Ndinh:integer;

73/164

Begin
(* Khoi tao mang Father danh dau cay con va khoi tao Heap *)
for i:= 1 to n do father[i]:=-1;
for i:=trunc(m/2) downto 1 do Heap(i,m);
last:=m; Ncanh:=0; Ndinh:=0;
MinL:=0;
Connect:=true;
While (Ndinh<n-1) and (Ncanh<m) do
Begin
Ncanh:=Ncanh+1;
u:=dau[1];
v:=Cuoi[1];
(* Kiem tra u va v co thuoc cung mot cay con *)
r1:=find(u);
r2:=find(v);
if r1<>r2 then
begin
(* Ket nap canh (u,v) vao cay khung *)
Ndinh:=Ndinh+1; Union(r1, r2);
DauT[Ndinh]:=u;
CuoiT[Ndinh]:=v;
MinL:=MinL+W[1];

74/164

end;
(* To chuc lai Heap *)
Dau[1]:=Dau[Last];
Cuoi[1]:=Cuoi[Last];
W[1]:=W[Last];
Last:=Last-1;
End;
If Ndinh<>n-1 then Connect:=false;
End;
Procedure Inketqua;
Var i:integer;
Begin
Writeln(******************************);
Writeln(***** Ket qua tinh toan ********);
Writeln(*******************************);
Writeln(Do dai cua cay khung nho nhat: ,MinL);
Writeln(Cac canh cua cay khung nho nhat);
For i:=1 to n-1 do
Writeln((,DauT[i]:2,,,CuoiT[i]:2,));
Writeln(*******************************);
End;
Begin

75/164

Clrscr;
Nhapdl;
Indulieu;
Kruskal;
If connect then Inketqua
Else
Writeln( Do thi khong lien thong);
Readln;
End.
File d liu ca bi ton trong v d 3 c dng sau:

76/164

Thut ton Prim

Thut ton Kruskal lm vic km hiu qu vi nhng th dy ( th vi s cnh m
n(n-1)/2). Trong trng hp thut ton Prim t ra hiu qu hn. Thut ton Prim cn
c gi l phng php ln cn gn nht. Trong phng php ny bt u t mt nh
tu ca th, u tin ta ni s vi nh ln cn gn n nht, chng hn l nh y.
Ngha l trong s cc cnh k ca nh s, cnh (s,y) c di nh nht. Tip theo trong
s cc cnh k vi hai nh s hoc y ta tm cnh c di nh nht, cnh ny dn n
nh th ba z, v ta thu c cy b phn gm 3 nh v 2 cnh. Qu trnh ny s tip
tc cho n khi ta thu c cy gm n nh v n-1 cnh s chnh l cy khung nh nht
cn tm.
Gi s th cho bi ma trn trng s C = ? c[i,j], i, j= 1, 2, . . . , n? . trong qu trnh
thc hin thut ton, mi bc c th nhanh chng chn nh v cnh cn b sung
vo cy khung, cc nh ca th s c gn cho cc nhn. Nhn ca mt nh v s
gm hai phn v c dng [d[v], near[v]], trong d[v] dng ghi nhn di ca cnh
c di nh nht trong s cc cnh ni vi nh v vi cc nh ca cy khung ang
xy dng (ta s gi l khong cch t nh v n tp nh ca cy khung), ni mt cch
chnh xc
d[v]:= min ? c[v,w] : w VH ? ( = c[v,z]),
cn near[v] ghi nhn nh ca cy khung gn v nht (near[v]:=z).
Thut ton Prim c m t y trong th tc sau:
Procedur Prim;
Begin
(* buoc khoi tao *)
chon s la mot dinh nao do cua do thi;
VH:= ? s ? ; T:= ; d[s]:=0; near[s]:=s.
For v V\VH do
Begin
D[v]:=c[s,v];
near[v]:=s;

77/164

End;
(* buoc lap *)
stop:=false;
while not stop do
begin
tim u V\VH thoa man:
d[u] =min ? d[v]: u V\VH ? ;
VH:= VH ? ? u ? ; T := T ? ? (u, near[u]) ? ;
If ? VH ? =n then
Begin
H=( VH,T) la cay khung nho nhat cua do thi;
Stop:=true;
End
Else
For v V\ VH do
If d[v]>c[u,v] then
Begin
d[v]:=c[u,v];
near[v]:=u;
End;
end;
End;

78/164

Th d 4. Tm cy khung nh nht cho th xt trong v d 3 theo thut ton Prim. Ma

trn trng s ca th c dng

Bng di y ghi nhn ca cc nh trong cc bc lp ca thut ton, nh nh du *

l nh c chn b sung vo cy khung (khi nhn ca n khng cn b bin i
trong cc bc lp tip theo, v vy ta nh du ghi nhn iu ):

Mt s bi ton dn v bi ton cy khung nh nht

Trong mc ny ta nu hai bi ton c th dn v bi ton cy khung nh nht, v v th
c th gii c nh cc thut ton m t trong mc trc
a) Bi ton cy khung ln nht. D dng nhn thy rng trong cc thut ton trn ta
khng cn s dng n i hi v du ca di. V th c th p dng chng i vi

79/164

 th c cc cnh vi di c du tu . V vy, gi s ta phi tm cy ln nht (tc

l c di c(H) ln nht) th ch cn i du tt c cc o v p dng mt trong hai
thut ton va m t.
b) Bi ton tm mng in vi tin cy ln nht. Cho li in c n nt. ng dy
ni nt i vi nt j c tin cy 1>p[i ,j]>0, i, j=1, 2, . . . , n. Gi G = (V, E) l th
tng ng vi li in ny. Hy tm cy khung H ca th G vi tin cy
p(e)e H
ln nht.
Bi ton ny dn v bi ton tm cy khung vi tng di nh nht trn th G vi
di ca mi cnh e E l log p(e). Thc vy, gi s H l cy khung nh nht trn
th vi di log p(e), ta c
- ? log p(e) - ? log p(e)e H

e H

vi mi cy khung H ca th G. T suy ra
? log p(e) ? log p(e)e H

e H

do
log p(e) log p(e)

e H

e H

hay l
p(e) p(e)e H

e H

vi mi cy khung H. Vy H l cy khung c tin cy ln nht.

80/164

Bi ton ng i ngn nht

Trong cc ng dng thc t, vi ton tm ng i ngn nht gia hai nh ca mt
th lin thng c mt ngha to ln. C th dn v bi ton nh vy nhiu bi ton thc
t quan trng. V d, bi ton chn mt hnh trnh tit kim nht (theo tiu chun hoc
khong cch hoc thi gian hoc chi ph) trn mt mng giao thng ng b, ng
thy hoc ng khng; bi ton chn mt phng php tit kim nht a ra mt
h thng ng lc t trng thi xut pht n trng mt trng thi ch, bi ton lp lch
thi cng cc cng cc cng on trong mt cng trnh thi cng ln, bi ton la chn
ng truyn tin vi chi ph nh nht trong mng thng tin, v.v Hin nay c rt nhiu
phng php gii cc bi ton nh vy. Th nhng, thng thng, cc thut ton
c xy dng da trn c s l thuyt th t ra l cc thut ton c hiu qu cao
nht. Trong chng ny chng ta s xt mt s thut ton nh vy.

CC KHI NIM M U
Trong chng ny chng ta ch xt th c hng G =(V,E), |V|=n, |E|=m vi cc cung
c gn trng s, ngha l, mi cung (u,v) E ca n c t tng ng vi mt s
thc a(u,v) gi l trng s ca n. Chng ta s t a(u,v) = , nu (u,v) E. Nu dy
v0, v1, . . ., vp
l mt ng i trn G, th di ca n c nh ngha l tng sau
p

?a(vi-1, vi). i=1

tc l, di ca ng i chnh l tng ca cc trng s trn cc cung ca n. (Ch

rng nu chng ta gn trng s cho tt c cung u bng 1, th ta thu c nh ngha
di ca ng i nh l s cung ca ng i ging nh trong cc chng trc
xt).
Bi ton tm ng i ngn nht trn th di dng tng qut c th pht biu nh
sau: tm ng i c di nh nht t mt nh xut pht s V n nh cui (ch) t
V. ng i nh vy ta s gi l ng i ngn nht t s n t cn di ca n ta s
k hiu l d(s,t) v cn gi l khong cch t s n t (khong cch nh ngha nh vy
c th l s m). Nu nh khng tn ti ng i t s n t th ta s t d(s,t)= . R
rng, nu nh mi chu trnh trong th u c di dng, trong ng i ngn nht
khng c nh no b lp li (ng i khng c nh lp li s gi l ng i c bn).
Mt khc nu trong th c chu trnh vi di m (chu trnh nh vy gi ngn gn
81/164

ta gi l chu trnh m) th khong cch gia mt s cp nh no ca th c th l

khng xc nh, bi v, bng cch i vng theo chu trnh ny mt s ln ln, ta c th
ch ra ng i gia cc nh ny c di nh hn bt c s thc cho trc no. Trong
nhng trng hp nh vy, c th t vn tm ng i c bn ngn nht, tuy nhin
bi ton t ra s tr nn phc tp hn rt nhiu, bi v n cha bi ton xt s tn ti
ng i Hamilton trong th nh l mt trng hp ring.
Trc ht cn ch rng nu bit khong cch t s n t, th ng i ngn nht t s
n t, trong trng hp trng s khng m, c th tm c mt cch d dng. tm
ng i, ch cn l i vi cp nh s, t V tu (s <> t) lun tm c nh v
sao cho
d(s,t) = d(s,v) + a(v,t).
Thc vy, nh v nh vy chnh l nh i trc nh t trong ng i ngn nht t s
n t. Tip theo ta li c th tm c nh u sao cho d(s,v) = d(s,u) + a(u,v), . . . T gi
thit v tnh khng m ca cc trng s d dng suy ra rng dy t, v, u, . . . khng cha
nh lp li v kt thc nh s. R rng dy thu c xc nh (nu lt ngc th t
cc nh trong n) ng i ngn nht t s n t. T ta c thut ton sau y tm
ng i ngn nht t s n t khi bit di ca n.
Procedure Find_Path;
(*
u vo:
D[v] - khong cch t nh s n tt c cc nh cn li v V;
- nh ch;
a[u,v], u, v V ma trn trng s trn cc cung.
u ra:
Mng Stack cha dy nh xc nh ng i ngn nht t s n t
*)
begin
stack:= ; stack t; v:=t;
while v <> s do
82/164

begin
u:=nh tho mn d[v]=d[u]+a[u,v];
stack u;
v:=u;
end;
end;
Ch rng phc tp tnh ton ca thut ton l O(n2), do tm nh u ta phi xt qua
tt c cc nh ca th. Tt nhin, ta cng c th s dng k thut ghi nhn ng i
trnh by trong chng 3: dng bin mng Truoc[v], v V, ghi nh nh i trc
v trong ng i tm kim.
Cng cn lu thm l trong trng hp trng s trn cc cnh l khng m, bi ton
tm ng i ngn nht trn th v hng c th dn v bi ton trn th c hng,
bng cch thay i mi cnh ca n bi n bi hai cung c hng ngc chiu nhau vi
cng trng s l trng s ca cc cnh tng ng. Tuy nhin, trong trng hp c trng
s m, vic thay nh vy c th dn n chu trnh m.

83/164

ng i ngn nht xut pht t mt nh

Phn ln cc thut ton tm khong cch gia hai nh s v t c xy dng nh k thut
tnh ton m ta c th m t i th nh sau: t ma trn trng s a[u,v], u,v V, ta tnh
cn trn d[v] ca khong cch t s n tt c cc nh v V. Mi khi pht hin
d[u] + a[u,v] < d[v] (1)
cn trn d[v] s c lm tt ln: d[v] + a[u,v].
Qu trnh s kt thc khi no chng ta khng lm tt thm c bt k cn trn no.
Khi , r rng gi tr ca mi d[v] s cho khong cch t nh s n nh v. Khi th
hin k thut tnh ton ny trn my tnh, cn trn d[v] s c gi l nhn ca nh v,
cn vic tnh li cc cn ny s c gi l th tc gn. Nhn thy rng tnh khong
cch t s n t, y, ta phi tnh khong cch t s n tt c cc nh cn li ca th.
Hin nay vn cha bit thut ton no cho php tm ng i ngn nht gia hai nh
lm vic thc s hiu qu hn nhng thut ton tm ng i ngn nht t mt nh n
tt c cc nh cn li.
S tnh ton m ta va m t cn cha xc nh, bi v cn phi ch ra th t cc nh
u v v kim tra iu kin (1). Th t chn ny c nh hng rt ln n hiu qu ca
thut ton.
By gi ta s m t thut ton Ford-Bellman tm ng i ngn nht t nh s n tt c
cc nh cn li ca th. Thut ton lm vic trong trng hp trng s ca cc cung
l tu , nhng gi thit rng trong th khng c chu trnh m.
Procedure Ford_Bellman
(*
u vo:
th c hng G=(V,E) vi n nh,
S V l nh xut pht,A[u,v], u, v V, ma trn trng s;
Gi thit: th khng c chu trnh m.
u ra:
Khong cch t nh s n tt c cc nh cn li d[v], v V.
84/164

Trc[v], v V, ghi nhn nh i trc v trong ng i ngn nht t s n v.

*)
begin
(* Khi to *)
for v V do
begin
d[v]:=a[s,v];
Truoc[v]:=s;
end;
d[s]:=0;
for k:=1 to n-2 do
for v V\ ? s ? do
for u V do
if d[v] > d[u] +a[u,v] then
begin
d[v]:=d[u]+a[u,v];
Truoc[v]:=u;
end;
end;
Tnh ng n ca thut ton c th chng minh trn c s trn nguyn l ti u ca quy
hoch ng. R rng l phc tp tnh ton ca thut ton l O(n3). Lu rng chng
ta c th chm dt vng lp theo k khi pht hin trong qu trnh thc hin hai vng lp
trong khng c bin d[v] no b i gi tr. Vic ny c th xy ra i vi k<n-2, v iu
lm tng hiu qu ca thut ton trong vic gii cc bi ton thc t. Tuy nhin, ci
tin khng thc s ci thin c nh gi phc tp ca bn thn thut ton. i
85/164

vi th tha tt hn l s dng danh sch k Ke(v), v V, biu din th, khi

vng lp theo u cn vit li di dng
For u Ke(v) do
If d[v] > d[u] + a[u,v] thenBegin
D[v]:=d[u]+a[u,v];Truoc[v]:=u;
End;
Trong trng hp ny ta thu c thut ton vi phc tp O(n,m).
Th d 1. xt th trong hnh 1. Cc kt qu tnh ton theo thut ton c m t trong
bng di y

Hnh 1. Minh ha thut ton Ford_Bellman

86/164

Bng kt qu tnh ton theo thut ton Ford_Bellman

Trong cc mc tip theo chng ta s xt mt s trng hp ring ca bi ton tm ng
i ngn nht m gii chng c th xy dng nhng thut ton hiu qu hn thut ton
Ford_Bellman. l khi trng s ca tt c cc cung l cc s khng m hoc l khi
th khng c chu trnh.

87/164

Trng hp ma trn trng s khng mThut ton Dijkstra

Trong trng hp trng s trn cc cung l khng m thut ton do Dijkstra ngh lm
vic hu hiu hn rt nhiu so vi thut ton trnh by trong mc trc. Thut ton c
xy dng da trn c s gn cho cc nh cc nhn tm thi. Nhn ca mi nh cho
bit cn ca di ng i ngn nht t s n n. Cc nhn ny s c bin i theo
mt th tc lp, m mi bc lp c mt nhn tm thi tr thnh nhn c nh. Nu
nhn ca mt nh no tr thnh mt nhn c nh th n s cho ta khng phi l cn
trn m l di ca ng i ngn nht t nh s n n. Thut ton c m t c th
nh sau.
Procedure Dijstra;
(*
u vo:
th c hng G=(v,E) vi n nh,
s V l nh xut pht, a[u,v], u,v V, ma trn trng s;
Gi thit: a[u,v] 0, u,v V.
u ra:
Khong cch t nh s n tt c cc nh cn li d[v], v V.
Truoc[v], v V, ghi nhn nh i trc v trong ng i ngn nht t s n v
*)
Begin
(* Khi to *)
for v V do
begin
d[v]:=a[s,v];
88/164

Truoc[v]:=s;
end;
d[s]:=0; T:=V\ ? s ? ; (* T l tp cc nh c nhn tm thi *)
(* Bc lp *)
while T <> do
begin
tm nh u T tho mn d[u]=min ? d[z]:z T ? ;
T:=T\ ? u ? ; (* C nh nhn ca nh u*)
For v T do
If d[v]>d[u]+a[u,v] then
Begin
d[v]:=d[u]+a[u,v];
Truoc[v]:=u;
End;
end;
End;
nh l 1. Thut ton Dijkstra tm c ng i ngn nht trn th sau thi gian c
O(n2).
Chng minh.
Trc ht ta chng minh l thut ton tm c ng i ngn nht t nh s n cc
nh cn li ca th. Gi s mt bc lp no cc nhn c nh cho ta di cc
ng i ngn nht t s n cc nh c nhn c nh, ta s chngminh rng ln gp
tip theo nu nh u* thu c nhn c nh d(u*) chnh l di ng i ngn nht t
s n u*.

89/164

K hiu S1 l tp hp cc nh c nhn c nh cn S2 l tp cc nh c nhn tm thi

bc lp ang xt. Kt thc mi bc lp nhn tm thi d(u*) cho ta di ca ng
i ngn nht t s n u* khng nm trng trong tp S1, tc l n i qua t nht mt nh
ca tp S2. Gi z S2 l nh u tin nh vy trn ng i ny. Do trng s trn cc
cung l khng m, nn on ng t z n u* c di L>0 v
d(z) < d(u*) L < d(u*).
Bt ng thc ny l mu thun vi cch xc nh nh u* l nh c nhn tm thi nh
nht. Vy ng i ngn nht t s n u* phi nm trn trong S1, v v th, d[u*] l
di ca n. Do ln lp u tin S1 = ? s? v sau mi ln lp ta ch thm vo mt nh
u* nn gi thit l d(v) cho di ng i ngn nht t s n v vi mi v S1 l ng
vi bc lp u tin. Theo qui np suy ra thut ton cho ta ng i ngn nht t s n
mi nh ca th.
By gi ta s nh gi s php ton cn thc hin theo thut ton. mi bc lp
tm ra nh u cn phi thc hin O(n) php ton, v gn nhn li cng cn thc hin
mt s lng php ton cng l O(n). thut ton phi thc hin n-1 bc lp, v vy thi
gian tnh ton ca thun ton c O(n2).
nh l c chng minh.
Khi tm c di ca ng i ngn nht d[v] th ng i ny c th tm da vo
nhn Truoc[v], v V, theo qui tc ging nh chng ta xt trong chng 3.
Th d 2. Tm ng i ngn nht t 1 n cc nh cn li ca th hnh 2.

Hnh 2. Minh ha thut ton Dijkstra

90/164

Kt qu tnh ton theo thut ton c trnh by theo bng di y. Qui c vit hai
thnh phn ca nhn theo th t: d[v]. nh c nh du * l nh c chn c
nh nhn bc lp ang xt, nhn ca n khng bin i cc bc tip theo, v th
ta nh du -.

Ch :
Nu ch cn tm ng i ngn nht t s n mt nh t no th c th kt thc thut
ton khi nh t tr thnh c nhn c nh.
Tng t nh trong mc 2, d dng m t thut ton trong trng hp th cho bi
danh sch k. c th gim bt khi lng tnh ton trong vic xc nh nh u mi
bc lp, c th s dng thut ton Heasort (tng t nh trong chng 5 khi th hin
thut ton Kruskal). Khi c th thu c thut ton vi phc tp tnh ton l O(m
log n).

91/164

 th trong th khng c chu trnh

By gi ta xt trng hp ring th hai ca bi ton ng i ngn nht, m gii n
c th xy dng thut ton vi phc tp tnh ton O(n2), l khi th khng c
chu trnh (cn trng s trn cc cung c th l cc s thc tu ). Trc ht ta chng
minh nh l sau.
nh l 2. Gi s G l th khng c chu trnh. Khi cc nh ca n c th nh s
sao cho mi cung ca th ch hng t nh c ch s nh hn n nh c ch s ln
hn, ngha l mi cung ca n c s biu din di dng (v[i], v[j]), trong i<j.
Th d 3. th trong hnh 3 c cc nh s tho mn iu kin nu trong nh l.

Hnh 3. th khng c chu trnh

chng minh nh l ta m t thut ton sau y, cho php tm ra cch nh s tho
mn iu kin nh l.
Procudure Numbering;
(* u vo: th c hng G=(V,E) vi n nh khng cha chu trnh c cho bi
danh sch k Ke(v), v V.
u ra:
Vi mi nh v V ch s NR [v] tho mn:
Vi mi cung (u,v) ca th ta u c NR [u] < NR [v] *)
Begin
For v V do Vao[v]:=0;
92/164

(* Tnh Vao[v]=deg - (v) *)

for u V do
for v Ke(u) do Vao[v]:=Vao[v]+1;
Queue:= ;
For v V do
if Vao[v]=0 then Queue v;
num:=0;
while queue<> do
begin
u queue;
num:=num+1; NR[u]:=num;
for v Ke(u) do
begin
Vao[v]:=Vao[v]-1;
If Vao[v]=0 then queue v;
end;
end;
End;
Thut ton c xy dng da trn tng rt n gin sau: r rng trong th khng
c chu trnh bao gi cng tm c nh c bn bc vo bng 0 (khng c cung i vo).
Thc vy, bt u t nh v1 nu c cung i vo n t v2 th ta li chuyn sang xt nh
v2 . Nu c cung t v3 i vo v2, th ta li chuyn sang xt nh v3. . .Do th khng c
chu trnh nn sau mt s hu hn ln chuyn nh vy ta phi i n nh khng c cung
i vo. Thot tin, tm cc nh nh vy ca th. R rng ta c th nh s chng
theo th t tu bt u t 1. Tip theo, loi b khi th nhng nh c nh
s cng cc cung i ra khi chng, ta thu c th mi cng khng c chu trnh, v
93/164

th tc c lp vi th mi ny. Qu trnh s c tip tc cho n khi tt c cc

nh ca th c nh s.
Ch :
R rng trong bc khi to ra phi duyt qua tt c cc cung ca th khi tnh bn bc
vo ca cc nh, v vy ta tn c O(m) php ton, trong m l s cung ca
th. Tip theo, mi ln nh s mt nh, thc hin vic loi b nh nh s cng
vi cc cung i ra khi n, chng ta li duyt qua tt c cc cung ny. Suy ra nh s
tt c cc nh ca th chng ta s phi duyt qua tt c cc cung ca th mt ln
na. Vy phc tp ca thut ton l O(m).
Thut ton c th p dng kim tra xem th c cha chu trnh hay khng? Thc
vy, nu kt thc thut ton vn cn c nh cha c nh s (num<n) th iu c
ngha l th cha chu trnh.
Do c thut ton nh s trn, nn khi xt th khng c chu trnh ta c th gi thit l
cc nh ca n c nh s sao cho mi cung ch i t nh c ch s nh n nh c
ch s ln hn. Thut ton tm ng i ngn nht trn th khng c chu trnh c
m t trong s sau y.
Procedure Critical_Path;
(* Tm ng i ngn nht t nh ngun n tt c cc nh cn li trn th khng
c chu trnh *)
u vo:
th G=(V,E), trong V= ? v[1], v[2], . . . , v[n] ? .
i vi mi cung (v[i], v[j]) E, ta c i<j.
th c cho bi danh sch k Ke(v), v V.
u ra:
Khong cch t v[1] n tt c cc nh cn li c ghi trong mng d[v[i]], i= 2, 3, . .
.,n *)
Begin
dv[1]]:=0;
for j:=2 to n do d[v[j]]:=a[v[1], v[j]];
94/164

for j:=2 to n do
for v Ke[v[j]] do d[v]:=min(d[v], d[v[j]]+a[v[j], v]);
End;
phc tp tnh ton ca thut ton l O(m), do mi cung ca th phi xt qua ng
mt ln.
Cc thut ton c m t trn thng c ng dng vo vic xy dng nhng
phng php gii bi ton iu khin vic thc hin nhng d n ln, gi tt l PERT
(Project Evaluation and Review Technique) hay CDM (Critical path Method). Mt th
d n gin cho ng dng ny c m t trong th d di y.

Th d 4. Vic thi cng mt cng trnh ln c chia thnh n cng on, nh s t

1 n n. C mt s cng on m vic thc hin n ch c tin hnh sau khi mt s
cng on no hon thnh. i vi mi cong on i bit t[i]] l thi gian cn thit
hon thnh n (i=1, 2,. . .,n). D liu vi n=8 c cho trong bng di y
Gi s thi im bt u tin hnh thi cng cng trnh l 0. Hy tm tin thi cng
cng trnh (ch r mi cng on phi c bt u thc hin vo thi im no) cho
cng trnh c hon thnh xong trong thi im sm nht c th c.

95/164

Ta c th xy dng th c hng n nh biu din hn ch v trnh t thc hin cc

cng vic nh sau: Mi nh ca th tng ng vi mt cng vic, nu cng vic i
phi c thc hin trc cng on j th trn th c cung (i,j), trng s trn cung ny
c gn bng t[i], xem hnh 4 di y.

Hnh 4. th minh ho PERT

Thm vo th hai nh 0 v n+1 tng ng vi hai s kin c bit: nh 0 tng ng
vi cng on l khi cng, n phi c thc hin trc tt c cc cng on khc, v
nh n+1 tng ng vi cng on ct bng khnh thnh cng trnh, n phi c thc
hin sau cc cng on, vi t[0]=t[n+1]=0 (trn thc t ch cn ni nh 0 vi tt c cc
nh c bn bc bng 0 v ni tt c cc nh c bn bc ra bng 0 vi nh n+1). Gi
th thu c l G. R rng bi ton t ra dn v bi ton tm ng i ngn nht t nh
0 n tt c cc nh cn li trn th G. Do th G r rng l khng cha chu trnh,
nn gii bi ton t ra c th p dng cc thut ton m t trn, ch cn i du tt
c cc trng s trn cc cung thnh du ngc li, hoc n gin hn ch cn i ton t
Min trong thut ton Critcal_Path thnh ton t Max. Kt thc thut ton, chng ta thu
c d[v] l di ng i di nht t nh 0 n nh v. Khi d[v] cho ta thi im
sm nht c th bt u thc hin cng on v, ni ring d[n+1] l thi im sm nht
c th ct bng khnh thnh, tc l thi im sm nht c th hon thnh ton b cng
trnh.
Cy ng i di nht ca bi ton trong th d 4 tm c theo thut ton c ch ra
trong hnh 4.

96/164

ng i ngn nht gia tt c cc cp nh

R rng ta c th gii bi ton tm ng i ngn nht gia tt c cc cp nh ca th
bng cch s dng n ln thut ton m t mc trc, trong ta s chn s ln lt l
cc nh ca th. R rng, khi ta thu c thut ton vi phc tp O(n4) (nu s
dng thut ton Ford_Bellman) hoc O(n3) i vi trng hp trng s khng m hoc
th khng c chu trnh. Trong trng hp tng qut, s dng thut ton Ford_Bellman
n ln khng phi l cch lm tt nht. y ta s m t mt thut ton gii bi ton trn
vi phc tp tnh ton O(n3): thut ton Floyd. Thut ton c m t trong th tc
sau y.
Procedure Floyd;
(* Tm ng i ngn nht gia tt c cc cp nh
u vo: th cho bi ma trn trng s a[i,j], i, j =1, 2,. . ,n.
u ra:
Ma trn ng i ngn nht gia cc cp nh
d[i,j]=, i,j = 1, 2. . .,n,
trong d[i,j] cho di ng i ngn nht t nh i n nh j.
Ma trn ghi nhn ng i
p[i,j], i, j = 1, 2.. . , n,
trong p[i,j] ghi nhn nh i trc nh j trong ng i ngn nht t i n j.
*)
begin
(* Khi to *)
for i:=1 to n do
for j:=1 to n do

97/164

begin
d[i,j]:=a[i.j];
p[i.j]:=i;
end;
(* Bc lp *)
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if d[i,j]>d[i,k]+d[k,j] then
begin
d[i,j]+d[i,k]+d[k,j];
p[i,j]>p[k,j];
end;
end;
R rng phc tp tnh ton ca thut ton l O(n3).
Kt thc chng ny chng ra trnh by mt cch th hin thut ton Dijkstra trn ngn
ng Pascal:

(* CHNG TRNH TM NG I NGN NHT T NH S N NH T THEO

THUT TON DIJKSTRA *)
uses crt;
const max=50;
var

98/164

n, s, t:integer;
chon:char;
Truoc:array[1..max] of byte;
d: array[1..max] of integer;
a: array[1..max,1..max] of integer;
final: array[1..max] of boolean;
procedure Nhapsolieu;
var
f:text;
fname:string;
i,j:integer;
begin
write(Vao ten file du lieu can doc:);
readln(fname);
assign(f,fname);
reset(f);
readln(f,n);
for i:=1 to n do
for j:=1 to n do read(f, a[i,j];
close(f);
end;
procedure Insolieu;

99/164

var
i,j:integer;
begin
writeln(So dinh cua do thi:,n);
writeln(Ma tran khoang cach:);
for i:=1 to n do
begin
for j:=1 to n do write(a[i,j]:3, );
writeln;
end;
end;
Procedure Inketqua;
Var
i,j:integer;
begin
writeln(Duong di ngan nhat tu ,s, den ,t);
write(t, );
while i<> s do
begin
i:=Truoc[i];
write(i, );
end;

100/164

end;
Procedure Dijkstra;
Var
U,v,minp:integer;
Begin
Write(Tim duon di tu s=);Readln(s);Write( den t=);Readln(t);
For v:=1 to n doBegin
d[v]:=a[s,v];
Truoc[v]:=s;
Filal[v]:=false;
End;
Truoc[s]:=0;D[s]:=0;Final[s]:=true;
While not final[t] do (* Buoc lap *)Begin
Tim u la dinh co nhan tam thoi nho nhat
minp:=maxint;
for v:=1 to n do
if (not final[v]) ans minp>d[v]) then
begin
u:=v;
minp:=d[v];
end;
final[u]:=true;

101/164

if not final[t] then

for v:=1 to n do
if (not final[v]) and (d[u]+a[u,v]<d[v]) then
begin
d[v]:=d[u]+a[u,v];
Truoc[v]:=u;
end;
End;
end;
Procedure Menu;
Begin
Clrscr;
Writeln(1. Nhap du lieu tu file);
Writeln(2. Giai bai toan);
Writeln(3. Ket thuc);
Writeln(---------------------);
Write(Hay chon chuc nang:):
End;
(* Chuong trinh chinhs *)
Begin
Repeat
Menu;

102/164

Chon:=readkey;
Writeln(chon);
Case chon of
1:Nhapsolieu;
2: begin
Insolieu;
Dijkstra;
Inketqua;
3:exit;
end;
Until false;
End.

103/164

Bi ton lung cc i trong mng

Bi ton lung cc i trong mng l mt trong s bi ton ti u trn th tm c
nhng ng dng rng ri trong thc t cng nh nhng ng dng th v trong l thuyt
t hp. Bi ton c xut vo u nm 1950, v gn lin vi tn tui ca hai nh
ton hc M l Ford v Fulkerson. Trong chng ny chng ra s trnh by thut ton
Ford v Fulkerson gii bi ton t ra v nu mt s ng dng ca bi ton.

MNG. LUNG TRONG MNG. BI TON LUNG CC I

nh ngha 1. Ta gi mng l th c hng G=(V,E), trong duy nht mt nh s

khng c cung i vo gi l nh pht, duy nht mt nh t khng c cung i ra gi l
im thu v mi cung e=(v,w) E c gn vi mt s khng m c(e) =c(v,w) gi l
kh nng thng qua ca cung e.
thun tin cho vic trnh by ta s qui c rng nu khng c cung (v,w) th kh nng
thng qua c(v,w) c gn bng 0.
nh ngha 2. Gi s cho mng G=(V,E). Ta gi mng f trong mng G=(V,E) ;l nh
x f: E R+ gn cho mi cung e=(v,w) E mt s thc khng m f(e)=f(v,w), gi l
lung trn cung e, tho mn cc iu kin sau:
Lung trn cung e E khng vt qu kh nng thng qua ca n:
0f(e)c(e),
iu kin cn bng lung trn mi nh ca mng: Tng lung trn cc cung i vo nh
v bng tng lung trn cc cung i ra khi nh v, nu v#s, t:
Div f (v) = ? f(w,v)

? f(v,w) = 0

w - (v)

w + (v)

trong o - (v) tp cc nh ca mng m t c cung n v, + (v) - tp cc nh

ca mng m t v c cung n n:
- (v) = ? w V : (w,v) E? ,
+ (v) = ? w V : (v,w) E? .
104/164

Gi tr ca lung f l s
Val(f) = ? f(s,w )

w + (s)

?? f(w,t).
w - (t)

Bi ton lung cc i trong mng:

Cho mng G(V,E). Hy tm lung f* trong mng vi gi tr lung val(f*) l ln nht.
Lung nh vy ta s gi l lung cc i trong mng.
Bi ton nh vy c th xut hin trong rt nhiu ng dng thc t. Chng hn khi cn
xc nh cng ln nht ca dng vn ti gia hai nt ca mt bn giao thng.
Trong v d ny li gii ca bi ton lung cc i s ch cho ta cc on ng ng xe
nht v chng to thnh "ch hp" tng ng vi dng giao thng xt theo hai nt c
chn. Mt v d khc l nu xt th tng ng vi mt h thng ng ng dn du.
Trong cc ng tng ng vi cc cung, im pht c th coi l tu ch du, im thu
l b cha, cn nhng im ni gia cc ng l cc nt ca th. Kh nng thng qua
ca cc cung tng ng vi tit din ca cc ng. Cn phi tm lung du ln nht c
th bm t tu ch du vo b cha.

105/164

Lt ct.ng tng lung.nh l

Ford_Fulkerson
nh ngha 3. Ta gi lt ct (X,X*) l mt cch phn hoch tp nh V ca mng ra
thnh hai tp X v X* = V\X, trong s X, t X* . Kh nng thng qua ca lt ct
(X,X*) l s
c(X,X*) = (v,w)

w X*

vX

Lt ct vi kh nng thng qua nh nht c gi l lt ct hp nht.

B 1.
Gi tr ca lung f trong mng lun nh hn hoc bng kh nng thng qua ca lt ct
(X,X*) bt k trong n: val(f) c(X,X*).
Chng minh. Cng cc iu kin cn bng lung Divf(v)=0 vi mi v X. Khi ta
c
(

f(w,v ) -

f(v,w) ) = -Val(f) v X

w - (v)

w + (v)

tng ny s gm cc s hng dng f(u,v) vi du cng hoc du tr m trong c t

nht mt trong hai nh u,v phi thuc tp X. Nu c hai nh u,v u trong tp X, th
f(u,v) xut hin vi du cng trong Divf(v) v vi du tr trong Divf(u), v th, chng
trit tiu ln nhau. Do , sau khi gin c cc s hng nh vy v tri, ta thu c
- f(v,w) + f(v,w) = -val(f), v X

v X*w X*

w X

hay l
vX

val(f) = f(v,w) - f(v,w)

v X*

w X*

w X

Mt khc, t iu kin 1 r rng l

f(v,w) c(v,w)

vX

v X* w X*

w X

Cn

106/164

- f(v,w) 0 v X*w X

suy ra val(f)c(X,X*). B c chng minh.

H qu 1. Gi tr lung cc i trong mng khng vt qu kh nng thng qua ca
lt ct hp nht trong mng.Ford v Fulkerson chng minh rng gi tr lung cc i
trong mng ng bng kh nng thng qua ca lt ct hp nht. c th pht biu v
chng minh kt qu ny chng ra s cn thm mt s khi nim.Gi s f l mt lung
trong mng G = (V,E). T mng G =(V,E) ta xy dng th c trng s trn cung Gf
= (V, Ef), vi tp cung Ef v trng s trn cc cung c xc nh theo qui tc sau:
Nu e=(v,w) E vi f(v,w) =0, th (v,w) Ef vi trng s c(v,w);
Nu e=(v,w) E vi f(v,w) =c(v,w), th (w,v) Ef vi trng s f(v,w);
Nu e=(v,w) E vi 0<f(v,w)<c(v,w), th (v,w) Ef vi trng s c(v,w)-f (v,w) v
(w,v) Ef vi trng s f(v,w).
Cc cung ca Gf ng thi cng l cung ca G c gi l cung thun, cc cung cn li
c gi l cung nghch. th Gf c gi l th tng lung.
Th d: Cc s vit cnh cc cung ca G hnh 1 theo th t l kh nng thng qua v
lung trn cung.
D dng kim tra c rng f c xy dng nh trn l lung trong mng v val(f) =
val(f) + . Ta s gi th tc bin i lung va nu l tng lung dc theo ng P.
nh ngha 4. Ta gi ng tng lung f l mi ng i t s n t trn th tng
lung G(f).
nh l 1. Cc mnh di y l tng ng:
(i) f l lung cc i trong mng:
(ii) khng tm c ng tng lung f;
(iii) val(f)=c(X,X*) vi mt lt ct (X,X*) no .
Chng minh.

107/164

(i) (ii). Gi s ngc li, tm c ng tng lung P. Khi ta c th tng gi tr

lung bng cch tng lung dc theo ng P. iu mu thun vi tnh cc i ca
lung f.
(ii) (iii). Gi s khng tm c ng tng lung. K hiu X l tp tt c cc nh
c th n c t nh s trong th Gf, v t X*=V\X. Khi (X,X*) l lt ct, v
f(v,w)=0 vi mi v X*, w X nn
val(f) = f(v,w) - f(v,w) = f(v,w)
X

w X

w X

vX

v X*

v X

Vi v X, w X*, do (v,w) Gf, nn f(v,w) = c(v,w). Vy

val(f) = f(v,w) = c(v,w) = c(X,X*)
X

vX

vX

w X*

(iii) (i). Theo b 1, val(f) c(X,X*) vi mi lung f v vi mi lt ct (X,X*). V

vy, t ng thc val(f) = c(X,X*) suy ra lung f l lung cc i trong mng.

108/164

Thut ton tm lung cc i

nh l 1 l c s xy dng thut ton lp sau y tm lung cc i trong mng:
Bt u t lung vi lung trn tt c cc cung bng 0 (ta s gi lung nh vy l lung
khng), v lp li bc lp sau y cho n khi thu c lung m i vi n khng cn
ng tng:
Bc lp tng lung (Ford-Fulkerson): Tm ng tng P i vi lung hin c. Tng
lung dc theo ng P.
Khi c lung cc i, lt ct hp nht c th theo th tc m t trong chng minh
nh l 1. S ca thut ton Ford-Fulkerson c th m t trong th tc sau y:
Procedure Max_Flow;
(* Thut ton Ford-Fulkerson *)
begin
(* Khi to: Bt u t lung vi gi tr 0 *)
for u V do
for v V do f(u,v):=0;
stop:=false;
while not stop do
if <Tm c ng tng lung P> then
<Tng lung dc theo P>
else stop:=true;
end;
tng lung trong Gf c th tm kim thut ton theo chiu rng (hay tm kim theo
chiu su) bt u t nh s, trong khng cn xy dng th tng minh Gf.
Ford_Fulkerson ngh thut ton gn nhn chi tit sau y gii bi ton lung cc
i trong mng (c th bt u t lung khng), sau ta s tng lung bng cch tm
cc ng tng lung. tm ng tng lung ta s p dng phng php gn nhn
109/164

cho cc nh. Mi nh trong qu trnh thc hin thut ton s mt trong ba trng thi:
cha c nhn, c nhn cha xt, c nhn xt. Nhn ca mt nh v gm 2 phn v c
mt trong 2 dng sau: [+p(v), (v)] hoc [-p(v), (v)]. Phn th nht +p(v) (-p(v)) ch
ra l cn tng (gim) lung theo cung (p(v), v) (cung v, p(v)) cn phn th hai (v) ch
ra lng ln nht c th tng hoc gim lung trn cc cung ca ng tng lung t
s ti v. u tin ch c nh s c khi to v nhn ca n l cha xt, cn tt c cc
nh cn li l u cha c nhn. T s ta gn nhn cho tt c cc nh k vi n v nhn
ca nh s s tr thnh xt. Tip theo, t mi nh v c nhn cha xt ta li gn nhn
cho tt c cc nh cha c nhn k n v nhn ca nh v tr thnh xt. Qu trnh s
lp li cho n khi hoc l nh t tr thnh c nhn hoc l nhn ca tt c cc nh c
nhn u l xt nhng nh t vn khng c nhn. Trong trng hp th nht ta tm
c ng tng lung, cn trong trng hp th hai i vi lung ang xt khng tn
ti ng tng lung (tc l lung l cc i). Mi khi ta tm c ng tng lung,
ta li tng lung theo ng tm c, sau xo tt c nhn v i vi lung mi thu
c li s dng php gn nhn cc nh tm ng tng lung. Thut ton s kt
thc khi no i vi lung ang c trong mng khng tm c ng tng lung.
Hai th tc tm ng tng lung v tng lung c th m t nh sau.
Procedure Find_Path;
(* Th tc gn nhn tm ng tng lung
p[v], [v] l nhn ca nh v;
VT danh sch cc nh c nhn nhng cha xt;
c[[u,v] kh nng thng qua ca cung (u,v), u, v V;
f[u, v] lung trn cung (u, v), u, v V . *)
begin
p[s]:=s;
[s]:=+ ;
VT=? { s} ;
PathFound:=true;
While VT<> do
Begin
110/164

U VT; (* Ly u t VV *)
For v VTdo
begin
If (f[u,v] <c[u,v] then
Begin
p[v]:=u;
[v]:=min { [u], c[u,v] f[u,v] };
VT= VT ? { v} ; (* Np v vo danh sch nh c nhn *)
If v = t then exit;
Else
If (f[v,u]>0) then
Begin
p[v]:=u;
[v]:=min{ [u], f[v,u] } ;
VT= VT ? { v} ; (* Np v vo danh sch nh c nhn *)
If v = t then exit;
End;
End;
End;
PathFound:=false;
end;
Procedure Inc_Flow;

111/164

(* Tng lung theo ng tng *)

begin
v:=p[t]; u:=t; tang:= [t];
while u<> s do
begin
if v>0 then f[v,u] := f[v,u] + tang;elsebegin
v := -v;f[u,v] := f[u,v] - tang;
end;u := v; v := p[u];
end;
end;
Thut ton Ford_Fulkerson c thc hin nh th tc:
Procedure Max_Flow;
(*Thut ton Ford_Fulkerson *)
begin
(* Khi to: Bt u t lung vi gi tr 0 *)
for u V do
for v V do f[u,v] := 0;
stop:=false;
while not stop do
begin
find_path;
if pathFound then Inc_Flow

112/164

else stop:=true;
end;
<Lung cc i trong mng l f[u,v], u, v V >
<Lt ct hp nht l (VT, V\VT)>
end;
Gi s l kh nng thng qua ca tt c cc khung ca th l cc s nguyn. Khi
sau mi ln tng lung, gi tr lung s tng ln t nht l 1. T suy ra thut ton
Ford_Fulkerson s dng sau khng qu val(f*) ln tng lung v cho ta lung cc i
trong mng. ng thi, r rng f*(u,v) s l s nguyn i vi mi cung (u,v) E. T
ra c cc kt qu sau:
nh l 2 (nh l v lung cc i trong mng v lt ct hp nht). Lung cc i trong
mng bng kh nng thng qua ca lt ct hp nht.
nh l 3 (nh l v tnh nguyn). Nu tt c cc kh nng thng qua l cc s nguyn
th lung tm c cc i vi lung trn cc cung l cc s nguyn.
Tuy nhin, nu cc kh nng thng qua l cc s rt ln th gi tr ca lung cc i
cng c th l rt ln v khi thut ton m t trn s i hi thc hin rt nhiu
bc tng lung. Th d trong hnh 2 s minh ho cho iu ny. Hnh 2(a) m t mng
cn xt vi cc kh nng thng qua trn cc cung. Hnh 2(b) m t lung trn cc cung
(s th hai bn cnh cung) sau khi thc hin tng lung dc theo ng tng lung (s, a,
b, t). Hnh 2(c) m t lung trn cc cung sau khi thc hin tng lung dc theo ng
tng lung (s, b, a, t). R rng, sau 2.106 ln tng lung theo ng (s, a, b, t) v (s, b,
a, t) mt cch lun phin ta thu c lung cc i.

Hnh 2.V d ti t i vi thut ton Ford_Fulkerson.

113/164

Hn th na, nu cc kh nng thng qua l cc s v t, ngi ta cn xy dng c

v d cho thut ton khng dng, v t hn nu dy cc gi tr lung xy dng theo
thut ton hi t th n cn khng hi t n gi tr lung cc i. Nh vy, mun thut
ton lm vic hiu qu, vic la chn ng tng lung cn c tin hnh ht sc cn
thn.
Edmonds v Karp ch ra rng nu ng tng lung c chn l ng ngn nht
t s n t trn th Gf. iu c th thc hin, nu trong th tc tm ng tng
Find_Path m t trn, danh sch VT c t chc di dng QUEUE (ngha l ta thc
hin tm ng tng bi th tc tm kim theo chiu rng) th thut ton s kt thc sau
khng qu mn/2 ln s dng ng tng lung. Nu rng, tm kim theo chiu rng
trn th i hi thi gian O(m+n), th thut ton thu c s c phc tp tnh ton
l O(nm2).
Nh cch t chc tm ng tng kho lo hn, ngi ta xy dng c thut ton
vi phc tp tnh ton tt hn nh: O(n2m) (Dinic, 1970). O(n3) (Karzanov, 1974),
O(n2m2), (Cherkasky, 1977), O(nm log n) (Sleator, - Tarrjan, 1980).
Ta kt thc mc ny bi v d minh ho cho thut ton Ford_Fulkerson sau y. Hnh
3(a) cho mng G cng vi thng qua ca tt c cc cung v lung gi tr 10 trong n.
Hai s vit bn cnh mi cung l kh nng thng qua ca cung (s trong ngoc) v lung
trn cung. ng tng lung c dng (s, v3, v2, v6, v7, t). Ta tnh c (t) = 1, gi tr
lung tng t 10 ln 1. Hnh 3 (b) cho lung thu c sau khi tng lung theo ng
tng tm c.

114/164

Hnh 3. Tng lung dc theo ng tng

Lung trong hnh 3 (b) l cc i. Lt ct hp nht

X ={ s, v2, v3, v5}, X = {v4, v6, v7, t} .
Gi tr lung cc i l 11.

115/164

Mt s bi ton lung tng qut

Trong phn ny ta nu ra mt s dng bi ton v lung tng qut m vic gii chng c
th dn v bi ton lung cc i trnh by trn.

Mng vi nhiu im pht v im thu.

Xt mng G vi p im pht s1, s2, . . ., sp v q im thu t1, t2,. . . , tq. Gi s rng lung
c th i t mt im pht bt k n tt c cc im thu. Bi ton tm lung cc i t
cc im pht n cc im thu c th a v bi ton vi mt im pht v mt im
thu bng cch a vo mt im pht gi s v mt im thu gi t v cnh ni s vi tt c
cc im pht v cnh ni cc im thu vi t.
Hnh 4 minh ho cho cch a mng vi nhiu im pht v nhiu im thu v mng
ch c mt im pht v mt im thu. Kh nng thng qua ca cung ni s vi im pht
sk s bng + nu khng c hn ch v lng pht ca im pht sk, v nu lng pht
ca sk b hn ch bi bk th cung (s, sk) c kh nng thng qua l bk. Cng nh vy, i
vi cc cung ni tk vi im thu t, gi s kh nng thng qua ca (tk, t) s l gii hn
hoc khng gii hn tu theo lng thu ca im thu ny c b gii hn hay khng.
Trng hp mt s im thu ch nhn "hng" t mt s im pht ta c bi ton nhiu
lung l mt bi ton phc tp hn rt nhiu so vi bi ton lung cc i gia im
pht s v im thu t.

Hnh 4. Mng vi nhiu im pht v thu.

116/164

Bi ton vi kh nng thng qua ca cc cung v cc nh.

Gi s trong th G, ngoi kh nng thng qua ca cc cung c(u,v), mi nh v V
cn c kh nng thng qua cc nh l d(v), v i hi tng lung i vo nh v khng
c vt qu d(v), tc l.
f(w,v) d(v)v V
Cn phi tm lung cc i gia s v t trong mng nh vy.Xy dng mt mng G sao
cho: mi nh v ca G tng ng vi 2 nh v+, v- trong G, mi cung (u,v) trong G ng
vi cung (u-,v+) trong G, mi cung (v, e) trong G ng vi mi cung (v-, w+) trong G.
Ngoi ra, mi cung (v+, v-) trong G c kh nng thng qua l d(v), tc l bng kh nng
thng qua ca nh v trong G.Do lung i vo nh v+ phi i qua cung (v+, v-) vi kh
nng thng qua d(v), nn lung cc i trong G s bng lung cc i trong G vi kh
nng thng qua ca cc cung v cc nh.

Hnh 5. Hnh 5a cho v d mng G vi kh nng thng qua cung v nh.

Hnh 5b l mng G tng ng ch c kh nng thng qua trn cc cung.

117/164

Mng trong kh nng thng qua ca mi cung b chn hai pha.

Xt mng G m trong mi cung (u, v) c kh nng thng qua (cn trn ca lung
trn cung) c(u,v) v cn di ca lung l d(u,v). Bi ton t ra l liu c tn ti lung
tng thch t s n t, tc l lung ? f(u,v): u, v V? tho mn thm rng buc
d(u,v) f(u,v) c(u,v) , u, v E,
hay khng?
a vo mng G nh pht sa v nh thu ta v xy dng mng Ga theo qui tc:
Mi cung (u,v) m d(u,v) 0 s tng ng vi 2 cung (sa, v) va (u, ta) vi kh nng
thng qua l d(u,v). Gim c(u,v) i d(u,v) tc l thay kh nng thng qua ca cung (u,v)
bi c(u,v) d(u,v) cn cn di ca n t bng 0. Ngoi ra thm vo cung (t,s) vi c(t,s)
=.

Hnh 6. Mng vi kh nng thng qua b chn hai pha.

118/164

Hnh 6(a) cho v d mng G vi kh nng thng qua ca cc cung b chn c hai pha.
th Ga tng ng c cho trong hnh 6(b).
K hiu d* = ? d(u,v).
d(u,v)0
nh l 4.
1) Nu lung ln nht trong mng Ga t sa n ta bng d* th tn ti lung tng thch
trong G.
2) Nu lung ln nht trong mng Ga t sa n ta l khc d* th khng tn ti lung
tng thch trong G.

119/164

Mt s ng dng trong t hp
Bi ton lung cc i c rt nhiu ng dng trong vic gii bi ton t hp. Kh khn
chnh y l phi xy dng mng tng ng sao cho vic tm lung cc i trong n
s tng ng vi vic gii bi ton t hp t ra. Mc ny s gii thiu mt s bi
ton nh vy.

Bi ton m ci vng qu.

C m chng trai mt vng qu n. i vi mi chng trai ta bit cc c gi m anh ta
va . Hi khi no th c th t chc cc m ci trong chng trai no cng snh
duyn vi cc c gi m mnh va .Ta c th xy dng th vi cc nh biu th cc
chng trai v cc c gi, cn cc cung biu th s va ca cc chng trai vi cc c
gi. Khi ta thu c mt th hai pha.
Th d. C 4 chng trai ? T1, T2, T3,T4?v 5 c gi ? G1, G2, G3,G4, G5?. S va cho
trong bng sau

th tng ng c cho trong hnh 7.

120/164

Hnh 7. Mng tng ng vi bi ton m ci vng qu

a vo im pht s v im thu t. Ni s vi tt c cc nh biu th cc chng trai, v
ni t vi tt c cc nh biu th cc c gi. Tt c cc cung ca th u c kh nng
thng qua bng 1. Bt u t lung 0, ta tm lung cc i trong mng xy dng c
theo thut ton Ford-Fulkerson. T nh l v tnh nguyn, lung trn cc cung l cc s
hoc 1. R rng l nu lung cc i trong th c gi tr Vmax = m, th bi ton c li
gii, v cc cung vi lung bng 1 s ch ra cch t chc m ci tho mn iu kin
t ra. Ngc li, nu bi ton c li gii th Vmax = m. Bi ton v m ci vng qu
l mt trng hp ring ca bi ton v cp ghp trn th hai pha m gii n c
th xy dng thut ton hiu qu hn.

Bi ton v h thng i din chung.

Cho tp m phn t X=? z1, z2, . . . ,zm?. Gi s <A1, A2, . . ., An> v <B1, B2, . . ., Bn>
l hai dy cc tp con ca X. Dy gm n phn t khc nhau ca X: <a1, a2, . . . ,an> c
gi l h thng cc i din chung ca hai dy cho nu nh tm c mt hon v
ca tp ? 1, 2,. . .,n? sao cho < a1, a2, . . . ,an> l h thng cc i din phn bit ca hai
dy <A1, A2, . . ., An> v <B (1), B (2), . . ., B (n)>, tc l iu kin sau c tho
mn: ai Ai ? B (i), i = 1, 2, . . ,n. Xy dng mng G=(V,E) vi tp nh
V = ? s, t? ? ? x1, x2, . . . ,xn?? ? u1, u2, . . . ,un?? ? v1, v2, . . . ,vn?? ? y1, y2, . . . ,yn?.
trong nh xi tng ng vi tp Ai, nh yi tng ng vi tp Bi, cc phn t uj, yj
tng ng vi phn t zj. Tp cc cung ca mng G c xc nh nh sau
E = ? (s,xi): 1in? ? ? (xi,uj): vi zj Ai, 1in, 1jm? ? ?(uj,vj):1jm? ? ?(vj, yi):
vi zj Bi, 1in, 1jm? ? ? (yi, t): 1in?
Kh nng thng qua ca tt c cc cung c t bng 1. D dng thy rng h thng
i din chung ca hai dy v tn ti khi v ch khi trong mng G=(V,E) tm c lung
vi gi tr n. xt s tn ti ca lung nh vy c th s dng thut ton tm lung
cc i t s n t trong mng G=(V,E).

V mt bi ton ti u ri rc.
Trong mc ny ta s trnh by thut ton c xy dng da trn thut ton tm lung
cc i gii mt bi ton ti u ri rc l m hnh ton hc cho mt s bi ton ti
u t hp.
Xt bi ton ti u ri rc:
f(x1,x2,...,xn) =
121/164

(1)
vi iu kin

trong aij ? 0,1? , i = 1, 2, . . . , m; j=1, 2, . . . n, pi nguyn dng, i = 1, 2, . . .,m.

Bi ton (1)-(3) l m hnh ton hc cho nhiu bi ton ti u t hp thc t. Di y
ta dn ra mt vi v d in hnh.
Bi ton phn nhm sinh hot. C m sinh vin v n nhm sinh hot chuyn . Vi
mi sinh vin i, bit aij =1, nu sinh vin i c nguyn vng tham gia vo nhm j,aij =0,
nu ngc li,v pij l s lng nhm chuyn m sinh vin i phi tham d, i = 1, 2, .
. . ,m; j=1, 2,. . . ,n. Trong s cc cch phn cc sinh vin vo nhm chuyn m h c
nguyn vng tham gia v m bo mi sinh vin i phi tham gia ng pi nhm, hy tm
cch phn phi vi s ngi trong nhm c nhiu sinh vin tham gia nht l nh nht c
th c.
a vo bin s
xij=1, nu sinh vin i tham gia vo nhm j,
xij=0, nu ngc li,
i=1, 2, . . .,m, j=1, 2,. . .,n, khi d thy m hnh ton hc cho bi ton t ra chnh l
bi ton (1)-(3).
Bi ton lp lch cho hi ngh. Mt hi ngh c m tiu ban, mi tiu ban cn sinh hot
trong mt ngy ti phng hp ph hp vi n. C n phng hp dnh cho vic sinh hot
ca cc tiu ban. Bit
aij = 1, nu phng hp i l thch hp vi tiu ban j,aij=0, nu ngc li,i=1, 2, . . .,m,
j=1, 2,. . .,n. Hy b tr cc phng hp cho cc tiu ban sao cho hi ngh kt thc sau t
ngy lm vic nht.

122/164

a vo bin s xij = 1, nu b tr tiu ban i lm vic phng j,xij=0, nu ngc li,i=1,

2, . . .,m, j=1, 2,. . .,n, khi d thy m hnh ton hc cho bi ton t ra chnh l bi
ton (1)-(3), trong pi=1, i=1, 2, . . .,m.
B 2.
Bi ton (1)-(3) c phng n ti u khi v ch khi

Chng minh. iu kin cn ca b l hin nhin v t s tn ti phng n ca bi

ton suy ra cc bt ng thc trong (4) c thc hin t nht di dng du ng thc.
chng minh iu kin , ch cn ch ra rng nu iu kin (4) c thc hin th bi
ton lun c phng n. Thc vy, gi s iu kin (4) c thc hin. Khi nu k
hiu I+i=? 1jn: aij=1?,th ? I+i? pi, i = 1, 2, . . .,m. Do nu gi IiI+i, ? Ii? =pi, i=1,
2,. . . ,m,th X* = (x*ij)mxn vi cc thnh phn c xc nh theo cng thc
x*ij = 1, j Ii, x*ij =0, j Ii, i= 1, 2, . . .,m,l phng n ca bi ton (1)-(3). B c
chng minh.
Do (4) l iu kin cn bi ton (1)-(3) c phng n, nn trong phn tip theo ta s
lun gi thit rng iu kin ny c thc hin.
By gi ta ch ra rng vic gii bi ton (1)-(3) c th dn v vic gii mt s hu hn
bi ton lung cc i trong mng. Trc ht, vi mi s nguyn dng k, xy dng
mng G(k) =(V,E) vi tp nh
V= ? s? ? ? ui :i=1, 2,. . . ,m? ? ? wj : j=1, 2, . . .,n? ? ? t?
trong s l im pht, t l im thu, v tp cung
E= ? (s,ui):i=1, 2,. . .,m? ? ? (ui,wj):i=1, 2,. . . ,m; j=1, 2, . . .,n? ? ? (wj,t): j=1, 2, . . .,n? .
Mi cung e E c gn vi kh nng thng qua q(e) theo qui tc sau:
q(s,ui)=pi, i=1, 2,. . .m,
q(ui,wi)=aij, i=1, 2,. . .m; j=1, 2, . . .,n;
q(wj,t)=k, j=1, 2, . . .,n.
123/164

Hnh 8 ch ra cch xy dng mng G(k).

Hnh 8. Mng G(k).

B sau y cho thy mi lin h gia lung cc i trong mng G(k) v phng n
ca bi ton (1)-(3).
B 3.
Gi s i vi s nguyn dng k no , lung cc i nguyn trong mng G(k) c gi
tr l . Khi X* = (x*ij)mxn vi cc thnh phn c xc nh theo cng thc
x*ij = ? * (ui,wj), i=1, 2,. . .,m; j=1, 2,. . . ,n.
l phng n ca bi ton (1)-(3).
Chng minh. Thc vy, do lung cc i trong mng c gi tr v l lung nguyn
nn
? * (s,ui)=pi, i=1, 2,. . .,m,
? * (ui,wj) ? 0,1? , i=1, 2,. . .,m, j=1, 2,. . .,n,
t suy ra
Vy X* l phng n ca bi ton (1)-(3). B c chng minh.
B 4.

124/164

Gi s X* =(x*ij) l phng n ti u v k* l gi tr ti u ca bi ton (1)-(3). Khi

lung cc i trong mng G(k*) c gi tr .
Chng minh. Do gi tr ca lung cc i trong mng G(k*) khng vt qu , nn
chng minh b ta ch cn ch ra lung vi gi tr trong mng G(k*).
Xy dng lung ? * theo cng thc sau:
? * (s,ui) = pi, ? * (ui, wj) = x*ij,
D dng kim tra c ? * l lung trong mng G(m) c gi tr . B c chng
minh.
B 5. Nu k=m th lung cc i trong mng G(m) c gi tr .
Chng minh. Lp lun tng t nh trong B 4, ta ch cn ch ra lung vi gi tr
trong mng G(m). Thc vy, gi s X* = (x*ij)mxn l phng n ca bi ton (1)-(3)
xy dng theo cng thc (5). Xy dng lung ? * theo cng thc ging nh trong chng
minh b 4, ta c lung vi gi tr . B c chng minh.
T b 3 v 4 suy ra vic gii bi ton (1)-(3) dn v vic tm gi tr k* nguyn dng
nh nht sao cho lung cc i trong mng G(k*) c gi tr . B 5 cho ta thy gi tr
k* [1,m]. V vy gii bi ton (1)-(3) ta c th p dng phng php tm kim nh
phn trn on [1,m] tm gi tr k*, trong mi bc cn gii mt bi ton lung
cc i. gii bi ton tm lung cc i trong mng c th s dng cc thut ton a
thc nh ni trn. T suy ra kt qu sau
nh l 5.
Bi ton (1)-(3) gii c nh thut ton a thc vi phc tp tnh ton l
log2m.ONF, trong ONF l phc tp tnh ton ca bi ton tm lung cc i trong
mng G(k).

125/164

Bi tp chng 3
Bi 1 : Cc min trn bng
Cho mt bng ch nht chia thnh MxN vung (M dng, N ct). Mi vung ghi mt
s nguyn dng (trong khong t 1 n 255). Mt min ca bng l tp hp tt c cc
c cng gi tr s sao cho chng i c sang nhau bng cch i qua cc c chung
cnh v c cng gi tr s ang xt. a ch ca mt min l ta [dng, ct] ca u
tin thuc min theo th t duyt t tri sang phi v t trn xung di. Din tch ca
mt min l s thuc min . Th d bng:

c 4 min, min t mu xm (gi tr cc l 2) c a ch [1, 3] v din tch l 7.

Cn xc nh:
S min ca mng.
Min c din tch ln nht (ch r gi tr din tch v a ch ca min).
D liu vo cho trong file vn bn (tn file c t bn phm) c dng:
MN
A[1, 1] A[1, 2]...A[1, N]
A[2, 1] A[2, 2]...A[2, N]
......................................
A[M, 1] A[M, 2]...A[M, N]
trong A[i, j] l gi tr s ca [i, j], cc s trn cng mt dng ghi cch nhau t nht
mt du trng.

126/164

Yu cu chng trnh thit k theo menu gm cc chc nng:

c d liu vo t file
Gii bi ton bng tm kim theo chiu rng.
Gii bi ton bng tm kim theo chiu su.
Kt thc chng trnh.
Kt qu tm uc a ra mn hnh.
Gii hn kch thc: M, N <= 100.

Bi 2.
Cho mt mng N (N <= 20) my tnh c nh s t 1 n N. S mng c cho
bi h gm M knh (on) ni trc tip gia mt s cp my trong mng, m knh tng
ng vi m cp. Cho bit chi ph truyn 1 n v thng tin theo mi knh ca mng.
Ngi ta cn chuyn mt bc thng ip t my s n my t. m bo an ton, ngi
ta chuyn bc thng in ny theo hai ng truyn tin khc nhau (tc khng c knh
no) ca mng c s dng trong c hai ng truyn tin; cho php hai ng truyn
tin cng i qua mt s my tnh). Chi ph ca mt ng truyn c hiu l tng chi
ph trn cc knh ca n. n gi ng truyn t my s sang my t c tnh nh sau:
Vi hai my s v t, cng bc thng ip c di l 1 n v thng tin, n gi truyn
cho cp (s, t) c tnh bng tng chi ph chuyn thng ip an ton (bng tng chi ph
ca hai ng truyn tin) l nh nht.
Ngi ta mong mun mng my tnh (mng truyn tin ni trn tha mn tnh cht an
ton theo ngha l t mt my bt k lun truyn c (mt cch an ton) thng ip ti
mt my bt k khc. Khi mt mng an ton, ngi ta tnh c n gi ca mng l
tng n gi mi ng truyn t mt my bt k ti mt my bt k khc.
Ma trn n gi ca mng l mng hai chiu A c N dng v N ct, m gi tr phn t
A[i, j] chnh l n gi t my i sang my j.

Bi 3 :
Mt kha hc gm N mn hc, mn hc i phi hc trong ti ngy. Gia cc mn hc c
mi quan h trc/sau: c mn hc ch hc c sau khi hc mt s mn hc khc.
Mi quan h c th hin bi mt mng hai chiu A[i, j]; i, j = 1, , N trong

127/164

A[i, j] = 1/0 v A[i, i] bng 0 vi mi i, A[i,j] = 1 khi v ch khi mn hc i phi c dy

xong trc khi hc mn j (ngy kt thc mn i phi trc ngy bt u mn j). Mn hc
i phi dy trc mn hc j nu c mt dy mn hc i1, i2, , ik sao cho a[it, it+1] = 1, 1
<= t <= k-1, i1=i v ik=j. Nu c mt nhm cc mn hc tng i mt khng c quan h
trc/sau th trong mi ngy, v nguyn tc, ta c th hc ng thi tt c nhng mn
hc ny (nu khng vi phm quan h vi cc mn hc khc). Mng A[i, j] c gi l
b tc nu c mt dy cc mn hc i1, i2,, ik, k > 1, m mn i1 phi dy trc mn
i2, mn i2 phi dy trc mn i3, , mn ik-1 phi dy trc mn ik, mn ik phi dy
trc mn i1.
Hy vit chng trnh vi tn KT3.PAS lm cc vic sau:
Hy xt xem mng A c b tc hay khng.
Nu mng A khng b tc, hy tnh xem kha hc c th kt thc trong thi gian nhanh
nht l bao nhiu ngy.
Theo cc hc bo m thi gian hon thnh ngn nht cu 2, hy tnh xem mt hc
sinh trong qu trnh hc phi hc ng thi trong mt ngy nhiu nht bao nhiu mn.
D liu vo c cho bi file text c tn MH.DAT trong s N ghi dng th nht,
trong nhm N dng tip theo, dng th i ghi N s A[i, 1], , A[i, N] dng cui cng
ghi N s nguyn dng ti khng ln hn 30, 1 <= i <= N; N <= 30.
Kt qu ghi ra file TKB.DAT nh sau: dng th nht ghi s 1/0 ty theo mng A b tc
/ khng b tc. Nu dng th nht ghi s 0, ta mi ghi tip kt qu cu 2 v 3.
Kt qu cu 2 ghi tip vo file TKB.DAT N+1 dng nh sau: dng du ghi s T l
s ngy ti thiu c th hon thnh kha hc, tip theo l N dng trong dng th
i ghi 2 s X, Y vi ngha mn hc th i hc t ngy th X n ngy th Y (ch
rngYX=ti1).
Kt qu cu 3 ghi tip vo file TKB.DAT nh sau: dng th nht ghi 2 s Z, W vi
ngha trong ngy Z phi hc W mn (W l s nhiu nht cc mn hc phi hc ng thi
trong mt ngy), tip theo l mt dng ghi tn cc mn hc phi hc ng thi trong
ngy Z.
Trong cc cu 2 v 3, c th c nhiu li gii tng ng ch cu a ra mt li gii.
V d 1

128/164

V d 2

129/164

Bi 4: Hnh vung Latinh

Hnh vung la tinh cp 4 l ma trn vung kch thc 4x4 m mi dng v mi ct ca
n u l mt hon v ca cc ch ci A, B, C, D. Hai hnh vung la tinh c gi l
tng ng nu t hnh ny ta c th thu c hnh kia nh s dng cc php bin i
sau: 1) i ch hai dng; 2) i ch hai ct; 3) i tn hai ch ci.
V d: Hai hnh vung la tinh
ABCD
1=BDAC

ABCD
2=BCDA

CADB

CDAB

DCBA

DABC

l tng ng, bi v i ch dng 3 v 4 ca 1 ta thu c

ABCD
BDAC
DCBA
CADB
tip n i ch ct 3 v 4 ta thu c
ABDC
BDCA
DCAB
CABD
cui cng, i tn hai ch C v D cho nhau (ngha l thay C bi D v thay D bi C) ta
thu c 2.
Yu cu: Cho 1, 2 l hai hnh vung la tinh cp 4. Hy xc nh xem hai hnh vung
cho c tng ng hay khng?
D liu vo: file vn bn LATIN.INP c cu trc nh sau:
130/164

4 dng u tin chc cc dng ca hnh vung 1;

4 dng tip theo cha cc dng ca hnh vung 2;
(cc phn t trong mt dng c vit lin nhau);
Kt qu: Ghi ra file vn bn c tn LATIN.OUT di dng sau:
Dng u tin ghi s lng php bin i k (k=0, nu hai hnh vung l khng tng
ng);
Cc dng tip theo ghi dy cc php bin i cn p dng t 1 thu c 2; thng
tin v mt php bin i bao gm: ch s ca php bin i, ch s hai dng (ct) cn
i ch hoc hai ch ci cn i tn cho nhau.
V d: cc file d liu v kt qu c th:

Bi 5: Truyn tin trn mng

C mt nhm gm N lp trnh vin c nh s t 1 ti N, mt s ngi trong h c
bit a ch email ca nhau. Khi bit mt thng tin no mi h gi thng tin cho nhau.
Bn l mt ngi rt quan trng v bn bit tt c cc mi quan h ca h cng nh bn
c mt thng tin rt c bit m mun cho tt c h u bit. Hy lp trnh ch ra mt s

131/164

t nht cc lp trnh vin cn cho h bit thng tin sao cho nhng ngi c th thng
bo cho tt c nhng ngi cn li thng tin ca bn.
D liu cho trong file vn bn vi tn INFOR.INP trong dng u chc s N (N <=
1000), dng th I trong N dng tip theo cha danh sch cc lp trnh vin m ngi I
bit a ch email ca h. Nu ngi th I khng bit a ch ca bt c ai th dng ny
l dng trng.
Kt qu ghi ra file vn bn vi tn INFOR.OUT trong dng u ghi s K l s ngi
cn cho h bit thng tin. Dng th hai ghi ra ch s ca nhng ngi .
V d:

Bi 6: Mi con ng u v 0
Mt s t nhin dng N u tm c 2 s nguyn dng x <= y sao cho N=xy. Vi
cch phn tch ny ta s hnh thnh ra s t nhhin mi N1=(x-1)(y+1). S ny c th
dng hoc bng 0. Nu n dng ta c th chn mt cch phn tch no v lp li
nhng thao tc trn.
Bi ton: Vi s t nhin N (N <= 10000) cho trc, hy cho bit ta c th sinh ra c
nhng s no.
D liuvo cho trong file text vi tn VE0.INP trong cha mt s duy nht N.
Kt qu ghi ra file text VE0.OUT trong lit k ra tt c cc s tm c theo th t
tng dn.

132/164

V d:

Bi 7: Chuyn bi
Cu b v N (N<=100) vng trn nh s t 1 ti N v t mu cc vng trn (c th
c cc vng trn c mu ging nhau) sau ni tng cp li bng cc cung nh hng,
mi cung c mt mu nht nh. Cc mu ca cung v ca vng trn c nh s t 1
n 100.
Cu b chn 3 s nguyn khc nhau L, K v Q nm trong phm vi t 1 ti N t vo
trong cc vng trn s L v K mi vng trn mt hn bi sau bt u di chuyn theo
quy tc sau :
Bi ch c chuyn theo cung c mu trng vi mu vng trn cha bi th 2
Bi ch c chuyn theo chiu cung
Hai vin bi khng c ng thi cng mt vng trn
Khng nht thit phi di chuyn ln lt cc vin bi.
Qu trnh di chuyn kt thc khi mt trong hai vin bi ti vng trn Q
Hy lp trnh xc nh cch di chuyn chm dt qu trnh sau mt s t nht cc bc
chuyn.
D liu vo: file BI.INP
Dng u : 4 s nguyn N L K Q
Dng th 2 : N s nguyn C1, C2, , Cn, Ci l mu vng trn i.
Dng th 3 : S nguyn M (0<=M<=10000)
M dng sau : mi dng 3 s nguyn Ai,Bi,Di xc nh cung mu Di i t vng trn Ai
ti vng trn Bi.
Cc s trn mt dng cch nhau mt du cch.

133/164

Kt qu: a ra file BI.OUT

Dng u : CO hoc KHONG cho bit qu trnh c kt thc c hay khng.
Nu dng u l CO th dng 2 cha s nguyn xc nh s bc di chuyn ti thiu.
V d :
BI.INP
5341
23214
8
212
415
452
513
322
234
531
351
BI.OUT
CO
3

Bi 8: G mn
Cho bng hnh ch nht kch thc MxN (M s dng, N s ct) vung. Mi mang
gi tr 0 hoc 1, nu (i, j) c mn A[i, j] = 1, ngc li th A[i, j] = 0.

134/164

(a) Mt ngi xut pht t (X1, Y1) khng c mn, kim tra xem ngi ny c th di
chuyn n (X2, Y2) c hay khng bng cch di chuyn sang nhng chung cnh
khng c mn.
(b) Nu kt qu cu a l ngi khng th di chuyn n (X2, Y2) c th hy ch ra
cch g t nht nhng qu mn anh ta c th di chuyn n (X2, Y2).
D liu vo: file text GOMIN.INP
Dng u l 6 s M, N, X1, Y1, X2, Y2 cch nhau bi khong trng.M dng tip theo,
mi dng gm N s 0/1 tng ng c mn hoc khng c mn, mi s cch nhau bi
khong trng.
D liu ra: file text GOMIN.OUT
Dng u cha s 0/1 tng ng vi i c / khng i c.
Nu l khng i c th dng th hai l s K tng ng vi s mn t nht cn phi g.
Nu c s K dng th hai th K dng tip theo, mi dng i gm 2 s tng ng vi ch
s ct v ch s dng ca th i cn phi g mn.

Bi 9:
Cho mt th v hng G gm N nh xc nh bi ma trn k A[N, N] trong A[i,
j] = 1 nu cnh (i, j) G v A[i, j] = 0 nu (i, j) G. Hy ci t thut ton v vit
chng trnh xc nh tnh lin thng ca th G. Nu G khng lin thng, hy cho
bit s thnh phn lin thng trong G v lit k c th cc thnh phn lin thng ny.

Bi 10: Tm kim
Mt vng t hnh ch nht c chia thnh cc mnh t theo dng li MxN. Mi
c th trng trt c s c nh du l 1, cc cn li c nh du l 0. Hai gi
l k nhau nu chng c chung 1 cnh (ngang hay dc). Mt khu t trng l tp hp
cc c th trng trt c nm k nhau ln nht ngha l cc khu t trng phn cch
nhau bi cc c nh du l 0. Hy xc nh s lng v ch r c th cc khu t
trng nm trong vng t. Gi thit rng s lng cc kh ln.

135/164

Bi tp chng 4
Bi 1: Hi ngh bn trn
Tng th k i hi ng Lin hp quc triu tp mt cuc hp c N nh ngoi giao
ca N t chc tham gia. Cc i din ngoi giao c b tr ngi quanh mt bn trn.
Gia mt s t chc c quan h cng thng, v vy khng th xp h ngi cnh nhau
c. Thng tin v quan h gia cc t chc c cho di dng cp s nguyn i, j nu
gia 2 t chc ny c quan h cng thng.Hy lp trnh gip Tng th k Lin hp quc
b tr ch ngi quanh bn hp. Cc t chc c nh s t 1 ti N, 0 < N <= 500.
D liu vo: t file CONF.INP, dng u tin cha s nguyn N, cc dng sau, mi
dng mt cp s i, j cho bit cc i din i v j khng ngi cnh nhau c. Kt thc l
mt dng cha 2 s 0.
Kt qu: a ra file CONF.OUT. Nu khng c cch b tr tha mn yu cu th a ra
thng bo KHONG CO, trong trng hp ngc li a ra dy N s nguyn xc nh
v tr ai ngi cnh ai quanh bn trn.
V d:
CONF.INP CONF.OUT
11 1 9 7 4 11 5 8 2 10 3 6
14
17
57
10 7
10 8
10 9
34
00

136/164

Bi 2: Domino
Cho trc N con c domino, hy vit chng trnh cho bit rng c cch sp N con c
theo ng lut domino sao cho cc con c hnh thnh vng trn hay khng, nu c
hy ch ra mt cch sp.
D liu vo: file DOMINO.INP
Dng u cha s N.N dng tip theo, mi dng cha 2 s t 0 n 6 mang gi tr i
din cho 2 u ca domino.
D liu ra: file DOMINO.OUT
Dng u cha s 1 hoc 0 tng ng vi sp c qun domino thnh vng trn v
khng sp c.Nu dng u l 1 (tng ng vi sp c) th dng th hai lit k ra
N ch s ca N con c domino theo th t sp thnh vng trn. Nu dng u l 0 th
khng c dng th hai.
V d:
DOMINO.INP
4
53
56
23
62
DOMINO.OUT
1
1342

Bi 3: Kim tra ng
Mt trm qung ng giao thng phi chu trch nhim v tnh trng ca mt mng
li giao thng ni gia cc im dn c. Hng thng, h phi c mt i i kim tra
mt vng qua khp mng li xem xt tnh trng hin thi ca cc ng giao thng
nhm bo sa cha kp thi nu c nhu cu. Hy vit chng trnh nhp vo mng li
137/164

giao thng v gip trm quyt nh l trnh ca i kim tra sao cho c th thm tt c
cc con ng m tng chiu di on ng i qua l nh nht.

Bi 4: M i tun
Hy ci t chng trnh xc nh l trnh ca con m trn bn c 8x8 bt u t (i,
j) i qua tt c cc ca bn c vmi ch 1 ln duy nht.M rng vi trng hp bn
c kch thc NxN.

Bi 5: Hi ngh bn trn
C 12 ngi ngi chung 1 bn tic trn. Mi ngi c t nht 6 ngi quen. Hy ch ra
cch sp xp sao cho mi ngi u ngi cnh ngi mnh quen . Tng qut, hy sp
N ngi ngi chung quanh bn trn sao cho mi ngi u ngi cnh ngi mnh quen.
Bit mi ngi c t nht (N + 1)/2 ngi quen.

138/164

Bi tp chng 5
Bi 1 : Mng an ton
Cho mt mng N (N <= 20) my tnh c nh s t 1 n N. S mng c cho
bi h gm M knh (on) ni trc tip gia mt s cp my trong mng, m knh tng
ng vi m cp. Cho bit chi ph truyn 1 n v thng tin theo mi knh ca mng.Ngi
ta cn chuyn mt bc thng ip t my s n my t. m bo an ton, ngi ta
chuyn bc thng in ny theo hai ng truyn tin khc nhau (tc khng c knh no)
ca mng c s dng trong c hai ng truyn tin; cho php hai ng truyn tin
cng i qua mt s my tnh). Chi ph ca mt ng truyn c hiu l tng chi ph
trn cc knh ca n. n gi ng truyn t my s sang my t c tnh nh sau:
Vi hai my s v t, cng bc thng ip c di l 1 n v thng tin, n gi truyn
cho cp (s, t) c tnh bng tng chi ph chuyn thng ip an ton (bng tng chi ph
ca hai ng truyn tin) l nh nht.Ngi ta mong mun mng my tnh (mng truyn
tin ni trn tha mn tnh cht an ton theo ngha l t mt my bt k lun truyn c
(mt cch an ton) thng ip ti mt my bt k khc. Khi mt mng an ton, ngi
ta tnh c n gi ca mng l tng n gi mi ng truyn t mt my bt k ti
mt my bt k khc.Ma trn n gi ca mng l mng hai chiu A c N dng v N
ct, m gi tr phn t A[i, j] chnh l n gi t my i sang my j.
Cu 1: Cho trc mt mng, hy kim ra tnh an ton ca mng .
Cu 2: Khi mng khng an ton c php b sung mt s knh truyn n tr thnh
an ton. n gi mi knh truyn b sung theo c coi bng hai ln gi tr cc i n
gi cc knh c. Mi knh b sung c coi c n gi nh nhau. Hy tm cch b
sung cc knh mi m n gi mng l nh nht.
Cu 3: Khi mng an ton hoc sau khi b sung knh mng an ton, hy in ra n gi
mng v ma trn n gi.
D liu vo: cho trong file INP.B2 vi cu trc nh sau:
Dng u tin ghi 2 s n, m cch nhau bi du cch.Mi dng th i trong s m dng
tip theo ghi thng tin v knh ni th i ca mng gm 3 s d[i], c[i], g[i] trong d[i],
c[i] l ch s ca hai my tng ng vi knh ny v g[i] (nguyn dng) l chi ph
truyn mt n v thng tin t my d[i] n my c[i] theo knh ny. Cc gi tr g[i] cho
trc khng vt qu 40 (v nh vy n gi cc knh b sung khng vt qu 80).
Kt qu: ghi ra file OUT.B2 theo qui cch sau:

139/164

Dng u tin ghi 1 s nguyn p th hin mng c an ton hay khng v p c ngha l
s lng knh cn b sung. p=0 c ngha mng an ton; p>0 c ngha mng khng an
ton v cn b sung p knh na mng an ton vi chi ph b sung t nht.p dng tip
theo ghi p knh b sung. Cch ghi nh trong file d liu vo.Dng tip theo ghi n gi
ca mng an ton.N dng tip theo ghi ma trn n gi ca mng an ton: mi hng ca
ma trn ghi trn mt dng.

Bi 2: Xy dng ng ng nc
C 1 trm cp nc v N im dn c. Hy xy dng chng trnh thit k tuyn ng
ng nc cung cp n mi nh sao cho tng chiu di ng ng phi dng l t nht.
Gi s rng cc ng ng ch c ni gia 2 im dn c hoc gia trm cp nc
vi im dn c.

140/164

Bi tp chng 6
Bi 1: Di chuyn trn cc hnh trn
Cho N hnh trn (nh s t 1 n N). Mt ngi mun i t hnh trn ny sang hnh
trn khc cn tun theo qui c:
Nu khong cch gia 2 im gn nht ca 2 hnh trn khng qu 50 cm th c th
bc sang.Nu khong cch ny hn 50cm v khng qu 80cm th c th nhy sang.Cc
trng hp khc khng th sang c.Mt ng i t hnh trn ny sang hnh trn
khc uc gi l cng "tt" nu s ln phi nhy l cng t. Hai ng i c s ln nhy
bng nhau th ng i no c s hnh trn i qua t hn th ng i "tt" hn.Cc
hnh trn c cho trong mt file vn bn, trong dng th i m t hnh trn s hiu i
(i = 1, 2,..., N) bao gm 3 s thc: honh tm, tung tm, ln bn knh (n v
o bng mt).Lp trnh c cc hnh trn t mt file vn bn (tn file vo t bn phm),
sau c mi ln c s hiu hnh trn xut pht S v hnh trn kt thc T t bn phm,
chng trnh s a ra ng i t S n T l "tt nht" theo ngha nu (hoc thng
bo l khng c).Yu cu ng i c vit di dng mt dy cc s hiu hnh trn
ln lt cn c i qua trong ni r tng s cc bc nhy, tng s cc hnh trn i
qua v nhng bc no cn phi nhy.Gii hn s hnh trn khng qu 100.

Bi 2: Tm hnh trnh tn t xng nht

Trn mt mng li giao thng, mt ngi mun i t im A n im B bng xe my.
Xe cha c ti a 3 lt xng v chy 100km ht 2,5 lt. Cc trm xng ch c t
cc im dn c, khng t gia ng v ngi ny khng mang theo bt k thng
cha xng no khc. Hy vit chng trnh nhp vo mng li giao thng v xc nh
gip ngi ny tuyn ng i t A n B sao cho t tn xng nht.

Bi 3: Di chuyn gia cc o
Trn mt o quc, c N hn o. Gi s tt c cc o u c hnh dng l hnh ch
nht nm ngang. Trn mi hn o c th c sn bay nm trung tm o, c th c
cng nm 4 gc o. Trn mi o u c tuyn ng xe but ni 4 gc o vi nhau
v vi trung tm o. Gia 2 o c th i li bng my bay nu c 2 o u c sn bay
v c th i li bng tu nu c 2 o u c cng.
Gi s rng:
Cc tuyn ng (b, khng, thy) u l ng thng.Chi ph cho mi km v tc
ca mi loi phng tin l:
141/164

Hy vit chng trnh xc nh tuyn ng v cch di chuyn gia 2 hn o trong o

quc sao cho:
Thi gian di chuyn t nht.
Chi ph di chuyn t nht.
Thi gian di chuyn t nht nhng vi mt s tin chi ph khng qu ng.
Chi ph di chuyn t nht nhng vi thi gian di chuyn khng vt qu T gi.

Bi 4: Hnh trinh ti y
Cc t i t cc thnh ph khc nhau x1, x2,., xn v cng ti mt a im thng
nht y. Nu tn ti ng i t xi n xj th ta k hiu tij l thi gian cn thit i t
xi n xj, cij l lng t c th i trn con ng trong mt n v thi gian (cij =
0 nu khng c ng i), cii l lng t c th ngh ng thi thnh ph xi, ai l s
lng xe ban u c xi. Hy t chc hnh trnh sao cho trong khong thi gian t s
t ti y l nhiu nht.

Bi 5: Tm ng ngn nht
Gi s X l tp cc khu dn c, U l tp cc ng s ni lin cc khu . Ta gi s mi
ch giao nhau ca cc con ng u thuc X. Vi con ng u, s l(u) l di ca u
tnh bng km. Hy ch ra tuyn ng i t mt khu i sang khu j sao cho tng chiu di
l nh nht.

Bi 6: ng i trn li
Cho 1 ma trn A[M, N], mi phn t ca n cha 1 s t nhin. T 1 (i, j) ta c th i
sang k n (c chung 1 cnh) nu gi tr ca k ny nh hn gi tr lu trong (i, j).
Hy tm 1 ng i t (i, j) ti (k, l) trn ma trn sao cho phi i qua t nht. Hy
tm 1 ng i t (i, j) ti (k, l) trn ma trn sao cho tng gi tr cc phi i qua
nh nht.
142/164

Bi 7 : Tm ng vi chi ph phi tr cho php

C N thnh ph c nh s t 1..N ni vi nhau bng cc on ng mt chiu. Mi
on ng bao gm 2 thng s : di v chi ph i ca on ng.A sng ti thnh
ph 1 v A mun di chuyn n thnh ph N nhanh nht c th.Bn hy gip A tm ra
ng i ngn nht t thnh ph 1 n thnh ph N m A c kh nng chi tr tin.D
liu vo: ROADS.IN
Dng u tin cha s nguyn K, 0 <= K <= 10000, s tin m A c.Dng th 2 cha
s nguyn N, 2 <= N <= 100, s thnh ph.Dng th 3 cha s nguyn R, 1 <= R <=
10000, tng s on ng.Mi dng trong s R dng tip theo m t mt on ng
bng cc s S, D, L v T cch nhau bi t nht mt khong trng.
S l thnh ph khi hnh, 1 <= S <= N.
D l thnh ph n, 1 <= D <= N.
L l di ca on ng, 1 <= L <= 100.
T l l ph, 0 <= T <= 100.
Ch rng gia 2 thnh ph c th c nhiu on ng ni 2 thnh ph ny.
D liu ra: ROADS.OUT
Ch c duy nht 1 dng cha tng di ca ng i ngn nht t 1->N v nh hn K.

143/164

144/164

Bi tp chng 7
Bi 1
Cho G=(V,E) th c hng trong khng c cung (s,t). Chng minh rng s ng
i c bn ni hai nh s v t l bng s t nht cc nh ca th cn loi b trong
th khng cn ng i ni s vi t.

Bi 2
Xy dng thut ton tm tp E1 tt c cc cung ca th m vic tng kh nng thng
qua ca bt k cung no trong E u dn n tng gi tr ca lung cc i trong mng.

Bi 3
Cho hai dy s nguyn dng {pi, i=1,2,,m} v {qj, j=1,2,,n}. Hy xy dng ma
trn A={aij : i=1,2,,m; j=1,2,n} vi cc phn tai j {0,1} c tng cc phn t trn
dng i l pi , tng cc phn t trn ct j l qj.

Bi 4
C m chng trai, n c gi v k b mi, Mi b mi p (p=1,2,,k) c mt danh sch
Lp mt s chng trai v c gi trong s cc chng trai v c gi ni trn l khch hng
ca b ta. B mi p c th se duyn cho bt c cp trai gi no l khch hng ca b ta,
nhng khng sc t chc qu dp m ci. Hy xy dng thut ton cn c vo danh
sch Lp, dp, p=1,2,,k; a ra cch t chc nhiu nht cc m ci gia m chng trai
v n c gi vi s gip ca cc b mi.

Bi 5 : Chuyn bi
Cu b v N (N<=100) vng trn, nh s t 1 ti N v t mu cc vng trn (c
th c cc vng trn c mu ging nhau), sau ni tng cp cc cung nh hng, mi
cung c mt mu nht nh. Cc mu (ca cung v vng trn) c nh s t 1 n
100.Cu b chn 3 s nguyn khc nhau L, K v Q nm trong phm vi t 1 ti N, t
vo trong cc vng trn s L v K mi vng mt hn bi, sau bt u di chuyn bi
theo nguyn tc sau:
Bi ch c chuyn theo cung c mu trng vi mu ca vng trn cha vin bi th 2.Bi
ch c chuyn theo chiu cung

145/164

Hai vin bi khng c ng thi cng mt vng trn;

Khng nht thit phi di chuyn ln lt cc vin bi,
Qu trnh di chuyn kt thc, khi mt trong hai vin bi ti vng trn Q.
Hy lp trnh xc nh cch di chuyn chm dt qu trnh sau mt s t nht cc bc
chuyn.
D liu vo t file BL.INP:
Dng u: 4 s nguyn N L K Q
Dng th 2: N s nguyn C1, C2,,Cn; Ci l mu vng trn i
Dng th 3: s nguyn M (0 M 10000)
M dng sau: mi dng 3 s nguyn Ai Bi Di; xc nh cung mu Di t vng trn Ai ti
vng trn Bi.
Cc s trn mt dng cch nhau mt du cch.
Kt qu a ra file BL.OUT:
Dng u: CO hoc KHONG, cho bit qu trnh c kt thc c hay khng,nu dng
u l CO th dng 2 cha s nguyn xc nh s bc chuyn ti thiu .

146/164

Bi 6 : Bng in
Mt li vung c ph trn mt bng in hnh vung. V tr nm trn giao ca 2
ng k ca li s c gi l nt. Tt c c nxn nt trn li.

147/164

C mt s nt cha tip im. Nhim v ca bn l cn ni cc tip im vi cc nt

trn bin ca bng bi cc on dy dn (gi l cc mch). Cc mch ch c chy
dc theo cc ng k ca li (ngha l khng c chy theo ng cho). Hai mch
khng c php c im chung, v vy hai mch bt k khng c php cng chy
qua cng mt on ng k ca li cng nh khng c chy qua cng mt nt ca
li. Cc mch cng khng c chy dc theo cc on k ca li trn bin (mch
phi kt thc khi n gp bin) v cng khng c chy qua nt cha tip im khc.
V d: Bng in v cc tip im c cho trong hnh 2a. Nt t m trong hnh v th
hin v tr cc tip im.
Yu cu: Vit chng trnh cho php ni c mt s nhiu nht cc tip im vi
bbin. Cc tip im trn bin tha mn i hi t ra, v th khng nht thit phi
thc hin mch ni chng. Nu nh c nhiu li gii th chi cn a ra mt trong s
chng.
D liu vo: file vn bn ELE.INP:
Dng u tin cha s nguyn n (3 <= n <= 15).Mi dng trong s n dng tip theo
cha n k t phn cch nhau bi mt du cch. Mi k t ch l 0 hoc 1. K t 1 th
hin tip im, k t 0 th hin nt khng c tip im trn v tr tng ng ca li.
Cc nt c nh s t 1 n n*n theo th t t tri sang phi, t trn xung di. Ch
s ca nt cha tip im s l ch s ca tip im.
Kt qu: ghi ra file ELE.OUT:
Dng u tin cha k l s tip im ln nht c th ni vi bin bi cc mch.Mi
dng trong s k dng tip theo m t mt mch ni mt trong s k tip im vi bin
theo qui cch sau: u tin l ch s ca tip im c ni, tip n l dy cc k t m
t hng ca mch ni: E: ng, W: ty, N: bc, S: nam. Gia ch s v dy k t phi
c ng mt du cch, cn gia cc k t trong dy k t khng c c du cch.Kt
qu phi c a ra theo th t tng dn ca ch s tip im.

148/164

V d:

149/164

Cc bi tp khc
Bi 1:
Mt kha hc gm N mn hc, mn hc i phi hc trong ti ngy. Gia cc mn hc c
mi quan h trc/sau: c mn hc ch hc c sau khi hc mt s mn hc khc.
Mi quan h c th hin bi mt mng hai chiu A[i, j]; i, j = 1, , N trong
A[i, j] = 1/0 v A[i, i] bng 0 vi mi i, A[i, j] = 1 khi v ch khi mn hc i phi c
dy xong trc khi hc mn j (ngy kt thc mn i phi trc ngy bt u mn j). Mn
hc i phi dy trc mn hc j nu c mt dy mn hc i1, i2, , ik sao cho a[it, it+1]
= 1, 1 <= t <= k-1, i1=i v ik=j. Nu c mt nhm cc mn hc tng i mt khng
c quan h trc/sau th trong mi ngy, v nguyn tc, ta c th hc ng thi tt c
nhng mn hc ny (nu khng vi phm quan h vi cc mn hc khc). Mng A[i, j]
c gi l b tc nu c mt dy cc mn hc i1, i2,, ik, k > 1, m mn i1 phi dy
trc mn i2, mn i2 phi dy trc mn i3, , mn ik-1 phi dy trc mn ik, mn ik
phi dy trc mn i1.Hy vit chng trnh vi tn KT3.PAS lm cc vic sau:
1. Hy xt xem mng A c b tc hay khng.
2. Nu mng A khng b tc, hy tnh xem kha hc c th kt thc trong thi gian
nhanh nht l bao nhiu ngy.
3. Theo cc hc bo m thi gian hon thnh ngn nht cu 2, hy tnh xem mt hc
sinh trong qu trnh hc phi hc ng thi trong mt ngy nhiu nht bao nhiu mn.
D liu vo c cho bi file text c tn MH.DAT trong s N ghi dng th nht,
trong nhm N dng tip theo, dng th i ghi N s A[i, 1], , A[i, N] dng cui cng
ghi N s nguyn dng ti khng ln hn 30, 1 <= i <= N; N <= 30.
Kt qu ghi ra file TKB.DAT nh sau: dng th nht ghi s 1/0 ty theo mng A b tc
/ khng b tc. Nu dng th nht ghi s 0, ta mi ghi tip kt qu cu 2 v 3.
Kt qu cu 2 ghi tip vo file TKB.DAT N+1 dng nh sau: dng du ghi s T l s
ngy ti thiu c th hon thnh kha hc, tip theo l N dng trong dng th i ghi
2 s X, Y vi ngha mn hc th i hc t ngy th X n ngy th Y (ch rng Y
X = ti 1).Kt qu cu 3 ghi tip vo file TKB.DAT nh sau: dng th nht ghi 2 s
Z, W vi ngha trong ngy Z phi hc W mn (W l s nhiu nht cc mn hc phi
hc ng thi trong mt ngy), tip theo l mt dng ghi tn cc mn hc phi hc ng
thi trong ngy Z.Trong cc cu 2 v 3, c th c nhiu li gii tng ng ch cn
a ra mt li gii.

150/164

V d 1

V d 2

151/164

Bi 2:
Gim c mt cng ty quyt nh t chc bui tic tr gp g ton th nhn vin trong
cng ty. Cng ty c t chc theo m hnh phn cp lnh o v mi quan h th
trng nhn vin to thnh cy c gc l gim c. m bo khng kh t nhin,
gim c quyt nh khng th trng v nhn vin di quyn ngi cng mt bn.
P gi l th trng ca Q, nu P l th trng trc tip ca Q hoc tn ti dy P1, P2,
, Pk (1 < k), sao cho P = P1, Q = Pk v Pi l th trng trc tip ca Pi+1 (i = 1, 2,
, k -1). Tt c mi ngi trong cng ty c nh s t 1 n N (N l tng s ngi
trong cng ty vi gim c bt u t 1).
Yu cu: tnh s lng bn t nht cn thit c th b tr cho mi ngi ngi theo
yu cu nu trn v cho mt phng n b tr ngi mi bn.
D liu vo: file text COMPANY.INP, dng u tin l s nguyn m s gh ti a
cho mt bn, dng th 2 s nguyn N s ngi trong cng ty, dng th ba (v cc
dng sau nu cn) l dy s nguyn, cc s cch nhau t nht mt du cch hoc nhm
k t xung dng, s nguyn th i trong dy cho bit ai l th trng trc tip ca nhn
vin i. Gim c khng c th trng nn s ny bng 0.
152/164

2 <= m <= 10, 1 <= N <= 200.

Kt qu: a ra file text COMPANY.OUT, dng u tin l s bn t nht cn thit, cc
dng sau mi dng tng ng vi mt bn v cha dy s nguyn xc nh ai c b
tr ngi sau bn .
V d:
COMPANY.INP
4
13
0 1 9 9 9 2 2 1 1 7 8 8 10
File kt qu COMPANY.OUT c th c ni dung:
5
13 3 4 5
10 6 8
7 9 11 12
2
1

Bi 3:
Trn bn c NxN, hy tm cch sp xp s lng ti a cc con hu sao cho khng con
no c th n con no.

Bi 4:
Cho 1 th c hng G, hy tm mt tp hp X0 t nht cc nh ca G sao cho mi
nh i ca G hoc thuc X0 hoc i ni trctip vi nh j thuc X0. Lm bi 14 trong
trng hp G v hng.

153/164

Bi 5:
Trn bn c NxN, hy tm cch sp xp s lng ti thiu cc con hu sao cho mi c
trn bn c b chiu bi t nht 1 con.

Bi 6:
Mt k tc x nui 15 c gi. Hng ngy cc c i chi vi nhau theo b 3. Hi c th
a cc c i chi trong ti a bao nhiu ngy khng c 2 c no i chung trong mt
b 3 qu 1 ln.Hy tng qut ha bi ton.

Bi 7:
Trong 1 tri giam thnh ph A, mi nh giam c mt trm gc c lp, nhng ngi
ng gc, chng hn nh giam x0, cng c th thy nhng g xy ra cc tri giam x1,
x2, x3 khc do cc nh giam ny thng vi x0 bi 1 hnh lang thng. Gi s bit cc
thng tin trn, hy xc nh s lng ti thiu cc lnh canh c th quan st c mi
nh giam.

Bi 8:
Mt s hi cng x1, x2, x3 c cc mt hng m cc hi cng y1, y2, y3cn n.
Lng hng c xi l si v yu cu hng ha ca yi l di. Nu c tu i t xi ti yj th ta
k hiu cij l tng lng hng m cc tu c th vn chuyn t xi ti yj. Vy c th tha
mn mi yu cu khng? T chc vn chuyn ra sao? Hy vit chng trnh gii quyt
bi ton trn.

Bi 9:
Trong mt cuc du lch, m gia nh phn nhau i trn n xe. Cc gia nh tng ng c
r1, r2, , rm ngi v cc xe tng ng c s1, s2, , sn ch ngi. Hy tm cch phn
phi sao cho 2 ngi cng gia nh khng ngi chung mt xe hoc cho bit khng th
lm nh vy.

Bi 10:
Trong mt trng trung hc, mi hc sinh n c m bn nam v mi hc sinh nam c m
bn n. Hy ch ra cch sp xp mi c gi c th ln lt khiu v vi cc bn trai
ca mnh v cc chng trai c th ln lt khiu v vi cc bn gi ca mnh.

154/164

Bi 11:
Mt nh in phi sn xut n cun sch bng 2 my: mt in, mt ng sch. Gi ak
l thi gian cn cho vic in cun th k v bk l thi gian cn cho vic ng cun .
Tt nhin l sch phi in xong mi ng, do my ng c th phi ch i lu hay
chng. Vy tin hnh theo th t no c th xong vic sm nht.

Bi 12: n nh
Trong mt lp c N dy bn v mi dy c M ch ngi. Trong lp c K cn s lp. Mi
mt cn s cm mt bi tp. Cc cn s ny c nhim v chuyn bi tp n cc
hc sinh khc ngi k mnh pha trc, sau, tri v phi. Sau khi cc cn s lm xong
cng vic ca mnh, mi hc sinh thng bo s lng bi tp mnh nhn c.
Da trn thng tin ny hy xc nh v tr ca cc cn s trong lp.

Bi 13:
C mt my thu v mt my pht tn hiu. Gi s my pht c th pht i 5 loi tn hiu
khc nhau a, b, c, d, e. my thu mi tn hiu c th c hiu theo 2 cch khc nhau:
tn hiu a c th hiu p hay q, tn hiu b c th hiu q hay r, ... S cc i cc tn hiu
m ta c th s dng l bao nhiu cho my thu khng xy ra nhm ln gia cc tn
hiu c s dng.

Bi 14:
Cho 1 th v hng G. Ngi ta mun t cc nh ca G bng 2 mu en, trng sao
cho 2 nh k nhau khng c t bi cng 1 mu. Hy cho bit c th lm c iu
ny khng. Nu c hy ch ra cch t.

Bi 15:
Cho mt th khng nh hng trong mt tp vn bn vi cch m ha nh sau
Dng u l s nh (n). Cc nh c xem nh s lin tip t 1 n n.
Mi dng sau l m t mt cnh cho bng ch s 2 nh l u mt ca cnh .
Yu cu t mu mt s nh thnh m sao cho s nh l ln nht nhng khng
c cnh no c php c c hai u mt l cc nh . Kt qu cho ra trn hai dng.
Dng th nht l s nh mu , dng th hai l s th t cc nh c mu .

155/164

Bi 16:
Gim c mt cng ty quyt nh t chc bui tic tr gp g ton th nhn vin trong
cng ty. Cng ty c t chc theo m hnh phn cp lnh o v mi quan h th
trng nhn vin to thnh cy c gc l gim c. m bo khng kh t nhin,
gim c quyt nh khng th trng v nhn vin di quyn ngi cng mt bn.
P gi l th trng ca Q, nu l P th trng trc tip ca Q hoc tn ti dy P1, P2,
..., Pk (1 < k), sao cho P = P1, Q = Pk v Pi l th trng trc tip ca Pi+1 (i = 1,2,
..., k-1). Tt c mi ngi trong cng ty c nh s t 1 n N tng s ngi trong
cng ty, bt u t gim c vi s l 1.
Yu cu tnh s lng bn t nht cn thit c th b tr cho mi ngi ngi theo yu
cu nu trn v cho mt phng n b tr ngi mi bn.
D liu vo : File ASCII COMPANY.INP, dng u tin l s nguyn m s gh ti
a cho mt bn, dng th 2 s nguyn N s ngi trong cng ty, dng th 3 (v cc
dng sau nu cn) l dy s nguyn, cc s cch nhau t nht mt du cch hoc nhm
k t xung dng, s nguyn th i trong dy cho bit ai l th trng trc tip ca nhn
vin i. Gim c khng c th trng nn s ny bng 0. 2 <= m <= 10, 1 <= N <= 200.
Kt qu : a ra file ASCII COMPANY.OUT, dng u tin l s bn t nht cn thit,
cc dng sau mi dng tng ng vi mt bn v cha dy s nguyn xc nh ai c
b tr ngi sau bn .
V d :
COMPANY.INP
4
13
0 1 9 9 9 2 2 1 1 7 8 8 10
File kt qu COMPANY.OUT c th c ni dung :
5
13 3 4 5
10 6 8
7 9 11 12

156/164

2
1

Bi 17:
Mt h thng c N (N<=50) thnh ph (c nh s t 1 n N) c ni vi nhau
bng mt h thng giao thng c cho bng cc ng ni trc tip cc cp hai thnh
ph: mi on ni trc tip c di l 1 v l ng i hai chiu. H thng ny c
gi l "chn-l" nu nh khi hai thnh ph c ni vi nhau (c th qua cc thnh ph
khc) bi mt ng i vi di chn th lun tm c ng i c di l ni
hai thnh ph . Cc bi ton c t ra :
Cu 1 : Vi mt h thng giao thng cho, kim tra xem n c tnh "chn-l" hay
khng ?
Cu 2 : Nu cu tr li ca cu 1 l ph nh th hy ch ra tp con X trong h thng cc
thnh ph ni trn v c nhiu nht cc thnh ph m m bo iu kin sau: Nu c
ng i ni hai thnh ph bt k trong X th di ng i phi chn (gi nguyn
h thng giao thng).
iu kin k thut :
File d liu vo tn CHANLE.INP:
Dng u tin cha gi tr N.
Cc dng tip theo cha lng chn cc s nguyn khng m m hai s nguyn cui
cng l 0, cn mi s nguyn khc ch l ch s thnh ph; tng cp hai s nguyn s
ch ra s hiu c3a hai thnh ph c ni trc tip vi nhau.
File kt qu ra c tn CHANLE.OUT:
Dng u c s 0 hoc 1 cho cu 1, trong 1 ch ra rng h thng ni trn c tnh chn
l, 0 ph nh.
Nu c kt qu ph nh th cc dng tip theo c dng :
+ Dng th 2 c s lng phn t ca X.
+ Cc dng tip theo (t dng th 3 tr i) cha s hiu cc thnh ph c trong X.
V d:

157/164

CHANLE.INP c ni dung :
4
121300
CHANLE.OUT
0
3
234
Nu file CHANLE.INP c ni dung :
5
1223
344551
00
CHANLE.OUT
1

158/164

Tham gia ng gp
Ti liu: Gio trnh l thuyt th
Bin tp bi: Thc s Nguyn Thanh Hng
URL: http://voer.edu.vn/c/9c021e14
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Cc khi nim c bn ca l thuyt th
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/dff2cfd5
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Cc thut ng c bn
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/8bb57be5
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: ng i,chu trnh, lin thng
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/89915f67
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Mt s dng th c bit
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/dc7bfbe3
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Biu din th trn my vi tnh
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/a2d8be8f
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Danh sch cnh(cung)
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/59983be8

159/164

Giy php: http://creativecommons.org/licenses/by/3.0/

Module: Danh sch k
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/68b497ec
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Cc thut ton tm kim trn th v ng dng
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/ace8b5e6
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Tm kim theo chiu rng trn th
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/89d6341f
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Tm ng i v kim tra tnh lin thng
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/d2dc68dc
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: th Euler v th Hamiton
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/86e257a7
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: th Hamilton
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/bfd2a4cd
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Cy v cy khung ca th
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/0e5f8db1
Giy php: http://creativecommons.org/licenses/by/3.0/

160/164

Module: Cy khung ca th
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/38e67226
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Xy dng tp cc chu trnh c bn ca th
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/c81ff79e
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Bi ton cy khung nh nht
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/a471d510
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Bi ton ng i ngn nht
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/379a7e15
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: ng i ngn nht xut pht t mt nh
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/8a2a4473
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Trng hp ma trn trng s khng m-Thut ton Dijkstra
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/6596ee64
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: th trong th khng c chu trnh
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/9907bd7f
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: ng i ngn nht gia tt c cc cp nh

161/164

Cc tc gi: Thc s Nguyn Thanh Hng

URL: http://www.voer.edu.vn/m/0458afc2
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Bi ton lung cc i trong mng
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/6ecc9764
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Lt ct.ng tng lung.nh l Ford_Fulkerson
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/e53b84ad
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Thut ton tm lung cc i
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/b8002118
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Mt s bi ton lung tng qut
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/71b4fb8b
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Mt s ng dng trong t hp
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/24536c8c
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Bi tp chng 3
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/2e1f015b
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Bi tp chng 4
Cc tc gi: Thc s Nguyn Thanh Hng

162/164

URL: http://www.voer.edu.vn/m/81c4fff8
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Bi tp chng 5
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/2ebf2242
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Bi tp chng 6
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/b3ee2dc1
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Bi tp chng 7
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/1f563e19
Giy php: http://creativecommons.org/licenses/by/3.0/
Module: Cc bi tp khc
Cc tc gi: Thc s Nguyn Thanh Hng
URL: http://www.voer.edu.vn/m/5c9f35e1
Giy php: http://creativecommons.org/licenses/by/3.0/

163/164

Chng trnh Th vin Hc liu M Vit Nam

Chng trnh Th vin Hc liu M Vit Nam (Vietnam Open Educational Resources
VOER) c h tr bi Qu Vit Nam. Mc tiu ca chng trnh l xy dng kho
Ti nguyn gio dc M min ph ca ngi Vit v cho ngi Vit, c ni dung phong
ph. Cc ni dung u tun th Giy php Creative Commons Attribution (CC-by) 4.0
do cc ni dung u c th c s dng, ti s dng v truy nhp min ph trc
ht trong trong mi trng ging dy, hc tp v nghin cu sau cho ton x hi.
Vi s h tr ca Qu Vit Nam, Th vin Hc liu M Vit Nam (VOER) tr thnh
mt cng thng tin chnh cho cc sinh vin v ging vin trong v ngoi Vit Nam. Mi
ngy c hng chc nghn lt truy cp VOER (www.voer.edu.vn) nghin cu, hc
tp v ti ti liu ging dy v. Vi hng chc nghn module kin thc t hng nghn
tc gi khc nhau ng gp, Th Vin Hc liu M Vit Nam l mt kho tng ti liu
khng l, ni dung phong ph phc v cho tt c cc nhu cu hc tp, nghin cu ca
c gi.
Ngun ti liu m phong ph c trn VOER c c l do s chia s t nguyn ca cc
tc gi trong v ngoi nc. Qu trnh chia s ti liu trn VOER tr ln d dng nh
m 1, 2, 3 nh vo sc mnh ca nn tng Hanoi Spring.
Hanoi Spring l mt nn tng cng ngh tin tin c thit k cho php cng chng d
dng chia s ti liu ging dy, hc tp cng nh ch ng pht trin chng trnh ging
dy da trn khi nim v hc liu m (OCW) v ti nguyn gio dc m (OER) . Khi
nim chia s tri thc c tnh cch mng c khi xng v pht trin tin phong
bi i hc MIT v i hc Rice Hoa K trong vng mt thp k qua. K t , phong
tro Ti nguyn Gio dc M pht trin nhanh chng, c UNESCO h tr v c
chp nhn nh mt chng trnh chnh thc nhiu nc trn th gii.

164/164