Giáo trình toán rời rạc
Nội dung tài liệu
Tải xuống
Link tài liệu:
Các tài liệu liên quan
Có thể bạn quan tâm
Thông tin tài liệu
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao ®¼ng C¬ ®iÖn hµ Néi
Khoa c«ng nghÖ th«ng tin
GIÁO TRÌNH MÔN
TOÁN RỜI RẠC
(Tài liệu lưu hành nội bộ)
Giáo viên biên soạn: Nguyễn Thị Xuyến
Khoa
Hµ Néi - 2011
: Công nghệ thông tin
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
Ch-¬ng 1. Lý thuyÕt tæ hîp
1.1. S¬ l-îc vÒ tæ hîp:
Tæ hîp lµ mét phÇn quan träng cña to¸n häc rêi r¹c chuyªn nghiªn
cøu sù s¾p xÕp c¸c ®èi t-îng, chñ ®Ò nµy ®· ®-îc nghiªn cøu tõ thÕ kû 17.
Khi nh÷ng trß ch¬i may rñi, liÖt kª,®Õm c¸c ®èi t-îng cã nh÷ng tÝnh chÊt
nµo ®ã lµ mét phÇn quan träng cña lý thuyÕt tæ hîp. VÝ dô ta dïng quy t¾c
®Õm ®Ó tÝnh tÊt c¶ c¸c sè ®iÖn tho¹i cã thÓ cã trªn toµn n-íc Mü, sè mËt
khÈu cho phÐp truy nhËt hÖ m¸y tÝnh, liÖt kª c¸c thø tù vÒ ®Ých kh¸c nhau
cña c¸c vËn ®éng viªn cã thÓ x¶y ra trong cuéc ch¹y thi.
Mét bµi to¸n kh¸c trong lý thuyÕt tæ hîp lµ viÖc t¹o ra c¸c c¸ch s¾p
xÕp theo mét kiÓu nµo ®ã. VÊn ®Ò nµy rÊt quan träng trong c¸c m« pháng
m¸y tÝnh.
1.1.1. Quy t¾c céng:
Gi¶ sö cã hai c«ng viÖc. ViÖc thø nhÊt cã thÓ lµm b»ng n1 c¸ch, viÖc
thø hai cã thÓ lµm b»ng n2 c¸ch vµ nÕu hai viÖc nµy kh«ng thÓ lµm ®ång thêi,
khi ®ã sÏ cã n1+n2 c¸ch lµm mét trong hai viÖc ®ã.
VÝ dô1: Gi¶ sö cÇn chän hoÆc lµ mét c¸n bé cña khoa tin hoÆc lµ mét
sinh viªn tin lµm ®¹i biÓu trong héi ®ång cña mét tr-êng. Hái cã bao nhiªu
c¸ch chän vÞ ®¹i biÓu nµy nÕu khoa tin cã 37 c¸n bé vµ 83 sinh viªn?.
Chóng ta më r«ng quy t¾c céng cho tr-êng hîp cã nhiÒu h¬n hai c«ng
viÖc. Gi¶ sö c¸c viÖc T1, T2, …,Tm cã thÓ lµm t-¬ng øng b»ng n1, n2, …, nm
c¸ch vµ gi¶ sö kh«ng cã hai viÖc nµo ®ã cã thÓ lµm ®ång thêi. Khi ®ã sè
c¸ch lµm mét trong m viÖc ®ã lµ n1+n2 +….+nm.
VÝ dô2: Mét sinh viªn cã thÓ chän bµi thùc hµnh m¸y tÝnh tõ mét trong
ba danh s¸ch t-¬ng øng cã 23, 15 vµ 19 bµi. Cã bao nhiªu c¸ch chän bµi
thùc hµnh?.
Quy t¾c céng cã thÓ ph¸t biÓu d-íi d¹ng ng«n ng÷ tËp hîp nh- sau:
NÕu A1, A2, …, Am lµ c¸c tËp rêi nhau, khi ®ã sè phÇn tö cña hîp c¸c tËp hîp
Khoa C«ng NghÖ Th«ng Tin
1
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
nµy b»ng tæng sè c¸c phÇn tö cña c¸c tËp thµnh phÇn.
A1 A2 ... Am A1 A2 ... Am
1.1.2. Quy t¾c nh©n:
Gi¶ sö nhiÖm vô nµo ®ã ®-îc t¸ch ra lµm hai viÖc. ViÖc thø nhÊt cã
thÓ lµm b»ng n1 c¸ch, viÖc thø hai cã thÓ lµm b»ng n2 c¸ch sau khi thùc hiÖn
viÖc thø nhÊt ®· lµm, khi ®ã sÏ cã n1 n 2 c¸ch thùc hiÖn nhiÖm vô nµy.
VÝ dô3: Trong mét trung t©m m¸y tÝnh cã 32 chiÕc m¸y vi tÝnh. Mçi
m¸y cã 24 cæng. Hái cã bao nhiªu cæng kh¸c nhau trong trung t©m nµy?.
Quy t¾c nh©n më réng:
Gi¶ sö r»ng mét nhiÖm vô nµo ®ã ®-îc thi hµnh b»ng c¸ch thùc hiÖn
c¸c viÖc T1, T2, …,Tm. NÕu viÖc Ti cã thÓ lµm b»ng ni c¸ch sau khi c¸c viÖc
T1, T2, …,Ti-1 ®· ®-îc lµm, khi ®ã cã n1 n 2 ... nm c¸ch thi hµnh nhiÖm vô ®·
cho.
VÝ dô4: Cã bao nhiªu biÓn ®¨ng kÝ xe « t« nÕu mçi biÓn chøa mét d·y
ba ch÷ c¸i tiÕp sau lµ ba ch÷ sè (kh«ng bá d·y ch÷ nµo ngay c¶ khi nã cã ý
nghÜa kh«ng ®Ñp).
Quy t¾c nh©n th-êng ®-îc ph¸t biÓu b»ng ng«n ng÷ tËp hîp nh- sau:
NÕu A1, A2, …, Am lµ c¸c tËp h÷u h¹n, khi ®ã sè phÇn tö cña tÝch
§Ò-c¸c cña c¸c tËp hîp nµy b»ng tÝch sè c¸c phÇn tö cña c¸c tËp thµnh phÇn.
A1 A2 ... Am A1 A2 ... Am
1.1.3. C¸c cÊu h×nh tæ hîp ®¬n gi¶n:
1.1.3.1. Ho¸n vÞ
Cho tËp A gåm n phÇn tö ( n 1). Mçi c¸ch s¾p xÕp thø tù n phÇn tö
cña tËp hîp A ®-îc gäi lµ mét ho¸n vÞ cña n phÇn tö ®ã.
Pn n! 1 2 3 .... (n 1) n
Quy -íc: 0!=1
1!=1
VÝ dô5: 6 ng-êi xÕp thµnh hµng ngang ®Ó chôp ¶nh. Hái cã thÓ bè trÝ
bao nhiªu kiÓu?.
Khoa C«ng NghÖ Th«ng Tin
2
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
1.1.3.2. ChØnh hîp:
Cho tËp hîp A gåm n phÇn tö. Mçi bé gåm k phÇn tö ( 0 k n ) s¾p
thø tù cña tËp hîp A lµ mét tæ hîp chÊp k cña n phÇn tö.
Ank n(n 1)....(n k 1)
n!
(n k )!
VÝ dô 6: Gi¶ sö r»ng cã t¸m vËn ®éng viªn ch¹y thi. Ng-êi th¾ng sÏ
nhËn huy ch-¬ng vµng, ng-êi vÒ ®Ých thø hai nhËn huy ch-¬ng b¹c, ng-êi vÒ
®Ých thø ba nhËn huy ch-¬ng ®ång. Cã bao nhiªu c¸ch trao c¸c huy ch-¬ng
nµy nÕu tÊt c¶ c¸c kÕt côc cña cuéc thi ®Òu cã thÓ x¶y ra?.
1.1.3.3. Tæ hîp:
Cho tËp hîp A gåm n phÇn tö. Mçi tËp con gåm k phÇn tö ( 0 k n )
cña tËp hîp A lµ mét chØnh hîp chÊp k cña n phÇn tö.
Cnk
n!
k !(n k )!
VÝ dô7: Cã bao nhiªu c¸ch tuyÓn 5 trong sè 10 cÇu thñ cña mét ®éi
bãng quÇn vît ®Ó ®i thi ®Êu t¹i mét tr-êng kh¸c?.
C¸c tÝnh chÊt cña hÖ sè tæ hîp:
a) TÝnh ®èi xøng
Cnk Cnnk
b) §iÒu kiÖn ban ®Çu
Cn0 Cnn 1
c) C«ng thøc ®Ö qui
Cnk Cnn11 Cnk1 ,
n >k >0
Tõ c«ng thøc b) vµ c), ta cã thÓ tÝnh tÊt c¶ c¸c hÖ sè tæ hîp chØ b»ng phÐp
céng. C¸c hÖ sè nµy ®-îc tÝnh vµ viÕt lÇn l-ît theo tõng dßng ( mçi dßng chØ
øng víi gi¸ trÞ n=0, 1, 2,…) theo b¶ng tam gi¸c dãi ®©y:
C00
C10
Khoa C«ng NghÖ Th«ng Tin
C11
3
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
…
…
Cn0
…
…
…
Cn1
…
…
…
…
…
Cnn 1
…
…
Cnn
…
…
B¶ng nµy gäi lµ tam gi¸c Pascal.
C¸c hÖ sè tæ hîp cã liªn quan chÆt chÏ víi viÖc khai triÓn luü thõa cña
mét nhÞ thøc
( x y)n Cn0 x n Cn1 x n1 y ... Cnn1 y n1 Cnn y n
C«ng thøc trªn ®-îc gäi lµ c«ng thøc khai triÓn nhÞ thøc Newton vµ
c¸c hÖ sè cña nã ®-îc gäi lµ c¸c hÖ sè cña nhÞ thøc.
1.2. Bµi to¸n ®Õm vµ ph-¬ng ph¸p gi¶i
1.2.1. Giíi thiÖu bµi to¸n
Mét trong nh÷ng vÊn ®Ò ®Çu tiªn cña viÖc nghiªn cøu tæ hîp lµ ®Õm
xem cã bao nhiªu cÊu h×nh tæ hîph cã thÓ ®-îc t¹o ra víi nh÷ng quy t¾c ®·
nªu ? Nh÷ng bµi to¸n nh- vËy ®-îc gäi lµ bµi to¸n ®Õm tæ hîp. Th«ng
th-êng, lêi gi¶i cña bµi to¸n ®Õm phô thuéc vµo mét sè gi¸ trÞ tham sè ban
®Çu vµ ng-êi ta cè g¾ng biÓu diÔn sù phô thuéc nµy b»ng nh÷ng c«ng thøc
to¸n häc. Nãi chung, ®Ó ®Õm c¸c cÊu h×nh ®· cho, ng-êi ta t×m c¸ch ®-a vÒ
c¸c cÊu h×nh quen thuéc b»ng c¸c thiÕt lËp mét t-¬ng quan 1-1 gi÷a chóng.
NhiÒu khi mét bµi to¸n ®Õm ®-îc ph©n thµnh nh÷ng bµi to¸n ®Õn nhá h¬n
b»ng c¸ch chia viÖc ®Õm thµnh tõng líp ®Ó ¸p dông nguyªn lý céng hoÆc
ph©n tÝch cÊu h×nh cÇn ®Õm nh- lµ viÖc ghÐp mét sè cÊu h×nh kh¸c ®Ó ¸p
dông nguyªn lý nh©n. D-íi ®©y lµ mét sè kü thuËt ®Õm.
VÝ dô 1. Cã bao nhiªu c¸ch xÕp 5 ng-êi ®øng thµnh mét hµng ngang
sao cho A kh«ng ®øng c¹nh B ?
Gi¶i: §Ó ®Õm sè c¸ch xÕp nµy, ta ®Õm phÇn cßn l¹i: sè c¸ch xÕp mµ A
®øng c¹nh B. Xem A vµ B nh- mét chç, ta cã 4!= 24 c¸c xÕp. Sè nµy cÇn
®-îc nh©n 2 v× A cã thÓ ®øng bªn tr¸i còng nh- bªn ph¶i B. Nh- vËy cã tÊt
Khoa C«ng NghÖ Th«ng Tin
4
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
c¶ 48 c¸ch xÕp A ®øng c¹nh B. Toµn bé cã 5! = 120c¸ch xÕp. Tõ ®ã nhËn
®-îc sè c¸ch xÕp mµ A kh«ng ®øng c¹nh B lµ 120 – 48 = 72 c¸ch.
VÝ dô 2. Mét ®ît ph¸t hµnh xæ sè víi c¸c sè vÐ gåm 2 phÇn: phÇn ®Çu
gåm 2 ch÷ c¸i lÊy tõ A ®Õn Z (26 ph©n tö) vµ phÇn sau gåm 4 ch÷ sè lÊy tõ 0
®Õn 9 910 ph©n tö). Hái x¸c xuÊt ®Ó tróng gi¶i ®éc ®¾c lµ bao nhiªu ?
Gi¶i: Tr-íc hÕt ta ®Õm sè vÐ ®-îc ph¸t hµnh. Mçi vÐ gåm 2 phÇn:
phÇn ch÷ vµ phÇn sè. PhÇn ch÷ cã 262 kh¶ n¨ng, phÇn sè cã 104 kh¶ n¨ng.
Theo nguyªn lý nh©n, sè vÐ ®-îc ph¸t hµnh lµ 262 x 104 = 6 760 000. Tõ ®ã
nhËn ®-îc x¸c suÊt ®Ó tróng gi¶i ®éc ®¾c lµ:
1 / 6 760 000 ~ 1,48 x 10-7
VÝ dô 3. Cho mét l-íi gåm c¸c « vu«ng. C¸c nót ®-îc ®¸nh sè tõ 0
®Õn n theo chiÒu tõ tr¸i sang ph¶i vµ tõ 0 ®Õn m theo chiÒu tõ d-íi lªn trªn
(xem h×nh vÏ). Hái cã bao nhiªu ®-êng ®i kh¸c nhau tõ nót (0,0) ®Õn nót
(n,m) nÕu chØ cho phÐp ®i trªn c¹nh c¸c « vu«ng theo chiÒu sang ph¶i hoÆc
lªn trªn ?
(0,m)
(n,m)
(0,0)
(n,0)
Gi¶i : Mét ®-êng ®i nh- thÕ ®-îc xem gåm n+m ®o¹n (mçi ®o¹n lµ
mét c¹nh « vu«ng). T¹i mçi ®o¹n chØ ®-îc chän mét trong 2 gi¸ trÞ : ®i lªn
(mµ ta m· lµ 1) hay sang ph¶i (mµ ta m· lµ 0). Sè ®o¹n ®i lªn ®óng b»ng m
vµ sè ®o¹n sang ph¶i ®óng b»ng n. Bµi to¸n dÉn vÒ viÖc t×m xem cã bao
nhiªu d·y nhÞ ph©n ®é dµi n + m trong ®ã cã ®óng m thµnh phÇn b»ng 1. ®©y
Khoa C«ng NghÖ Th«ng Tin
5
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
còng chÝnh lµ sè tËp con m ph©n tö cña mét tËp n + m phÇn t, v× thÕ sè ®-êng
®i cÇn ®Õm b»ng Cnm m
VÝ dô 4 : ThuËt to¸n ‘næi bät’ dïng ®Ó xÕp t¨ng dÇn d·y ai (i =
1,2,....,n) ®-îc m« t¶ b»ng ®o¹n ch-¬ng tr×nh PASCAL d-íi ®©y :
For i : = 2 to n do
Forj : = n down to i do
I a[ j I ] a[ j ]thenSwap (a[ j I ], a[ j ];
H·y ®Õm xem ph¶i lµm bao nhiªu phÐp so s¸nh?
Gi¶i: Ta chia sè phÐp so s¸nh thµn c¸c líp theo vßng lÆp i (i ®i tõ 2
®Õn n). Víi mçi i x¸c ®Þnh, ph¶i thùc hiÖn n-i+1 phÐp so s¸nh. Tõ ®ã nhËn
®-îc, theo nguyªn lý céng, sè c¸c phÐp so s¸nh lµ:
(n 1) (n 2) ... 1
n(n 1)
2
Cã thÓ lý luËn g¹n h¬n: thuËt to¸n ‚næi bät‛ viÕt trong ®o¹n ch¬ng
tr×nh ®· cho ph¶i so s¸nh tÊt c¶ c¸c cÆp phÇn tö kh¸c nhau. Tõ ®ã nhËn ®-îc
sè phÐp so s¸nh lµ:
C n2
n(n 1)
2
Mét ®Æc tÝnh cña c¸c bµi to¸n ®Õm tæ hîp lµ sè cÊu h×nh t¨ng rÊt
nhanh khi sè gi¸ trÞ tham gia vµo viÖc t¹o nªn cÊu h×nh ®ã t¨ng. §iÒu nµy
th-êng dÉn ®Õn c¸c con sè khæng lå mÆc dï c¸c con sè tham gia ban ®Çu
kh«ng lín. HiÖn t-îng nµy th-êng ®-îc gäi lµ sù bïng næ tæ hîp vµ chÝnh nã
lµ nguyªn nh©n lµm cho c¸c thuËt to¸n dùa vµo viÖc duyÖt toµn bé trë nªn
kh«ng kh¶ thi. ThÝ dô d-íi ®©y cho thÊy r»ng, dï qui c¸ch t¹o cÊu h×nh cã vÓ
rÊt h¹n chÕ nh-ng sè cÊu h×nh ®-îc t¹o, ho¸ ra l¹i rÊt lín.
VÝ dô 5. Ng«n ng÷ PASCAL chuÈn qui ®Þnh ®Æt tªn biÕn kh«ng qu¸ 8
ký tù. C¸c ký tù trong tªn biÕn chØ ®-îc phÐp lµ c¸c ch÷ c¸i (tõ A ®Õn Z)
hoÆc c¸c ch÷ sè (tõ 0 ®Õn 9) vµ ph¶i b¾t ®Çu b»ng ch÷ c¸i. Hái cã thÓ ®Þnh
nghÜa bao nhiªu biÕn kh¸c nhau ?
Khoa C«ng NghÖ Th«ng Tin
6
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
Gi¶i : Ta ph©n c¸c biÕn thµnh c¸c líp: 1-ký tù, … Sè c¸c biÕn thuéc
líp k-ký tù, theo nguyªn lý nh©n, b»ng 26 x 36k-1 (k = 1,2, …, 8). Tõ ®ã, theo
nguyªn lý céng, ta nhËn ®-îc sè c¸c biÕn kh¸c nhau lµ:
26.(1+36+362 + … +367) = 2 095 681 645 538.
1.2.2. Nguyªn lý bï trõ
Mét sè bµi to¸n ®Õm phøc t¹p h¬n, ®-îc dùa vµo nguyªn lý tæng qu¸t
cña nguyªn lý céng. NÕu kh«ng cã gi¶ thiÕt g× vÒ sù rêi nhau gi÷a 2 tËp A vµ
B th×
N(A B) = N(A) + N(B) – N(A B).
C«ng thøc (1) ®-îc më réng cho tr-êng hîp nhiÒu tËp nh- sau.
§Þnh lý. Gi¶ sö A1,A2, …, Am lµ c¸c tËp h÷u h¹n. Khi ®ã
N(A1 A2 … Am) = N1 – N2 + … + (-1)m-1 Nm ,
Trong ®ã Nk lµ tæng phÇn tö cña tÊt c¶ c¸c giao cña k tËp lÊy tõ m tËp
®· cho (nãi riªng N1 = N(A1) + … + N(Am), Nm = N(A1 A2 ... Am).
Chøng minh. Chó ý r»ng, sè c¸c giao cña k tËp lÊy tõ m tËp b»ng C mk , ,
k = 1,2, …, m. §Ó chøng minh c«ng thøc (1), ta sÏ tÝnh xem mçi phÇn tö cña
tËp A1 A2 ... Am ®-îc ®Õm bao nhiªu lÇn trong vÕ ph¶i cña nã. XÐt mét
phÇn tö tuú ý a A1 A2 ... Am1. Gi¶ sö a lµ phÇn tö cña k tËp trong sè m
tËp ®· cho. Khi ®ã a ®-îc ®Õm ë vÕ ph¶i cña c«ng thøc (1)
Ck1 Ck2 Ck3 ... (1) k 1 Ckk
LÇn do
Ck1 Ck2 Ck3 ... (1) k 1 Ckk
1 [1 Ck1 Ck2 Ck3 ... (1) k Ckk ] 1 (1 1) k 1 ,
Suy ra mçi phÇn tõ a A1 A2 ... Am ®-îc tÝnh ®óng 1 lÇn ë vÕ ph¶i
cña c«ng thøc (1) , ®iÒu ®ã ®· chøng minh tÝnh ®óng ®¾n cña c«ng thøc (1).
B©y giê ta ®«ng nhÊt tËp Ak víi tÝnh chÊt Ak cho trªn mét tËp X nµo ®ã
vµ ®Õm xem cã bao nhiªu phÇn tö cña X kh«ng tho¶ m·n bÊt cø mét tÝnh chÊt
Aknµo c¶.
Khoa C«ng NghÖ Th«ng Tin
7
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
Gäi N lµ sè cÇn ®Õm, N lµ sè phÇn tö cña X, ta cã:
N N N ( A1 A2 ... Am ) N N1 N 2 ... (1) m N m
(3)
Trong ®ã Nk lµ tæng c¸c phÇn tö cña X tho¶ m·n k tÝnh chÊt lÊy tõ m
tÝnh chÊt ®· cho.
C«ng thøc (3) ®-îc gäi lµ nguyªn lý bï trõ. Nã cho phÐp tÝnh N qua
c¸c Nk trong tr-êng hîp c¸c sè nµy dÔ tÝnh to¸n h¬n.
Ta sÏ xÐt mét sè thÝ dô minh ho¹ cho viÖc sö dông nguyªn lý bï trõ ®Ó
gi¶i c¸c bµi to¸n ®Õm.
VÝ dô 6: Hái trong tËp X=[1,2,…, 10000] cã bao nhiªu sè kh«ng chia
hÕt cho bÊt cø sè nµo trong c¸c sè 3,4,7?
Gi¶i. Gäi
Ai x X : x chia hÕt cho i
, i=3,4,7.
Khi ®ã A3 A4 A7 lµ tËp c¸c sè trong X chia hÕt cho Ýt nhÊt mét trong
3 sè 3,4,7, suy ra theo c«ng thøc (3), sè l-îng c¸c sè cÇn ®Õm sÏ lµ
N ( X ) N ( A3 A7 ) N1 N 2 N 3.
Ta cã
N1 N ( A3 ) N ( A4 ) N ( A7 )
[10000 / 3] [10000 / 4] [10000 / 7]
3333 2500 1428 7261,
N 2 N ( A3 A4 ) N ( A3 A7 ) N ( A4 A7 )
10000 /(3 4) 10000 /(3 7) 10000 /( 4 7)
833 476 357 1666,
N3 N ( A3 A4 A7 ) 10000 /(3 4 7) 11
Ký hiÖu [r] ®Ó chØ sè nguyªn lín nhÊt kh«ng v-ît qu¸ r.
Tõ ®ã sè l-îng c¸c sè cÇn ®Õm lµ 10000-7261+1666-119=4286.
1.3. Bµi to¸n tån t¹i vµ ph-¬ng ph¸p gi¶i
1.3.1. Giíi thiÖu bµi to¸n
Trong môc tr-íc, ta ®· tËp trung chó ý vµo viÖc ®Õm sè c¸c cÊu h×nh
tæ hîp (sè phÇn tö cña c¸c ®èi t-îng tæ hîp) tho¶ m·n nh÷ng tÝnh chÊt nµo
Khoa C«ng NghÖ Th«ng Tin
8
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
®ã, ch¼ng h¹n ®Õm sè tæ hîp, chØnh hîp, ho¸n vÞ, … Trong nh÷ng bµi to¸n
®ã sù tån t¹i cña c¸c cÊu h×nh lµ hiÓn nhiªn vµ c«ng viÖc chÝnh lµ ®Õm sè
phÇn tö tho¶ m·n tÝnh chÊt ®Æt ra. Tuy nhiªn, trong rÊt nhiÒu baßi to¸n tæ
hîp, viÖc chØ ra sù tån t¹i cña mét cÊu h×nh tho¶ m·n c¸c tÝnh chÊt cho tr-íc
lµ hÕt søc khã kh¨n. Ch¼ng h¹n, khi mét kú thñ cÇn ph¶i tÝnh to¸n c¸c n-íc
®i cña m×nh ®Ó gi¶i ®¸p xem liÖu cã kh¶ n¨ng th¾ng hay kh«ng, hay chØ lµ
bøc mËt m· gi¶ cña ®èi ph-¬ng tung ra nh»m ®¶m b¶o an toµn cho bøc ®iÖn
thËt…Nh vËy, trong tæ hîp xuÊt hiÖn mét vÊn ®Ò thø hai rÊt quan träng lµ:
xÐt sù tån t¹i cña c¸c cÊu h×nh tæ hîp víi c¸c tÝnh chÊt cho tr-íc. C¸c bµi
to¸n thuéc d¹ng nµy ®-îc gäi lµ c¸c bµi to¸n tån t¹i tæ hîp.
Mét bµi to¸n tån t¹i tæ hîp xem nh- gi¶i xong nÕu hoÆc chØ ra mét
c¸ch x©y dùng cÊu h×nh, hoÆc chøng minh r»ng chóng kh«ng cã. Tuy nhiªn
c¶ hai kh¶ n¨ng ®Òu kh«ng ph¶i dÔ. §Ó thÊy râ sù phøc t¹p cña vÊn ®Ò, d-íi
®©y ta sÏ xÐt mét sè bµi to¸n tån t¹i tæ hîp cæ ®iÓn næi tiÕng.
1.3.1.1. Bµi to¸n vÒ 36 sÜ quan
Bµi to¸n nµy ®-îc Euler ®Ò nghÞ, néi dung cña nã nh- sau: cã mét lÇn
ng-êi ta triÖu tËp tõ 6 trung ®oµn mçi trung ®oµn 6 sÜ quan thuéc 6 cÊp bËc
kh¸c nhau: ThiÕu uý, trung uý, th-îng uý, ®¹i uý, thiÕu t¸, trung t¸ vÒ tham
gia duyÖt binh ë s- ®oµn bé. Hái r»ng cã thÓ xÕp 36 sÜ quan nµy thµnh mét
®éi ngò h×nh vu«ng sao cho trong mçi mét hµnh ngang còng nh- mçi mét
hµng däc ®Òu cã ®¹i diÖn cña c¶ 6 trung ®oµn vµ cña c¶ 6 cÊp bËc.
§Ó ®¬n gi¶n ta dïng c¸c ch÷ c¸i in hoa A, B, C, D, E, F ®Ó chØ c¸c
phiªn hiÖu trung ®oµn cßn c¸c ch÷ c¸i th-êng a, b, c, d, e, f ®Ó chØ c¸c cÊp
bËc. Bµi to¸n nµy cã thÓ tæng qu¸t ho¸ nÕu thay con sè 6 bëi n. trong tr-êng
hîp n=4, mét lêi gi¶i cña bµi to¸n 16 sÜ quan lµ
Ab Dd Ba Cc
Bc Ca Ad Db
Cd Bd Dc Aa
Da Ac Cb Bd
Mét lêi gi¶i trong tr-êng hîp n = 5 lµ
Khoa C«ng NghÖ Th«ng Tin
9
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
Aa Bb Cc Dd Ee
Cd De Ea Ab Bc
Eb Ac Bd Ce Da
Be Ca Db Ec Ad
De Ed Ae Ba Cb
Do lêi gi¶i cña bµi to¸n cã thÓ biÒu diÔn bëi 2 h×nh vu«ng víi c¸c ch÷
c¸i la tinh hoa vµ th-êng chån c¹nh nhau nªn bµi to¸n tæng qu¸t ®Æt ra cßn
®-îc biÕt d-íi tªn gäi bµi to¸n vÒ h×nh vu«ng la tinh trùc giao. Trong hai thÝ
dô trªn ta cã h×nh vu«ng la tinh trùc giao cÊp 4 vµ 5.
Euler ®· mÊt rÊt nhiÒu c«ng søc ®Ó t×m lêi gi¶i cho bµi to¸n 36 sÜ quan
thÕ nh-ng «ng ®· kh«ng thµnh c«ng. V× vËy «ng ®· ®Ò ra gi¶ thuyÕt lµ c¸ch
xÕp nh- vËy kh«ng tån t¹i. Gi¶ thuyÕt nµy ®-îc nhµ to¸n häc Ph¸p Tarri
chøng minh n¨m 1901 b»ng c¸c duyÖt tÊt c¶ mäi kh¶ n¨ng xÕp. Euler c¨n cø
vµo sù kh«ng tån t¹i lêi gi¶i khi n = 2 vµ n = 6 cßn ®Ò ra mét gi¶ thuyÕt tæng
qu¸t h¬n lµ; kh«ng tån t¹i h×nh vu«ng la tinh trùc giao cÊp n = 4k + 2. Gi¶
thuyÕt nµy ®· tån t¹i suèt hai thÕ kû m·i ®Õn n¨m 1960 ba nhµ to¸n häc Mü
lµ Boce, Parker, Srikanda míi chØ ra ®-îc mét lêi gi¶i víi n = 10 vµ sau ®ã
chØ ra ph-¬ng ph¸p x©y dùng hinh vu«ng la tinh trùc giao cho mäi n = 4k +
2, víi k > 1.
T-ëng chõng bµi to¸n ®Æt ra chØ cã ý nghÜa thuÇn tuý cña mét bµi to¸n
®è hãc bóa thö trÝ tuÖ con ng-êi. ThÕ nh-ng gÇn ®©y ng-êi ta ®· ph¸t hiÖn
nh÷ng øng dông quan träng cña vÊn ®Ò trªn vµo quy ho¹ch thùc nghiÖm, s¾p
xÕp c¸c lÞch thi ®Êu trong c¸c gi¶i cê quèc tÕ, h×nh häc x¹ ¶nh,…
1.3.1.2. Bµi to¸n 4 mÇu
Cã nh÷ng bµi to¸n mµ néi dung cña nã cã thÓ gi¶i thÝch cho bÊt kú ai,
tuy nhiªn lêi gi¶i cña nã th× ai còng cã thÓ thö t×m, nh-ng mµ khã cã thÓ t×m
®-îc. Ngoµi ®Þnh lý Fermat th× bµi to¸n 4 mµu lµ mét bµi to¸n nh- vËy. Bµi
to¸n cã thÓ ph¸t biÓu trùc quan nh- sau: chøng minh r»ng mäi b¶n ®å trªn
mÆt ph¼ng ®Òu cã thÓ t« b»ng 4 mµu sao cho kh«ng cã hai n-íc l¸ng giÒng
nµo l¹i bÞ t« bëi cïng mét mµu. chó ý r»ng, ta xem nh- mçi n-íc lµ mét
Khoa C«ng NghÖ Th«ng Tin
10
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
vïng liªn th«ng vµ hai n-íc ®-îc gäi lµ l¸ng giÒng nÕu chóng cã chung biªn
giíi lµ mét ®-êng liªn tôc.
3
2
1
4
Con sè 4 kh«ng ph¶i lµ ngÉu nhiªn. Ng-êi ta chøng minh ®-îc r»ng
mäi b¶n ®å ®Òu ®-îc t« víi sè mÇu lín h¬n 4, cßn víi sè mÇu Ýt h¬n 4 th×
kh«ng t« ®-îc, ch¼ng h¹n b¶n ®å gåm 4 n-íc trªn h×nh 1 kh«ng thÓ t« ®-îc
víi sè mÇu Ýt h¬n 4.
Bµi to¸n nµy xuÊt hiÖn vµo kho¶ng nh÷ng n¨m 1850 – 1852 tõ mét
nhµ bu«n ng-êi Anh lµ Gazri khi t« b¶n ®å hµnh chÝnh n-íc Anh ®· cè g¾ng
chøng minh r»ng nã cã thÓ t« b»ng 4 mÇu. Sau ®ã, n¨m 1852 «ng ta ®· viÕt
th- cho De Morgan ®Ó th«ng b¸o vÒ gi¶ thuyÕt nµy. N¨m 1878, Keli trong
mét bµi b¸o ®¨ng ë TuyÓn tËp c¸c c«ng tr×nh cña Héi to¸n häc Anh cã hái
r»ng bµi to¸n nµy ®· ®-îc gi¶i quyÕt hay ch-a? Tõ ®ã bµi to¸n trë thµnh næi
tiÕng, vµ trong suèt h¬n mét thÕ kû qua ®· cã rÊt nhiÒu ng-êi lµm to¸n,
nghiÖp d- còng nh- chuyªn nghiÖp, ®· cè g¾ng chøng minh gi¶ thuyÕt nµy.
Tuy nhiªn m·i ®Õn n¨m 1976 hai nhµ tãan häc Mü lµ K.Appel vµ W. Haken
míi chøng minh ®-îc gi¶ thuyÕt nµy b»ng m¸y tÝnh ®iÖn tö. TÊt nhiªn mét
chøng minh víi sù gióp ®ì cña m¸y tÝnh ®iÖn tö kh«ng thùc sù tho¶ m·n
®-îc nhu cÇu cña c«ng chóng muèn kiÓm tra tÝnh ®óng ®¾n cña c¸ch chøng
minh. V× vËy, chÝnh hai t¸c gi¶ trªn vµo cuèi nh÷ng n¨m 1990 ®· cã c«ng bè
mét cuèn s¸ch tr×nh bµy vÒ ph-¬ng ph¸p chøng minh cña m×nh (cuèn s¸ch
dµy trªn 800 trang). Còng vµo nh÷ng n¨m cuèi cña thÕ kû 20, mét nhãm c¸c
nhµ to¸n häc Mü ®· ®-a ra mét chøng minh cã thÓ kiÓm tra b»ng tay! RÊt
tiÕc lµ chøng minh nµy còng kh«ng ph¶i lµ ®¬n gi¶n. Cho ®Õn nay c¸c nhµ
to¸n häc vÉn ®ang nç lùc nghiªn cøu ®Ó t×m ra mét c¸ch chøng minh dÔ hiÓu
nh- b¶n th©n néi dung cña bµi to¸n.
Khoa C«ng NghÖ Th«ng Tin
11
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
1.3.1.3. H×nh lôc gi¸c thÇn bÝ
N¨m 1910 Clifford Adams ®Ò ra bµi to¸n h×nh lôc gi¸c thÇn bÝ sau:
trªn 19 « lôc gi¸c (xem h×nh vÏ ë d-íi) h·y ®iÒn vµo c¸c sè tõ 1 ®Õn 19 sao
cho tæng theo 6 h-íng cña lôc gi¸c lµ b»ng nhau (vµ ®Òu b»ng 38).
Sau 47 n¨m trêi kiªn nhÉn cuèi cïng «ng ta ®· t×m ®-îc lêi gi¶i. Sau
®ã v× s¬ ý ®¸nh mÊt b¶n th¶o «ng ta ®· tèn thªm 5 n¨m ®Ó kh«i phôc l¹i.
N¨m 1962 Adams ®· c«ng bè lêi gi¶i ®ã.
ThËt kh«ng thÓ ngê lµ ®ã lµ lêi gi¶i duy nhÊt (nÕu kh«ng tÝnh ®Õn c¸c
lêi gi¶i sai kh¸c nhau bëi phÐp biÕn h×nh ®¬n gi¶n).
1.3.1.4. Bµi to¸n chän 2n ®iÓm trªn l-íi n x n ®iÓm
Cho mét l-íi « vu«ng gåm n x n ®iÓm. Hái cã thÓ chän trong sè
chóng 2n, ®iÓm, sao cho kh«ng cã 3 ®iÓm ®-îc chän nµo lµ th¼ng hµng hay
kh«ng? HiÖn nay ng-êi ta míi biÕt ®-îc rÊt Ýt vÒ lêi gi¶i cña bµi to¸n trong
nh÷ng t×nh huèng kh«ng tÇm th-êng. C©u hái vÒ sù tån t¹i cña lêi gi¶i cña
bµi to¸n víi nh÷ng gi¸ trÞ lín cña n vÉn cßn ®Ó ngá.
1.3.1.5. Ph-¬ng ph¸p ph¶n chøng
Mét trong nh÷ng c¸ch gi¶i bµi to¸n tån t¹i lµ dïng lËp luËn ph¶n
chøng: gi¶ thiÕt ®iÒu ®Þnh chøng minh lµ sai, tõ ®ã dÉn ®Õn m©u thuÉn.
VÝ dô 1. Cho 7 ®o¹n th¼ng cã ®é dµi lín h¬n 10 vµ nhá h¬n 100.
Chøng minh r»ng lu«n t×m ®-îc 3 ®o¹n ®Ó cã thÓ ghÐp thµnh mét tam gi¸c.
Gi¶i: Chó ý r»ng, cÇn vµ ®ñ ®Ó 3 ®o¹n cã thÓ ghÐp thµnh mét tam gi¸c
lµ tæng ®é dµi cña 2 ®o¹n nhá ph¶i lín h¬n ®é dµi cña ®o¹n lín, ta s¾p c¸c
®o¹n ®· cho theo thø tù t¨ng dÇn cña ®é dµi a1, a2,…, a7 vµ chøng minh r»ng
trong ®¸y ®· xÕp lu«n t×m ®-îc 3 ®o¹n liªn tiÕp sao cho tæng cña 2 ®o¹n ®Çu
lín h¬n ®o¹n cuèi. Gi¶ thiÕt ®iÒu nµy kh«ng x¶y ra, nghÜa lµ ®ång thêi x¶y ra
c¸c bÊt ®¼ng thøc:
a1 a2 a3 ,
a 2 a3 a 4 ,
a3 a 4 a5 ,
Khoa C«ng NghÖ Th«ng Tin
12
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
a 4 a5 a 6 ,
a5 a 6 a 7 ,
Tõ gi¶ thiÕt a1, a2 cã gi¸ trÞ lín h¬n 10, ta nhËn ®-îc a3 > 20. Tõ a2 >
10 vµ a3 > 20, ta nhËn ®-îc a4 > 30, … , cø nh vËy ta nhËn ®îc a5 > 50, a6
> 80 vµ a7 > 130. BÊt ®¼ng thøc cuèi cïng m©u thuÉn víi gi¶ thiÕt c¸c ®é dµi
nhá h¬n 100 vµ ®iÒu ®ã chøng minh kÕt luËn cña bµi to¸n.
VÝ dô 2. C¸c ®Ønh cña mét thËp gi¸c ®Òu ®-îc ®¸nh sè bëi c¸c sè
nguyªn 0,1, … , 9 mét c¸ch tuú ý. Chøng minh r»ng lu«n t×m ®îc ba ®Ønh
liªn tiÕp cã tæng c¸c sè lµ lín h¬n 13.
Gi¶i: Gäi x1, x2, … , x10 lµ c¸c sè g¸n cho c¸c ®Ønh cña 1,2, … , 10 cña
thËp gi¸c. Gi¶ sö ng-îc l¹i lµ kh«ng t×m ®-îc ba ®Ønh nµo tho¶ m·n kh¼ng
®Þnh cña thÝ dô. Khi ®ã ta cã
k1 x1 x2 x3 13 ,
k 2 x2 x3 x4 13 ,
………
k 9 x9 x10 x1 13 ,
k10 x10 x1 x2 13 ,
Tõ ®ã suy ra
k1 k 2 ... k10 130.
MÆt kh¸c do
k1 k 2 ... k10 3( x1 x2 ... x10
3(0 1 2 ... 9)
135 ,
Suy ra
135 k1 k 2 ... k10 130 .
M©u thuÉn thu ®-îc ®· chøng tá kh¼ng ®Þnh trong vÝ dô lµ ®óng.
VÝ dô 3. Chøng minh r»ng kh«ng thÓ nèi 31 m¸y vi tÝnh thµnh mét
m¹ng sao cho mçi m¸y ®-îc nèi víi ®óng 5 m¸y kh¸c.
Khoa C«ng NghÖ Th«ng Tin
13
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
Gi¶i: Gi¶ sö ng-îc l¹i lµ t×m ®-îc c¸ch nèi 31 m¸y sao cho mçi m¸y
®-îc nèi víi ®óng 5 m¸y kh¸c. Khi ®ã sè l-îng kªnh nèi lµ 5x31/2= 75,5 ?!
M©u thuÉn thu ®-îc ®· chøng minh kh¼ng ®Þnh trong thÝ dô lµ ®óng.
1.3.2. Nguyªn lý Dirichlet
Trong rÊt nhiÒu bµi to¸n tæ hîp, ®Ó chøng minh sù tån t¹i cña mét cÊu
h×nh víi nh÷ng tÝnh chÊt cho tr-íc, ng-êi ta sö dông nguyªn lý ®¬n gi¶n sau,
gäi lµ nguyªn lý Dirchlet:
Nguyªn lý Direchlet. NÕu ®em xÕp nhiÒu h¬n n ®èi t-îng vµo n c¸i
hép, th× lu«n t×m ®-îc c¸i hép chøa kh«ng Ýt h¬n 2 ®èi t-îng.
Chøng minh. ViÖc chøng minh nguyªn lý trªn chØ lµ mét lËp luËn ph¶n
chøng ®¬n gi¶n. Gi¶ sö ng-îc l¹i lµ kh«ng t×m ®-îc c¸i hép nµo ch÷a kh«ng
Ýt h¬n 2 ®èi t-îng. §iÒu ®ã cã nghÜa lµ mçi c¸i hép chøa kh«ng qu¸ mét ®èi
t-îng. Tõ ®ã suy ra tæng sè ®èi t-îng xÕp trong n c¸i hép lµ kh«ng v-ît qu¸
n, tr¸i víi gi¶ thiÕt lµ cã nhiÒu h¬n n ®èi t-îng ®-îc xÕp trong chóng.
LËp luËn hoµn toµn t-¬ng tù, cã thÓ chøng minh Nguyªn lý Dirichlet
tæng qu¸t sau.
Nguyªn lý Dirichlet tæng qu¸t. NÕu ®em xÕp n ®èi t-îng vµo k c¸i hép, th×
lu«n t×m ®-îc mét c¸i hép chøa kh«ng Ýt h¬n n/k ®èi t-îng.
Nguyªn lý trªn ®-îc nhµ to¸n häc næi tiÕng ng-êi §øc lµ Dirichlet ®Ò
xuÊt tõ thÕ kû 19 vµ «ng ®· ¸p dông nã ®Ó gi¶i nhiÒu bµi to¸n tån t¹i tæ hîp.
C¸c thÝ dô d-íi ®©y cho ta thÊy nguyªn lý ®-îc sö dông nh- thÕ nµo.
VÝ dô 1. Trong sè 367 ng-êi bao giê còng t×m ®-îc hai ng-êi cã ngµy
sinh nhËt gièng nhau bëi v× chØ cã tÊt c¶ 366 ngµy sinh nhËt kh¸c nhau.
VÝ dô 2. Trong kú thi häc sinh giái ®iÓm bµi thi ®-îc ®¸nh gi¸ bëi mét
sè nguyªn trong kho¶ng tö 0 ®Õn 100. Hái r»ng Ýt nhÊt ph¶i cã bao nhiªu häc
sinh dù thi ®Ó cho ch¾c ch¾n t×m ®-îc hai hä sinh cã kÕt qu¶ thi nh- nhau?
Gi¶i. Theo nguyªn lý Dirichlet, sè häc sinh cÇn t×m lµ 102, v× ta cã
101 kÕt qu¶ ®iÓm thi kh¸c nhau.
Khoa C«ng NghÖ Th«ng Tin
14
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
VÝ dô 3. Trong sè nhøng ng-êi cã mÆt trªn tr¸i ®Êt lu«n t×m ®-îc hai
ng-êi cã hµn r¨ng gièng nhau, bëi v× chØ cã tÊt c¶
232 = 4 294 967 296
Hµm r¨ng kh¸c nhau mµ sè ng-êi trªn hµnh tinh chóng ta hiÖn nay ®·
v-ît qu¸ 5 tû.
VÝ dô 4. Trong 100 ng-êi cã Ýt nhÊt 9 ng-êi sinh cïng mét th¸ng.
Gi¶i: XÕp nh÷ng ng-êi cïng sinh mét th¸ng vµo mét nhãm. Cã 12
th¸ng tÊt c¶. VËy theo nguyªn lý Dirichlet, tån t¹i Ýt nhÊt mét nhãm cã
kh«ng Ýt h¬n 100/12 = 8,3… nghÜa lµ 9 ngêi.
VÝ dô 5. Cã n¨m lo¹i häc bæng kh¸c nhau. Hái r»ng ph¶i cã Ýt nhÊt bao
nhiªu sinh viªn ®Ó ch¾c ch¾n r»ng cã Ýt ra lµ s¸u ng-êi cïng nhËn häc bæng
nh- nhau?
Gi¶i: Sè sinh viªn Ýt nhÊt cÇn cã ®Ó ®¶m b¶o ch¾c ch¾n cã 6 sinh viªn
cïng nhËn häc bæng nh- nhau lµ sè nguyªn nhá nhÊt n sao cho n/5 > 5. Sè
nguyªn nhá nhÊt ®ã lµ n = 5x5+1=26. VËy 26 lµ sè l-îng sinh viªn nhá nhÊt
®¶m b¶o ch¾c ch¾n lµ cã s¸u sinh viªn cïng h-ëng mét lo¹i häc bæng.
VÝ dô 6. BiÓn sè xe m¸y ph©n khèi lín gåm 7 ký tù:
NN- NNN - XX,
Trong ®ã hai ký tù ®Çu lµ m· sè ®Þa danh, ba ký tù tiÕp theo lµ sè hiÖu
xe, mçi ký tù lµ mét sè tõ 0 ®Õn 9, hai ký tù cuèi lµ m· ®¨ng ký gåm hai ch÷
c¸i lÊy trong b¶ng ch÷ c¸i la tinh gåm 26 ch÷ c¸i. Hái r»ng, ®Ó cã 2 triÖu
biÓn sè xe m¸y kh¸c nhau th× cÇn ph¶i cã Ýt nhÊt bao nhiªu m· ®Þa danh kh¸c
nhau?
Gi¶i: Víi mçi mét m· ®Þa danh ta cã 103.262 = 676.103 biÓn sè xe
m¸y kh¸c nhau. V× vËy ®Ó cã 2 triÖu biÓn sè xe m¸y kh¸c nhau, cÇn cã Ýt
nhÊt nghÜa lµ m· ®Þa danh kh¸c nhau.
2.106/(676.103),
Trong nhiÒu øng dông thó vÞ cña nguyªn lý Dirichlet, kh¸i niÖm ®èi
t-îng vµ c¸i hép cÇn ph¶i ®-îc lùa chän mét c¸ch kh«n khÐo h¬n. TiÕp theo,
ta sÏ dÉn ra mét vµi thÝ dô nh- vËy.
Khoa C«ng NghÖ Th«ng Tin
15
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
VÝ dô 7. Trong mét phßng häp bao giê còng t×m ®-îc hai ng-êi cã sè
ng-êi quen trong sè nh÷ng ng-êi dù häp lµ b»ng nhau.
Gi¶i: Gäi sè ng-êi dù häp lµ n, khi ®ã sè ng-êi quen cña mét ng-êi
nµo ®ã trong phßng häp chØ cã thÓ nhËn c¸c gi¸ trÞ tõ 0 ®Õn n-1. Râ rµng
trong phßng kh«ng thÓ ®ång thêi cã ng-êi cã sè ng-êi quen lµ 0 (tøc lµ
kh«ng quen ai c¶) vµ cã ng-êi cã sè ng-êi quen lµ n-1 (tøc lµ quen tÊt c¶).
V× vËy, theo sè l-îng ng-êi quen ta chØ cã thÓ ph©n n ng-êi ra thµnh n-1
nhãm. Theo nguyªn lý Dirichlet suy ra cã Ýt nhÊt mét nhãm ph¶i cã kh«ng Ýt
h¬n hai ng-êi, tøc lµ lu«n t×m ®-îc Ýt ra lµ hai ng-êi cã sè ng-êi quen lµ
b»ng nhau.
Bµi to¸n nµy cã thÓ ph¸t biÓu d-íi d¹ng ng«n ng÷ h×nh häc nh- sau:
trªn mÆt ph¼ng cho n ®iÓm, gi÷a chóng cã mét sè ®iÓm ®-îc nèi víi nhau
bëi c¸c ®o¹n th¼ng. Khi ®ã bao giê còng t×m ®-îc hai ®iÓm cã cïng mét sè
c¹nh nèi ph¸t ra tõ chóng.
VÝ dô 8. Trong mét th¸ng gåm 30 ngµy mét ®éi bãng chuyÒn thi ®Êu
mçi ngµy Ýt nhÊt mét trËn, nh-ng kh«ng ch¬i qu¸ 45 trËn. H·y chøng minh
r»ng ph¶i t×m ®-îc mét gi¶i ®o¹n gåm mét sè ngµy liªn tôc nµo ®ã trong
th¸ng sao cho trong giai ®o¹n ®ã ®éi ch¬i ®óng 14 trËn.
Gi¶i: Gi¶ sö aj lµ tæng sè trËn thi ®Êu cho ®Õn hÕt ngµy thø j cña ®éi.
Khi ®ã
a1, a2, …, a30
Lµ d·y t¨ng c¸c sè nguyªn d-¬ng vµ ®ång thêi 1 a J 45 . Suy ra d·y
©1+14, a+14, ..., a30+1414
Còng lµ d·y t¨ng c¸c sè nguyªn d-¬ng vµ 15 aJ+14 59.
TÊt c¶ cã 60 sè nguyªn d-¬ng
a1, a2, ..., a30, a1+14, a2+14, ..., a30+ 14,
trong ®ã tÊt c¶ ®Òu nhá h¬n hoÆc b»ng 59. V× vËy theo nguyªn lý Dirichlet,
hai trong sè c¸c sè nguyªn nµy ph¶i lµ b»ng nhau. V× c¸c sè a1, …, a30 lµ ®«i
Khoa C«ng NghÖ Th«ng Tin
16
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
mét kh¸c nhau vµ c¸c sè a1+ 14, …, a30 + 14 còng lµ ®«i mét kh¸c nhau, nªn
suy ra ph¶i t×m ®-îc chØ sè i vµ j sao cho ai = aj + 14. §iÒu ®ã cã nghÜa lµ cã
®óng 14 trËn ®Êu trong giai ®o¹n tõ ngµy j + 1 ®Õn ngµy i.
VÝ dô 9. Chøng minh r»ng, trong sè n + 1 sè nguyªn d-¬ng, mçi sè
kh«ng lín h¬n 2n, bao giê còng t×m ®-îc hai sè sao cho sè nµy chia hÕt cho
sè kia.
Gi¶i: Gäi c¸c sè ®· cho lµ
a1,a2, …, an+1.
ViÕt mçi mét sè aj trong n + 1 sè trªn d-íi d¹ng:
aj = 2kj qj , j = 1,2, …, n + 1
trong ®ã kj lµ nguyªn kh«ng ©m, qj lµ sè lÎ. C¸c sè q1, q2, …, qn+1 lµ c¸c sè
nguyªn lÎ mçi sè kh«ng lín h¬n 2n. Do trong ®o¹n tõ 1 ®Õn 2n chØ cã n sè
lÎ, nªn tõ nguyªn lý Dirichlet suy ra lµ hai trong sè c¸c sè q1, q2, …, qn+1 lµ
b»ng nhau, tøc lµ t×m ®-îc hai chØ sè i vµ j sao cho qi = qj = q. Khi ®ã ai =
2kj q. Suy ra nÕu ki < kj th× aj chia hÕt cho ai, cßn nÕu ki kj th× ai chia hÕt cho
a j.
VÝ dô 10. Trong mÆt ph¼ng cho 6 ®iÓm ®-îc nèi víi nhau tõng ®«i mét
bëi c¸c cung mµu xanh hoÆc mµu ®á. Chøng minh r»ng lu«n t×m ®-îc 3
®iÓm sao cho c¸c cung nèi chóng cã cïng mét mµu (ta sÏ nãi lµ chóng t¹o
thµnh tam gi¸c xanh hoÆc ®á).
Gi¶i: Chän ®iÓm P nµo ®ã. Tõ nã cã 5 cung nèi víi 5 ®iÓm cßn l¹i.
Theo nguyªn lý Dirichlet, cã 3 trong sè 5 cung ®ã ph¶i cã cïng mét mµu,
ch¼ng h¹n lµ mµu xanh. Gi¶ sö ®ã lµ c¸c cung PA, PB, PC. NÕu nh- mét
trong sè 3 cung AB, AC, BC cã mµu xanh th× nã cïng víi hai trong sè ba
cung PA, PB, PC t¹o thµnh mét tam gi¸c xanh. NÕu ng-îc l¹i th× tam gi¸c
ABC lµ mét tam gi¸c ®á.
VÝ dô 11. Trªn mÆt ph¼ng cho 9 ®iÓm ®-îc nèi víi nhau ®«i mét bëi
c¸c ®o¹n nèi cã mÇu xanh hoÆc ®á sao cho trong sè 3 ®iÓm bÊt kú bao giê
còng t×m ®-îc hai ®iÓm ®-îc nèi víi nhau bëi ®o¹n nèi mµu ®á. Chøng minh
Khoa C«ng NghÖ Th«ng Tin
17
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
r»ng trong sè c¸c ®iÓm ®· cho lu«n t×m ®-îc 4 ®iÓm mµ c¸c ®o¹n th¼ng nèi
chóng ®Òu cã mµu ®á.
Gi¶i: Gäi 9 ®iÓm ®· cho lµ A, B, C, D, E, F, G, H, I. XÐt 2 tr-êng hîp:
a) T×m ®-îc mét ®iÓm lµ ®Çu mót cña Ýt nhÊt 4 ®o¹n nèi mµu xanh
ch¼ng h¹n ®iÓm ®ã lµ A vµ c¸c ®o¹n mµu xanh ®ã lµ AB, AC, AD, AE. Theo
gi¶ thiÕt, trong sè c¸c ®o¹n nèi bÊt kú 3 ®iÓm nµo còng cã Ýt nhÊt mét ®o¹n
mµu ®á, suy ra c¸c ®o¹n BC, Be, BD, CD, CE, ED lµ mµu ®á. VËy B, C, D, E
lµ bèn ®iÓm cÇn t×m.
b) Mçi ®iÓm ®Òu lµ ®Çu mót cña nhiÒu nhÊt lµ 3 ®o¹n nèi mµu xanh.
Trong tr-êng hîp nµy, kh«ng thÓ tÊt c¶ 9 ®iÓm ®Òu lµ ®Çu mót cña ®óng 3
®o¹n nèi mµu xanh (chøng minh t-¬ng tù nh- trong thÝ dô 3, môc 3.2), tõ ®ã
suy ra ph¶i t×m ®-îc ®iÓm (I ch¼ng h¹n) lµ ®Çu mót cña nhiÒu nhÊt lµ 2 ®o¹n
nèi mµu xanh. Khi ®ã I lµ ®Çu mót cña Ýt nhÊt 6 ®o¹n mµu ®á, ch¼ng h¹n IA,
IB, IC, ID, IE, IF. Theo kÕt qu¶ cña thÝ dô 10, trong sè 6 ®iÓm A, B, C, D, E,
F ph¶i cã Ýt nhÊt 3 ®iÓm, ch¼ng h¹n A, B, C, sao cho c¸c ®o¹n nèi chóng cã
cïng mµu, vµ tõ gi¶ thiÕt suy ra mµu ®ã ph¶i lµ mµu ®á. VËy I, A, B, C lµ
bèn ®iÓm cÇn t×m.
1.3.3. HÖ ®¹i diÖn ph©n biÖt
Trong nhiÒu t×nh huèng, sù tån t¹i cña cÊu h×nh tæ hîp phô thuéc vµo
mét sè ®iÒu kiÖn rµng buéc c¸c tham sè ban ®Çu. Mét trong nh÷ng h-íng
gi¶i quyÕt lµ ng-êi ta cè g¾ng ph¸t hiÖn ra c¸c ®iÒu kiÖn ®ã. Bµi to¸n hÖ ®¹i
diÖn ph©n biÖt tr×nh bµy d-íi ®©y lµ mét minh ho¹ cho h-íng t×m kiÕm nµy.
Gi¶ sö S1, S2,…, Sm lµ mét hä c¸c tËp con cña mét tËp hîp S (c¸c Si
kh«ng nhÊt thiÕt kh¸c nhau). Ta gäi mét bé cã thø tù a1, a2, …, am lµ mét hÖ
®¹i diÖn ph©n biÖt cña hä nµy nÕu ai Si vµ ai aj (i j). hÖ ®¹i diÖn ph©n
biÖt ®-îc viÕt t¾t lµ TRAN (transversal) vµ thµnh phÇn ai cña hÖ ®-îc gäi lµ
®¹i diÖn cña tËp con S1 (i = 1, … , m).
VÝ dô 12. S = 1,2,3,4,5 , S1 2,5, S 2 2,5, S3 1,2,3,4, S 4 1,2,5cã
TRAN lµ (2,5,3,1). Mét TRAN kh¸c cña hä nµy lµ (5,2,4,1).
Khoa C«ng NghÖ Th«ng Tin
18
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
Kh«ng ph¶i lóc nµo còng t×m ®-îc TRAN. Mét ®iÒu dÔ nhËn thÊy lµ
nÕu hä ®ang xÐt cã TRAN, th× mäi hîp cña k tËp bÊt kú trong hä ph¶i cã Ýt
nhÊt k phÇn tö (v× lu«n t×m ®-îc k ®¹i diÖn kh¸c nhau cña k tËp ®ã). Nãi kh¸c
®i, nÕu t×m ®-îc k tËp nµo ®ã cña hä, mµ hîp cña chóng cã Ýt h¬n k phÇn tö,
th× ch¾c ch¾n hä ®ang xÐt sÏ kh«ng cã TRAN. Ch¼ng h¹n trong thÝ dô trªn,
nÕu thay tËp S4 cña hä ®ang xÐt bëi tËp 2,5, th× hä nµy sÏ kh«ng tån t¹i
TRAN, v× S1 S 2 S 4 2,5 cã Ýt h¬n 3 phÇn tö.
P. Hall ®· chøng minh ®-îc ®iÒu kiÖn cÇn võa nªu, còng ®ång thêi lµ
®ñ cho sù tån t¹i TRAN, qua ®Þnh lý ®¸nh gi¸ cËn d-íi cña sè TRAN d-íi
®©y:
§Þnh lý Hall. Gi¶ sö c¸c tËp con S1, S2, …, Sm tho¶ m·n ®iÒu kiÖn:
N (S i1 S i2 ... S i1 ) k
(1)
Víi mäi 1 k m,1 i1 ik m vµ mçi tËp con nµy chøa Ýt nhÊt t phÇn
tö.
Khi ®ã:
. nÕu t m th× hä ®ang xÐt cã Ýt nhÊt t! TRAN
. nÕu t m th× hä ®ang xÐt cã Ýt nhÊt t!/(t-m) ! TRAN.
§iÒu kiÖn (1) ®-îc gäi lµ ®iÒu kiÖn Hall vµ ta gäi mét hä con cña hä
S1, S2, …, Sm lµ tíi h¹n nÕu ®èi víi nã bÊt ®¼ng thøc (1) trë thµnh ®¼ng thøc.
Chøng minh. Quy n¹p theo m, víi m = 1, ta cã t = t !/(t-1) ! TRAN, ®Þnh lý
®óng. Gi¶ sö ®Þnh lý ®óng cho mäi hä tËp con cña S cã Ýt h¬n m tËp, ta cÇn
chøng minh ®Þnh lý ®óng cho hä tËp con gåm m tËp. Chia lµm 2 tr-êng hîp :
. Kh«ng cã hä con tíi h¹n. Chän a1 lµ mét phÇn tö cña S1. Lo¹i nã ra
khái S1, S2, …, Sm (bÕu cã mÆt) vµ gäi hä nhËn ®-îc lµ S2’,S3’, …, Sm’ . DÔ
dµng thö l¹i hä nµy tho¶ m·n ®iÒu kiÖn Hall vµ mçi tËp thuéc hä cã Ýt nhÊt t1 phÇn tö. Theo gi¶ thiÕt quy n¹p hä nµy cã Ýt nhÊt (t-1)! TRAN khi t-1 m1 hay t m vµ cã Ýt nhÊt (t-1) !/(t-m) ! khi t-1 > m-1 hay t > m. MÆt kh¸c,
mçi TRAN cña S2’,S3’, …, Sm’ cïng víi a1. x¸c ®Þnh mét TRAN cña S1, S2,
Khoa C«ng NghÖ Th«ng Tin
19
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
…, Sm (a1 ®¹i diÖn cho S1). §iÒu nµy ®óng cho mçi c¸ch chän a1 trong sè Ýt
nhÊt t c¸ch chän nã tõ S1. Tõ ®ã nhËn ®-îc ®¸nh gi¸ cÇn chøng minh.
. Cã mét hä con tíi h¹n. Kh«ng mÊt tÝnh tæng qu¸, cã thÓ gi¶ thiÕt hä
®ã lµ S1, S2, …, Sk (k < m). Tõ sù tån t¹i cña hä con tíi h¹n suy ra t k, v×
vËy theo gi¶ thiÕt quy n¹p, hä S1, S2, …, Sk cã Ýt nhÊt t! TRAN. Gäi T’ =
(a1,a2, …, ak) lµ mét TRAN nh- thÕ. Bá c¸c phÇn tö cña T’, nÕu cã mÆt, ra
khái c¸c tËp Sk+1, …, sm vµ gäi c¸c tËp thu ®-îc lµ S’k+1,…, S’m. Khi ®ã hä
S’k+1,…, S’m sÏ tho¶ m·n ®iÒu kiªn Hall. ThËt vËy, nÕu cã mét hä con gåm k’
t©p jcña hä ®ang xÐt, mµ hîp cña chóng Ýt h¬n k’ phÇn tö, th× hä con gåm k +
k’ tËp cña hä S1, S2, …, Sm, nhËn ®-îc b»ng c¸ch ghÐp hä con nµy víi hä S1,
S2, …, Sk sÏ cã hîp Ýt h¬n k + k’ phÇn tö vµ ®iÒu nµy lµ m©u thuÉn víi gi¶
thiÕt cña ®Þnh lý. Nh- vËy hä S’k+1, …, S’m cã Ýt nhÊt mét TRAN. LÊy Ýt nhÊt
t! TRAN cña hä S1, S2, …, Sk ghÐp víi TRAN nµy, ta ®-îc Ýt nhÊt t! TRAN
cña hä S1, S2, …, Sm. §Þnh lý ®-îc chøng minh.
ViÖc xÐt sù tån t¹i còng nh- x©y dùng TRAN cã nhiÒu øng dông trong
thùc tÕ. D-íi ®©y lµ mét sè bµi to¸n mµ viÖc gi¶i quyÕt nã ®-îc ®-a vÒ viÖc
x©y dùng TRAN.
Bµi to¸n ng-êi thi hµnh. Cã m ng-êi thi hµnh vµ n c«ng viÖc. Gi¶ sö
víi mçi ng-êi thø i, ta biÕt ®-îc tËp Si lµ tËp hîp c¸c c«ng viÖc mµ ng-êi ®ã
cã thÓ lµm. Hái cã thÓ ph©n c«ng mçi ng-êi lµm mét viÖc kh«ng?
Lêi gi¶i cña bµi to¸n ®-îc dÉn vÒ viÖc xÐt sù tån t¹i TRAN cña hä Si
vµ viÖc x©y dùng mét TRAN chÝnh lµ x©y dùng méth sù ph©n c«ng nh- thÕ.
Bµi to¸n chuyÓn m¹ch. XÐt mét hÖ thèng chuyÓn m¹ch ®¬n gi¶n
gåm 2 nhãm c¸c cùc: ®Çu vµo vµ ®Çu ra. T¹i ®Çu vµo sÏ xuÊt hiÖn ®ßi hái vÒ
nèi m¹ch. §ßi hái nµy cã thÓ ®-îc tho¶ m·n b»ng c¸ch nèi nã víi mét ®Çu
ra nµo ®ã. TËp hîp c¸c ®Çu vµo cã ®ßi hái nèi m¹ch ®-îc gäi lµ danh môc
®ßi hái. §Çu vµo nèi víi ®Çu ra qua mét m¹ch nèi vµ m¹ch nèi nµy cÇn ph¶i
kh«ng ®-îc bËn nghÜa lµ nã ch-a phôc vô cho ®Çu vµo nµo. C¸c m¹ch nèi
nh- vËy gäi lµ danh môc tù do. Kh«ng gi¶m tæng qu¸t, ta cã thÓ coi r»ng
Khoa C«ng NghÖ Th«ng Tin
20
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
danh môc ®ßi hái gåm m ®Çu vµo ®Çu tiªn vµ Si lµ tËp c¸c chØ sè c¸c m¹ch
nèi tù do mµ theo ®ã, ®ßi hái tõ ®Çu vµo i cã thÓ ®-îc chuyÓn tíi mét ®Çu ra.
NÕu hä S1, S2, …, Sm cã TRAN th× dßng vµo gåm m ®ßi hái cã thÓ ®-îc phôc
vô bëi thiÕt bÞ chØnh m¹ch. Trong tr-êng hîp kh«ng tån t¹i TRAN th× cÇn
ph¶i ®iÒu chØnh l¹i c¸c m¹ch nèi ®Ó chän c¸ch nèi kh¸c.
Bµi to¸n ®¸m c-íi vïng quª. T¹i mét lµng quª nä cã m chµng trai
®Õn tuæi lÊy vî. Víi mçi chµng trai i, ta biÕt tËp Si c¸c c« g¸i mµ chµng ta
thÝch. Hái r»ng cã thÓ ghÐp mçi c« cho mçi chµng mµ chµng nµo còng võa ý
hay kh«ng? Râ rµng bµi to¸n ®-îc dÉn vÒ viÖc xÐt sù tån t¹i TRAN cña hä
S i . Trong tr-êng hîp tån t¹i, mçi TRAN mµ kÕt qu¶ ®Õm ®-îc dÉn vÒ c¸c
cÊu h×nh ®· biÕt.
VÝ dô 1. XÐt tËp 1,2,..., n. §Õm sè TRAN cña hä tËp con
S1 S
i ,1 i n .
Gi¶i: Mçi TRAN lµ mét ho¸n vÞ (a1,a2 …, an) cña 1,2,..., n sao cho ai
i víi mäi i, do vËy cã thÓ ®ång nhÊt mçi TRAN víi mét mÊt thø tù trªn
tËp ®ang xÐt. Tõ ®ã nhËn ®-îc sè TRAN cÇn ®Õm lµ Dn (sè mÊt thø tù – xem
ch-¬ng 2).
ThÝ
dô
2.
§Õm
sè
TRAN
cña
hä
tËp
con
cña
tËp
1,2,..., n: S1 1,2, S 2 1,2,3, S3 2,3,4,..., S n1 n 2,1, n, S n n 1, n.
Gi¶i : ®Ò bµi to¸n x¸c ®Þnh c¶ víi n = 1, ta xem trong tr-êng hîp nµy
S1 = 1 . Gäi Fn lµ sè TRAN cÇn ®Õm (øng víi n > 1). Chia c¸c TRAN nµy
thµnh 2 lo¹i:
1 lµ ®¹i diÖn cho S1, khi ®ã c¸c thµnh phÇn cßn l¹i sÏ lµ mét hÖ ®¹i
diÖn cña hä 2,3, 2,3,4,..., n 1, n. Do vËy lo¹i nµy cã Fn-1 TRAN.
2 lµ ®¹i diÖn cho S1. Khi ®ã b¾t buéc 1 ph¶i lµ ®¹i diÖn cho S2 vµ
c¸c thµnh phÇn cßn l¹i sÏ lµ mét hÖ ®¹i diÖn cña hä 3,4, 3,4,5,..., n 1, n.
VËy lo¹i nµy cã Fn-2 TRAN.
Tõ ®ã nhËn ®-îc hÖ thøc Fn = Fn-1 + Fn-2. C¸c gi¸ trÞ F1 = 1, F2 = 2
®-îc tÝnh trùc tiÕp. §©y còng lµ hÖ thøc truy håi x¸c ®Þnh c¸c sè Fibonaci
Khoa C«ng NghÖ Th«ng Tin
21
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
1.4. Bµi to¸n liÖt kª vµ ph-¬ng ph¸p gi¶i
1.4.1. Giíi thiÖu bµi to¸n
NÕu nh- trong bµi to¸n ®Õm (xem ch-¬ng 2), ta chØ ®ßi hái ®Õm sè
cÊu h×nh tæ hîp lµ bao nhiªu th× trong nhiÒu t×nh huèng, ta cßn ph¶i cÇn chØ
râ nh÷ng cÊu h×nh tæ hîp ®ã lµ nh÷ng cÊu h×nh nµo. Bµi to¸n ®-a ra danh
s¸ch tÊt c¶ cÊu h×nh tæ hîp cã thÓ cã, ®-îc gäi lµ bµi to¸n liÖt kª tæ hîp. V×
thÕ, kh¸c víi bµi to¸n ®Õm t×m kiÕm mét c«ng thøc cho lêi gi¶i, bµi to¸n liÖt
kª l¹i cÇn x¸c ®Þnh mét thuËt to¸n ®Ó theo ®ã cã thÓ lÇn l-ît x©y dùng ®-îc
tÊt c¶ c¸c cÊu h×nh ®ang quan t©m. Râ rµng cã nhiÒu c¸ch liÖt kª, tuy nhiªn
chóng ph¶i ®¶m b¶o 2 nguyªn t¾c:
kh«ng ®-îc lÆp l¹i mét cÊu h×nh,
kh«ng ®-îc bá sãt mét cÊu h×nh.
Cã thÓ nãi r»ng ph-¬ng ph¸p liÖt kª lµ c¸ch cuèi cïng ®Ó cã thÓ gi¶i
®-îc mét sè bµi to¸n tæ hîp hiÖn nay. Khã kh¨n chÝnh cña ph-¬ng ph¸p nµy
lµ sù ‚bïng næ tæ hîp‛. §Ó x©y dùng chõng 1 tû cÊu h×nh (con sè nµy kh«ng
ph¶i lµ lín ®èi víi c¸c bµi to¸n tæ hîp – xem l¹i c¸c sè mÊt thø tù Dn’ sè
ph©n bè Un’ sè h×nh vu«ng la tinh ln, …) vµ gi¶ thiÕt r»ng mçi thao t¸c x©y
dùng mÊt kho¶ng 1 gi©y, ta ph¶i bá ra qu·ng 31 n¨m míi gi¶i xong. Tuy
nhiªn víi sù ph¸t triÓn cña m¸y tÝnh ®iÖn tö, b»ng ph-¬ng ph¸p liÖt kª, nhiÒu
bµi to¸n tæ hîp ®· t×m thÊy lêi gi¶i. MÆt kh¸c, chÝnh sù nç lùc t×m kiÕm
nh÷ng gi¶i ph¸p h÷u hiÖu cho nh÷ng bµi to¸n khã thuéc lÜnh vùc nµy, ®·
thóc ®Èy m¹nh mÏ sù ph¸t triÓn cña nhiÒu ngµnh to¸n häc. Trong ch-¬ng
nµy, sau phÇn giíi thiÖu kh¸i niÖm thuËt to¸n, chóng ta sÏ tr×nh bµy hai
ph-¬ng ph¸p liÖt kª th-êng sö dông nhÊt, ®ã lµ ThuËt to¸n sinh vµ ®Æc biÖt lµ
thuËt to¸n quay lïi, mét thuËt to¸n cã tÝnh phæ dông cao.
1.4.2. ThuËt to¸n vµ ®é phøc t¹p tÝnh to¸n
Nh- ®· giíi thiÖu ë trªn, ta hiÓu viÖc gi¶i bµi to¸n liÖt kª lµ x©y dùng
mét thuËt to¸n ®Ó theo ®ã cã thÓ lÇn l-ît x©y dùng ®-îc tÊt c¶ c¸c cÊu h×nh
cÇn quan t©m. VËy cÇn hiÒu thuËt to¸n lµ g×? môc nµy dµnh ®Ó giíi thiÖu
Khoa C«ng NghÖ Th«ng Tin
22
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
kh¸i niÖm thuËt to¸n vµ mét sè vÊn ®Ò liªn quan cÇn thiÕt cho viÖc tr×nh bµy
c¸c ch-¬ng sau.
1.4.2.1. Kh¸i niÖm thuËt to¸n
ThuËt to¸n ®· ®-îc biÕt ®Õn tõ rÊt l©u. B¶n th©n thuËt ng÷ ThuËt to¸n
(Algorithm) lµ viÕt t¾t tªn cña nhµ to¸n häc thÕ kû thø IX: Abu Ja’fa
Mohamed Musa al- Khowarizmi. §Çu tiªn, thuËt to¸n ®-îc hiÓu nh- lµ c¸c
qui t¾c thùc hiÖn c¸c phÐp tÝnh sè häc víi c¸c con sè ®-îc viÕt trong hÖ c¬
®Õm thËp ph©n. Cïng víi sù ph¸t triÓn cña m¸y tÝnh, kh¸i niÖm thuËt to¸n
cµng ®-îc hiÓu theo nghÜa réng h¬n vµ chÝnh x¸c h¬n. Kh¸i niÖm thuËt to¸n
®-îc ®Þnh nghÜa mét c¸ch h×nh thøc chÝnh x¸c th«ng qua m¸y Turing. Tuy
nhiªn, trong gi¸o tr×nh nµy chóng ta ch-a cÇn ®Õn ®Þnh nghÜa chÝnh x¸c nµy,
mµ cã thÓ hiÓu thuËt to¸n mét c¸ch trùc quan h¬n ®Þnh nghÜa sau.
§Þnh nghÜa. Ta hiÓu thuËt to¸n gi¶i bµi to¸n ®Æt ra lµ mét thñ tôc x¸c
®Þnh bao gåm mét d·y h÷u h¹n c¸c b-íc cÇn thùc hiÖn ®Ó thu ®-îc lêi gi¶i
cña bµi to¸n.
ThuËt to¸n cã c¸c ®Æc tr-ng sau ®©y:
§Çu vµo (Input): ThuËt to¸n nhËn d÷ liÖu vµo tõ mét tËp nµo ®ã.
§Çu ra (Output): Víi mçi tËp c¸c d÷ liÖu ®Çu vµo, thuËt to¸n ®-a ra
c¸c d÷ liÖu t-¬ng øng víi lêi gi¶i cña bµi to¸n.
ChÝnh x¸c (Precision): c¸c b-íc cña thuËt to¸n ®-îc m« t¶ chÝnh
x¸c.
H÷u h¹n (Finiteness): ThuËt to¸n cÇn ph¶i ®-a ®-îc ®Çu sau nét sè
h÷u h¹n (cã thÓ rÊt lín) b-íc víi mäi ®Çu vµo.
§¬n trÞ (Uniqueness): C¸c kÕt qu¶ trung gian cña tõng b-íc thùc
hiÖn thuËt to¸n ®-îc x¸c ®Þnh mét c¸ch ®¬n trÞ vµ chØ phô thuéc vµo ®Çu vµo
vµ c¸c kÕt qu¶ cña c¸c b-íc tr-íc.
Tæng qu¸t (Generality): ThuËt to¸n cã thÓ ¸p dông ®Ó gi¶i mäi bµi
to¸n cã d¹ng ®· cho.
Khoa C«ng NghÖ Th«ng Tin
23
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
VÝ dô 1. Cho 3 sè nguyªn a, b, c. M« t¶ thuËt to¸n t×m sè lín nhÊt
trong ba sè ®· cho.
Gi¶i. Tuy r»ng bµi to¸n ®Æt ra lµ rÊt ®¬n gi¶n nh-ng môc ®Ých cña
chóng ta lµ dïng nã ®Ó gi¶i thÝch kh¸i niÖm thuËt to¸n. ThuËt to¸n gåm c¸c
b-íc sau:
B-íc 1. §Æt x:=a;
B-íc 2. NÕu b > x th× ®Æt x:=b;
B-íc 3. NÕu c > x, th× ®Æt x:=c.
T- t-ëng cña thuËt to¸n lµ duyÖt lÇn l-ît gi¸ trÞ cña tõng sè vµ gi÷ l¹i
gi¸ trÞ lín nhÊt vµo biÕn x. KÕt thóc thuËt to¸n x cho sè nguyªn lín nhÊt
trong 3 sè ®· cho.
Ký hiÖu y:=z trong m« t¶ thuËt to¸n ë trªn cã nghÜa lµ thay thÕ gi¸ trÞ
®ang cã cña y bëi gi¸ trÞ cña z. Khi phÐp to¸n y:=z ®-îc thùc hiÖn xong, gi¸
trÞ cña z kh«ng bÞ thay ®æi. Ta gäi: = lµ to¸n tö g¸n.
B©y giê ta sÏ theo dâi qu¸ tr×nh thùc hiÖn thuËt to¸n víi nh÷ng gi¸ trÞ
cô thÓ cña a, b, c. Tr-íc hÕt gi¶ sö
a= 1, b = 5, c = 3.
T¹i b-íc 1, ta ®Æt gi¸ trÞ cña x lµ a (1). T¹i b-íc 2, do b > x (5 > 1 ),
nªn x ®-îc ®Æt b»ng b (5). T¹i b-íc 3, do ®iÒu kiÖn c > x (3>5) kh«ng ®-îc
thùc hiÖn, nªn ta kh«ng ph¶i lµm ®éng t¸c g¸n. KÕt thóc thuËt to¸n, x cã gi¸
trÞ 5 lµ gi¸ trÞ lín nhÊt trong 3 sè a, b, c.
Gi¶ sö
a= 7, b = 2, c = 31.
T¹i b-íc 1, ta ®Æt gi¸ trÞ cña x lµ a (7). T¹i b-íc 2, do ®iÒu kiÖn b > x
(2 >7) kh«ng tho¶ m·n, nªn ta kh«ng lµm g× c¶… T¹i bíc 3, do c > x (31 >
7), nªn ta g¸n x b»ng 31. KÕt thóc thuËt to¸n, x cã gi¸ trÞ 31 lµ gi¸ trÞ lín
nhÊt trong 3 sè a, b, c.
B©y giê ta sÏ thÊy r»ng thuËt to¸n võa m« t¶ cã c¸c tÝnh chÊt nªu ë
trªn.
Khoa C«ng NghÖ Th«ng Tin
24
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
ThuËt to¸n nhËn ®Çu vµo lµ ba sè a, b, c vµ ®-a kÕt qu¶ ë ®Çu ra lµ x.
C¸c b-íc cña thuËt to¸n ®-îc m« t¶ chÝnh x¸c ®Õn møc ta cã thÓ viÕt
ch-¬ng tr×nh theo thuËt to¸n trªn ng«n ng÷ lËp tr×nh vµ thùc hiÖn trªn m¸y
tÝnh.
NÕu ®Çu vµo lµ ®· x¸c ®Þnh, kÕt qu¶ t¹i mçi b-íc cña thuËt to¸n ®-îc
x¸c ®Þnh duy nhÊt. Ch¼ng h¹n, víi ®Çu vµo
a = 7, b = 2, c = 31,
t¹i b-íc 3 cña thuËt to¸n, x lu«n ®-îc ®Æt b»ng 31, kh«ng phô thuéc vµo viÖc
thuËt to¸n ®-îc thùc hiÖn b»ng tay hay bëi m¸y tÝnh.
ThuËt to¸n kÕt thóc sau ba b-íc vµ ®-a ra lêi gi¶i cña bµi to¸n, v× vËy,
thuËt to¸n lµ h÷u h¹n.
ThuËt to¸n tr×nh bµy trong vÝ dô lu«n ®-a ra gi¸ trÞ cña sè lín nhÊt
trong ba sè bÊt kú nh- vËy, thuËt to¸n cã tÝnh tæng qu¸t.
1.5. Bµi tËp
1. Cho 5 ký tù A, B, C, D, E.
a) Cã bao nhiªu x©u ký tù ®é dµi lµ 4 cã thÓ lËp ®-îc tõ c¸c ký tù ®·
cho, nÕu kh«ng cho phÐp lÆp l¹i ký tù?.
b) Cã bao nhiªu x©u ký tù trong (a) b¾t ®Çu tõ B?.
c) Cã bao nhiªu x©u ký tù trong (a) kh«ng b¾t ®Çu tõ B?.
2. §oµn chñ tÞch cña mét cuéc häp gåm 6 ng-êi A, B, C, D, E, F cÇn
bÇu ra Ban l·nh ®¹o gåm 1 chñ tÞch, 1 phã chñ tÞch vµ mét th- ký.
a) Hái cã bao nhiªu c¸ch kh¸c nhau?.
b) Cã bao nhiªu c¸ch mµ trong ®ã mét trong hai ng-êi A, B lµ chñ
tÞch?.
c) Cã bao nhiªu c¸ch mµ trong ®ã E lµ thµnh viªn cña Ban l·nh ®¹o?.
d) Cã bao nhiªu c¸ch mµ trong ®ã D vµ F lµ thµnh viªn cña Ban l·nh
®¹o?.
3. Cã bao nhiªu x©u nhÞ ph©n ®é dµi 10 b¾t ®Çu bëi hoÆc lµ 101 hoÆc
lµ 111?.
Khoa C«ng NghÖ Th«ng Tin
25
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
4. Mét c¸n bé tin häc do ®·ng trÝ nªn ®· quªn mËt khÈu cña phÇn
mÒm m¸y tÝnh cña m×nh. May m¾n anh ta cßn nhí mËt khÈu cã d¹ng NNNXX, trong ®ã NNN lµ c¸c ch÷ sè, cßn XX lµ c¸c ch÷ c¸i lÊy trong b¶ng ch÷
c¸i cã 26 ch÷. Hái trong tr-êng hîp xÊu nhÊt cÇn ph¶i thö bao nhiªu mËt
khÈu ®Ó cã thÓ t×m l¹i mËt khÈu ®· ®Æt?.
5. Cã bao nhiªu ho¸n vÞ cña c¸c ch÷ c¸i trong x©u ABCDEF mµ trong
®ã cã chøa x©u con DEF?.
6. Cã bao nhiªu c¸ch xÕp 6 ng-êi vµo ngåi quanh c¸i bµn trßn (hai
c¸ch xÕp kh«ng coi lµ kh¸c nhau nÕu chóng cã thÓ thu ®-îc tõ nhau bëi phÐp
quay trßn)?.
7. Cã bao nhiªu c¸ch xÕp 7 häc sinh nam vµ 5 häc sinh n÷ ra thµnh
mét hµng ngang sao cho kh«ng cã hai n÷ sinh nµo ®øng c¹nh nhau?.
8. Cã 3 giá ®ùng c¸c qu¶ cÇu xanh, ®á, tÝm.Mçi giá chØ chøa c¸c qu¶
cÇu cïng mµu vµ mçi giá chøa Ýt nhÊt lµ 8 qu¶ cÇu.
a. Cã bao nhiªu c¸ch chän ra 8 qu¶ cÇu?.
b. Cã bao nhiªu c¸ch chän ra 8 qu¶ cÇu mµ trong ®ã cã Ýt nhÊt mét
qu¶ cÇu ®á, mét qu¶ cÇu xanh vµ 1qu¶ cÇu tÝm?.
9. Mét nhãm sinh viªn cã n nam vµ n n÷. Cã bao nhiªu c¸ch xÕp thµnh
mét hµng sao cho nam n÷ ®øng xen nhau?.
10. T×m hÖ sè x101y99 trong khai triÓn cña (2x-3y)200.
11. Một hộp có 14 viên bi trong đó có 8 viên đỏ và 6 viên xanh
a/ Có bao nhiêu cách chọn một hộp gồm 6 viên?
b/ Trong đó có nhiều nhất là 2 viên Xanh?
12. Trong một hộp bánh trung thu có 6 loại bánh thịt và 4 loại bánh
đậu xanh. Có bao nhiêu cách chọn ra 6 bánh để làm quà tặng
a/ Lấy tùy ý các loại bánh trung thu trong hộp trên?
b/ Có đúng 4 loại bánh thịt?
13. Một bạn học sinh có 7 cuốn sách gồm 3Toán, 2 Lý, 2 Hóa. Mỗi
buổi học lấy ra 3 cuốn
a/ Có bao nhiêu cách lấy sao cho mỗi loại có đúng một cuốn?
Khoa C«ng NghÖ Th«ng Tin
26
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
b/Có bao nhiêu cách lấy sao cho mỗi lần lấy có đúng 2 quyển sách
toán?
14. Có thể nhận được bao nhiêu xâu khác nhau bằng cách sắp xếp lại
các chữ cái của từ SUCCESS?
15. Trong một kì thi, một học sinh phải trả lời 7 trong 10 câu hỏi.
a/ Có bao nhiêu cách chọn nếu nếu 4 câu hỏi đầu là bắt buộc?
b/ Nếu chọn tùy ý
Khoa C«ng NghÖ Th«ng Tin
27
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
Ch-¬ng 2. C¸c kh¸i niÖm c¬ b¶n
cña lý thuyÕt ®å thÞ
Lý thuyÕt ®å thÞ lµ mét lÜnh vùc nghiªn cøu ®· cã tõ l©u v¸ cã nhiÒu
øng dônghiÖn ®¹i. Nh-ng t- t-ëng c¬ b¶n cña lý thuyÕt ®å thÞ ®-îc ®Ò xuÊt
vµo nh÷ng n¨m ®Çu cña thÕ kØ 18 bëi nhµ to¸n häc nçi l¹c ng-êi Thôy Sü
Leonhard Euler. ChÝnh «ng lµ ng-êi ®· sö dông ®å thÞ ®Ó gi¶i bµi to¸n næi
tiÕng vÒ c¸c c¸i cÇu ë thµnh phè Konigberg.
§å thÞ ®-îc sö dông ®Ó gi¶i c¸c bµi to¸n trong nhiÒu lÜnh vùc kh¸c
nhau. Ch¼ng h¹n, ®å thÞ cã thÓ dö dông ®Ó x¸c ®Þnhc¸c m¹ch vßng trong vÊn
®Ò gi¶i tÝch m¹ch ®iÖn. Chóng ta cã thÓ ph©n biÖt c¸c hîp chÊt ho¸ häc h÷u
c¬ kh¸c nhau víi cïng c«ng thøc ph©n tö nh-ng kh¸c nhau vÒ cÊu tróc ph©n
tö nhê ®å thÞ. Chóng ta cã thÓ ®Þnh xem hai m¸y tÝnh trong m¹ng cã thÓ trao
®æi th«ng tin ®-îc víi nhau hay kh«ng nhê m« h×nh ®å thÞ cña m¹ng m¸y
tÝnh. §å thÞ c¸ träng sè trªn c¸c c¹nh cã thÓ sö dông ®Ó gi¶i c¸c bµi to¸n nhsau: T×m ®-êng ®i ng¾n nhÊt gi÷a hai thµnh phè trong m¹ng giao th«ng.
Chóng ta còng cßn sö dông ®å thÞ ®Ó gi¶i c¸c bµi to¸n vÒ lËp lÞch, thêi kho¸
biÓu vµ ph©n bè tÇn sè cho c¸c tr¹m ph¸t thanh vµ truyÒn h×nh….
2.1. §Þnh nghÜa ®å thÞ
§å thÞ lµ mét cÊu tróc rêi r¹c bao gåm c¸c ®Ønh vµ c¸c c¹nh nèi cña
c¸c ®Ønh nµy. Chóng ta ph©n biÖt c¸c lo¹i ®å thÞ kh¸c nhau bëi kiÓu vµ sè
l-îng c¹nh nèi hai ®Ønh n¸o ®ã cña ®å thÞ. §Ó cã thÓ h×nh dung ®-îc t¸i sao
l¹i cÇn ®Õn c¸c lo¹i ®å thÞ kh¸c nhau, chóng ta sÏ nªu vÝ dô sö dông chung ®Ó
m« t¶ mét m¹ng m¸y tÝnh. Gi¶ sö ta cã mét m¹ng gåm c¸c m¸y tÝnh vµ c¸c
kªnh ®iÖn tho¹i (gäi t¾t lµ kªnh tho¹i) nèi c¸c m¸y tÝnh nµy. Chóng ta cã thÓ
biÓu diÔn c¸c vÞ trÝ ®Æt m¸y tÝnh bëi c¸c ®iÓm vµ c¸c kªnh tho¹i nèi chóng
bëi c¸c ®o¹n nèi, xem h×nh 1.
Khoa C«ng NghÖ Th«ng Tin
28
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
H×nh 1. S¬ ®å m¹ng m¸y tÝnh
NhËn thÊy r»ng trong m¹ng ë h×nh 1, gi÷a hai m¸y bÊt kú cã nhiÒu
nhÊt lµ mét kªnh tho¹i nèi chóng kªnh tho¹i nµy cho phÐp liªn l¹c c¶ hai
chiÒu vµ kh«ng cã m¸y tÝnh nµo l¹i ®-îc nèi víi chÝnh nã. S¬ ®å m¹ng m¸y
tÝnh cho trong h×nh 1 ®-îc gäi lµ ®¬n ®å thÞ v« h-íng. Ta ®i ®Õn ®Þnh nghÜa
sau
§Þnh nghÜa1. §¬n ®å thÞ v« h-íng G = (V,E) bao gåm v lµ tËp c¸c
®Ønh, vµ E lµ tËp c¸c cÆp kh«nh cã thø tù gåm hai ph©n tö kh¸c nhau cña v
gäi lµ c¸c c¹nh.
Trong tr-êng hîp gi÷a hai m¸y tÝnh nµo ®ã th-êng xuyªn ph¶i truyÒn
t¶i nhiÒu th«ng tin ng-êi ta ph¶i nèi hai m¸y nµy bëi nhiÒu kªnh tho¹i. M¹ng
víi ®a kªnh tho¹i gi÷a c¸c m¸y ®-îc ®-a trong h×nh 2.
H×nh 2. S¬ ®å m¹ng m¸y tÝnh víi ®a kªnh tho¹i
§Þnh nghÜa 2. §a ®å thÞ v« h-íng G = (V,E) bao gåm V lµ tËp c¸c
®Ønh, vµ E cÆp kh«ng cã thø tù gåm hai phÇn tö kh¸c nhau cña gäi lµ c¸c
Khoa C«ng NghÖ Th«ng Tin
29
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
c¹nh. Hai c¹nh e1 vµ e2 ®-îc gäi lµ c¹nh lÆp nÕu chóng cïng t-¬ng øng víi
mét cÆp ®Ønh.
H×nh 3. S¬ ®å m¹ng m¸y tÝnh víi kªnh th«ng b¸o
Râ rµng mçi ®¬n ®å thÞ ®Òu lµ ®a ®å thÞ, nh-ng kªnh kh«ng ph¶i ®a ®«
thÞ nµo còng lµ ®¬n ®« thÞ, v× trong ®a ®« thÞ cã thÓ cã hai (hoÆc nhiÒu h¬n)
c¹nh nèi mét cÆp ®Ønh nµo ®ã.
Trong m¹ng m¸y tÝnh cã thÓ cã nh÷ng lªnh tho¹i nèi mét m¸y nµo ®ã
víi chÝnh nã (ch¼ng h¹n víi môc ®Ých th«ng b¸o). M¹ng nh- vËy ®-îc cho
trong h×nh 3. Khi ®ã ®a ®å thÞ kh«ng thÓ m« t¶ ®-îc m¹ng nh- vËy, bëi v× cã
nh÷ng khuyªn (c¹nh nèi mét ®Ønh víi chÝnh nã). Trong tr-êng hîp nµy
chóng ta cÇn sö dông ®Õn kh¸i niÖm gi¶ ®å thÞ v« h-íng, ®-îc ®Þnh nghÜa
nh- sau:
§Þnh nghÜa 3. Gi¶ ®å thÞ v« h-íng G = (V,E) bao gåm V lµ tËp c¸c
®Ønh, vµ E lµ hä c¸c cÆp cã thø tù gåm hai phÇn tö (kh«ng nhÊt thiÕt ph¶i
kh¸c nhau) cña V gäi lµ c¸c c¹nh. C¹nh e ®-îc gäi lµ khuyªn nÕu nã cã d¹ng
e = (u,u).
C¸c kªnh tho¹i trong m¹ng m¸y tÝnh cã thÓ chØ cho phÐp truyÒn tin
theo mét chiÒu. Ch¼ng h¹n, trong h×nh 4 m¸y chñ ë Hµ Néi chØ cã thÓ nhËn
tin tõ c¸c m¸y ë ®Þa ph-¬ng, cã mét sè m¸y chØ cã thÓ göi tin ®i, cßn c¸c
kªnh tho¹i cho phÐp truyÒn tin theo c¶ hai chiÒu ®-îc thay thÕ bëi hai c¹nh
cã h-íng ng-îc chiÒu nhau.
Khoa C«ng NghÖ Th«ng Tin
30
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
H×nh 4. M¹ng m¸y víi c¸c kªnh tho¹i mét chiÒu
Ta ®i ®Õn ®Þnh nghi· sau.
§Þnh nghÜa 4. §¬n ®å thÞ cã h-íng G = (V,E) bao gåm V lµ tËp c¸c
®Ønh, vµ E lµ tËp c¸c cÆp cã thø tù gåm hai phÇn tö kh¸c nhau cña V gäi lµ
c¸c cung.
NÕu trong m¹ng cã thÓ cã ®a kªnh tho¹i mét chiÒu, ta sÏ ph¶i sö dông
®Õn kh¸i niÖm ®a ®å thÞ cã h-íng:
§Þnh nghi· 5. §a ®å thÞ cã h-íng G = (V,E) bao gåm V lµ tËp c¸c
®Ønh, vµ e lµ hä c¸c cÆp cã thø tù gåm hai phÇn tö kh¸c nhau cña V gäi lµ
c¸c cung. Hai cung e1, e2 t-¬ng øng víi cïng mét cÆp ®Ønh ®-îc gäi lµ cung
lÆp.
Trong c¸c phÇn tiÕp theo chñ yÕu chóng ta sÏ lµm viÖc víi ®¬n ®å thÞ
v« h-íng vµ ®¬n ®å thÞ cã h-íng. V× vËy, ®Ó cho ng¾n gän, ta sÏ bá qua tÝnh
tõ ®¬n khi nh¾c ®Õn chóng.
2.2. C¸c thuËt ng÷ c¬ b¶n
Trong môc nµy chóng ta sÏ tr×nh bµy mét sè thuËt ng÷ c¬ b¶n cña lý
thuyÕt ®å thÞ. Tr-íc tiªn, ta xÐt c¸c thuËt ng÷ m« t¶ c¸c ®Ønh vµ c¹nh cña ®å
thÞ v« h-íng.
§Þnh nghÜa 1. Hai ®Ønh u vµ v cña ®å thÞ v« h-íng G ®-îc gäi lµ kÒ
nhau nÕu (u, v) lµ c¹nh cña ®å thÞ G. NÕu e = (u,v) lµ c¹nh cña ®å thÞ th× ta
nãi c¹nh nµy lµ liªn thuéc víi hai ®Ønh u vµ v, hoÆc còng nãi lµ c¹nh e lµ nèi
®Ønh u vµ ®Ønh v, ®ång thêi c¸c ®Ønh u vµ v sÏ ®-îc gäi lµ c¸c ®Ønh ®Çu cña
Khoa C«ng NghÖ Th«ng Tin
31
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
c¹nh (u,v).
§Ó cã thÓ biÕt cã bao nhiªu c¹nh liªn thuéc víi mét ®Ønh, ta ®-a vµo
®Þnh nghÜa sau.
§Þnh nghÜa 2. Ta gäi bËc cña ®Ønh v trong ®å thÞ v« h-íng lµ sè c¹nh
liªn thuéc víi nã vµ sÏ ký hiÖu lµ deg(v).
b
c
d
e
g
b
a
f
H×nh 5. §å thÞ v« h-íng G
VÝ dô 1. XÐt ®å thÞ cho trong h×nh 5, ta cã
deg(a) = 1, deg(b) = 4, deg(c) = 4, deg(f) = 3, deg(d) = 1, deg(e)=3,
deg(g) = 0.
RÊt nhiÒu tÝnh chÊt cña ®å thÞ cã h-íng kh«ng phô thuéc vµo h-íng
trªn c¸c cung cña nã. V× vËy, trong nhiÒu tr-êng hîp sÏ thuËn tiÖn h¬n nÕu
ta bá qua h-íng trªn c¸c cung ®-îc gäi lµ ®å thÞ v« h-íng t-¬ng øng víi ®å
thÞ cã h-íng ®· cho.
2.3. §-êng ®i, chu tr×nh. §å thÞ liªn th«ng
§Þnh nghÜa 1. §-êng ®i ®é dµi n tõ ®Ønh u ®Õn ®Ønh v, trong ®ã n lµ sè
nguyªn d-¬ng, trªn ®å thÞ v« h-íng G = (V,E) lµ d·y
x0, x1, …,xn-1, xn
trong ®ã u = x0, v = xn, (xi, xi+1) E, i = 0, 1, 2,…, n-1.
§-êng ®i nãi trªn cßn cã thÓ biÓu diÔn d-íi d¹ng d·y c¸c c¹nh.
(x0, x1), (x1, x2),….,(xn-1, xn).
§Ønh u gäi lµ ®Ønh ®Çu, cßn ®Ønh v gäi lµ ®Ønh cuèi cña ®-êng ®i.
§-êng ®i cã ®Ønh ®Çu trïng víi ®Ønh cuèi (tøc lµ u = v) ®-îc gäi lµ chu tr×nh.
§-êng ®i hay chu tr×nh ®-îc gäi lµ ®¬n nÕu nh- kh«ng cã c¹nh nµo bÞ lÆp
l¹i.
Khoa C«ng NghÖ Th«ng Tin
32
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
VÝ dô 1. XÐt ®å thÞ v« h-íng cho trong h×nh 1:
a
b
b
c
d
e
f
H×nh 6. §-êng ®i trªn ®å thÞ
Ta cã: a, d, c, f, e lµ ®-êng ®i ®¬n ®é dµi 4. Cßn d, e, c, a kh«ng lµ
®-êng ®i, do (e, c) kh«ng ph¶i lµ c¹nh cña ®å thÞ. D·y b, c, f, e, b lµ chu tr×nh
®é dµi 4. §-êng ®i a, b, e, d, a, b cã ®é dµi lµ 5 kh«ng ph¶i lµ ®-êng ®i ®¬n,
do c¹nh (a, b) cã mÆt trong nã hai lÇn.
Kh¸i niÖm ®-êng ®i vµ chu tr×nh trªn ®å thÞ cã h-íng ®-îc ®Þnh nghÜa
hoµn toµn t-¬ng tù nh- tr-êng hîp ®å thÞ v« h-íng, chØ kh¸c lµ ta cã chó ý
®Õn h-íng trªn c¸c cung.
§Þnh nghÜa 2. §-êng ®i ®é dµi n tõ ®Ønh u ®Õn ®Ønh v, trong ®ã n lµ sè
nguyªn d-¬ng, trªn ®å thÞ cã h-íng G = (V,A) lµ d·y
x0, x1, …,xn-1, xn
trong ®ã u = x0, v = xn, (xi, xi+1) A, i = 0, 1, 2, …,n-1
§-êng ®i nãi trªn cßn cã thÓ biÓu diÔn d-íi d¹ng d·y c¸c cung:
(x0, x1), (x1, x2),…., (xn-1, xn)
§Ønh u gäi lµ ®Ønh ®Çu, cßn ®Ønh v gäi lµ ®Ønh cuèi cña ®-êng ®i.
§-êng ®i cã ®Ønh ®Çu trïng víi ®Ønh cuèi (tøc lµ u = v) ®-îc gäi lµ chu tr×nh.
§-êng ®i hay chu tr×nh ®-îc gäi lµ ®¬n nÕu nh- kh«ng cã cung nµo bÞ lÆp
l¹i.
VÝ dô 2. Trªn ®å thÞ cã h-íng cho trong h×nh 6: a, d, c, f, e lµ ®-êng ®i
®¬n ®é dµi 4. Cßn d, e, c, a kh«ng lµ ®-êng ®i, do (e,c) kh«ng ph¶i lµ cung
cña ®å thÞ. D·y b, c, f, e, b lµ chu tr×nh ®é dµi 4. §-êng ®i a, b, e, d, a, b cã
®é dµi lµ 5 kh«ng ph¶i lµ ®-êng ®i ®¬n, do cung (a, b) cã mÆt trong nã hai
lÇn.
XÐt mét m¹ng m¸y tÝnh. Mét c©u hái ®Æt ra lµ hai m¸y tÝnh bÊt kú
trong m¹ng nµy cã thÓ trao ®æi th«ng tin ®-îc víi nhau hoÆc lµ trùc tiÕp qua
Khoa C«ng NghÖ Th«ng Tin
33
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
kªnh nèi chóng hoÆc th«ng qua mét hoÆc vµi m¸y tÝnh trung gian trong
m¹ng? NÕu sö dông ®å thÞ ®Ó biÓu diÔn m¹ng m¸y tÝnh nµy (trong ®ã ®Ønh
cña ®å thÞ t-¬ng øng víi c¸c m¸y tÝnh, cßn c¸c c¹nh t-¬ng øng víi c¸c kªnh
nèi) c©u hái ®ã ®-îc ph¸t biÓu trong ng«n ng÷ ®å thÞ nh- sau: Tån t¹i hay
ch¨ng ®-êng ®i gi÷a mäi cÆp ®Ønh cña ®å thÞ?
§Þnh nghÜa 3. §å thÞ v« h-íng G = (V,E) ®-îc gäi lµ liªn th«ng nÕu
lu«n t×m ®-îc ®-êng ®i gi÷a hai ®Ønh bÊt kú cña nã.
Nh- vËy hai m¸y tÝnh bÊt kú trong m¹ng cã thÓ trao ®æi th«ng tin ®-îc
víi nhau khi vµ chØ khi ®å thÞ t-¬ng øng víi m¹ng m¸y lµ ®å thÞ liªn th«ng.
2.4. Bµi tËp
1. VÏ ®å thÞ cã h-íng G=(V,E) cho bëi:
V={A,B,C,D,E,F}
Vµ E={(E,G), (B,F),(D,C), (D,F), (F,B), (C,F), (A,F), (E,D)}
2. Cho ®¬n ®å thÞ v« h-íng liªn th«ng G=(V,E) víi n ®Ønh.
a) Chøng minh r»ng lu«n cã mét ®-êng ®i ®¬n nèi hai ®Ønh u, v bÊt kú
cña ®å thÞ.
b) Chøng minh r»ng lu«n tån t¹i ®-êng ®I kh«ng qu¸ n ®Ønh nèi hai
®Ønh u, v bÊt kú cña ®å thÞ.
3. Giả sử G= có |X|=n đỉnh. Nếu có đường đi từ đỉnh A đến
đỉnh B thì cũng có đường đi từ đỉnh A đến đỉnh B với độ dài n-1
4. a/Có bao nhiêu cạnh trong đồ thị có mười đỉnh, mỗi đỉnh có bậc là
6?
b/ Có thể tồn tại đồ thị đơn 15 đỉnh mỗi đỉnh có bậc 5 không?
c/ Chỉ ra đồ thị có 5 đỉnh với các bậc 3,3,3,3,2,là tồn tại
Khoa C«ng NghÖ Th«ng Tin
34
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
Ch-¬ng 3. BiÔu diÔn ®å thÞ vµ
c¸c thuËt to¸n t×m kiÕm
RÊt nhiÒu thuËt to¸n trªn ®å thÞ ®-îc x©y dung trªn c¬ së duyÖt tÊt c¶
c¸c ®Ønh cña ®å thÞ sao cho mçi ®Ønh cña nã ®-îc viÕng th¨m ®óng mét lÇn.
V× vËy, viÖc x©y dung nh÷ng thuËt to¸n cho phÐp duyÖt mét c¸ch hÖ thèng
tÊt c¶ c¸c ®Ønh cña ®å thÞ lµ mét vÊn ®Ò quan träng thu hót sù quan t©m
nghiªn cøu cña nhiÒu t¸c gi¶. Nh÷ng thuËt to¸n nh- vËy chóng ta sÏ gäi lµ
thuËtto¸n t×m kiÕm trªn ®å thÞ. C¸c thuËt to¸n nµy gi÷ mét vai trß quan träng
trong viÖc thiÕt kÕ c¸c thuËt to¸n trªn ®å thÞ. Trong môc nµychóng ta sÏ giíi
thiÖu hai thuËt to¸n t×m kiÕm c¬ b¶n trªn ®å thÞ: ThuËt to¸n t×m kiÕm theo
chiÒu réng (Breadth First Search), thuËt to¸n t×m kiÕm theo chiÒu s©u (Depth
First Search) vµ øng dông cña chóng vµo viÖc gi¶i mét vµi bµi to¸n trªn ®å
thÞ.
Trong môc nµy chóng ta sÏ xÐt ®å thÞ v« h-íng G = (V, E), víi n ®Ønh
vµ m c¹nh. Chóng ta sÏ quan t©m ®Õn viÖc ®¸nh gi¸ hiÖu qu¶ cña c¸c thuËt
to¸n trªn ®å thÞ, mµ mét trong nh÷ng ®Æc tr-ng quan träng nhÊt lµ ®é phøc
t¹p tÝnh to¸n, tøc lµ sè phÐp to¸n mµ thuËt to¸n cÇn ph¶i thùc hiÖn trong t×nh
huèng xÊu nhÊt ®-îc biÓu diÔn nh- lµ hµm cña kÝch th-íc ®Çu vµo cña bµi
to¸n. Trong c¸c thuËt to¸n trªn ®å thÞ, ®Çu vµo lµ ®å thÞ G = (V, E), v× vËy,
kÝch th-íc cña bµi to¸n lµ sè ®Ønh n vµ sè c¹nh m cña ®å thÞ. Khi ®ã ®é phøc
t¹p tÝnh to¸n cña thuËt to¸n sÏ ®-îc biÓu diÔn nh- lµ hµm cña hai biÕn sè
f(n,m) lµ sè phÐp to¸n nhiÒu nhÊt cÇn ph¶i thùc hiÖn theo thuËt to¸n ®èi víi
mäi ®å thÞ víi n ®Ønh vµ m c¹nh. Khi so s¸nh tèc ®é t¨ng cña hai hµm nhËn
gi¸ trÞ kh«ng ©m f(n) vµ g(n) chóng ta sÏ sö dông ký hiÖu sau:
f(n) = O(g(n))
t×m ®-îc c¸c h»ng sè C, N > 0 sao cho
f(n) ≤ C (gn)
víi mäi n ≥ N
T-¬ng tù nh- vËy nÕu f(n1, n,…nk), g(n1, n2,…,nk) lµ c¸c hµm nhiÒu
biÕn, ta viÕt
Khoa C«ng NghÖ Th«ng Tin
35
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
f(n1, n2,…,nk) = O (g(n1, n2,…,nk))
T×m ®-îc c¸c h»ng sè C, N > 0 sao cho
f(n1, n2,…nk) ≤ C g (n1, n2,…nk) víi mäi n1, n2,…nk ≥ N
NÕu ®é phøc t¹p tÝnh to¸n cña thuËt to¸n lµ O (g(n)) th× ta sÏ cßn nãi
lµ nã ®ßi hái thêi gian tÝnh cì O (g(n)).
3.1. Ma trËn träng sè vµ danh s¸ch c¹nh
3.1.1. Ma trËn träng sè
XÐt ®¬n ®å thÞ v« híng G=(V,E), víi tËp ®Ønh V={1,2,…,n}, tËp c¸c
c¹nh E={e1,e2,…,em}. Ta gäi ma trËn kÒ cña ®å thÞ G lµ (0,1)-Ma trËn
A={aij:i,j=1,2,…,n}
Víi c¸c phÇn tö ®-îc x¸c ®Þnh theo quy t¾c nh- sau;
aij=0, nÕu (i,j) E vµ aij=1, nÕu (i,j) E ,
i,j=1,2,…,n.
C¸c tÝnh chÊt cña ma trËn kÒ
1) Râ rµng ma trËn kÒ cña ®å thÞ v« h-íng lµ ma trËn ®èi xøng, tøc lµ:
a[i,j]=a[j,i], i,j=1,2,….n.
ng-îc l¹i, mçi (0,1)-ma trËn ®èi xøng cÊp n sÏ t-¬ng øng, chÝnh x¸c ®Õn
c¸ch ®¸nh sè ®Ønh (cßn nãi lµ: chÝnh x¸c ®Òn ®¼ng cÊu), víi mét ®å thÞ v«
h-íng n ®Ønh.
2) Tæng c¸c phÇn tö trªn dßnh i (cét j) cña ma trËn kÒ chÝnh b»ng bËc
cña ®Ønh i (®Ønh j).
3) NÕu kÝ hiÖu
a ,i,j=1, 2, …., n
lµ c¸c phÇn tö cña ma trËn tÝch
A
.A
....
A
Ap =
p
Khi ®ã
aijp , i, j 1,2,..., n
Cho ta sè ®-êng ®i kh¸c nhau tõ ®Ønh i ®Õn ®Ønh j qua p-1 ®Ønh trung
gian.
Ma trËn kÒ cña ®å thÞ cã h-íng ®-îc ®Þnh nghÜa mét c¸ch hoµn toµn
t-¬ng tù .
Khoa C«ng NghÖ Th«ng Tin
36
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
L-u ý r»ng ma trËn kÒ cña ®å thÞ cã h-íng kh«ng ph¶i lµ ma trËn ®èi
xøng.
Chó ý: Trªn ®©y chóng ta chØ xÐt ®¬n ®å thÞ . Ma trËn kÒ cña ®a ®å thÞ
cã thÓ x©y dùng hoµn toµn t-¬ng tù , chØ cã kh¸c lµ thay v× ghi1 vµo vÞ trÝ
a[i,j] nÕu (i,j) lµ c¹nh cña ®å thÞ, chóng ta sÏ ghi k lµ c¹nh nèi hai ®Ønh i vµ j.
Trong rÊt nhiÒu vÊn ®Ò øng dông cña lý thuyÕt ®å thÞ, mçi c¹nh
e=(u,v) cña ®å thÞ ®-îc g¸n víi mét con sè c(e) (cßn viÕt lµ c(u,v)) äi lµ
träng sè cña c¹nh e. §å thÞ trong tr-êng hîp nh- vËy ®-îc gäi lµ ®å thÞ cã
träng sè . Trong tr-êng hîp ®å thÞ cã träng sè , thay v× ma trËn kÒ , ®Ó biÓu
diÔn ®å thÞ ta sö dông ma trËn cã träng sè.
C =c[i,j], i,j = 1, 2, ….,n
Víi
c[i,j]= c(i,j),
nÕu (i,j) E
vµ
c[i,j]=
nÕu(i,j) E
trong ®ã sè , tuú tõng tr-êng hîp cô thÓ, cã thÓ ®Æt b»ng mét trong
c¸c gi¸ trÞ sau: 0,+ ,-
¦u ®iÓm lín nhÊt cña ph-¬ng ph¸p biÓu diÔn ®å thÞ b»ng ma trËn kÒ hoÆc
ma trËn träng sè) lµ ®Ó tr¶ lêi c©u hái: Hai ®Ønh u ,v cã kÒ nhau trªn ®å thÞ
hay kh«ng, chóng ta chØ ph¶i thùc hiÖn mét phÐp so s¸nh. Nh-îc ®iÓm lín
nhÊt cña ph-¬ng ph¸p nµy lµ: kh«ng phô thuéc vµo sè c¹nh cña ®å thÞ, ta
lu«n ph¶i sö dông
®¬n vÞ bé nhí ®Ó l-u tr÷ ma trËn kÒ cña nã.
3.1.2. Danh s¸ch c¹nh (cung)
Trong tr-êng hîp ®å thÞ th-a (®å thÞ cã sè c¹nh m tho¶ m·n bÊt ®¼ng
thøc: m<6n) ng-êi ta th-êng dïng c¸ch biÓu diÔn ®å thÞ d-êi dµnh danh s¸ch
c¹nh
Trong c¸ch biÓu diÏn ®å thÞ bëi danh s¸ch c¹nh (cung) chóng ta sÏ l-u
tr÷ danh s¸ch tÊt c¶ c¸c c¹nh (cung) cña ®å thÞ cã h-íng (v« h-íng). Mçi
c¹nh (cung) e=(x,y) cña ®å thÞ sÏ t-¬ng øng víi hai biÕn Dau [e], Cuoi[e] .
Nh- vËy, ®Ó l-u tr÷ ®å thÞ ta cÇn sö dông 2m bé nhí. Nh-îc ®iÓm cña c¸ch
Khoa C«ng NghÖ Th«ng Tin
37
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
biÓu diÔn nµy lµ ®Ó x¸c ®Þnh c¸c ®Ønh cña ®å thÞ lµ kÒ víi mét ®Ønh cho tr-íc
chóng ta ph¶I lµm cì m phÐp so s¸nh (khi duyÖt qua danh s¸ch tÊt c¶ c¸c
c¹nh cña ®å thÞ)
Chó ý: trong tr-êng hîp ®å thÞ cã träng sè ta cÇn thªm m bé nhí ®Ó
l-u tr÷ träng sè cña c¸c c¹nh .
VÝ dô3. Danh s¸ch c¹nh (cung) cña ®å thÞ G (G1) cho trong h×nh 1 lµ:
Dau
Cuoi
Dau
Cuoi
1
2
1
2
1
3
1
3
1
5
3
2
2
3
3
4
2
5
5
4
3
4
5
6
4
5
6
5
4
6
5
6
Danh s¸ch c¹nh cña G
Danh s¸ch cung cña G
3.2. T×m kiÕm theo chiÒu réng vµ chiÒu s©u
3.2.1. T×m kiÕm theo chiÒu s©u trªn ®å thÞ.
ý t-ëng chÝnh cña thuËt to¸n cã thÓ tr×nh bµy nh- sau. Ta sÏ b¾t ®Çu
t×m kiÕm tõ mét ®Ønh v0 nµo ®ã cña ®å thÞ. Sau ®ã chän u lµ mét ®Ønh tuú ý
kÒ víi v0 vµ lÆp l¹i qu¸ tr×nh ®èi víi u. ë b-íc tæng qu¸t, gi¶ sö ta ®ang xÐt
®Ønh v. NÕu nh- trong sè c¸c ®Ønh kÒ víi v t×m ®-îc tÝnh w lµ ch-a xÐt th× ta
sÏ nãi r»ng ®Ønh nµy lµ ®· duyÖt xong vµ quay trë l¹i tiÕp tôc t×m kiÕm tõ
®Ønh mµ tr-íc ®ã ta ®Õn ®-îc ®Ønh v (nÕu v = v 0, th× kÕt thóc t×m kiÕm). Cã
thÓ nãi n«m na lµ t×m kiÕm theo chiÒu s©u b¾t ®Çu tõ ®Ønh v ®-îc thùc hiÖn
trªn c¬ së t×m kiÕm theo chiÒu s©u tõ tÊt c¶ c¸c ®Ønh ch-a xÐt kÒ víi v. Qu¸
tr×nh nµy cã thÓ m« t¶ bëi thñ tôc ®Ö qui sau ®©y.
procedure DFS(v);
(* t×m kiÕm theo chiÒu s©u b¾t ®Çu tõ ®Ønh v;
Khoa C«ng NghÖ Th«ng Tin
38
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
C¸c biÕn Chuaxet, Ke lµ biÕn toµn côc *)
begin
Th¨m_®Ønh(v);
Chuaxet v: = false;
for u Ke(v) do
if chuaxet u then DFS(u(;
end; (* ®Ønh v lµ ®· duyÖt xong*)
Khi ®ã, t×m kiÕm theo chiÒu s©u trªn ®å thÞ ®-îc thùc hiÖn nhê thuËt
to¸n sau:
BEGIN
(* Initialization *)
for v V do Chuaxet v: = true;
for v V do
if Chuaxetv then DFS(v);
Râ rµng lÖnh gäi DFS(v) sÏ cho phÐp ®Õn th¨m tÊt c¶ c¸c ®Ønh thuéc
cïng thµnh phÇn liªn th«ng víi ®Ønh v, b¬Øu v× sau khi th¨m ®Ønh lµ lÖnh gäi
®Õn thñ tôc DFS ®èi víi tÊt c¶ c¸c ®Ønh kÕ víi nã. MÆc kh¸c, do mçi khi
th¨m ®Ønh v song, ®Õn chuaxet v ®-îc ®Æt t¹i gi¸ trÞ false nªn mçi ®Ønh sÏ
®-îc th¨m ®óng mçi lÇn. Thuéc to¸n lÇn l-ît sÏ tiÕn hµnh t×m kiÕm c¸c ®Ønh
ch-a ®-îc th¨m, v× vËy, nã sÏ xÐt qua c¸c ®Ønh qu¶ ®å thÞ (kh«ng nhÊt thiÕt
ph¶i liªn th«ng).
§Ó ®¸nh gi¸ ®é phøc t¹p tÝnh to¸n qu¶ thñ tôc, tr-íc hÕt nhËn thÊy
r»ng sè phÐp to¸n cÇn ®-îc thùc hiÖn víi hai chu tr×nh qu¶ thuéc to¸n (hai
vßng for ë ch-¬ng tr×nh chÝnh) lµ cì n. Thñ tôc DFS ph¶i thùc hiÖn kh«ng
qu¸ n lÇn. Tæng sè phÐp to¸n cÇn ph¶i thùc hiÖn trong c¸c thñ tôc nµy lµ
O(n+m), do trong c¸c thñ tôc nµy ta ph¶i xÐt qua tÊt c¶ c¸c c¹nh vµ c¸c ®Ønh
cña ®å thÞ. VËy ®é phøc t¹p tÝnh to¸n cña thuËt to¸n lµ O(n+m).
VÝ dô 1. XÐt ®å thÞ cho trong h×nh 1. C¸ ®Ønh cña nã ®-îc ®¸nh sè l¹i
theo thø tù chóng ®-îc th¨m theo thñ tôc t×m kiÕm theo chiÒu s©u m« t¶ ë
Khoa C«ng NghÖ Th«ng Tin
39
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
trªn. Gi¶ thiÕt r»ng c¸c ®Ønh trong danh s¸ch kÕ cu¶ ®Ønh v (ke (v)) ®-îc s¾p
xÕp theo thø tù t¨ng dÇn cña chØ sè.
3(9)
7(8)
2(2)
1(1)
4(3)
12(11)
10(12)
5(5)
6(4)
8(6)
9(7)
13(10)
11(13)
H×nh 1. ChØ sè míi (trong ngoÆc) cña c¸c ®Ønh ®-îc ®¸nh l¹i theo thø tù
chóng ®-îc th¨m trong thuËt to¸n t×m kiÕm theo chiÒu s©u.
ThuËt to¸n t×m kiÕm theo chiÒu s©u trªn ®å thÞ v« h-íng tr×nh bµy ë
trªn dÔ dµng cã thÓ m« t¶ l¹i cho ®å thÞ cã h-íng. Trong tr-êng hîp ®å thÞ
cã h-íng, thñ tôc DFS(v) sÏ cho phÐp th¨m tÊt c¶ c¸c ®Ønh u nµo mµ tõ v cã
®-êng ®i ®Õn u. §é phøc t¹p tÝnh to¸n cña thuËt to¸n lµ O(n+m).
3.2.2. T×m kiÕm theo chiÒu réng trªn ®å thÞ
§Ó ý r»ng trong thuËt to¸n t×m kiÕm theo chiÒu s©u ®Ønh ®-îc th¨m
cµng muén sÏ cµng sím trë thµnh ®· duyÖt xong. §iÒu ®ã lµ hÖ qu¶ tÊt yÕu
cña viÖc c¸c ®Ønh ®-îc th¨m sÏ ®-îc kÕt n¹p vµo trong ng¨n xÕp STACK).
t×m kiÕm theo chiÒu réng trªn ®å thÞ, nÕu nãi mét c¸ch ng¾n gän, ®-îc x©y
dùng dùa trªn c¬ së thay thÕ ng¨n xÕp (STACK) bëi hµng ®îi QUEUE). Víi
sù c¶i biªn nh- vËy, ®Ønh ®-îc th¨m cµng sím sÏ cµng sím trë thµnh ®·
duyÖt xong (tøc lµ cµng sím dêi khái hµng ®îi). Mét ®Ønh sÏ trë thµnh ®·
duyÖt xong ngay sau khi ta xÐt xong tÊt c¶ c¸c ®Ønh kÒ (ch-a ®-îc th¨m) víi
nã. Thñ tôc cã thÓ m« t¶ nh- sau:
procedure BFS(v);
(*
t×m kiÕm theo chiÒu réng b¾t ®Çu tõ ®Ønh v;
C¸c biÕn Chuaxet, Ke lµ biÕn toµn côc *)
begin
QUEUE: =
QUEUE v; (* kÕt n¹p v vµo QUEUE *)
Khoa C«ng NghÖ Th«ng Tin
40
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
Chuaxet[v] : = false;
while QUEUE do
begin
p QUEUE; (* lÊy tõ QUEUE *)
th¨m_ ®Ønh(p);
for u Ke(p) do
if Chuaxet[u] then
begin
QUEUE u; Chuaxet[u]: = false;
end;
end;
end;
Khi ®ã, t×m kiÕm theo chiÒu réng trªn ®å thÞ ®-îc thùc hiÖn nhê thuËt
to¸n sau:
BEGIN
(*
Initialization *)
for v V do Chuaxet[v]: = true;
for v V do
if Chuaxet[v] then BFS(v);
END
LËp luËn t-¬ng tù nh- trong thñ tôc t×m kiÕm theo chiÒu s©u, cã thÓ
chØ ra ®-îc r»ng lÖnh gäi BFS(v) sÏ cho phÐp ®Õn th¨m tÊt c¶ c¸c ®Ønh thuéc
cïng thµnh phÇn liªn th«ng víi ®Ønh v, vµ mçi ®Ønh cña ®å thÞ sÏ ®-îc th¨m
®óng mét lÇn. §é phøc t¹p tÝnh to¸n cña thuËt to¸n lµ O(n+m).
VÝ dô 2. XÐt ®å thÞ trong h×nh 2. Thø tù th¨m ®Ønh cña ®å thÞ nµy theo
thuËt to¸n t×m kiÕm theo chiÒu réng ®-îc ghi trong ngoÆc.
Khoa C«ng NghÖ Th«ng Tin
41
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
3(12)
7(6)
2(2)
1(1)
4(3)
12(4)
10(7)
5(9)
6(5)
8(13)
9(10)
13(11)
11(8)
H×nh 2. ChØ sè míi (trong ngoÆc) cña c¸c ®Ønh ®-îc ®¸nh l¹i theo thø tù
chóng ®-îc th¨m trong thuËt to¸n t×m kiÕm theo chiÒu s©u
3.3. Mét sè øng dông
Trong môc nÇyt xÐt øng dông c¸c thuËt to¸n t×m kiÕm m« t¶ trong c¸c
môc tr-íc vµo viÖc gi¶i hai bµito¸n c¬ b¶n trªn ®å thÞ: Bµito¸n t×m ®-êng ®i
vµ bµito¸n vÒ x¸c ®Þnh c¸c thµnh phÇn liªn th«ng cña ®å thÞ.
a. Bµi to¸n t×m ®-êng ®i gi÷a hai ®Ønh: Gi¶ sö s vµ t lµ hai ®Ønh nµo
®ã cña ®å thÞ. H·y t×m ®-êng ®i tõ s ®Õn t.
Nh- trªn ®· ph©n tÝch, thñ tôc DFS(s) (BFS(s)) sÏ cho phÐp th¨m tÊt c¶
c¸c ®Ønh thuéc cïng mét thµnh phÇn liªn th«ng víi s. V× vËy, sau khi thùc
hiÖn xong thñ tôc, nÕu Chuaxet[t]=true, th× ®iÒu ®ã cã nghÜa lµ kh«ng cã
®-êng ®i tõ s ®Õn t, cßn nÕu Chuaxet[t]=false th× t thuéc cïng mét thµnh
phÇn liªn th«ng víi s, hay nãi c¸ch kh¸c: tån t¹i ®-êng ®i tõ s ®Õn t. Trong
tr-êng hîp tån t¹i ®-êng ®i, ®Ó ghi nhËn ®-êng ®i, ta dïng thªm biÕn
Truoc[v] ®Ó ghi nhËn ®Ønh ®i tr-íc ®Ønh v trong ®-êng ®i t×m kiÕm tõ s ®Õn
v. Khi ®ã, ®èi víi thñ tôc DFS(v) cÇn söa ®æi c©u lÖnh if trong ®ã nh- sau:
If Chuaxet[u] then
begin
Truoc[u]:=v;
DFS(u);
end;
Cßn ®èi víi thñ tôc DFS(v) cÇn söa ®æi c©u lÖnh if trong ®ã nh- sau:
if Chuaxet[u] then
Khoa C«ng NghÖ Th«ng Tin
42
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
begin
QUEUE u; Chuaxet[u]:=false;
Truoc[u]:=p;
end;
§-êng ®i cÇn kh«i phôc theo quy t¾c sau:
t p1:=Truoc[t] p2:= Truoc[p1] … s.
Chó ý: §-êng ®i t×m ®-îc theo thuËt to¸n t×m kiÕm theo chiÒu réng lµ
®-êng ®i ng¾n nhÊt (theo sè c¹nh) tõ ®Ønh s ®Õn ®Ønh t. §iÒu nµy suy trùc
tiÕp tõ thø tù th¨m®Ønh theo thuËt to¸n t×m kiÕm theo chiÒu réng.
b)T×m c¸c thµnh phÇn liªn th«ng cña ®å thÞ: H·y cho biÕt ®å thÞ
gåm bao nhiªu thµnh phÇn liªn th«ng vµ tong thµnh phÇn liªn th«ng cña nã
gåm nh÷ng ®Ønh nµo.
Do thñ tôc DFS(s) (BFS(s)) cho phÐp th¨m tÊt c¶ c¸c ®Ønh thuéc cïng
mét thµnh phÇn liªn th«ngvíi s, nªn sè thµnh phÇn liªn th«ng cña ®å thÞ
chÝnh b»ng sè lÇn gäi ®Õn thñ tôc nµy. VÊn ®Ò cßn l¹i lµ c¸ch ghi nhËn c¸c
®Ønh trong tong thµnh phÇn liªn th«ng. Ta dïng thªm biÕn Index[v] ®Ó ghi
nhËn chØ sè cña thµnh phÇn liªn th«ng chøa ®Ønh v, vµ dïng thªm biÕn
Inconnect ®Ó ®Õm sè thµnh phÇn liªn th«ng (biÕn nµy cÇn ®-îc khëi t¹o gi¸
trÞ lµ 0).Thñ tôc Th¨m_®Ønh(v) trong c¸c thñ tôc DFS(v) vµ BFS(v) cã nhiÖm
vô g¸n: Index[v]:= Inconnect, cßn c©u lÖnh if trong c¸c ch-¬ng tr×nh chÝnh
gäi ®Õn c¸c thñ tôc nµy cÇn ®-îc söa l¹i nh- sau
Inconnect:=0;
if Chuaxet[u] then
begin
Inconnect:= Inconnect+1;
DFS(v); (*BFS(v)*)
end;
KÕt thóc vßng lÆp thø hai trong ch-¬ng tr×nh chÝnh, Inconnect cho sè
thµnh phÇn liªn th«ng cña ®å thÞ, cßn biÕn m¶ng Index[v], v Vcho phÐp liÖt
Khoa C«ng NghÖ Th«ng Tin
43
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
kª c¸c ®Ønh thuéc cïng mét thµnh phÇn liªn th«ng.
3.4. Bµi tËp
1. Gi¶ sö ®å thÞ G=(V,E) ®-îc cho bëi danh s¸ch kÒ. H·y viÕt thñ tôc
lo¹i bá c¹nh (u,v), thªm c¹nh (x,y) vµo ®å thÞ.
2. Hãy vẽ các đồ thị có các ma trận kề sau:
a bc
M G1
010
101
010
a b c d
M G2
0011
0010
1101
1010
3. Vẽ đa đồ thị vô hướng được biểu diễn bởi các ma trận sau:
a b c d
M G1
1201
2030
0311
1010
a b c d
M G2
1021
0112
2110
1201
4. ¸p dông thñ tôc t×m kiÕm theo chiÒu s©u t×m tÊt c¶ c¸c cÇu tªn ®å
thÞ thÞ v« h-íng.
5. ¸p dông thñ tôc t×m kiÕm theo chiÒu s©u kiÓm tra xem ®å thÞ cã
h-íng G=(V,A) cã chøa chu tr×nh hay kh«ng?
Khoa C«ng NghÖ Th«ng Tin
44
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
Ch-¬ng 4. C©y Vµ C©y Khung Cña §å ThÞ
§å thÞ v« h-íng liªn th«ngcã chu tr×nh ®-îc gäi lµ c©y, kh¸i niÖm
c©y ®Çu tiªn ®-îc Cayley ®-a ra vµo n¨m 1857, khi «ng sö dông chóng ®Ó
®Õm sè d¹ng cÊu tróc ph©n tö cña c¸c ph©n hîp chÊt ho¸ häc trong ho¸ häc
h÷u c¬. C©y cßn ®-îc sö dông réng r·i trong rÊt nhiÒu lÜnh vùc kh¸c nhau,
®Æc biÖt trong tin häc, c©y ®-îc sö dông ®Ó x©y dùng c¸c thuËt to¸n tæ chøc
c¸c th- môc. C¸c thuËt to¸n cÊt gi÷ truyÒn d- liÖu vµ t×m kiÕm…..
4.1. C©y vµ c¸c tÝnh chÊt c¬ b¶n cña c©y
§Þnh nghÜa 1. Ta gäi c©y lµ ®å thÞ v« h-íng liªn th«ng kh«ng cã chu
tr×nh. §å thÞ kh«ng cã chu tr×nh ®-îc gäi lµ rõng.
Nh- vËy. Rõng lµ ®« thÞ mµ mçi thµnh phÇn liªn th«ng cña nã vµ mét
c©y.
VÝ dô 1. Trong h×nh 1 lµ rõng gåm 3 c©y T1, T2 ,T3
T1
T2
T3
H×nh 1. Rõng gåm ba c©y T1, T2, T3
Cã thÓ nãi c©y lµ ®å thÞ v« h-íng ®¬n gi¶n nhÊt. §Þnh lý sau ®©y cho
ta mét sè tÝnh chÊt cña c©y.
§Þnh lý 1. Gi¶ sö T= (V,E) lµ ®å thÞ v« h-íng n ®Ønh. Khi ®ã c¸c
mÖnh ®Ó sau ®©y lµ t-¬ng ®-¬ng:
(1) T lµ c©y
(2) T kh«ng chøa chu tr×nh vµ cã n -1 c¹nh
(3) T liªn th«ng vµ cã n - 1 c¹nh
(4) T liªn th«ng vµ mçi c¹nh cña nã ®Òu lµ cÇu
Khoa C«ng NghÖ Th«ng Tin
45
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
(5) Hai ®Ønh bÊt kú cña T ®-îc nèi víi nhau bëi ®óng mét ®-êng ®i
®¬n
(6) T kh«ng chøa chu tr×nh nh-ng hÔ cø thªm vµo nã mét c¹nh ta thu
®-îc ®óng mét chu tr×nh.
Chøng minh. Ta sÏ chøng minh ®Þnh lý theo s¬ ®å sau:
(1) (2) (3) (4) (5) (6) (1).
(1) (2) theo ®Þnh nghÜa T kh«ng chøa chu tr×nh. Ta sÏ chøng minh
b»ng quy n¹p theo sè ®Ønh n kh¼ng ®Þnh: Sè c¹nh cña c©y víi n ®Ønh lµ n - 1.
Râ rµng kh¼ng ®Þnh ®óng víi n = 1. Gi¶ sö n > 1. Tr-íc hÕt nhËn thÊy r»ng
trong mét c©y T cã n ®Ønh ®Òu t×m ®-îc Ýt nhÊt mét ®Ønh treo (tøc lµ ®Ønh cã
bËc lµ l). Thùc vËy, gäi v1, v2,… vk lµ ®-êng ®i dµi nhÊt (theo sè c¹nh) trong
T. Khi ®ã râ rµng v1 vµ vk lµ c¸c ®Ønh treo, v× tõ v1 (vk) kh«ng cã c¹nh nèi tíi
bÊt cø ®Ønh nµo trong sè c¸c ®Ønh v2, v3…, vk (do ®å thÞ kh«ng chøa chu
tr×nh), còng nh- tíi bÊt cø ®Ønh nµo kh¸c cña ®å thÞ (do ®-êng ®i ®ang xÐt lµ
dµi nhÊt). Lo¹i bá v1 vµ c¹nh (v1, v2) khái T ta thu ®-îc c©y T1 víi n - 1 ®Ønh,
mµ theo gi¶ thiÕt qui n¹p cã n - 2 c¹nh. VËy c©y T cã n - 2 + 1 = n - 1 c¹nh.
(2) (3) ta chøng minh b»ng ph¶n chøng. Gi¶ sö T kh«ng liªn th«ng.
Khi ®ã T ph©n r· thµnh k ≥ 2 thµnh phÇn liªn th«ng T1, T2, …., Tk. Do T
chøa chu tr×nh nªn mçi Ti (i = 1,2,…,k) còng kh«ng chøa chu tr×nh, v× thÕ
mçi T1 lµ c©y. Do ®ã nÕu gäi n(T1) vµ e(T1) theo thø tù lµ sè ®Ønh vµ c¹nh cña
Ti, ta cã
e(Ti) = n(Ti) - 1, i = 1,2….,k.
Suy ra
n -1 = e(T) = e(T1) + …. + e(Tk)
= n (Ti) + …. + n(Tk) - k
= n(T) - k < n -1?!
M©u thuÉn thu ®-îc chÝnh táT lµ liªn th«ng
(3) (4) viÖc lo¹i mét c¹nh bÊt kú khái T dÉn ®Õn ®å thÞ víi n ®Ønh vµ n
- 2c¹nh ro rµnglµ ®å thÞ kh«ng liªn th«ng. VËy mäi c¹nh trong T ®Òu lµ cÇu.
Khoa C«ng NghÖ Th«ng Tin
46
PDF Studio - PDF Editor for Mac, Windows, Linux. For Evaluation. https://www.qoppa.com/pdfstudio
Tr-êng Cao §¼ng C¬ §iÖn Hµ Néi
(4) (5) Do T lµ liªn th«ng nªn hai ®Ønh bÊt k× cña nã ®-îc nèi víi
nhau bëi mét ®-êng ®i ®¬n. NÕu cã cÆp ®Ønh nµo cña Tcã hai ®-êng ®i ®¬n
kh¸c nhau nèi chung, th× tõ ®o suy ra ®å thÞ chøa chu tr×nh,vµ v× thÕ c¸c c¸nh
trªn chu tr×nh nµy kh«ng ph¶i lµ cÇu ?!
(5) (6) T kh«ng chøachu tr×nh, bëi v× nÕu cã chu tr×nhth× ho¸ ra t×m
®-îc cÆp ®Ønh cña T ®-îc néi víi nhau bëi hai ®-êng ®i ®¬n. B©y giê, nÕu
thªm vµo T mét c¹nh e nèi hai ®Ønh u vµ v nµo ®ã cña T. Khi ®ã c¹nh nµy
cïng víi ®-êng ®i ®¬n nèi u víi v sÏ t¹o thµnh chu tr×nh trong T. Chu tr×nh
thu ®-îc nµy lµ duy nhÊt, v× nÕu thu ®-îc nhiÒu h¬n mét chu tr×nh th× suy ra
trong T tr-íc ®ã ph¶i cã s½n chu tr×nh.
(6) (1) gi¶ sö T kh«ng liªn th«ng. Khi ®ã nã gåm Ýt ra lµ 2 thµnh
phÇn liªn th«ng. V× vËy, nÕu thªm vµo T mét c¹nh nèi hai ®Ønh thuéc hai
thµnh phÇn liªn th«ng kh¸c nhau ta kh«ng thu ®-îc thªm mét chu tr×nh nµo
c¶. §iÒu ®ã m©u thuÉn víi gi¶ thiÕt (6).
§Þnh lý ®-îc chøng minh.
4.2. C©y khung nhá nhÊt cña ®å thÞ.
§Þnh nghÜa 2. Gi¶ sö G = (V, E) lµ ®å thÞ v« h-íng liªn th«ng. C©y T
= (V, F) víi F E ®-îc gäi lµ c©y khung cña ®å thÞ G.
VÝ dô 2. §å thÞ G vµ c©y khung cña nã ®-îc cho trong h×nh 2.
b
a
c
b
d a
e
c
e
d
c
b
a
e
d
H×nh 2.®å thÞ vµ c¸c c©y khung cña nã
Bµi to¸n c©y khung nhá nhÊt cña ®å thÞ lµ mét trong sè nh÷ng bµi to¸n
tèi -u trªn ®å thÞ t×m ®-îc øng dông trong nhiÒu lÜnh vùc kh¸c nhau cña ®êi
sèng. Trong môc nµy chóng ta sÏ tr×nh bµy nh÷ng thuËt to¸n c¬ b¶n ®Ó gi¶i
bµi to¸n nµy. Tr-íc hÕt chóngd ta ph¸t biÓu néi dung cña bµi to¸n.
Cho G = (V,E) lµ ®å thÞ v« h-íng liªn th«ng víi tËp ®Ønh V = {1,
2,…,n} vµ tËp c¹nh E gåm m c¹nh. Mçi c¹nh e cña ®å thÞ G ®îc g¸n víi mét
Khoa C«ng NghÖ Th«ng Tin
47