TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN KHOA HỌC MÁY TÍNH -------------o0o------------
BÀI GIẢNG MÔN HỌC
TOÁN HỌC RỜI RẠC HỆ ĐẠI HỌC
Số tín chỉ: 3TC Hệ đào tạo: ĐHCQ Ngành: CNTT, HTTTQL, TMĐT. Bộ môn giảng dạy: Bộ môn KHMT – Khoa CNTT.
Thái Nguyên, năm 2015
0
MỤC LỤC
Mục Trang
Chương 1: TẬP HỢP VÀ LOGIC MỆNH ĐỀ……………………………… 2
1.1 Tập hợp và các phép toán trên tập hợp………………………………….. 2
1.2. Quan hệ…………………………………..……………………………... 5
1.3. Logic mệnh đề………………………………….. …………………….. 8
1.4. Suy luận toán học và các phương pháp chứng minh…………………… 16
Chương 2: GIẢI THUẬT VÀ CÁC PHƯƠNG PHÁP ĐẾM………………. 22
2.1. Thuật toán và các đặc trưng cơ bản của thuật toán……………………… 22
2.2. Thuật toán đệ quy…………………………………..……………………. 28
2.3. Thuật toán quay lui………………………………….. …………………. 33
2.4. Các nguyên lý đếm cơ bản………………………………….. ………… 37
2.5. Hoán vị và tổ hợp…………………………………..…………………… 40
Chương 3: LÝ THUYẾT ĐỒ THỊ VÀ CÂY………………………………… 50
3.1. Đồ thị và các khái niệm cơ bản trong đồ thị ……………………………. 50
3.2. Bậc, đường đi, chu trình và tính liên thông của đồ thị………………….. 54
3.3. Các phương pháp duyệt đồ thị…………………………………………... 57
3.4. Một số đơn đồ thị đặc biệt………………………………….. …………. 59
3.5. Đồ thị Euler…………………………………..…………………………. 63
3.6. Đồ thị Hamilton………………………………………………………… 68
3.7. Thuật toán tìm đường đi ngắn nhất. ………………………………….. 73
3.8. Cây và cây khung của đồ thị……………………………………………. 80
1
TÀI LIỆU THAM KHẢO…………………………………………………… 90
CHƯƠNG 1
TẬP HỢP & LOGIC MỆNH ĐỀ
1.1.Tập hợp 1.1.1 Khái niệm chung về tập hợp
Tập hợp là một trong những khái niệm quan trọng nhất của toán học, nó là gốc rễ của các ngành toán học khác nhau. Vào nửa đầu thế kỷ 19, nhà toán học người Đức Geory Cautar (1845 – 1918) đã nghiên cứu các tập hợp và ứng dụng của chúng như là nền tảng của các ngành toán học (các công trình được công bố vào những năm từ 1871 – 1883) . Lý thuyết tập hợp sau khi xuất hiện đã thống nhất được nhiều quan niệm toán học và đã xây dựng nên các cơ sở logic của nhiều ngành toán học khác nhau.
Tập hợp được coi là 1 cấu trúc rời rạc bao gồm nhiều đối tượng được nhóm lại với nhau, thông thường các đối tượng trong một tập hợp có một vài tính chất tương tự nhau.
Các đối tượng trong tập hợp được gọi là các phần tử của tập hợp đó. Trật tự của các các phần tử trong tập hợp là không quan trọng, quan trọng là phần tử đó có mặt trong tập hợp hay không. Ví dụ: Tập hợp các số tự nhiên N. Tập N+ các số tự nhiên khác 0 Tập các số nguyên Z Tập các số hữu tỷ Q Tập các số thực R Ký hiệu: Phần tử tập hợp dùng chữ in thường. Tập hợp dùng chữ in hoa. Để ký hiệu x là phần tử của tập A, ta viết: xA (x thuộc A hay x là phần tử của A). Nếu x không là phần tử của tập A thì ta viết: xA (x không thuộc A). 1.1.2.Một số tập hợp đặc biệt a.Tập con
gọi là phần bù của A trong
2
Cho 2 tập hợp A và B. Nếu mọi phần tử của A đều là phần tử của B thì ta viết: AB hoặc BA và gọi là A là tập con của B (A được chứa trong B; A được bao hàm trong B; A là bộ phận của B; B bao hàm A…). Ví dụ: N*NZQR Hai tập A và B được gọi là bằng nhau nếu AB và BA. Ký hiệu là A=B Nếu AB và AB thì ta nói A là tập con thực sự của B, ký hiệu A B. Nếu A không là tập con thực sự của B thì ta viết AB b.Tập hợp rỗng:Tập hợp không chứa phần tử nào gọi là tập rỗng. Tập rỗng được ký hiệu là .Với mọi tập A ta có A.Tập rỗng là duy nhất. c.Tập hợp các tập con của một tập hợp: Cho X là một tập hợp. Tập hợp các tập con của tập X ký hiệu là P(X) hay 2X. P(X) = {A | AX} Ví dụ: X = thì P(X) = {} X = {a, b} thì P(X) = {, {a}, {b}, {a,b}} d. Tập hợp bù: Với mỗi AX đặt AC = X\A hay X. Ta có: AAC = X hay ; AAC = hay
Theo tính chất ta có:
(AB)C = ACBC (AB)C = ACBC 1.1.3 Cách xác định tập hợp a. Liệt kê các phần tử của tập hợp trong cặp ngoặc {…} Một tập hợp có thể được xác định bằng cách liệt kê tất cả các phần tử của nó: A = {a, e, o, i, u}: tập tất cả các nguyên âm (của bảng chữ cái Aab) A = {1, 2, 3, 5, 7} Khi không liệt kê hết ta dùng dấu …
A = {0, 1, 2, …, 99}: Tập tất cả các số tự nhiên từ 0 đến 99. B = {0, 2, 4, 6, …}: Tập tất cả các số tự nhiên chẵn.
b. Chỉ ra thuộc tính đặc trưng của các phần tử trong tập hợp bằng một mệnh đề
(x) nào đó.
Nếu A là tập gồm các phần tử x của tập X có tính chất P(x) thì ta viết: A = {xX | P(x)} Ví dụ : A = {xR | x2 – 4x + 3 = 0} B = {nN | n là ước của 20} C = {nN* | xn + yn = zn có nghiệm nguyên dương}
c. Dùng giản đồ Venn Qui ước:
Tập hợp vũ trụ U: tập chứa tất cả các phần tử đang xét, được biểu diễn bằng
một hình chữ nhật.
Bên trong hình chữ nhật, dùng hình tròn, hình elip để biểu diễn cho các tập hợp. Các điểm được dùng để biểu diễn cho các phần tử của tập hợp.
Ví dụ : U = N A = {2, 4, 6, 8, 10}
A .2 .10 .8 .4 .6
N
1.1.4 Phép toán trên tập hợp a. Phép hợp: Cho hai tập hợp A, B. Ta gọi A hợp B là tập gồm các phần tử thuộc A hoặc thuộc B. Ký hiệu là AB, như vậy AB = {a | aA hoặc aB}.
b. Phép giao: Cho hai tập hợp A, B. Ta gọi A giao B là tập gồm các phần tử vừa thuộc A vừa
thuộc B. Ký hiệu là AB, như vậy AB = {a | aA và aB}.
Nếu không có phần tử nào vừa thuộc A vừa thuộc B thì AB = . Trong trường
hơp này ta nói A và B rời nhau hoặc không giao nhau.
3
c. Phép hiệu: Cho hai tập hợp A, B. Ta gọi A trừ B (hay hiệu của A và B) là tập gồm các phần tử thuộc A nhưng không thuộc B. Ký hiệu là A\B.
A\B = {a | aA và aB}. Lưu ý: A\B khác B\A. d. Phép hiệu đối xứng: Cho hai tập hợp A, B. Ta gọi hiệu đối xứng của A và B là tập gồm các phần tử chỉ
thuộc A hoặc chỉ thuộc B, không đồng thời thuộc cả A và B. Ký hiệu là AB.
B = {1, 3, 5, 6}
A B = {(A\B) (B\A)}. Ví dụ 1: Cho A ={0, 1, 2, 4, 6} AB = {0, 1, 2, 3, 4, 5, 6} AB = {0,6} A\B = {1, 2, 4} B\A = {3, 5} AB = {1, 2, 4, 3, 5} Ví dụ 2: A = {xN | x chia hết cho 2}; B = {xN | x chia hết cho 3} AB = {xN | x chia hết cho 2 và chia hết cho 3}
1.1.4 Các tính chất trên tập hợp
Với A, B, C là các tập hợp bất kỳ ta có: 1.Tính chất giao hoán: AB = BA và AB = BA 2.Tính chất kết hợp: (AB)C = A(BC) (AB)C = A(BC)
3.Tính chất phân phối: A(BC) = (AB)(AC)
A(BC) = (AB)(AC)
4.Luật đối ngẫu Demorgan:
5.Luật nuốt: nếu AB thì AB = B, AB = A Chứng minh: Các tính chất 1, 2, 5 là hiển nhiên. Các tính chất còn lại được chứng minh tương tự nhau.
Chứng minh tính chất 3: A(BC) = (AB)(AC) Thật vậy với aA(BC) aA hoặc aBC aA hoặc aB và aC aA hoặc aB và aA hoặc aC aAB và aAC a (AB)(AC) Tức là có tính chất 3.
Lưu ý:
Vì A và AA với A nên: A = A, A = , AA = A, AA = A
1.1.5 Mở rộng các phép toán tập hợp a. Mở rộng tính chất 2
Với các tập A1, A2,…, An ta có:
A1A2 A3 = (A1A2)A3
=
A1A2 A3 = (A1A2)A3
=
b.Mở rộng tính chất 3
2
Cho các tập hợp X, A1, A2,…, An ta có:
c.Mở rộng tính chất 4
Cho các tập hợp X, A1, A2,…, An ta có:
1.1.7 Tích đề các a. Tích đề các của 2 tập hợp
Cho A, B là 2 tập hợp. Với mỗi aA, bB. Ta gọi (a, b) là một cặp. Hai cặp (a, b)
và (c, d) gọi là bằng nhau nếu a = c và b = d. Ta gọi tích đề các của A và B là tập AB gồm các cặp (a, b) với aA, bB
AB = {(a,b) | aA, bB}
Tích đề các AA ký hiệu là A2 (Bình phương đề các) Ví dụ: = {1, 2, 3}; B = {a, b} thì: AB = {(1, a); (1, b); (2, a); (2, b); (3, a); (3, b)} BA = {(a, 1); (a, 2); (a, 3); (b, 1); (b, 2); (b, 3)} AA = A2 = {(1, 1); (1, 2); (1, 3); (2, 1); (2, 2); (2, 3); (3, 1); (3, 2); (3, 3)} BB = B2 = {(a,a); (a,b); (b,a); (b,b)} b.Tích đề các của n tập hợp
Cho n tập hợp A1, A2,…, An. Khi đó tích đề các của n tập hợp này ký hiệu là
A1 A2 … An =
Hai bộ (a1, a2, …, an) và (b1,b2, …, bn) gọi là bằng nhau nếu: a1 = b1; a2 = b2 ; …; an = bn
và gọi là luỹ thừa đề các bậc n của tập hợp Nếu A1 = A2 = … = An thì ký hiệu
A. 1.1.8 Tập hợp hữu hạn a. Bản số của tập hữu hạn
Tập A được gọi là hữu hạn nếu nó là tập hoặc liệt kê được tất cả các phần tử của tập A, như vậy tập A là hữu hạn nếu:
A = A = {a1, a2, …, an) với các ai là khác nhau ( i = 1,..,n). Trong trường hợp 1 ta nói A có bản số 0. Trong trường hợp 2 ta nói A có bản số n.
Kí hiệu: A=0; hay N(A)=0; A=n; hay N(A)=n
Nhận xét: Bản số của một tập hữu hạn chính là số phần tử của tập đó. Hai tập hữu hạn cùng bản số có cùng số phần tử. b.Tính chất của bản số hữu hạn
3
Định lý 1: Cho A, B là hai tập hữu hạn, khi đó: 1. |AB| = |A| + |B| – |AB| 2. |A\B| = |A| – |AB|
3. |AB| = |A| + |B| – 2|AB|
Chứng minh: 1.Giả sử |A| = m; |B| = n. A = {a1, a2, …, am} và B = {b1, b2, …, bn} Xét trường hợp AB = :
AB = {a1, a2, …, am, b1, b2, …, bn} do đó |AB| = m + n = |A| + |B|
Trường hợp AB có k phần tử. Đặt AB = {a1, a2, …, ak}. Khi đó: A = {a1, a2, …, ak, ak+1, …, am}; B = {b1, b2, …, bk, bk+1,…, bn}
Vì AB = {a1, a2, …, ak, ak+1, …, am, bk+1,…, bn} nên: |AB| = m + (n – k) = m + n – k = |A| + |B| – |AB| 1.Do A = (A\B) (AB) mà (A\B) (AB) = nên theo (1) ta có:
|A| = |A\B| + |AB| |A\B| = |A| – |AB| 2.Vì (A\B)(B\A) = nên áp dụng (1) và sau đó áp dụng (2) ta có:
|AB| = |(A\B)(B\A)| = |A\B| + |B\A| = |A| – |AB| + |B| – |BA| = |A| + |B| – 2|AB|
Lưu ý theo tính chất (2) nếu BA thì |A\B| = |A| – |B| Các tập hợp A1, A2,…, An gọi là đôi một rời nhau nếu 2 tập bất kỳ trong chúng đều
rời nhau, tức là AiAj = . Với ij. Theo định lý 1, nếu A1A2 = thì |A1A2|= |A1| + |A2| Áp dụng tính chất (1) (n-1) lần, ta có:
Định lý 2: Cho A1, A2,…, An là các tập đôi một rời nhau. Khi đó,
|A1A2… An| = |A1| + |A2| + …+ |An| Định lý 3: Với tập hợp A, B ta có: |AB| = |A|.|B| Chứng minh: Giả sử A = {a1, a2, …, am} |A| = m B = {b1, b2, …, bn} |B| = n Với ai, ta có:
| {ai} B| = n vì AB = và các tập {a1} B; {a2} B; …; {am} B
đôi một rời nhau nên theo định lý 2 ta có:
|AB| = |{a1} B| + |{a2} B| + … + |{am}B | = m n = |A|.|B| Định lý 4: Cho A1, A2,…, An là các tập hợp bất kỳ. Khi đó
|A1A2… An| = |A1| |A2| … |An|
1.2.Quan Hệ 1.2.1 Khái niệm về quan hệ Trong thực tế, ta thường gặp mối quan hệ giữa các phần tử của tập hợp này với các
phần tử của tập hợp khác, hoặc ngay trong cùng một tập hợp.
Nếu gọi A là tập các đối tượng (phần tử) mà ta đang xét thì mỗi nhóm gồm m phần . Các nhóm gồm m phần tử tử có quan hệ với nhau là một phần tử của
như vậy tạo thành một tập con của Am. Ta có các định nghĩa: a. Quan hệ 2 ngôi: Một quan hệ 2-ngôi từ tập A đến tập B là tập con của tích đề các A
x B. Nếu R là một quan hệ 2-ngôi từ A đến B thì .
Nếu hay aRb thì ta nói a,b có R-quan hệ với nhau. Nếu thì ta
4
nói a,b không có R-quan hệ với nhau. Trong trường hợp A=B thì quan hệ R được gọi là quan hệ 2 ngôi trên chính tập A. Quan hệ 2-ngôi được gọi tắt là quan hệ.
b. Tương tự ta có khái niệm về quan hệ m-ngôi: Một quan hệ m-ngôi trên tập hợp A là tập con của tích đề các Am. Nếu R là một quan hệ m-ngôi trên A thì khi (a1, a2, …, am) R ta nói a1, a2, …, am có R-quan hệ với nhau. Ví dụ: Cho A: Tập các nước; B: Tập các thủ đô
R A B = {(a, b) | nếu a có thủ đô là b}
Ta có: (Việt Nam, Hà nội) R; (Lào, Viêng chăn) R
(Thái Lan, Băng cốc) R; (Singapo, Hà nội) R
Ví dụ 2: A: Tập các cán bộ trong khoa CNTT
R = {(a, b) | a, b A và a, b có cùng tuổi} A A R là một quan hệ trên A.
1.2.2 Tính chất của quan hệ Cho quan hệ R trên A. Nếu (x,y)R thì ta nói x có R quan hệ với y (x có quan hệ với y) viết là : xRy hay (x, y) R. Nếu (x, y) R thì hiểu là x không có quan hệ với y. Quan hệ R trên tập A có các tính chất sau: i.Tính chất phản xạ nếu với xA ta có xRx ii.Tính chất đối xứng nếu: vớix, yA: xRy thì yRx. iii.Tính chất phản đối xứng nếu : vớix, yA: xRy yRx thì x=y. iv.Tính chất bắc cầu nếu: vớix, y, zA: xRy yRx thì xRz. Ví dụ 1 : + Xét trong tập số tự nhiên N: Quan hệ xRy nếu x y là quan hệ có tính chất phản xạ, phản đối xứng, bắc cầu. + Xét tập các tam giác, quan hệ R: đồng dạng, có tính chất phản xạ, đối xứng, bắc cầu.
Ví dụ 2: Cho tập A={1, 2, 3, 4} Quan hệ R trên tập hợp A được định nghĩa a, bA :aRb a+b =2k kZ, khi đó: 1. R có tính chất phản xạ: aA ta có a+a=2a aRa hay (a,a)R 2. R có tính chất đối xứng: a, bA và a+b=2k thì cũng có b+a=2k hay nếu có aRb thì cũng có bRa 3. R có tính chất bắc cầu : a, b,c A nếu a+b=2k, b+c=2k’ thì a+c=(2k-b)+(2k’-b)= 2k+2k’-2b=2k’’ hay (a,c)R 1.2.3 Quan hệ tương đương a.Định nghĩa Một quan hệ R trên tập A gọi là quan hệ tương đương nếu R có các tính chất phản xạ, đối xứng, và bắc cầu.
Nếu R là quan hệ tương đương thì thay cho cách viết xRy ta viết xy (x tương
đương y). Vậy là một quan hệ tương đương trên A nếu với x, y, zA ta có:
xx (tính phản xạ) xy yx (tính đối xứng) xy yz xz (tính bắc cầu)
5
b. Ví dụ : Cho tập A={1, 2, 3, 4, 5, 6, 7} Quan hệ R trên tập hợp A được định nghĩa a, bA :aRb a-b =3k kZ, khi đó R là quan hệ tương đương, thực vậy: 1. R có tính chất phản xạ: aA ta có a-a=0=3.0 aRa hay (a,a)R 2. R có tính chất đối xứng: a, bA và a-b=3k b-a=3(-k)=3k’ bRa
3. R có tính chất bắc cầu : a, b,c A nếu a-b=3k, b-c=3k’ thì a-c= 3k+b+3k’-b=3(k+k’)=3k’’ hay (a,c)R c.Lớp tương đương
Cho A là một tập và R là một quan hệ tương đương trên A. Với xA, tập
gọi là lớp tương đương chứa x.
và có
= .
Định lý 1: Các lớp tương đương là , hoặc bằng nhau, hoặc rời nhau. Chứng minh: Xét lớp tương đương bất kỳ [x]: Vì xRx nên x [x] [x] . Để chứng minh phần còn lại ta giả sử 2 lớp = ta chỉ cần chứng minh nên xRz, vì z nên zRy. Chọn z vì z
t tRx tRy t . Vậy = .
và
Từ định lý ta có: Các lớp tương đương chia A thành các tập con rời nhau (các phân hoạch tập A). Tập hợp mà mỗi phần tử là 1 lớp tương đương của tập A theo quan hệ tương đương R () gọi là tập thương của A theo quan hệ R (). Ký hiệu là X/R X/.
Vậy X/R = {[x] | x X}.
Ví dụ: Trên tập Z các số nguyên xét quan hệ aRb nếu a – b 3. Ta có R là một quan hệ tương đương trên Z. Thật vậy: x, y, z Z:
a/x – x = 0 3 aRa suy ra R có tính chất phản xạ. b/xRy x – y 3 –(y – x) 3 hay yRx suy ra R có tính chất đối xứng. c/ xRy x – y 3 và yRz x – y 3 (x – z) 3 suy ra R có tính chất bắc cầu. Ta xét các lớp tương đương theo quan hệ này ta có xRy x – y 3 x và y chia cho 3 có cùng số dư. Khi chia cho 3 số dư có thể là 0, 1, 2. Do đó ta có các lớp tương đương đúng là:
các số chia hết cho 3
các số chia cho 3 dư 1 các số chia cho 3 dư 2
Vậy Z =
Quan hệ tương đương trên gọi là quan hệ đồng dư theo modul 3, ký hiệu là ab (mod 3). 1.2.4 Quan hệ thứ tự a. Định nghĩa quan hệ thứ tự Một quan hệ R trên tập A gọi là quan hệ thứ tự nếu R có các tính chất phản xạ, phản đối xứng và bắc cầu.
Nếu R là quan hệ thứ tự trên A thì thay cho cách viết xRy ta viết xy (x nhỏ hơn
hay bằng y). Vậy là một quan hệ thứ tự trên A nếu với x, y, z A, ta có: 1.x x (tính phản xạ) 2.x y y x thì x = y (tính phản đối xứng) 3.x y y z thì x z (tính bắc cầu) Ký hiệu x < y có nghĩa là x y và x y: đọc là x nhỏ hơn y.
Tập A cùng với một quan hệ thứ tự trên nó gọi là tập được sắp thứ tự, khi đó ký
6
hiệu là (A, ).
) trong tập P(A) = 2A ( tập các tập con của tập A) là quan
Ví dụ 1: Trong N, Z, Q, R quan hệ thông thường là quan hệ thứ tự. Ví dụ 2: Quan hệ bao hàm ( hệ thứ tự. Thật vậy: 1. X P(A): A A có tính chất phản xạ. 2. X, Y P(A): A B B A A = B nên có tính chất phản đối xứng. 3. X, Y, Z P(A): A B B C A C nên có tính chất bắc cầu. b. Quan hệ thứ tự toàn phần và bộ phận
Cho A là một tập hợp được sắp thứ tự. Nếu với x, y A ta có x y hoặc y x thì ta nói x và y so sánh được với nhau. Nếu mọi x, y A đều so sánh được với nhau thì ta nói A là tập sắp thứ tự toàn phần (sắp thứ tự tuyến tính). Trong trường hợp ngược lại, nói rằng A là tập sắp thứ tự bộ phận. Ví dụ : Quan hệ thông thường trên N, Z, Q, R là quan hệ thứ tự toàn phần. Quan hệ “chia hết” trong N* là quan hệ thứ tự bộ phận (2 và 3 không so sánh được với nhau). c.Phần tử lớn nhất, nhỏ nhất, tối đại và tối thiểu Cho A là một tập được sắp thứ tự: Phần tử a A gọi là phần tử lớn nhất (nhỏ nhất) nếu với x A đều có x a (a x). Phần tử a A gọi là phần tử tối đại (tối thiểu) nếu với x A đều có a x a = x ( x a kéo theo x = a). Ví dụ : Trong tập N với quan hệ ta có 0 là phần tử nhỏ nhất; 0 là phần tử tối thiểu. Không có phần tử lớn nhất, phần tử tối đại. Trong tập P(A) với quan hệ có là phần tử nhỏ nhất, A là phần tử lớn nhất. 1.3.Logic mệnh đề 1.3.1.Khái niệm mệnh đề và giá trị chân lý Một mệnh đề là một câu đúng hoặc sai, không thể vừa đúng vừa sai. Giá trị đúng hoặc sai của một mệnh đề được gọi là giá trị chân lý của mệnh đề.
Về ký hiệu, ta thường dùng các chữ cái như p, q, r… để ký hiệu cho các biến nhận giá trị đúng hoặc sai. Giá trị chân lý “đúng – true” thường được viết là 1 hoặc T và giá trị chân lý “sai – false” được viết là 0 hoặc F. Ví dụ 1: Các phát biểu sau đây là các mệnh đề
1. 6 là một số nguyên tố 2. 5 là số lẻ 3. 4<-2 4. Tam giác cân có 2 góc bằng nhau 5. H2O là một axit. Các mệnh đề 2, 4 có giá trị chân lý “đúng” hay là các mệnh đề đúng. Các mệnh đề
1, 3, 5 có giá trị chân lý “sai” hay là các mệnh đề sai. Ví dụ 2: Các phát biểu sau đây không phải là các mệnh đề vì tính đúng sai của chúng không xác định.
7
1. Hãy đóng cửa sổ lại! 2. Ai đang đọc sách? 3. Cô ấy rất thông minh 4. Cho x là một số nguyên dương. 5. x là một số lẻ 6. x + y = z
Mệnh đề có hai loại:
(1)Mệnh đề sơ cấp (elementary): mệnh đề sơ cấp là các “nguyên tử” theo nghĩa là nó không thể phân tích được thành một hay nhiều (từ 2 trở lên) mệnh đề thành phần đơn giản hơn.
(2) Mệnh đề phức hợp (compound): mệnh đề phức hợp là mệnh đề được tạo thành từ một hay nhiều mệnh đề khác bằng cách sử dụng các liên kết logic như từ “không” dùng trong việc phủ định một mệnh đề, các từ nối: “và”, “hay”, “hoặc”, “suy ra”, vv … Ví dụ : xét các mệnh đề sau: p: “15 chia hết cho 3” ; q: “2 là một số nguyên tố và là một số lẻ” Ta có: p là mệnh đề sơ cấp, q là mệnh đề phức hợp, vì q được tạo thành từ 2 mệnh đề: p1 : “2 là một số nguyên tố” ; P2: “2 là một số lẻ” nhờ vào liên kết logic “và”. 1.3.2.Các phép toán mệnh đề
Khi có các mệnh đề phức hợp theo các mệnh đề sơ cấp thì việc tính toán giá trị chân lý sẽ được thực hiện như thế nào? Để trả lời được cần có các phép toán logic, các phép toán logic ở đây là các ký hiệu được dùng thay cho các từ liên kết logic như từ “không”, “và”, “hay”, “hoặc”, “suy ra”, “nếu … thì …”, “nếu và chỉ nếu…” Các phép toán logic được định nghĩa bằng bảng giá trị chân lý (truth table).
a.Phép phủ định
Ký hiệu là: Giả sử p là một mệnh đề, phủ định của p được ký hiệu là hay . Bảng giá trị
chân lý của phép phủ định được cho bởi bảng:
p
0 1 1 0
Ví dụ 1: Cho mệnh đề p: 5<3 : 5 3
Giá trị chân lý của p là 0 là 1 Giá trị chân lý của
Ví dụ 2: Chỉ ra rằng và p luôn có cùng giá trị chân lý:
Giải: lập bảng giá trị chân lý của mệnh đề (p)
0 1 1 0 0 1
Qua bảng giá trị chân lý của mệnh đề ta nhận thấy rằng và luôn có cùng giá trị chân
tương đương logic với
lý nên ta có thể nói rằng là b.Phép hội
Cho p, q là 2 mệnh đề. Ta ký hiệu mệnh đề “p và q” là pq. Phép hội được định nghĩa bởi bảng giá trị chân lý sau đây.
8
p 0 0 1 1 q 0 1 0 1 pq 0 0 0 1
Ví dụ 1: Cho các mệnh đề
p: “5>2” ; q: “6 là số nguyên tố” r: “Một tam giác đều cũng là tam giác cân” Giá trị chân lý của p, q, r là 1, 0, 1. Khi đó ta có:
pq = 0; pr = 1 qr = 0;
luôn có giá trị chân lý bằng 0 (tức là một mệnh đề luôn sai)
Ví dụ 2: Bằng cách lập bảng giá trị chân lý ta có: 1.Các mệnh đề p và pp luôn có cùng giá trị chân lý. 2.Mệnh đề c.Phép tuyển
Cho p, q là 2 mệnh đề. Ta ký hiệu mệnh đề p hoặc q (p hay q) là pq. Phép tuyển
hay phép hoặc được định nghĩa bởi bảng chân lý sau:
p 0 0 1 1 q 0 1 0 1 pq 0 1 1 1
Ví dụ 1: Với các mệnh đề p, q, r đã cho ta có:
pq = 1; pr = 1
là luôn đúng.
Ví dụ 2: Lập bảng giá trị chân lý ta luôn có mệnh đề Nhận xét: Một mệnh đề phức hợp mà luôn đúng bất kể các giá trị chân lý của các mệnh dề thành phần của nó được gọi là hằng đúng. Một mệnh đề mà luôn luôn sai được gọi là mâu thuẫn. Một mệnh đề không phải hằng đúng, cũng không phải mâu thuẫn được gọi là tiếp liên Ví dụ 3 : là luôn đúng nó là hằng đúng.
là luôn luôn sai nó là mâu thuẫn.
Phép loại trừ ký hiệu là XOR. p XOR q được định nghĩa bởi bảng chân lý sau:
p 0 0 1 1 q 0 1 0 1 p XOR q 0 1 1 0
p XOR q đúng khi trong 2 mệnh đề p và q có một mệnh đề đúng, một mệnh đề sai.
d.Phép kéo theo, ký hiệu là
Cho p và q là 2 mệnh đề. Mệnh đề p kéo theo q ký hiệu là p q dùng để diễn đạt
phát biểu: nếu p thì q và được định nghĩa bởi bảng chân lý sau:
9
p 0 0 1 1 q 0 1 0 1 p q 1 1 0 1
Ví dụ : với nN, ta xét mệnhđề:
p: n chia hết cho 5 q: n chia hết cho 9
Lúc đó mệnh đề p q có giá trị xác định cụ thể:
n = 45 p: 1 q: 1 p q: 1 n = 15 p: 1 q: 0 p q: 0 n = 16 p: 0 q: 0 p q: 1
Xét mệnh đề p q (1). Khi đó các mệnh đề sau đây gọi là các mệnh đề liên kết với (1)
(2) (3) (4)
Mệnh đề (1) được gọi là mệnh đề thuận Mệnh đề (2) được gọi là mệnh đề đảo Mệnh đề (3) được gọi là mệnh đề phản Mệnh đề (4) được gọi là mệnh đề phản đảo Các mệnh đề liên kết chia thành 2 cặp tương đương:
i/ ii/ với mệnh đề (1): Nếu có p thì có q do đó còn nói: p là điều kiện đủ để có q. Mệnh đề (1) tương đương mệnh đề (4) nghĩa là không q thì không p, do đó có thể
nói: q là điều kiện cần để có p. e.Phép kéo theo hai chiều (phép tương đương). Ký hiệu là Cho p, q là 2 mệnhđề. Mệnh đề p tương đương q dùng để diễn đạt phát biểu: p nếu và chỉ nếu q và được định nghĩa bởi bảng giá trị chân lý sau:
P 0 0 1 1 q 0 1 0 1 p q 1 0 0 1
Mệnh đề p q được đọc là: p nếu và chỉ nếu q hay còn được phát biểu dưới các
dạng khác:
p khi và chỉ khi q p là điều kiện cần và đủ cho q Độ ưu tiên của các toán tử logic
1. 2. , 3. ,
có nghĩa là
Trong đó các toán tử liệt kê trên cùng dòng có cùng độ ưu tiên. Ví dụ : 1. 2. có nghĩa
1.3.3.Biểu thức logic (công thức logic)
10
Trong đại số ta có các biểu thức số học được xây dựng từ các hằng số, các biến số và các phép toán số học. Khi thay thế các biến trong một biểu thức số học bởi các hằng số
là , , , ,
là một biểu thức logic với các biến mệnh đề x, p, q, r.
thì kết quả thực hiện các phép toán trong biểu thức là một hằng số. Trong đại số mệnh đề ta có biểu thức logic cũng được xây dựng như sau: a.Định nghĩa: Các mệnh đề chưa xác định p, q, r… gọi là các biến mệnh đề. 1.Các biến mệnh đề là các biểu thức 2.Nếu P, Q là các (công thức) biểu thức logic thì các (công thức) biểu thức. 3.Mọi ký hiệu khác không được xác định theo 2 qui tắc 1, 2 đều không là các biểu thức. Ví dụ: p(x, y, z) = b.Sự tương đương logic
Hai biểu thức logic E và F theo bộ biến mệnh đề nào đó được gọi là tương đương logic khi E và F luôn có cùng giá trị chân lý trong mọi trường hợp giá trị chân lý của bộ biến mệnh đề.
Khi đó ta viết E F hay E F và đọc là “E tương đương với F”. Như vậy, để chứng minh 2 biểu thức logic là tương đương logic thì có thể lập bảng giá trị chân lý.
Ví dụ: Chứng minh Giải: ta lập bảng giá trị chân lý như sau:
0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1
Nhìn vào giá trị chân lý trên 2 cột cuối ta thấy:
c.Phép biến đổi công thức (biểu thức): Để biến đổi biểu thức một cách thuận tiện, ta qui ước các điều sau:
1.Không viết dấu ngoặc ngoài cùng đối với mỗi công thức (biểu thức). 2.Thay ký hiện bởi dấu . hoặc bỏ đi. 3.Các phép toán được thực hiện theo thứ tự: , , , 4.Nếu có dấu phủ định trên một biểu thức thì bỏ dấu ngoặc hai đầu biểu thức đó. Ví dụ :
( ) được viết là p q r được viết là
gọi là luật bài trung: Trong nên ta có một luật = . Luật =
11
d.Các luật của logic mệnh đề Biểu thức logic A gọi là hằng đúng nếu A nhận giá trị 1 với mọi hệ giá trị chân lý của bộ biến mệnh đề có mặt trong A. Biểu thức logic A gọi là hằng sai nếu A nhận giá trị 0 với mọi hệ giá trị chân lý của bộ biến mệnh đề có mặt trong A. Khi A là hằng đúng thì ta gọi A là một luật, ký hiện là = A. Khi A là hằng sai thì ta gọi A là một mâu thuẫn. Ví dụ : hai mệnh đề phủ định lẫn nhau, có ít nhất một mệnh đề đúng.
Các luật logic cơ bản
,
,
1. Luật phủ định kép: 2. Luật giao hoán: 3. Luật kết hợp: 4. Luật phân phối:
,
,
5. Luật Demorgan: 6. Luật về mối liên hệ giữa p với chính nó, với , với 0 và 1:
7. Luật kéo theo: 8. Luật tương đương:
Vế phải
Nhận xét: Có thể dùng các luật logic để biến đổi tương đương các biểu thức logic, hay nói cách khác, để chứng minh 2 biểu thức logic tương đương ta có thể dùng phương pháp biến đổi logic. Ví dụ: Chứng minh Ta biến đổi vế trái về vế phải như sau: Vế trái 1.3.4.Các dạng chính tắc a.Dạng chính tắc tuyển
Giả sử p1, p2, …, pn là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh
(i = 1… n).
hoặc là các biểu thức hội cơ bản theo 3
đề p1, p2, …, pn được gọi là một biểu thức hội cơ bản nếu nó có dạng sau: F = q1 q2 … qn với qi = pi hoặc Ví dụ: Biểu thức xyz hoặc biến mệnh đề x, y, z.
Biểu thức E (p1, p2, …, pn) theo các biến mệnh đề p1, p2, …, pn được gọi là có dạng chính tắc tuyển khi E có dạng: E = E1 E2 … Em. Trong đó mỗi biểu thức Ei đều có dạng là một biểu thức hội cơ bản theo các biến mệnh đề p1, p2, …, pn. Ví dụ : Các biểu thức sau đây có dạnh chính tắc tuyển.
Định lý: Mọi biểu thức logic F(p1, p2, …, pn) đều có thể viết dưới dạng chính tắc tuyển duy nhất (không kể sự sai khác về thứ tự trước sau của các biểu thức hội cơ bản trong phép tuyển).
Nói cách khác, ta có duy nhất một tập hợp các biểu thức hội cơ bản {E1, E2, …, Em}
12
sao cho biểu thức E (p1, p2, …, pm) E1 E2 … Em. Ví dụ : Tìm dạng chính tắc tuyển của biểu thức:
b. Dạng chính tắc hội
Giả sử p1, p2, …, pn là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh đề p1, p2, …, pn được gọi là một biểu thức tuyển cơ bản nếu nó có dạng sau:
(i = 1… n). F = q1 q2 … qn với qi = pi hoặc
hoặc là các biểu thức tuyển cơ bản theo
Ví dụ: Biểu thức x y z hoặc 3 biến mệnh đề x, y, z.
Biểu thức E (p1, p2, …, pn) theo các biến mệnh đề p1, p2, …, pn được gọi là có dạng chính tắc hội khi E có dạng: E = E1 E2 … Em. Trong đó mỗi biểu thức Ei đều có dạng là một biểu thức tuyển cơ bản theo các biến mệnh đề p1, p2, …, pn. Ví dụ : Các biểu thức sau đây có dạng chính tắc hội.
Định lý: Mọi biểu thức logic F(p1, p2, …, pn) đều có thể viết dưới dạng chính tắc hội duy nhất (không kể sự sai khác về thứ tự trước sau của các biểu thức tuyển cơ bản trong phép hội).
Nói cách khác, ta có duy nhất một tập hợp các biểu thức tuyển cơ bản {E1, E2, …,
Em} sao cho biểu thức E (p1, p2, …, pm) E1 E2 … Em. Ví dụ 1: Tìm chính tắc hội của biểu thức sau:
Ví dụ 2: Tìm chính tắc tuyển của biểu thức:
1.3.5.Vị từ, lượng từ a.Vị từ (Hàm mệnh đề)
13
P(x) là một hàm mệnh đề (một biến) xác định trên tập X nếu với mỗi xX thì P(x) là một mệnh đề. Hàm mệnh đề một biến còn được gọi là vị từ 1-ngôi.
EP(x)={ aX P(a) là mệnh đề đúng}
Nếu P(x) là một hàm mệnh đề xác định trên X thì x được gọi là biến tử, một phần tử cụ thể aX gọi là hằng tử, P(a) là một hàm mệnh đề hoàn toàn xác định. Tương tự ta có hàm mệnh đề m biến, hay vị từ m-ngôi với mN* b.Miền đúng của hàm mệnh đề Giả sử P(x) là một hàm mệnh đề trên X, khi đó miền đúng của P(x) là tập Ví dụ:
1. P(x): x2-6x+5=0 với x R có EP(x)={ 1,5} 2. P(x): x2-6x+50 với x R có EP(x)=
Hàm mệnh đề P(x) xác định trên X gọi là hằng đúng nếu EP(x)=X, gọi là hằng sai nếu EP(x)=, gọi là thực hiện được nếu EP(x) Ví dụ:
1. P(x): x2+1>0 là hằng đúng trên R 2. P(x): x2+1=0 là hằng sai trên R 3. P(x): 3x-4=0 là thực hiện được trên R nhưng không thực hiện được trên N Hai hàm mệnh đề P(x) và Q(x) cùng xác định trên tập X được gọi là tương đương
hoặc khi và chỉ khi EP(x)= EQ(x)
logic, kí hiệu là c.Phép toán trên các hàm mệnh đề
Cho P(x) là một hàm mệnh đề xác định trên X, ta gọi phủ định của P(x) là
Phép phủ định hàm mệnh đề xác định trên X, nhận giá trị 1 trên tập các phần tử
, nhận giá trị 0 trên miền đúng của P(x)
EP(x)
Ta có:
Phép hội Cho 2 hàm mệnh đề P(x), Q(x) cùng xác định trên X, hội của P(x) và Q(x) là hàm mệnh đề P(x) Q(x) xác định trên X, nhận giá trị 1 trên tập các phần tử aX sao cho
, nhận giá trị 0 trong các trường hợp còn lại.
14
Ta có:
, nhận giá trị 1 trong các trường hợp còn lại.
Phép kéo theo
Phép tuyển Cho 2 hàm mệnh đề P(x), Q(x) cùng xác định trên X, tuyển của P(x) và Q(x) là hàm mệnh đề P(x) Q(x) xác định trên X, nhận giá trị 0 trên tập các phần tử aX sao cho Ta có: Cho 2 hàm mệnh đề P(x), Q(x) cùng xác định trên X, ta gọi P(x) kéo theo Q(x) là hàm mệnh đề P(x) Q(x) xác định trên X, nhận giá trị 0 trên tập các phần tử aX sao cho
, nhận giá trị 1 trong các trường hợp còn lại.
là mệnh đề đúng
là mệnh đề sai là mệnh đề đúng là mệnh đề sai
Ta có: Phép tương đương Cho 2 hàm mệnh đề P(x), Q(x) cùng xác định trên X, ta gọi P(x) tương đương Q(x) là hàm mệnh đề P(x) Q(x) xác định trên X, nhận giá trị 1 trên tập các phần tử aX sao cho , nhận giá trị 0 trong các trường hợp còn lại. Ta có: d. Lượng từ Cho P(x) là hàm mệnh đề xác định trên X. Ta gọi xX P(x) hiểu là Với mọi xX, P(x) là mệnh đề đúng nếu EP(x)=X, sai trong các trường hợp khác. Ta gọi xX P(x) hiểu là tồn tại xX, P(x) là mệnh đề đúng nếu EP(x), sai trong các trường hợp khác. Ký hiệu gọi là lượng từ phổ dụng (với mọi), ký hiệu gọi là lượng từ tồn tại Như vậy: xX P(x) đúng P(x) hằng đúng trên X xX P(x) đúng P(x) thực hiện được trên X Ví dụ: 1. 2. 3. 4. e. Lượng từ trên các hàm mệnh đề nhiều biến Cho hàm mệnh đề 2 biến Px,y) xác định trên X x Y. Khi đó với mỗi y cố định xX P(x,y), xX P(x,y) là các mệnh đề, do đó ta được các hàm mệnh đề xX P(x,y), xX P(x,y) xác định theo yY. Ta có thể áp dụng các lượng từ với mọi và tồn tại lên các hàm mệnh đề này để được các mệnh đề xác định: xX yY P(x,y), xX yY P(x,y) , xX yY P(x,y) , xX yY P(x,y) f. Mối liên hệ giữa 2 mệnh đề phổ dụng và tồn tại Cho P(x) là hàm mệnh đề xác định trên X, khi đó ta có: ; 2. 1.
15
1.4 Suy luận toán học & các phương pháp chứng minh 1.4.1 Qui tắc suy luận Giả sử A1, A2, ..., An, B là các biểu thức logic. Ta nói B là hệ quả logic của A1, A2, ..., An nếu với mọi bộ giá trị chân lý có thể nhận của bộ biến mệnh đề có mặt trong trong các biểu thức đó mà A1, A2, ..., An đồng thời nhận giá trị 1 đều có B nhận giá trị 1.
Khi B là hệ quả logic của A1, A2, ..., An thì nói rằng có một qui tắc suy luận từ các tiên đề A1, A2, ..., An tới hệ quả logic B.
Qui tắc suy luận trên được kí hiệu là: hay A1, A2, ..., An = B
Ta có A1, A2, ..., An đồng thời nhận giá trị 1 khi và chỉ khi Khi đó đúng nhận giá trị 1 nhận giá 1 thì B cũng nhận giá trị 1
Hay có qui tắc suy luận có luật
Như vậy để chứng minh qui tắc suy luận ta có thể dùng một trong 2 phương
pháp sau:
1. Lập bảng giá trị chân lý, xét theo đúng định nghĩa 2. Chỉ ra mệnh đề là hằng đúng.
Ví dụ 1: Chứng minh qui tắc suy luận
Cách 1: Lập bảng giá trị chân lý
p 0 0 1 1 q 0 1 0 1 1 1 0 1
Nhìn vào bảng giá trị chân lý ta thấy có một bộ giá trị của p,q làm cho p,q nhận giá trị 1
thì cũng nhận giá trị 1, do đó theo định nghĩa ta có qui tắc suy luận
Cách 2: Để chứng minh qui tắc suy luận ta cần chứng minh
( hằng đúng)
(ĐPCM)
Thực vậy:
Ví dụ 2: Chứng minh qui tắc suy luận
Cách 1: Lập bảng giá trị chân lý
16
p 0 0 0 0 1 1 q 0 0 1 1 0 0 r 0 1 0 1 0 1 pq 1 1 1 1 0 0 qr 1 1 0 1 1 1 pr 1 1 1 1 0 1
1 1 1 1 0 1 1 1 0 1 0 1
Nhìn vào bảng giá trị chân lý ta thấy có 4 bộ giá trị của p,q, r làm cho pq và qr đồng cũng nhận giá trị 1, do đó theo định nghĩa ta có qui tắc suy thời nhận giá trị 1 thì
luận
Cách 2: Để chứng minh qui tắc suy luận ta cần chứng minh
( hằng đúng)
Thực vậy:
(ĐPCM)
1.4.2 Các qui tắc suy luận cơ bản Trong suy luận toán học người ta thường dùng 28 qui tắc suy luận cơ bản sau, các qui tắc này đã được chứng minh theo 2 phương pháp trên. 2 ví dụ vừa xét là qui tắc suy luận số1 và qui tắc số 3.
1. 2.
3. 4.
5. 6.
7. 8.
9. 10.
11. 12.
13. 14.
15. 16. ;
17. ; 18.
17
19. 20.
21. 22.
23. 24.
25. 26. ;
27. 28.
1.4.3 Hai kiểu suy luận a.Suy luận diễn dịch (Suy diễn): Là suy luận theo các quy tắc suy luận, xác định rằng nếu các tiên đề là đúng thì kết luận rút ra cũng phải đúng. Ví dụ: Từ 2 tiền đề >3 và <4 suy ra 3<<4, trong suy luận này ta đã sử dụng qui tắc suy luận số 13. b.Suy luận có lý: Là suy luận không theo qui tắc suy luận nào để từ tiên đề đã có rút ra được kết luận xác định. Nếu các tiền đề đều đúng thì kết luận chưa chắc đã đúng mà chỉ mang tính chất dự đoán, giả thuyết. Trong toán học thường dùng 2 kiểu suy luận có lý, đó là phép qui nạp không hoàn và phép tương tự.
Hai kiểu suy luận này có vai trò đặc biệt quan trọng trong phát minh sáng tạo, nó giúp con người đưa ra những phán đoán về các kết quả mới.
1.4.4 Các phương pháp chứng minh a. Khái niệm về chứng minh
Khi có quy tắc suy luận nếu tất cả các tiền đề A1, A2, ..., An đều
18
đúng thì kết luận logic B gọi là kết luận chứng minh và mệnh đề B gọi là đã được chứng minh. Như vậy một kết luận chứng minh là một kết luận logic của các tiền đề đúng. Ví dụ: Có qui tắc suy luận: Với a,bR, nếu a=b thì a2=b2 Đặt A: a=b; B: a2=b2 1/ A:2=2 ; B:22=22 ; có AB nên B:22=22 là một kết luận logic và B cũng là một kết luận chứng minh vì tiền đề A là đúng. 2/ A: -2=2 ; B:(-2)2=22 ; có AB nên B:22=22 là một kết luận logic nhưng B không phải là một kết luận chứng minh vì tiền đề A là sai. b. Kết cấu của chứng minh Một chứng minh có 3 bộ phận cấu thành: 1. Luận đề: Là mệnh đề cần phải chứng minh 2. Luận cứ: Là các mệnh đề được thừa nhận được lấy ra làm tiên đề trong mỗi suy luận. 3. Luận chứng: Là các quy tắc suy luận được vận dụng trong mỗi bước suy luận của chứng minh. c. Các phương pháp chứng minh trong toán học i.Chứng minh theo phương pháp trực tiếp Mệnh đề B gọi là được chứng minh trực tiếp nếu ta chỉ ra được B là kí hiệu logic của các tiền đề đúng A1, A2, ..., An Ví dụ: Chứng minh trực tiếp định lý: Nếu n là số lẻ thì n2 cũng là số lẻ Chứng minh: Theo giả thiết n là số lẻ n=2k+1, kZ
n2=4k2+4k+1, kZ hay n2= 2(2k2+2k)+1=2k’+1, k’Z n2 là số lẻ (ĐPCM) ii.Chứng minh theo phương pháp phản chứng: Là phương pháp sử dụng qui tắc suy luận số 26.
26. ;
q: n là số lẻ
tức là n là số chẵn n=2k, kZ
Ví dụ: Chứng minh rằng: Nếu 3n+2 là số lẻ thì n cũng lẻ Đặt p: 3n+2 là số lẻ Ta phải chứng minh pq Giả thiết có Khi đó ta có 3n+2=3.2k+2=2(3k+1)=2k’ , k’Z 3n+2 là số chẵn, điều này mâu thuẫn với giả thiết p đã cho 3n+2 là số lẻ. Vậy theo quy tắc suy luận số 26 ta có ĐPCM hay pq iii. Chứng minh theo phương pháp phân chia trường hợp Cho P(x) là một hàm mệnh đề xác định trên X. Giả sử X= với
Khi đó ta có quy tắc suy luận
1/ r=0 ; 2/ r=1; 3/ r=2
Giả sử cần chứng minh tính chất đúng đắn của khẳng định P(n) với mọi số tự
1. Trước tiên kiểm tra P(1) đúng 2. Sau đó chứng minh rằng, với mọi số tự nhiên k1, từ tính đúng đắn của
19
Ví dụ: Cho nZ, hãy chứng minh n3+2n chia hết cho 3 Ta có n3+2n=n(n2+2) sẽ chia hết cho 3 khi n là bội của 3 Với mỗi nZ, gọi r = n mod 3 khi đó ta có: Có 3 trường hợp (r=0)(r=1)(r=2) Xét trường hợp1: với r=0, n có dạng n=3k, kZ n3+2n =3k(9k2+2) chia hết cho 3 Xét trường hợp 2: với r=1, n có dạng n=3k+1, kZ n3+2n =3(k+1)(9k2+6k+3)=(3k+1)3(3k2+2k+1) chia hết cho 3 Xét trường hợp 3: với r=2, n có dạng n=3k+2, kZ n3+2n =3(k+2)(9k2+12k+6)=(3k+2)3(3k2+4k+2) chia hết cho 3 Như vậy trong mọi trường hợp (r=0), (r=1), (r=2) có thể có ta đều chứng minh được n3+2n chia hết cho 3. Vậy có ĐPCM iv. Chứng minh theo qui nạp toán học: Giả sử P(n) là một khẳng định phụ thuộc vào số tự nhiên n, cần phải chứng minh P(n) đúng với n. Ta không thể dùng phép qui nạp hoàn toàn vì tập N là vô hạn, không thể tiến hành kiểm tra tất cả các trường hợp riêng. Nếu dùng phép quy nạp không hoàn toàn để kết luận thì có thể dẫn đến sai lầm. Để khắc phục khó khăn này ta dùng một phương pháp suy luận đặc biệt gọi là phương pháp qui nạp toán học. nhiên n0 (nZ+), ta thực hiện: khẳng định n=k cũng suy ra được khẳng định đúng khi n=k+1. Khi khẳng định đúng với n=k+1 thì khẳng định P(n) được coi là đúng với mọi số tự nhiên n. Một hình thức khác của phương pháp qui nạp toán học: Chứng minh nn0 P(n) là đúng 1. Chỉ ra khẳng định P(n0) là đúng 2. Nếu khẳng định P(k) là đúng thì khẳng định P(k+1) cũng đúng với mọi số tự nhiên k n0 ( hay nếu P(1), P(2),...,P(k) đúng thì P(k+1) cũng đúng)
1. Khi n=2, ta có P2): 2 hay P(2) là đúng 2. Giả sử các khẳng định P(2), P(3), ...,P(k) đúng, ta cần chứng minh P(k+1)
* Nếu k+1 là số nguyên tố thì P(k+1): (k+1) tức P(k+1) là đúng * Nếu k+1 là hợp số thì k+1=a1.a2 với 2a1k và 2a2k
20
Kết luận, khẳng định P(n) đúng với mọi số nguyên n n0 Ví dụ 1: Chứng minh rằng với mọi số tự nhiên n2 đều phân tích được thành tích của một hay nhiều thừa số nguyên tố. Gọi P(n) là khẳng định: Số tự nhiên n phân tích được thành tích của một hoặc nhiều thừa số nguyên tố. cũng đúng. Xét số tự nhiên k+1, có 2 khả năng xảy ra: Theo giả thiết qui nạp ta có a1, a2 có thể phân tích được thành tích của một hoặc nhiều thừa số nguyên tố, khi đó k+1= a1. a2 phân tích được thành tích của các thừa số nguyên tố, hay P(k+1) là đúng. Kết luận: Mọi số nguyên n2 đều phân tích được thành tích của một hay nhiều thừa số nguyên tố. Ví dụ 2: Chứng minh rằng Sn= 1 + 3 + 5 + ... + (2n-1) = n2 với mọi số tự nhiên n 1 Chứng minh: 1. Khi n=1, ta có S1=1=12 hay S1 là đúng 2. Giả sử khẳng định đúng với n=k>1, kZ+ Nghĩa là ta có: Sk= 1 + 3 +...+(2k-1)=k2 Xét Sk+1=1 + 3 + ....+(2k-1) + (2k+1) = k2+2k+1=(k+1)2 tức là khẳng định đúng với n=k+1. Kết luận: Sn= 1 + 3 + 5 + ... + (2n-1) = n2 với mọi số tự nhiên n 1
CHƯƠNG 2 GIẢI THUẬT & CÁC PHƯƠNG PHÁP ĐẾM
2.1. Thuật toán và các đặc trưng cơ bản của thuật toán 2.1.1. Khái niệm thuật toán Một bài toán hay một vấn đề cần giải quyết thường được diễn đạt theo một sơ đồ chung dưới dạng: A B , trong đó A: Được hiểu là giả thiết, các điều kiện ban đầu hoặc là cái đã cho, đã có khi bắt đầu giải bài toán. B: được hiểu là kết luận, mục tiêu cần đạt được hoặc là cái phải tìm, phải làm ra khi kết thúc bài toán. : Được hiểu là suy luận, giải pháp cần xác định hoặc là một chuỗi các thao tác cần thực hiện, cần thi hành để có được cái phải tìm từ cái đã cho. Như vậy, giải bài toán có nghĩa là xuất phát từ dữ liệu vào, thực hiện một dãy hữu hạn những thao tác có cơ sở khoa học thích hợp để tìm được dữ liệu ra (kết quả) theo yêu cầu của bài toán. Một bài toán trên máy tính cũng mang đầy đủ các tính chất của một bài toán nói
chung nhưng có thể diễn đạt theo một cách khác: Input: Các dữ liệu vào của bài toán hay A-Thông tin vào Output: Các dữ liệu ra thoả mãn yêu cầu của bài toán hay B-Thông tin ra : Chương trình tạo ra từ các lệnh cơ bản của máy cho phép biến đổi từ A thành B Khi xác định một bài toán trên máy tính thường gặp phải hai khó khăn chính như sau:
1. Thông Tin về A hay B không đầy đủ và không rõ ràng. 2. Thông tin về các điều kiện đặt ra cho cách giải thương không được nêu ra một cách
minh bạch.
Khi giải quyết bài toán cần khắc phục hoặc bằng các phương pháp khác nhau để hoàn thiện dần các thiếu sót về thông tin của A hoặc B nhằm giải quyết trọn vẹn bài toán theo đúng nhu cầu của người dùng. Ví dụ 1: Cho 2 số tự nhiên a, b. Tìm ước số chung lớn nhất của chúng. Xác định bài toán: A. Xác định thông tin vào: 2 số tự nhiên a, b B. Xác định thông tin ra: Số tự nhiên d thõa mãn: d là ước của a và d là ước của b; d lớn nhất trong tập các ước chung của a và b. Xác định các thao tác xử lý thông tin: Xây dựng một dãy hữu hạn các thao tác cho phép tính được d từ a và b. Ví dụ a=16 b=24 d=8 Ví dụ 2: Cho một dãy số nguyên dương a1, a2, ...., an Hãy tìm từ dãy trên một dãy con (không nhất thiết phải liên tiếp) tăng và có độ dài là dài nhất. Xác định bài toán:
A. Xác định thông tin vào: + một dãy số nguyên dương a1, a2, ...., an + Mỗi số được xác định bởi 2 yếu tố là giá trị của số và vị trí (số thứ tự) của số đó trong dãy. B. Xác định thông tin ra:
+ Một dãy lấy từ dãy số đã cho: ai1, ai2, ...., aik
21
(dãy con thu được sau khi đã gạch bỏ một số phần từ của dãy đã cho)
Dãy con này phải có 2 tính chất:
1. Tăng ai1< ai2 < .... Xác định các thao tác xử lý thông tin: 1. Lần lượt duyệt các phần tử của dãy đã cho
2. Phải quyết định xem loại bỏ phần tử nào để dãy còn lại là tăng và dài nhất. Nhận xét: 1. Việc xác định bài toán là khá quan trọng, nó ảnh hưởng rất lớn đến cách thức và chất lượng của việc giải quyết bài toán. 2. Một bài toán cho dù được diễn đạt bằng các thông tin chính xác thì cũng phải giả
định là phần lớn thông tin về A và B là tiềm ẩn trong đầu người giải, thông báo về A hoặc
B chỉ là biểu tượng gợi nhớ đến các thông tin tiềm ẩn đó. 3. Bước đầu tiên để xác định một bài toán là phải phát biểu lại bài toán một cách
chính xác theo ngôn ngữ của riêng mình vì đó chính là cách ta tiếp cận bài toán, hiểu bài
toán. Bước tiếp sau là tìm hiểu các thông tin vào A và thông tin ra B, tìm các mối liên hệ
giữa chúng.
Qua ví dụ trên, chúng ta thấy rằng để biểu diễn lời giải cho một bài toán trên máy tính
(dù là rất đơn giản), chúng ta phải làm rõ tất cả mọi chi tiết của cách giải, hướng dẫn cụ
thể từng bước, từng bước một thì máy tính mới có thể thi hành được. Cách biểu diễn lời
giải vấn đề một cách rõ ràng, chi tiết để có thể thi hành được trên máy tính được gọi là
thuật toán.
Định nghĩa: Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các
phép toán hoặc hành động cần thực hiện để giải quyết một vấn đề.
2.1.2. Các đặc trưng cơ bản của thuật toán Thuật toán có vai trò rất quan trọng trong khoa học máy tính. Để có thể lập trình
giải bài toán trên máy tính, ta cần có một thuật toán bảo đảm những tính chất nhất định.
Khi mô tả một thuật toán chúng ta cần chú ý đến các tính chất sau đây:
1. Nhập (input): Mỗi thuật toán cần có một số (có thể bằng 0) dữ liệu vào. Đó là các giá
trị cần đưa vào khi thuật toán bắt đầu làm việc. Các dữ liệu này cần được lấy từ tập hợp
giá trị cụ thể nào đó.
2. Xuất (output): Mỗi thuật toán cần có một hoặc nhiều dữ liệu ra. Đó là các giá trị có
quan hệ hoàn toàn xác định với các dữ liệu vào và tùy theo chức năng mà thuật toán đảm
nhiệm, đó là kết quả của sự thực hiện thuật toán
3. Tính xác định (definiteness): ở mỗi bước của thuật toán, các thao tác phải hết sức rõ
ràng. Không thể gây nên sự nhập nhằng, lẫn lộn, tùy tiện. Hay nói cách khác, trong cùng
một điều kiện, hai bộ xử lý cùng thực hiện một bước của thuật toán thì phải cho cùng một
kết quả.
4. Tính hữu hạn dừng (finiteness): Một thuật toán bao giờ cũng phải dừng lại sau một số
hữu hạn bước.
5. Tính đúng đắn: Sau khi thực hiện tất cả các lệnh của thuật toán ta phải được kết quả
mong muốn, kết quả đó thường được xác định theo định nghĩa có trước.
5. Tính hiệu quả (về thời gian): Thuật toán cần phải được thực hiện một cách chính xác và
trong một khoảng thời gian cho phép. Hoặc có thể hiểu: Tính hiệu quả của một thuật toán
được đánh giá dựa trên các tiêu chuẩn sau:
1. Dung lượng bộ nhớ cần có
2. Số các phép tính cần thực hiện
3. Thời gian cần thiết để chạy chương trình
4. Có dễ hiểu đối với con người không
5. Có dễ cài đặt trên máy không.
6. Tính tổng quát. Thuật toán phải áp dụng được cho tất cả các bài toán có dạng như mong
muốn, chứ không phải chỉ áp dụng được cho một số trường hợp đặc biệt nào đó. Điều này
22 có nghĩa là thuật toán có thể làm việc với các dữ liệu khác nhau trong một miền xác định
và luôn dẫn đến kết quả mong muốn.
Mở rộng khái niệm thuật toán: Để có thể giải các bài toán bằng máy tính ta thường phải
có quan niệm rộng hơn về thuật toán, với các đặc điểm sau:
1. Không cần xác định toàn bộ lời giải, các thao tác theo từng bước một cách chính xác,
đơn trị và rõ ràng. Thay vào đó chỉ cần chỉ ra một cách chuyển từ một bước giải i tới bước
giải kế tiếp i+1 và tìm cách chia nhỏ bài toán thành các bài toán con, đó chính là thuật
toán đệ quy để giải các bài toán tổng quát.
2. Có nhiều bài toán không có cách giải đúng, hoặc cách giải đúng không thể chấp nhận
được do hạn chế về thời gian chạy và kích thước bộ nhớ. Nhưng nếu cháp nhận kết quả
gần đúng thì có thể tồn tại nhiều cách giải đỡ phức tạp và có hiệu quả hơn, đó chính là các
thuật toán Heuristic để giải các bài toán gần đúng.
2.1.3. Các phương pháp biểu diễn thuật toán
Khi chứng minh hoặc giải một bài toán trong toán học, ta thường dùng những ngôn
ngữ toán học như: “ta có”, “điều phải chứng minh”, “giả thuyết”,... và sử dụng những
phép suy luận Toán học như phép suy ra, tương đương,...Thuật toán là một phương pháp
thể hiện lời giải bài toán nên cũng phải tuân theo một số quy tắc nhất định. Để có thể
truyền đạt thuật toán cho người khác hay chuyển thuật toán thành chương trình máy tính,
ta có các phương pháp biểu diễn thuật toán sau: 1. Dùng ngôn ngữ tự nhiên
2. Dùng lưu đồ hay sơ đồ khối
3. Dùng mã giả
a. Dùng ngôn ngữ tự nhiên
Trong cách biểu diễn thuật toán theo ngôn ngữ tự nhiên, người ta sử dụng ngôn
ngữ thường ngày để liệt kê các bước của thuật toán. Phương pháp này không yêu cầu
người viết thuật toáncũng như người đọc thuật toán phải nắm được các quy tắc. Tuy vậy
cách biểu diễn này thường dài dòng, không thể hiện rõ cấu trúc của thuật toán, đôi lúc gây
hiểu lầm hoặc khó hiểu cho người đọc. Gần như không có một quy tắc cố định nào trong
việc thể hiện thuật toán bằng ngôn ngữ tự nhiên.
b. Dùng lưu đồ - sơ đồ khối Lưu đồ hay sơ đồ khối là một công cụ trực quan để diễn đạt các thuật toán. Biểu
diễn thuật toán bằng lưu đồ sẽ giúp người đọc theo dõi được sự phân cấp các trường hợp
và quá trình xử lý của thuật toán. Phương pháp lưu đồ thường được dùng trong những
thuật toán có tính rắc rối, khó theo dõi được quá trình xử lý. Lưu đồ là một hệ thống các nút có hình dạng khác nhau theo qui ước, thể hiện các
chức năng khác nhau và được nối với nhau bởi các cung. Lưu đồ được tạo bởi 4 thành
phần chủ yếu sau đây:
1/ Nút giới hạn: được biểu diễn bởi hình ôvan có ghi chữ bên trong như : Nhập/ xuất a,b k:=1;
S:=S+k 23 Các nút trên còn được gọi là nút đầu và nút cuối của lưu đồ.
2/ Nút thao tác: Gồm có 2 loại: Thao tác nhập/xuất được biểu diễn bởi hình bình hành và
Thao tác xử lý được biểu diễn bởi hình chữ nhật. Ví dụ: F a=0 T 3/ Nút điều kiện:
Thường là một hình thoi có ghi điều kiện cần kiểm tra. Trong các cung nối với nút này có
2 cung ra chỉ hướng đi theo 2 trường hợp: điều kiện đúng và điều kiện sai. Bắt đầu a, b 4/ Cung (mũi tên): là các đường nối từ nút này đến nút khác của lưu đồ, chỉ hướng đi
của thuật toán.
Hoạt động của thuật toán theo lưu đồ được bắt đầu từ nút đầu tiên. Sau khi thực hiện
các thao tác hoặc kiểm tra điều kiện ở mỗi nút thì bộ xử lý sẽ theo một cung để đến nút
khác. Quá trình thực hiện thuật toán dừng khi gặp nút kết thúc hay nút cuối.
Ví dụ 1: Lập lưu đồ thuật toán giải phương trình bậc 1: ax+b = 0 a<>0 x:=-b/a False True b<>0 x False PT vô số nghiệm PT vô nghiệm Kết thúc True 24 Ví dụ 2: Lập sơ đồ khối biểu diễn thuật toán tìm USCLN của 2 số tự nhiên a, b Begin a, b a<>b USCLN là a 0 1 a>b End a:=a-b 1 0 b:=b-a 25 Hình 2.2: Lưu đồ thuật toán tìm ước số chung lớn nhất của 2 số a,b. c. Dùng giả mã Tuy sơ đồ khối thể hiện rõ quá trình xử lý và sự phân cấp các trường hợp của thuật
toán nhưng lại cồng kềnh, để mô tả một thuật toán nhỏ phải dùng một không gian rất lớn.
Nếu biểu diễn thuật toán một cách hiệu quả, người ta thường dùng giả mã (pseudocode). Khi thể hiện thuật thuật toán bằng giả mã, ta sẽ vay mượn các cú pháp của một
ngôn ngữ lập trình nào đó để thể hiện thuật toán. Dùng giả mã vừa tận dụng được các khái
niệm trong ngôn ngữ lập trình, vừa giúp người cài đặt dễ dàng nắm bắt được nội dung của
thuật toán (tất nhiên là trong giả mã ta vẫn dùng một phần ngôn ngữ tự nhiên). Một khi đã
vay mượn cú pháp và khái niệm của ngôn ngữ lập trình thì chắc chắn giả mã sẽ bị phụ
thuộc vào ngôn ngữ lập trình đó, chẳng hạn là ngôn ngữ lập trình PASCAL, nhất là cấu
trúc điều khiển ngôn ngữ lập trình cấu trúc chọn, cấu trúc lặp.
Trong giả mã ta còn sử dụng cả các ký hiệu toán học, các biến, và đôi khi cả cấu trúc
kiểu thủ tục. Cấu trúc thuật toán kiểu thủ tục thường được sử dụng để trình bày các thuật
toán đệ qui hay các thuật toán quá phức tạp cần phải được trình bày thành nhiều cấp độ.
Cùng với việc sử dụng các biến, trong thuật toán rất thường gặp một phát biểu, hành
động đặt (hay gán) một giá trị cho một biến. Chẳng hạn như hành động tăng biết i lên 1 có
thể được viết như sau: i := i + 1 hay i = i + 1
Các cấu trúc thường được sử dụng trong giả mã dựa theo ngôn ngữ lập trình PASCAL
gồm:
Cấu trúc chọn: if (điều kiện) then (hành động)
if (điều kiện) then (hành động)
else (hành động) Cấu trúc lặp: while (điều kiện) do (hành động)
Repeat (hành động) Until (điều kiện)
for (biến) := (giá trị đầu) to (giá trị cuối) do (hành động)
for (biến) := (giá trị đầu) downto (giá trị cuối) do (hành động)
Cấu trúc nhảy goto. Ngoài ra người ta còn sử dụng lệnh ngắt vòng lặp break.
Dưới đây là các thuật toán được biểu diễn bằng giả mã (sử dụng các cấu trúc điều
khiển của ngôn ngữ lập trình PASCAL). Trước khi viết các bước thực hiện thuật toán ta
thường ghi rõ những gì được cho trước (phần nhập) và kết quả cần đạt được (phần xuất).
Ví dụ 1: Giải phương trình bậc nhất ax+b=0; a, b, x R
Input : các hệ số a,b
Outputt: nghiệm x hoặc thông báo PT vô nghiệm
Thuật toán với ngôn ngữ tự nhiên:
0. Bắt đầu thuật toán
1. Nhập hệ số a, b
2. Kiểm tra xem a =0 hay không + Nếu có thì kiểm tra tiếp xem b = 0 hay không - Nếu có thì kết luận phương trình vô số nghiệm, chuyển sang bước 5
- Nếu không thì kết luận phương trình không xác định, chuyển sang bước 5 + Nếu không thì chuyển sang bước 3 26 3. Tính nghiệm x=-b/a
4. Xuất nghiệm x
5. Kết thúc Thuật toán giả mã:
Begin
1. Read(a, b)
2. if a=0 then
If b = 0 then 3. x:=-b/a;
4. Write(x)
End;
Ví dụ 2: Tìm USCLN của 2 số tự nhiên a, b.
Input : Hai số tự nhiên a, b
Outputt: Số tự nhiên d là ước của a và d là ước của b; d lớn nhất trong tập các ước chung
của a và b.
Thuật toán giả mã:
Begin 1. Read(a,b)
2. While a<>b Do
if a>b then a:=a-b Else b:=b-a 3.d:=a
4. Write(d) End;
Hoặc có thể xây dựng thành thủ tục sau:
Function USCLN1(a,b:word):word;
Begin While a<>b Do
If a> b then a:= a-b
Else b:=b-a;
USCLN:=a; End;
Function USCLN2(a,b:word):word;
Var r: word;
Begin While b<>0 Do Begin r:= a mod b;
a:= b; b:= r; End;
USCLN:=a; 27 End;
2.2. Thuật toán đệ quy
2.2.1. Khái niệm đệ quy
Đệ quy là một khái niệm tồn tại trong cuộc sống, trong toán học, trong lập trình.
Đệ quy cho một phương pháp ngắn gọn và sáng sủa để mô tả các đối tượng cũng như một
số quá trình. Như vậy đệ quy là một phương pháp xác định tập hợp các đối tượng thỏa
mãn một yêu cầu nào đó. Nó bao gồm các quy tắc, trong đó một số quy tắc dùng để xác định các đối tượng ban đầu, còn quy tắc khác dùng để xác định các đối tượng tiếp theo
nhờ các đối tượng ban đầu đã được xác định.
Ví dụ 1: Định nghĩa số tự nhiên 0 là số tự nhiên
n là số tự nhiên nếu (n -1) là số tự nhiên Định nghĩa trên được xuất phát từ hệ các mệnh đề Pê a nô về số tự nhiên :
i.0 là một số tự nhiên
ii.0 không phải là số tự nhiên kề sau của bất kỳ số tự nhiên nào
iii.Mọi số tự nhiên n có một và chỉ một số tự nhiên n’ kề sau nó
iv.Nếu m là số tự nhiên kề sau của số tự nhiên n và m là số tự nhiên kề sau của số tự nhiên
k thì n = k
v.Nếu A N sao cho 1. 0 A
2. m A m’ A thì A N Theo tiên đề 5 để có khái niệm với số tự nhiên n ta có thể định nghĩa qui nạp như sau: Cho định nghĩa với n = 0
Nếu có định nghĩa với n thì có định nghĩa với n’ đã được định nghĩa thì A thõa mãn v.1 và v.2 đều đã được định nghĩa. Thậy vậy, Gọi A là tập các phần tử
của tiên đề 5 nên A=N, tức là
Ví dụ 2: Hàm giai thừa n! với n là số nguyên dương được tính như sau 0! =1
n! = n (n - 1)! nếu n > 0
1 nếu n=0
Hay n!= n(n-1)! nếu n>0 Như vậy, một khái niệm X gọi là định nghĩa theo đệ quy nếu trong định nghĩa X có sử
dụng ngay chính khái niệm X.
Thuật toán đệ quy: Nếu lời giải của bài toán T được thực hiện bởi lời giải của bài toán T’
có dạng như T thì đó là lời giải đệ quy. Giải thuật chứa lời giải đệ quy gọi là giải thuật đệ
quy. Một thuật toán được gọi là đệ quy nếu nó giải quyết bài toán bằng cách rút gọn
liên tiếp bài toán ban đầu tới bài toán cũng như vậy nhưng có dữ liệu đầu vào nhỏ
hơn.
Ví dụ : Xét bài toán tìm một từ trong từ điển
Cho một quyển từ điển được xếp theo vần a, b,c,..... và một từ cho trước. Hãy tìm và tra
nghĩa của từ đã cho.
Thuật toán dưới dạng giả mã
BEGIN IF BEGIN + 28 ELSE Ta thấy sau mỗi lần từ điển được tách đôi thì một nửa thích hợp sẽ lại được tìm END;
kiếm bằng một chiến thuật như đã dùng trước đó. Có một trường hợp đặc biệt, khác với mọi trường hợp trước, sẽ đạt được sau nhiều
lần tách đôi, đó là trường hợp từ điển chỉ còn duy nhất một trang. Lúc đó việc tách đôi
ngừng lại và bài toán đã đủ nhỏ để ta có thể giải quyết trực tiếp bằng cách tìm từ mong
muốn trên trang đó, chẳng hạn bằng cách tìm tuần tự. Trường hợp đặc biệt này gọi là
trường hợp suy biến.
2.2.2. Chương trình con đệ quy Một chương trình con (hàm hoặc thủ tục) được gọi là đệ quy nếu trong quá trình thực hiện nó có phần phải gọi đến chính nó. If n = 0 then gt: = 1 (phần cơ sở)
Else gt: = n * gt(n - 1); (phần đệ quy) Có những ngôn ngữ lập trình cho phép chương trình con đệ quy nhưng cũng có
những ngôn ngữ khác lại không cho phép. Pascal cho phép dùng đệ quy với chương trình
con.
Cấu trúc chính của một chương trình con đệ quy gồm 2 phần: Phần cơ sở và phần đệ quy
Phần cơ sở: Bao gồm các trường hợp dừng mà có thể trực tiếp giải quyết được ngay
(trường hợp suy biến).
Phần đệ quy: Là phần trong thuật toán có yêu cầu gọi đệ quy, tức là yêu cầu thực hiện lại
thuật toán ở cấp độ thấp hơn (điều kiện kiểm soát đệ quy).
Ví dụ 1: Hàm tính giai thừa của n Function gt(n: byte): longint;
Begin
End;
Trong thuật toán tính giai thừa n ở trên, có một bước mà ta tính (n-1)! để từ đó tính
ra kết quả. Ðó là bước 2 trong trường hợp n > 0. Chính bước tính (n-1)! này trong thuật
toán làm cho thuật toán trở thành thuật toán đệ quy. Ta còn gọi bước này là bước thực
hiện đệ quy. Khi có lệnh gọi hàm, chẳng hạn x:=gt(5) thì máy sẽ ghi nhớ là gt(5):=5*gt(4)
và đi tính gt(4) Kế tiếp máy lại ghi nhớ gt(4):=4*gt(3) và đi tính gt(3)
Kế tiếp gt(3):=3*gt(2) và đi tính gt(2)
Kế tiếp gt(2):=2*gt(1) và đi tính gt(1)
Kế tiếp gt(1):=1*gt(0)
Theo định nghĩa của hàm gt thì gt(0)=1 máy sẽ quay ngược lại
Gt(1)=1*1=1
Gt(2)=2*gt(1)=2
Gt(3)=3*gt(2)=3*2
Gt(4)=4*gt(3)=4*3*2
Gt(5)=5*gt(4)=5*4*3*2=120 Đặc điểm của chương trình con đệ quy: 1. Trong CTC đệ quy có lời gọi đến chính nó
2. Mỗi lần có lời gọi thì kích thước của bài toán đã thu nhỏ hơn trước (phần hạ bậc)
3. Có một trường hợp đặc biệt: trường hợp suy biến: bài toán sẽ được giải quyết khác hẳn và gọi đệ qui cũng kết thúc. 29 Ví dụ 2: Tìm ước số chung lớn nhất của 2 số tự nhiên a, b
Người ta nhận thấy: a nếu b=0 USCLN(b, phần dư a/b ) nếu b<>0 Else Uscln:=uscln(b, a mod b); If b=0 then uscln:=a Begin
End; r:= a mod b;
If r=0 then uscln:=a Else Uscln:=uscln(b, r); Begin
End; USCLN(a, b)=
Do vậy hàm USCLN có thể viết đệ qui như sau:
Function USCLN(a, b:Integer): Integer;
Hay
Function USCLN(a, b:Integer): Integer;
Var r: integer;
Khi thiết kế thuật toán đệ quy thì ta cần phải thực hiện các yêu cầu sau:
Xác định được phần cơ sở của thuật toán đệ quy
Xác định được phần đệ quy Cần lưu ý rằng phần cơ sở luôn luôn phải có hay nói cách khác là phần đệ quy luôn
luôn phải nằm trong điều kiện kiểm soát dừng đệ quy, vì nếu không thì thuật toán sẽ bị
lặp vô hạn do việc gọi đệ quy luôn được thực hiện.
2.2.3. Một số bài toán đệ quy cơ bản
a. Dãy số Fibonaci Bài toán được đặt ra đầu tiên bởi nhà toán học Fibonaci đưa ra vào thế kỷ XIII trong tác phẩm Liberabaci, dựa trên sự sinh sản của họ nhà thỏ.
Nội dung của bài toán phát biểu như sau:
Một cặp thỏ mới sinh (một con đực và một con cái) được thả lên một hòn đảo. Giả
sử rằng một cặp thỏ chưa sinh sản được trước khi đầy hai tháng tuổi. Từ khi chúng đầy
hai tháng tuổi, mỗi tháng chúng sinh được một cặp thỏ con (một con đực và một con cái).
Hãy xây dựng công thức truy hồi tính số cặp thỏ có được sau n tháng, giả thiết các 30 con thỏ là trường thọ.
Ta có thể giải quyết bài toán này như sau:
Gọi fn là số cặp thỏ có được sau n tháng thì
Với n=1 (ở tháng thứ nhất) f1 = 1 (cặp ban đầu)
Với n=2 (ở tháng thứ hai) f2 = 1 (cặp ban đầu chưa sinh sản được)
Với n=3 ( ở tháng thứ 3) f3 = 2 (Cặp thỏ bố mẹ ban đầu và cặp thỏ con mới được sinh
ra)
f4 = 3 (cặp ban đầu sinh thêm, cặp con sinh ra ở n=3 chưa sinh được)
f5 = 5 (cặp con sinh ở n=3 bắt đầu sinh sản được)
f6 = 8 (cặp con sinh sản tiếp)…
Như vậy, nếu mỗi cặp thỏ ở tháng thứ (n - 1) đều sinh con thì fn = 2*(n - 1) nhưng
không phải như vậy, trong các cặp thỏ ở tháng thứ (n -1) chỉ có một cặp thỏ đã có ở tháng
thứ (n - 2) mới sinh con ở tháng thứ n thôi. Do đó fn = fn - 2 + fn - 1
Vì vậy ta có công thức đệ quy tính fn n=1, 2,... fn = 1 nếu n 2
fn – 2 + fn - 1 nếu n > 2 2 5 8 13 21…được gọi là dãy số Fibonaci If n <= 2 then Fibo: = 1
Else Fibo: = Fibo (n - 1) + Fibo (n - 2); Function Fibo (n: byte): Word;
Begin
End; Dãy số 1
3
1
Xây dựng hàm đệ quy tính fn
b. Bài toán “Tháp Hà Nội” Đây là trò chơi xếp hình rất phổ cập vào cuối thế kỷ 19, nội dung của bài toán được phát biểu như sau: Tương truyền rằng tại một ngôi tháp tại Hà Nội có một tấm đế bằng đồng trên đó
có ba cọc bằng kim cương. Từ lúc khai thiên lập địa, trên một trong ba cái cọc thượng đế
đã để 64 chiếc đĩa bằng vàng với đường kính giảm dần. Ngày đêm các nhà sư dịch chuyển
đĩa sang một chiếc cọc khác theo quy tắc: Mỗi lần chỉ được dịch chuyển một đĩa, mỗi đĩa
có thể dịch chuyển từ một cọc này sang cọc khác bất kỳ, nhưng không được để một chiếc
đĩa lên trên một đĩa khác có đường kính nhỏ hơn. Ngày tận thế sẽ đến khi tất cả các đĩa
được chuyển sang một chiếc cọc khác.
Giả sử Hn là số lần dịch chuyển cần thiết để giải bài toán Tháp Hà Nội có n đĩa. Hãy lập
hệ thức truy hồi đối với dãy Hn.
Ta có thể phát biểu bài toán tháp Hà Nội cổ dưới dạng sau: Có 3 cột A, B, C. Trên một cột, gọi là cột A có một chồng gồm n đĩa bằng gỗ hình
tròn to nhỏ khác nhau được xuyên lỗ ở giữa tựa như những đồng xu và đặt chòng lên nhau
để tạo thành một tòa tháp. Người chơi phải chuyển được tòa tháp sang cột BA theo các
quy tắc sau: a. Người chơi được sử dụng cột còn lại để đặt tạm các tầng tháp
b. Mỗi lần chỉ được chuyển 1 tầng tháp từ một cột sang một trong hai cột còn lại. c. Không bao giờ được đặt tầng tháp lớn lên trên tầng tháp nhỏ. Hãy tìm cách giải bài toán trên với số lần chuyển ít nhất. Hoặc bài toán: Có 3 cột A, B, C và n đĩa kích thước khác nhau ở cột A, đĩa to ở dưới đĩa
bé ở trên. Hãy chuyển các đĩa từ cột A sang cột B sao cho: và n đĩa kích thước khác nhau ở cột A, đĩa to ở dưới đĩa bé ở trên. Hãy chuyển
các đĩa từ cột A sang cột B sao cho:
Mỗi lần chỉ chuyển được một đĩa.
Một đĩa có thể chuyển sang một cột bất kỳ nhưng khi chuyển phải tuân theo quy tắc đĩa to ở dưới, đĩa bé ở trên. Ta có thể phân tích theo kiểu đệ quy như sau:
Để chuyển n đĩa từ cột A sang cột B lấy C làm trung gian người ta tìm cách: Chuyển (n - 1) đĩa từ cột A sang cột C lấy B làm trung gian
Chuyển chiếc to nhất (còn lại) từ cột A sang cột B
Chuyển (n - 1) đĩa từ cột C sang cột B 31 Ta xây dựng thủ tục chuyển theo thuật toán đệ quy như sau Procedure chuyen (n, A, B, C: byte);
Begin Begin chuyen (n - 1, A, C, B);
chuyen (1, A, B, C);
chuyen (n - 1, C, B, A); If n = 1 then writeln(A, ‘’,B)
Else
End; End;
2.3. Thuật toán quay lui
2.3.1. Bài toán liệt kê
Nếu như trong bài toán đếm, ta chỉ cần đếm số cấu hình tổ hợp là bao nhiêu thì
trong nhiều trường hợp, ta còn phải chỉ rõ những cấu hình tổ hợp đó là những cấu hình.
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ê. Bài toán: Cho một tập A và một tính chất T, hãy xây dựng tất cả các cấu hình 1 0 1 0 1 1 0 0 1 0 1 0 1 000 001 010 011 100 101 110 111
Với bài toán này ta phải xây dựng thuật toán để xác định tất cả các cấu hình đảm (a1, a2,..,an) xuất phát từ A sao cho mỗi cấu hình đều thoả mãn tính chất T.
Ví dụ: A = {0, 1}, T là 1 dãy có n phần tử. Xây dựng tất cả các cấu hình xuất phát từ A
sao cho mỗi cấu hình đều thỏa mãn tính chất T chính là liệt kê tất cả các xâu nhị phân có
độ dài n.
Với n = 3 thì 23 = 8 dãy bảo 2 nguyên tắc sau: 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 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ập hợp”. Để
xây dựng chừng một tỷ cấu hình và giả thiết rằng mỗi thao tác xây dựng mất khoảng một
giây, ta phải bỏ ra khoả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 phần
này, chúng ta sẽ trình bày phương pháp liệt kê thường được sử dụng nhất, đó là thuật toán
quay lui.
2.3.2. Thuật toán quay lui Tư tưởng của thuật toán quay lui xuất phát từ bài toán có tên gọi “Hoàng tử cứu công chúa“. Nội dung của bài toán như sau: 32 Công chúa bị một con quỷ nhốt trong một cái hang sâu có rất nhiều đường đi (mỗi
ngã rẽ đặc trưng bởi một đỉnh nào đó). Để cứu được công chúa thì bắt buộc hoàng tử phải
tìm một cách nào đó để có thể đi qua tất cả các đường đi trong hang. Rõ ràng yêu cầu đề
ra là khi đã đi rồi thì không được đi lại (không lặp) và hơn nữa phải không được bỏ sót một
đường đi nào (vét cạn hết tất cả các đường đi). Để làm được điều đó hoàng tử chỉ có cách là chuẩn bị một cuộn dây dài và buộc một đầu dây vào cửa hang sau đó bắt đầu đi vào hang theo nguyên tắc sau: Mỗi khi đi đến đâu thì đánh dấu các đường đã đi (tránh lặp lại)
Nếu còn đi được thì cứ đi tiếp (để không bỏ sót)
Nếu không còn đường đi nữa thì quay về mức trên vừa đi để tìm đường khác đi tiếp (quay lui) Vậy tư tưởng chính của thuật toán quay lui là việc xây dựng dần các thành phần của cấu hình bằng cách thử tất cả các khả năng sao cho thoả mãn : Không được lặp lại cấu hình nào
Không bỏ sót cấu hình nào Nội dung Thuật toán
Giả sử cấu hình cần xây dựng có dạng x = (x1, x2,…,xn) trong đó xi A (i =1, 2,..,n)
Mỗi cấu hình x đều thoả mãn tính chất T, người ta tiến hành quy nạp như sau:
- Giả sử đã xác định được (i - 1) thành phần của cấu hình (x1, x2,…,xi - 1 ) lời giải bộ
phận cấp (i - 1)
- Tiến hành xây dựng thành phần thứ i của cấu hình xi bằng cách duyệt tất cả các khả năng
đề cử của xi Đánh số các khả năng đề cử cho xi từ 1 đến ni
Với mỗi khả năng j (j = 1,2,.., ni ) xét 2 khả năng Khả năng 1: Nếu chấp nhận j thì ta sẽ đi xác định xi theo j sau đó kiểm tra nếu i = n thì ghi nhận
thêm một cấu hình mới, nếu i < n thì đi xây dựng tiếp thành phần thứ (i + 1)
Khả năng 2: Nếu không có khả năng nào của j được chấp nhận thì ta quay lại bước trước để xác
định lại xi - 1 Điều quan trọng trong thuật toán quay lui là ta phải ghi nhớ tất cả các khả năng đã thử
để tránh trùng lặp và bước xác định thành phần thứ i sẽ được xây dựng bằng thủ tục đệ
quy như sau: Procedure Try(i: integer); {Xây dựng thành phần thứ i của cấu hình}
Var j: integer; {j là khả năng được đề cử cho xi }
Begin
For j Sau khi xây dựng thủ tục đệ quy, chương trình chính có dạng:
BEGIN
Khoitao; {khởi tạo các giá trị ban đầu cho các biến sử dụng trong chương
trình chính}
Try (1);
Readln; END. 33 Trong thủ tục quay lui điều quan trọng nhất là ta phải xác định được tập đề cử xi và
xác định điều kiện chấp nhận j. Thông thường giá trị này, ngoài việc phụ thuộc j , còn phụ
thuộc vào việc đã chọn các khả năng tại i-1 bước trước. Trong những trường hợp như vậy, cần phải ghi nhớ trạng thái mới sau khi xác định xi theo j và trả lại trạng thái cũ sau lời
gọi của Try (i+1). Việc này được thực hiện thông qua biến trạng thái (mảng lôgic).
Ví dụ 1: Hãy liệt kê tất cả các dãy nhị phân độ dài n Giả sử dãy nhị phân có độ dài n là một véc tơ nhị phân gồm n thành phần (a1,
a2,..,an) trong đó ai {0, 1}. Cần xây dựng thành phần thứ i của cấu hình tức là xây dựng
ai (ai {0, 1}) ai có tập giá trị đề cử là {0, 1}
ai có điều kiện chấp nhận: Không có điều kiện chấp nhận Thủ tục quay lui xây dựng thành phần ai
Procedure Try(i: integer); Var j: integer;
Begin For j: = 0 to 1 do Begin a[i]: = j;
If i = n then ghi nhận else Try (i+1);
End; End;
Trong thủ tục trên cần xây dựng thêm các thủ tục: ghi nhận, khởi tạo. Chương trình liệt kê dãy nhị phân
Program Daynhiphan;
Uses crt;
var n,d:integer;
a:array[1..20] of integer;
procedure KHOITAO;
begin
write('nhap do dai day nhi phan n= '); readln(n); 34 d:=0;
end;
procedure GHINHAN;
var i:integer;
begin
d:=d+1; write('day nhi phan thu',d:3,': ');
for i:=1 to n do write(a[i]:2);writeln;
end;
procedure TRY(i:integer);
var j:integer;
begin
for j:=0 to 1 do
begin
a[i]:=j;
if i=n then GHINHAN else Try(i+1);
end;
end;
BEGIN khoitao;
Try(1); readln; END.
Ví dụ 2: Liệt kê tất cả các hoán vị của tập n số tự nhiên đầu tiên {1, 2, ..., n} Gọi hoán vị của tập A = {1, 2, ..., n} là một bộ gồm n thành phần (a1, a2,..,an) trong
đó ai A, i = 1,2,..,n và ai, aj đôi một khác nhau. Ta đi xây dựng thành phần thứ i của cấu
hình ai ai có tập giá trị đề cử là 1, 2,…,n
ai có điều kiện chấp nhận: Giá trị chưa được dùng và để kiểm soát người ta of Boolean; dùng mảng logic b: array[1..n]
- Nếu b[j] = True thì j chưa dùng
- Nếu b[j] = False thì j đã được dùng Với mỗi giá trị đề cử j nếu b[j] = True thì j được chấp nhận và ta đi xác định ai theo j và sau đó đặt b[j] = False (để xác định rằng j đã được dùng rồi)
Thủ tục quay lui xây dựng thành phần thứ i của cấu hình Procedure Try(i: integer); Var j: integer;
Begin For j: = 1 to n do If b[j] then {chấp nhận j} Begin a[i]: = j; {xác định a[i] theo j}
b[j]: = False; {ghi nhận trạng thái mới}
If i = n then ghi nhận b[j]: = True; {trả lại trạng thái cũ} Else Try (i+1); {xây dựng thành phần thứ i + 1}
End; End; 35 Chương trình liệt kê các hoán vị
program hoanvi;
uses crt;
var
n,d:integer;
a:array[1..20] of integer;
b:array[1..20] of boolean;
procedure KHOITAO;
var i:integer;
begin
write('n=');readln(n);
for i:=1 to n do b[i]:=true;
d:=0;
end;
procedure GHINHAN;
var i:integer;
begin
d:=d+1; write('Hoan vi thu',d:3,':');
for i:=1 to n do write(a[i]:3);
writeln;
end;
procedure Try(i:integer);
var j:integer;
begin
for j:=1 to n do
if b[j]= true then {chap nhan j}
begin
a[i]:=j; {xac dinh a[i] theo j}
b[j]:=false; {ghi nhan trang thai moi}
if i=n then GHINHAN else Try(i+1);
b[j]:=true; {tra lai trang thai cu}
end;
end;
BEGIN
khoitao;Try(1);
readln; END.
2.4. Các nguyên lý đếm cơ bản
2.4.1. Phép đếm Cho A là một tập hợp khác rỗng, để xác định số phần tử của tập hợp A ta thường
thực hiện việc đếm bằng cách lần lượt gán cho các phần tử của A các số tự nhiên kế tiếp
nhau, và số tự nhiên đầu tiên (được dùng để gán cho phần tử đầu tiên được xem xét) là 1.
Nếu quá trình này kết thúc với số tự nhiên n (được gán cho phần tử cuối cùng) thì ta nói A
là một tập hợp hữu hạn và có n phần tử.
2.4.2. Nguyên lý đếm cộng Cơ sở của nguyên lý cộng là mối liên hệ giữa số phần tử của một tập hợp với số
phần tử của các tập hợp con tạo thành phân hoạch của tập hợp đã cho, được phát biểu
trong mệnh đề sau đây: Mệnh đề: Cho A và B là 2 tập hợp hữu hạn rời nhau, nghĩa là A B = . Khi ấy ta có: | A B | = | A | + | B |
Một cách tổng quát: Nếu A1, A2, ..., An là các tập hợp hữu hạn rời nhau, nghĩa là
phần giao của hai tập hợp bất kỳ trong n tập hợp là rỗng, thì số phần tử của phần hội của
các tập hợp trên bằng tổng của các số lượng phần tử trong mỗi tập hợp: | A1 A2 . . . An | = | A1 | + | A2 | + . . . + | An | Nguyên lý cộng : cách chọn đối tượng 36 Nếu có m1 cách chọn đối tượng a1, m2 cách chọn đối tượng a2,...., mn cách chọn đối
tượng an và nếu cách chọn đối tương ai không trùng bất kỳ cách chọn đối tượng aj nào
(ij ,i,j=1,..,n) thì sẽ có tất cả
Ví dụ 1: Chúng ta cần chọn một sinh viên CNTT năm thứ 1 hay năm thứ 2 đi dự một hội
thảo. Hỏi có bao nhiêu cách chọn lựa một sinh viên như thế biết rằng có 100 sinh viên
CNTT năm thứ 1 và 200 sinh viên CNTT năm thứ hai ?
Giải : Ta có thể thực hiện một trong 2 việc chọn lựa khác nhau: chọn một sinh viên
CNTT năm 1, hoặc chọn một sinh viên CNTT năm 2. Để thực hiện công việc thứ nhất ta
có 100 cách, và để thực hiện công việc thứ 2 ta có 200 cách. Vậy để chọn một sinh viên
tin theo yêu cầu ta có 100+200 = 300 cách. Chúng ta có thể mở rộng nguyên lý cộng cho trường hợp nhiều sự chọn lựa hơn
như sau: Giả sử ta phải thực hiện một công việc bằng cách chọn một trong m sự chọn lựa
các biện pháp khác nhau T1, T2, ..., Tm. Để thực hiện Ti, 1 i m, ta có ni cách. Vậy ta
có số cách thực hiện công việc trên là n1 + n2 + ... + nm. Nguyên lý cộng dạng tổng quát
này có thể được chứng minh bằng qui nạp.
Ví dụ 2: Trong một đợt phổ biến đề tài tốt nghiệp. Ban chủ nhiệm Khoa công bố 3 danh
sách đề tài bao gồm 23 đề tài về chủ đề “Xây dựng hệ thông tin quản lý”, 15 đề tài về chủ
đề “Xây dựng chương trình thi trắc nghiệm”, 10 đề tài về chủ đề “Trí tuệ nhân tạo”. Hỏi
một sinh viên có bao nhiêu khả năng lựa chọn một đề tài trong 3 danh sách đề tài trên?
Giải: Sinh viên có thể chọn một đề tài trong danh sách thứ thứ nhất theo 23 cách, trong
danh sách thứ hai theo 15 cách, và trong danh sách thứ ba theo 19 cách. Do đó số cách
chọn đề tài là 23+15+19 = 57.
Ví dụ 3: Xác định giá trị của k sau khi đoạn chương trình sau đây được thực hiện xong k := 0
for i1 := 1 to n1 do k := k + 1;
for i2 := 1 to n2 do k := k + 1;
...
for im := 1 to nm do k := k + 1; Lời giải. Giá trị của k ban đầu là 0. Sau đó là m vòng lặp khác nhau. Mỗi thao tác lặp
trong một vòng lặp là cộng thêm 1 vào k. Vòng lặp thứ i có ni thao tác, và tất cả m vòng
lặp không thể thực hiện 2 vòng lặp nào một cách đồng thời. Do đó số thao tác để thực
hiện xong đoạn chương trình trên là n1 + n2 + ... + nm. Đây cũng chính là giá trị cuối cùng
của k.
2.4.3. Nguyên lý nhân cách chọn đối tượng ... Am ) = N(A1) N(A2) ... N(Am) A2 Nếu có m1 cách chọn đối tượng a1, và sau đó với mỗi cách chọn a1 như thế có m2
cách chọn đối tượng a2 , sau đó với mỗi cách chọn a1 và a2 như thế có m3 cách chọn đối
tượng a3,...., cuối cùng, với mỗi cách chọn a1, a2,...,an-1 như vậy, có mn cách chọn đối
tượng an thì sẽ có tất cả
Ví dụ 1. 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.
Giải. Thủ tục chọn cổng gồm hai việc, việc chọn máy và sau đó chọn cổng của chiếc máy
này. Vì có 32 cách chọn máy và 24 cách chọn cổng bất kể máy nào đã được chọn. Do đó
theo qui tắc nhân có 32*24 =768 cổng
Quy tắc nhân 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 hợp hữu hạn, khi đó số phần tử của tích Đề các của các
tập này bằng tích của số các phần tử của mọi tập thành phần
N( A1
Ví dụ 2. Có nhiều nhất 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ố.
Giải. Có tất cả 26 cách chọn cho mỗi một trong ba chữ cái và 10 cách chọn cho mỗi chữ
số. Do đó đó có nhiều nhất là 26.26.26.10.10.10.= 17 576 000 biển đăng ký xe.
Ví dụ 3. Giá trị của biến k bằng bao nhiêu sau khi chương trình sau được thực hiện? 37 k:= 0;
for i1 :=1 to n1
for i2:=1 to n2
...
for im :=1 to nm Do k:=k+1; Giải. Đầu tiên giá trị của k được gán bằng 0. Có m vòng lặp for lồng nhau. Sau mỗi lần
lặp của vòng for, giá trị của k tăng lên 1. Vòng for thứ nhất lặp n1 lần, vòng for thứ hai lặp
n2 lần, ... vòng for thứ m lặp nm lần. Vậy , theo nguyên lý nhân, kết thuc m vòng lặp for
lồng nhau, giá trị cuối cùng của k là k = n1 *n2 ...* nm
2.4.4. Nguyên lý lồng chim bồ câu (nguyên lý Dirichlet)
Peter Gustav Lejeune Dirichlet là nhà toán học người Đức sống ở thế kỷ 19
(1805-1859), ông phát biểu một nguyên tắc về phân chia phần tử vào các lớp, nguyên tắc
này được gọi là là nguyên lý Dirichlet. Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì ít nhất trong một ngăn sẽ có nhiều hơn một con chim.
Định lý 1: (Nguyên lý lồng chim bồ câu) Nếu có k+1 hoặc nhiều hơn đồ vật được đặt vào
trong k hộp, thì có ít nhất một hộp chứa hai hoặc nhiều hơn hai đồ vật.
Chứng minh: Giả sử không có hộp nào trong k hộp chứa nhiều hơn một đồ vật. Khi đó
tổng số vât được chứa trong các hộp nhiều nhất là bằng k. Điều này trái với giả thiết là có
ít nhất k+1 vật. Nguyên lý lồng chim bồ câu cũng thường được gọi là nguyên lý Dirichlet mang tên vật = 1 vật. Khi nhà toán học người Đức ở thế kỷ 19.
Ví dụ 1. Trong bất kỳ một nhóm 367 người thể nào cũng có ít nhất hai người trùng ngày
sinh ( vì một năm có nhiều nhất 366 ngày)
Định lý 2: (Nguyên lý Dirichlet tổng quát) Nếu có N đồ vật được đặt vào trong k hộp, sẽ
tồn tại một hộp chứa ít nhất
Chứng minh: Giả sử không có hộp nào trong k hộp chứa nhiều hơn
đó tổng số vật được chứa trong các hộp nhiều nhất là: k( -1) < k(((N/k)+1)-1) = N (*) < (N/k) + 1. Bất đẳng thức (*) trái với giả thiết. 38 trong đó ta đã dùng bất đẳng thức
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ọc 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ì có 101 kết quả điểm thi
khác nhau.
Ví dụ 3: Trong bất kỳ một nhóm gồm 21 chữ số của hệ thập phân đều có ít nhất 3 chữ số
trùng nhau. Thật vậy: Vì nếu chứa 21 vật vào 10 hộp thì ít nhất có một hộp chứa nhiều
hơn 2 vật
Ví dụ 4: Trong 48 sinh viên của lớp CĐ có ít nhất =4 người cùng tháng sinh =18 phòng học 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 C) = N1 – N2 + N3 B là tập các sinh viên giỏi cả Toán và Tin. Vì mỗi sinh viên trong lớp hoặc giỏi C) = N(A) + N(B) + N(C) - N(A B) - N(A C) - N(B C) + C) =500 là số phần tử cần đếm, N là số phần tử của X, ta có:
= N - N(A1 A2 ... Am) = N - N1 + N2 -... +(-1)mNm ( nguyên lý bù 39 Ví dụ 5: Trong một trường đại học có 38 ca học phân cho các lớp. Nếu có 677 lớp khác
nhau thì cần phải có bao nhiêu phòng học?
Giải: Theo nguyên lý Dirichlet sẽ có
2.4.5. Nguyên lý bù trừ
lý cộng.
Nếu không có giả thiết về sự rời nhau giữa hai tập A, B thì
N(A B) = N(A) + N(B) – N(A B)
Mở rộng: Cho A1 , A2 , ..., Am là các tập hữu hạn khi đó
... Am) = N1 – N2 +... +(-1)m-1Nm
N(A1 A2
trong đó Nk là tổng của tất cả các phần tử của tất cả các giao của k tập lấy từ m tập đã cho
Ví dụ 1 : N(A B
Trong đó: N1 = N(A) + N(B) + N(C)
N2 = N(A B) + N(A C) + N(B C)
N3 = N(A B C )
Ví dụ 2: Trong một lớp cao đẳng có 30 sinh viên giỏi toán, 25 sinh viên giỏi Tin, 7 sinh
viên giỏi cả toán và tin. Hỏi trong lớp có bao nhiêu sinh viên, nếu mỗi sinh viên hoặc giỏi
toán hoặc giỏi tin hoặc giỏi cả hai môn?
Giải: Gọi A là tập các sinh viên giỏi Toán, B là tập các sinh viên giỏi Tin, khi đó
A
Toán hoặc giỏi Tin Hoặc giỏi cả hai môn nên số sinh viên trong lớp là N(A B)
N(A B) = N(A) + N(B) – N(A B) = 30 + 25 – 7 = 48
Ví dụ 3: Có bao nhiêu xâu nhị phân độ dài là 8 hoặc là bắt đầu bởi 00 hoặc là kết thúc bởi
11?
Giải: Dễ thấy số xâu nhị phân độ dài 8 bắt đầu bởi 00 là 26 = 64 và số xâu nhị phân độ dài
8 kết thúc bởi 11 là 26 = 64. Ngoài ra số xâu nhị phân độ dài 8 bắt đầu bởi 00 và kết thúc
bởi 11 là 24
= 16. Vậy số xâu nhị phân hoặc bắt đầu bởi 00 hoặc kết thúc bởi 11 là: 64 +
64 – 16 = 112.
Ví dụ 4: Biết rằng có 100 sinh viên học tiếng Anh, 70 học sinh học tiếng Nga, và 50 học
sinh học tiếng Pháp, 40 học sinh học cả tiếng Anh và tiếng Nga, 20 học sinh học cả tiếng
Anh và tiếng Pháp, 12 học sinh hoạc cả tiếng Pháp và tiếng Nga. Néu tất cả 500 sinh viên
đều theo học ít nhất một ngoại ngữ, thì có bao nhiêu sinh viên học cả ba thứ tiếng?
Giải: Gọi A là tập các sinh viên học tiếng Anh, B là tập các sinh viên học tiếng Nga, C là
tập các sinh viên học tiếng Pháp. Khi đó số sinh viên theo học cả ba thứ tiếng sẽ là
N(A B C)
Theo nguyên lý bù trừ ta có
N(A B
N(A B C )
mà N(A) = 100 , N(B) = 70 , N(C) = 50 , N(A B) =40 , N(A C) =20
N(B C) = 12 , N(A B
Suy ra N(A B C )= 500 – 100 – 70 -50 +40 + 20 + 12 = 352
Lưu ý: Nếu 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 thỏa mãn bất cứ một tính chất Ak nào cả?
Ký hiệu
trừ)
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 2.5. Hoán vị & tổ hợp
2.5.1. Hoán vị
Định nghĩa: Cho tập hợp A gồm n phần tử. Một cách sắp xếp n phần tử này thành một
dãy (không kín gồm n phần tử đó) gọi là một hoán vị của tập hợp A.
Kí hiệu: Pn là số các hoán vị của n phần tử.
Công thức tính: Pn = n! (1)
Chứng minh: (Bằng phương pháp qui nạp) 1. Với n=1, ta có A={a} thì có một cách sắp xếp các phần tử của A thành dãy. Hay công thức (1) đúng với n=1 Mặt khác, ta có 1!=1 Vậy P1=1! 2. Giả sử công thức (1) đúng với n=k ≥1 số hoán vị của tập hợp A gồm k phần tử là Pk = k!, ta cần chứng minh (1) cũng đúng với n= k+1.
Thực vậy, xét tập hợp A gồm k+1 phần tử, tức là A={a1, a2, ...,ak, ak+1}
Vì tập A có k+1 phần tử nên có k+1 cách chọn phần tử đầu tiên của dãy, ứng với mỗi
cách chọn phần tử đầu tiên này còn lại k phần tử theo giả thiết qui nạp, có k! cách
sắp xếp k phần tử này.
Do đó có tất cả (k+1)*k!=(k+1)! Cách sắp xếp (k+1) phần tử của tập hợp A, điều này chứng tỏ (1) đúng với n=k+1. Vậy ta có Pn= n! là số chỉnh hợp chập k của tập A gồm n phần tử. Ví dụ 1: Một bàn có 4 học sinh. Hỏi có bao nhiêu cách sắp xếp chỗ ngồi cho 4 học sinh
đó.
Giải: Mỗi phương án lựa chọn để xếp chỗ ngồi là hoán vị từ 4 học sinh. Vậy có 4!=16
cách.
Ví dụ 2: Có một người bán hàng phải đi bán hàng tại 8 thành phố. Anh ta bắt đầu cuộc
hành trình tại một thành phố nào đó, nhưng có thể đến bảy thành phố kia theo bất kỳ thứ
tự nào mà anh ta muốn . Hỏi anh ta có thể đi qua tất cả các thành phố này theo bao nhiêu
lộ trình khác nhau?
Giải: Số lộ trình có thể giữa các thành phố bằng số hoán vị của bảy phần tử, vì thành phố
đầu tiên đã được xác định, nhưng bảy thành phố còn lại có thể có thứ tự tuỳ ý. Do đó có
7! = 5040 cách để người bán hàng chọn hành trình của mình.
Ví dụ 3: Cho tập A={1, 3, 5,7}. Có bao nhiêu số gồm 4 chữ số khác nhau được thành lập
từ A.
Giải: Số gồm 4 chữ số khác nhau được thành lập từ A chính là một hoán vị của A, do đó
số các số theo yêu cầu là P4=4!=1.2.3.4=24 (số theo yêu cầu)
2.5.2. Chỉnh hợp không lặp
Định nghĩa: Cho tập hợp A gồm n phần tử, giả sử k là một số tự nhiên thõa mãn: 1 k
n. Mỗi cách sắp xếp k phần tử của tập hợp A thành một dãy hở gọi là mộ chỉnh hợp
không lặp chập k của n phần tử.
Kí hiệu:
Định lý 1: Số chỉnh hợp chập k của tập có n phần tử là = n(n - 1)(n - 2)...(n – k + 1) = Chứng minh: Thật vậy: Phần tử đầu tiên của chỉnh hợp có thể chọn bằng n cách, vì tập có n phần tử Phần tử thứ hai của chỉnh hợp được chọn từ (n – 1 ) phần tử còn lại của tập, tức là có (n – 1) cách chọn phần tử này
Tương tự ta có (n – 2) cách chọn phần tử thứ ba, và cứ như thế ta có (n –k +1) cách chọn
phần tử thứ k. Việc lựa chọ các phần tử là phụ thuộc nhau nên theo quy tắc nhân ta được:
40 n= n! = n*(n – 1)*(n – 2)*... *(n – k + 1) = Đặc biệt khi k = n thì ta có Ak
Ví dụ 1: Có bao nhiêu cách chọn 3 lớp khác nhau trong 10 lớp để trao giải nhất, nhì, ba
trong cuộc thi phòng chống ma tuý (Nếu lớp nào cũng có khả năng đoạt giải)
Giải: Mỗi một cách chọn ra 3 lớp đó chính là chỉnh hợp chập 3 của 10 phần tử. = =10*9*8 = 720 (cách) Ví dụ 2: Cho tập A= {0, 1, 2, 3, 4, 5}. Có bao nhiêu số chẵn, mỗi số gồm 5 chữ số khác
nhau được thành lập từ A.
Giải: Ta xét các khả năng có thể xảy ra cho dạng số cần tìm: 1. Dạng 5=1.2.3.4.5=120 (số) Chọn a, b, c, d{1, 2, 3, 4, 5} có m1=A4 4=4.3.2=24 (Cách) 2. Dạng Chọn a {1, 3, 4, 5} có m1=4 (Cách)
Chọn b, c, d {0, 1, 3, 4, 5}\{a} có m2= A3
Với trường hợp này ta có tất cả m1x m2=4.24=96 (số) 4=4.3.2=24 (Cách) 3. Dạng Chọn a {1, 3, 2, 5} có m1=4 (Cách)
Chọn b, c, d {0, 1, 2, 3, 5}\{a} có m2= A3
Với trường hợp này ta có tất cả m1x m2=4.24=96 (số) = nk Các cách chọn của 3 trường hợp trên có quan hệ độc lập, vậy số các số theo yêu cầu là
120+96+96=312 (số)
2.5.3. Chỉnh hợp lặp
Định nghĩa :Chỉnh hợp lặp chập k của n phần tử là một cách sắp xếp có thứ tự k phần tử
của n phần tử, mỗi phần tử có thể lấy lặp lại.
Ký hiệu : Số chỉnh hợp lặp chập k của n phần tử là
Định lý 1: Số các chỉnh hợp lặp chập k từ tập n phần tử bằng nk:
Chứng minh :
Phần tử đầu tiên của chỉnh hợp lặp có thể chọn bằng n cách, vì tập có n phần tử Phần tử thứ hai của chỉnh hợp được chọn từ n phần tử của tập vì phần tử có thể được lấy lặp lại, tức là có n cách chọn phần tử này Tương tự ta có n cách chọn phần tử thứ ba, và cứ như thế ta có n cách chọn phần tử 41 thứ k. Theo quy tắc nhân ta được:
= nk
Ví dụ 1: Tính số dãy nhị phân có độ dài là 8.
Giải : Mỗi dãy nhị phân độ dài 8 là một bộ gồm 8 thành phần, trong đó mỗi thành phần
chỉ nhận một trong hai giá trị 1 hoặc 0. Từ đó suy ra số các dãy nhị phân có độ dài 8 là 28
= 256.
Như vậy số dãy nhị phân có độ dài n sẽ là 2n
Ví dụ 2: Cho tập A=1,2,3. Hãy đếm các số có 2 chữ số được xây dựng từ tập hợp A.
Giải: Số lượng các số có 2 chữ số được xây dựng từ tập A chính là chỉnh hợp lặp chập 2
của tập gồm 3 phần tử và bằng 32=9
(1,2) , (2,1) , (1,3) , (3,1), (2,3), (3,2),(1,1), (2, 2), (3, 3)
2.5.4. Hoán vị có lặp Định nghĩa: Cho s phần tử khác nhau a1, a2,..., as Một chỉnh hợp có lặp chập m của s phần
tử đã cho, trong đó có k1 phần tử a1, k2 phần tử a2 ,..., ks phần tử as được gọi là một hoán
vị có lặp cấp m (m=k1 + k2 +...+ ks) và có kiểu (k1, k2,..., ks) của s phần tử.
Kí hiệu: Cm(k1, k2,..., ks) là số các hoán vị có lặp cấp m kiểu (k1, k2,..., ks) Khi đó ta có Cm(k1, k2,..., ks) = (phần chứng minh coi như bài tập dành cho các bạn sinh viên)
Ví dụ: Có bao nhiêu cách phân chia 10 người thành 3 nhóm sao cho số người trong mỗi
nhóm theo thứ tự là: 2, 3, 5. Mỗi cách phân nhóm chính là một hoán vị có lặp cấp 10 kiểu (2,3,5) do đó số cách phân nhóm theo yêu cầu là: C10(2,3,5)= 2.5.5. Tổ hợp không lặp
Định nghĩa: Cho tập A gồm n phần tử, k là một số tự nhiên thõa mãn 1 kn. Mỗi tập
hợp con gồm k phần tử của tập hợp A được gọi là một tổ hợp chập k của tập hợp A gồm n
phần tử. ( Ngoài ra có thể định nghĩa theo cách khác: Tỏ hợp chập k của n phần tử là
cách chọn không phân biệt thứ tự k phần tử lấy từ tập n phần tử đã cho, mỗi phần tử
không được lấy lặp lại.
Ký hiệu : là Số tổ hợp chập k của n phần tử n và Định lý : = n, k nguyên dương , 0 k n n. n cách chọn k phần tử, với mỗi cách chọn này lại có k! cách sắp
n .k! cách sắp xếp k phần tử của Chứng minh: Ta sẽ tính số tổ hợp thông qua việc thiết lập công thức liên hệ giữa Ck
Ak Ta có tất cả Ck n , xếp chúng thành một dãy có thứ tự. Như vậy có tất cả Ck
một tập hợp gồm n phần tử thành một dãy. Theo cách tính số chỉnh hợp chập k của n phần tử thì số cách sắp xếp này là Ak n.k!= Ak n = do đó Ck Suy ra : n=1, Cn n=1 Hệ quả: Cho n , k là các số nguyên không âm sao cho k n. Khi đó
Nhận xét: n-1 + Ck-1 n=Ck n-1 với 0 k n Nếu k=0, k=n thì C0
Ck Ví dụ 1: Có bao nhiêu cách tuyển 5 trong số 10 cầu thủ cầu lông để đi thi đấu.
Lời giải: Số cách tổ hợp chập 5 của 10 phần tuyển chính là số tử: Ví dụ 2: Có bao nhiêu cách lập một đề thi gồm 3 câu hỏi từ một tập 15 câu hỏi Giải: Đó chính là số tổ hợp chập 3 của 15 phần tử: 42 2.5.6. Tổ hợp có lặp Định nghĩa: Cho tập hợp A gồm n phần tử khác nhau, A={a1, a2, ..., an}, m là một số tự
nhiên bất kỳ. Một tổ hợp có lặp chập m của n phần tử đã cho là một tập hợp chứa m phần
tử, trong đó mỗi phần tử là một trong n phần tử đã cho.
Cách tính số tổ hợp có lặp
Số các tổ hợp có lặp chập m của n phần tử, kí hiệu là
(phần chứng minh coi như bài tập dành cho các bạn sinh viên)
Ví dụ 1: Cho A={a, b} với ab . Các tổ hợp chập 3 của A là: (a,a,a); (a,a,b); (a,b,b);
(b,b,b) Số các tổ hợp có lặp chập 3 của A gồm 2 phần tử là ... n im-1 im i1 n+m-1 Ví dụ 2: Cho biết giá trị của k sau khi đoạn chưong trình sau được thực hiện
k:=0;
For i1 := 1 to n do
For i2 := 1 to i1 do
....
For im := 1 to im-1 do k:=k+1;
Giải: Ta thấy giá trị khởi tạo của k=0 và 1 được cộng dồn vào k mỗi lần vòng lặp lồng
nhau được duyệt qua ứng với tập các số nguyên i1 , i2 ,... , im , trong đó
1
Số bộ các số nguyên như thế là số cách chọn có lặp m số nguyên từ tập 1, 2, ..., n
Thật vậy mỗi lần một tập các số nguyên như thế được chọn , chúng ta sắp xếp chúng theo
thứ tự không giảm. Khi đó sẽ xác định duy nhất một bộ im, im-1 , ..., i1 . Ngược lại mọi bộ như thế sẽ ứng với một tập không có thứ tự m phần tử hay một tổ (Hằng đẳng thức Pascal) hợp lặp chập m từ n phần tử. Suy ra k = Cm
2.5. 7 Hệ số nhị thức
Định lý 1: Cho n, k là các số nguyên dương, với n k, khi đó:
Chứng minh: Giả sử T là một tập có n+1 phần tử, gọi a là một phần tử bất kỳ của T; S=T-
{a}. Khi đó Ck
n+1 là số các tập con có k phần tử của tập T, hoặc là chứa phần tử a cùng
với k-1 phần tử của S, hoặc là chứa k phần tử của S và không chứa a. Vì có Ck-1
n tập con
chứa k-1 phần tử của S và C k
n tập con chứa k phần tử của tập S, do vậy . Khai triển ta có hằng đẳng thức Pascal hay tam giác Pascal: 43 1 1 1 2 1 1 3 3 1 1 6 4 4 1 1 10 10 5 1 5 1 Hằng đẳng thức Pascal chỉ ra rằng khi cộng 2 hệ số nhị thức liền kề trong tam giác sẽ nhận được hệ số nhị thức của hàng tiếp theo ở giữa. Định lý 2: Cho n là số nguyên dương, khi đó Chứng minh: Một tập hợp n phần tử có tất cả 2n tập con khác nhau (1) Mặt khác ta thấy, mỗi tập con có hoặc không có phần tử nào hoặc 1 phần tử, 2 phần tử,..., hoặc n phần tử. Số tập con có 0 phần tử là Số tập con có 1 phần tử là Số tập con có 2 phần tử là .. Số tập con có n phần tử là Do đó ta có tất cả tập con của tập n phần tử. Kết hợp với (1) ta có Định lý 3: Cho x, y là 2 biến và n là một số nguyên dương, khi đó: (x + y)n = (n 2) n cách chọn như vậy, khi đó y được chọn từ k tổng
n=Ck n Chứng minh: Ta chứng minh định lý này bằng suy luận tổ hợp. Các số hạng trong
khai triển của (x+y)n sẽ có dạng xn-kyk với k=0,1,2,...,n .Để nhận được số hạng dạng xn-kyk
ta chọn x từ n-k tổng (x+y) và có Cn-k
còn lại. Do đó hệ số của xn-kyk là Cn-k 44 Hệ quả : Khi x = y = 1 ta có = 2n Khi x =1, y = -1 ta có (-1)k = 0 Ví dụ 1: Tìm khai triển của biểu thức (x+y)4 (x+y)4 = x4 + 4x3y + 6x2y2+ 4xy3 + y4 Ví dụ 2: Tính hệ số của x12y13 trong khai triển của (x +y)25 25 = C13 = 5 200 300 45 2.5.8. Các thuật toán liệt kê tổ hợp và hoán vị
Thuật toán1 : Xuất ra màn hình tất cả các chỉnh hợp chập k của n số nguyên dương
- Với mỗi vị trí của chỉnh hợp ta lần lượt chọn các giá trị từ 1 đến n (chưa được chọn) vào
vị trí này và đánh dấu số đã chọn.
- Tiếp tục tìm các số ở vị trí tiếp theo cho đến khi chọn đủ k số vào vị trí của chỉnh hợp và
sau đó xuất kết quả ra màn hình.
Program CHINH_HOP;
uses crt;
Const maxn=10;
Var n,k:byte;
A,B:Array[1..maxn] of byte;
dem:integer;
procedure Nhap;
var i:integer;
Begin
clrscr;
write('Nhap n:');readln(n);
write('Nhap k:');readln(k);
For i:=1 to n do A[i]:=0;
B:=A;
dem:=0;
end;
Procedure Ghinhan;
var i:integer;
begin
inc(dem);
write('Chinh hop thu ',dem,'.');
for i:=1 to k do write(A[i]:3);
writeln;
end;
Procedure Try(i:integer);
var j:integer;
begin
for j:=1 to n do
if B[j]=0 then
begin 46 B[j]:=i;
A[i]:=j;
if i=n then ghinhan else try(i+1);
A[i]:=0;
B[j]:=0;
end;
end;
Begin
Nhap;
Try(1);
readln;
End.
Thuật toán 2 : Xuất ra màn hình tất cả các tổ hợp chập k của n số nguyên dương
{1,2,...,n}
- Với mỗi vị trí của tổ hợp ta lần lượt chọn các giá trị từ 1 đến n (Chưa được chọn và có
giá trị lớn hơn giá trị của phần tử trước đó, nếu có) vào vị trí này và đánh dấu số đã chọn.
- Tiếp tục tìm các số ở vị trí tiếp theo cho đến khi chọn đủ k số vào vị trí của tổ hợp và sau
đó xuất kết quả ra màn hình
Program TO_HOP;
uses crt;
Const maxn=10;
Var n,k:byte;
A,B:Array[0..maxn] of byte;
dem:integer;
procedure Nhap;
var i:integer;
Begin
clrscr;
write('Nhap n:');readln(n);
write('Nhap k:');readln(k);
For i:=1 to n do A[i]:=0;
B:=A;
dem:=0;
end;
Procedure Ghinhan;
var i:integer;
begin
inc(dem);
write('To hop thu ',dem,'.');
for i:=1 to k do write(A[i]:3);
writeln;
end;
Procedure Try(i:integer);
var j:integer;
begin
for j:=A[i-1]+1 to n do
if B[j]=0 then
begin 47 B[j]:=i;
A[i]:=j;
if i=k then ghinhan else try(i+1);
A[i]:=0;
B[j]:=0;
end;
end;
Begin
Nhap;
Try(1);
readln;
End.
Thuật toán3 : Nhập vào một chuỗi ký tự S. Xuất ra màn hình tất cả các hoán vị khác
nhau của các ký tự trong chuỗi S (Các ký tự trong S không nhất thiết khác nhau)
- Tương tự giải thuật tìm hoán vị một tập hợp nhưng khác khi chọn một phần tử nào trong
S vào một vị trí nào đó của hoán vị ta phải kiểm tra xem phần tử đó đã sử dụng hay chưa
và đồng thời có phần tử nào trong S giống với phần tử đang xét và có vị trí xuất hiện
trong S trước phần tử này mà chưa được sử dụng hay không.
Program hoanvilap;
uses crt;
Var s:string;
KT:Array[1..255] of Boolean;
B:Array[1..255] of Char;
n:byte;
dem:longint;
Function OK(k:byte):boolean;
Var j:byte;
Begin
OK:=False;
For j:=1 to k-1 do
if (S[k] = S[j]) and (not KT[j]) then Exit;
OK:=True;
end;
Procedure Ghinhan;
Var i:Byte;
Begin
Inc(dem);
write('Hoan vi thu ',dem,'.');
For i:=1 to n do write(B[i]);
Writeln;
end;
Procedure Try(i:byte);
Var j:byte;
Begin
For j:=1 to n do
If (not (KT[j])) and (OK(j)) then
begin 48 KT[j]:=True;
B[i]:=S[j];
If i=n then Ghinhan else Try(i+1);
KT[j]:=False;
B[i]:=#0;
end;
end;
BEGIN
clrscr; Write('S=');readln(S);
n:=Length(S); dem:=0;
Fillchar(KT,Sizeof(KT),0);
Fillchar(B,Sizeof(B),0);
Try(1);
readln;
END. CHƯƠNG 3
LÝ THUYẾT ĐỒ THỊ & CÂY Lý thuyết đồ thị là một ngành khoa học có lịch sử phát triển khá sớm nhưng lại có
nhiều ứng dụng hiện đại. Những ý tưởng cơ bản của nó được đưa ra từ thế kỷ 18 bởi
nhà toán học Thụy Sĩ tên là Leonhard Euler. Ông đã dùng đồ thị để giải quyết bài toán
7 chiếc cầu Konigsberg nổi tiếng. Đồ thị cũng được dùng để giải các bài toán trong nhiều lĩnh vực khác nhau. Chẳng hạn
dùng đồ thị để xác định xem có thực hiện một mạch điện trên một bảng điện phẳng
được không. Chúng ta cũng có thể phân biệt hai hợp chất hóa học có cùng công thức
phân tử nhưng có cấu trúc khác nhau nhờ đồ thị. Chúng ta cũng có thể xác định xem
hai máy tính có được nối với nhau bằng một đường truyền thông hay không nếu dùng
mô hình đồ thị mạng máy tính. Đồ thị với các trọng số được gán cho các cạnh của nó
có thể dùng để giải các bài toán như bài toán tìm đường đi ngắn nhất giữa hai thành
phố trong một mạng giao thông. Chúng ta cũng có thể dùng đồ thị để lập lịch thi và
phân chia kênh cho các đài truyền hình. Mỗi cạnh tương ứng hoặc Cần thơ (v7) TN (v1) HCM (v4) Long an(v8) Hà nội (v2) Khánh hòa
(v6) HP(v3) Huế (v5) 3.1. Đồ thị và các khái niệm cơ bản trong đồ thị
3.1.1. Định nghĩa
Đồ thị (Graph) là một cấu trúc rời rạc gồm 2 thành phần G = (V, E). Trong đó V (Vertex)
là tập hữu hạn các đỉnh, E (Edge) là tập hữu hạn các cạnh.
V , tập V ta có thể đánh số
viết là
với cặp hai đỉnh
Nếu cạnh có quy định chiều thì được gọi là cạnh có hướng (cung).
Nếu cạnh không quy định chiều thì được gọi là cạnh vô hướng.
Đồ thị G = (V,E) được gọi là đơn đồ thị nếu giữa hai đỉnh bất kỳ được nối với nhau bởi
không quá một cung.
Đồ thị G = (V,E) được gọi là đa đồ thị nếu giữa hai đỉnh bất kỳ được nối với nhau bởi hai
cung trở lên.
Đồ thị G = (V,E) được gọi là có hướng nếu có chứa cạnh có hướng
Đồ thị G = (V,E) được gọi là vô hướng nếu tất cả các cạnh đều là vô hướng
Một đồ thị vô hướng luôn được coi là đồ thị có hướng bằng cách thay một cung bất kỳ
bằng hai cung ngược chiều nhau.
Giả đồ thị (Pseudo graph): Nếu tồn tại một cạnh nối một đỉnh với chính nó gọi là khuyên
Ví dụ: 49 3.1.2. Biểu diễn đồ thị Để lưu trữ đồ thị và thực hiện các thuật toán khác nhau với đồ thị trên máy tính cần phải tìm những cấu trúc dữ liệu thích hợp để mô tả đồ thị
a. Biểu diễn bằng ma trận kề (ma trận lân cận kề)
Cho đồ thi G = (V, E) với V gồm n đỉnh (n >=1). Để biểu diễn G người ta dùng một ma
trận vuông A[nxn] các phần tử là 0,1 được xác định theo quy tắc sau v1 v2 v4 v3 Ví dụ: với đồ thị được biểu diễn Ma trận kề được biểu diễn như sau: v1
0
1
1
1 v2
1
0
1
0 v3
1
1
0
0 v4
1
0
0
0 v1
v2
v3
v4 Trường hợp là đa đồ thị có khuyên: Nếu có k cạnh nối vi với vj Ai,j= nếu vi có khuyên v2 v1 v5 v4 v3 50 Ví dụ: A = Chú ý:
Ma trận kề của một đồ thị tuỳ thuộc vào thứ tự liệt kê các đỉnh. Do vậy có n! ma trận liền
kề khác nhau của một đồ thị n đỉnh.
Với đồ thị vô hướng thì các phần tử đối xứng qua đường chéo chính.
Ma trận kề của đồ thị có hướng không phải là ma trận đối xứng
Tổng tất cả các giá trị trên hàng i chính là số bậc ra của đỉnh đó, tổng tất cả các giá trị trên
cột j chính là số bậc vào của đỉnh đó
Trong thực tế mỗi một cung sẽ luôn xác định một giá trị nào đó, giá trị đó có thể là độ dài,
có thể là tiền đi lại, chi phí,...giá trị này gọi là trọng số Cij được hiểu như sau: Cij = 0 nếu vi vj
Trọng số thực nếu (vi, vj ) E
nếu (vi, vj ) E 1 1 2 3 7 3 5 8 4 5 4 Ví dụ: Ma trận trọng số của đồ thị được biểu diễn như sau 51 Ưu nhược điểm của phương pháp mô tả bằng ma trận kề, ma trận trọng số:
Ưu điểm: biết được hai đỉnh u, v có kề nhau không, biết được trọng số của hai đỉnh u và v
bất kỳ.
Nhược điểm: tốn bộ nhớ. Với đồ thị n đỉnh cần n2 ô nhớ, nếu số cạnh của đồ thị ít thì
phương pháp này quá lãng phí bộ nhớ.
b. Biểu diễn đồ thị bằng ma trận liên thuộc
Cho đồ thị vô hướng G = (V,E), với tập đỉnh V = 1,2,..,n và tập cạnh
E =e1,e2,..,en. Để biểu diễn G người ta dùng ma trận liên thuộc M[nxm]. Trong đó e7 Mij = 1 nếu cạnh ej nối với đỉnh vi
0 nếu cạnh ej không nối với đỉnh vi 1 e5 2
e3 e4 e1 e2 5 3 4 e6 Ví dụ: Ma trận liên thuộc của đồ thị được biểu diễn như sau: v1 v2 v4 v3 c. Biểu diễn đồ thị bằng danh sách cạnh (cung)
Trong trường hợp đồ thị thưa (m <6*n), người ta thường dùng cách biểu diễn đồ thị
theo danh sách cạnh.
Trong cách biểu diễn này chúng ta lưu trữ danh sách tất cả các cạnh. Mỗi cạnh e =(x,y)
của đồ thị sẽ tương ứng với 2 biến dau[e], cuoi[e]
Ví dụ: Cuối Đầu v2 v1 v4 v1 v4 v2 v1 v3 v2 v3 v3 v4 52 d. Biểu diễn đồ thị bằng danh sách kề
Trong rất nhiều vấn đề ứng dụng của lý thuyết đồ thị, cách biểu diễn đồ thị dưới dạng
danh sách kề là cách biểu diễn thích hợp nhất.
Với mỗi đỉnh v của đồ thị chúng ta lưu giữ các đỉnh kề với nó, mà ta ký hiệu là ke(v) v1 v2 v4 v3 4 Nil 2 4 Nil 1 2
Nil Ví dụ 3
Nil Biểu diễn đồ thị trên bằng danh sách kề như sau:
1
2
3
4 h b a Number:1..n;{số hiệu đỉnh kề}
Next:Pointer; e g d c f Như vậy, mỗi đỉnh của đồ thị có một danh sách các đỉnh kề với nó. Cấu trúc được mô
phỏng như sau:
Type
Pointer=^Member;
Member=Record
End;
Graph=array[1..n] of Pointer;
Var
G:graph;
3.2. Bậc, đường đi, chu trình và tính liên thông của đồ thị
3.2.1. Bậc của đỉnh
Hai đỉnh u và v của đồ thị G được gọi là kề nhau nếu (u,v) là 1 cạnh của đồ thị G. Và đặt
e=(u,v) thì e gọi là cạnh liên thuộc với hai đỉnh u và v.
Nếu một cạnh e = (u,v) là một cung của đồ thị có hướng thì ta nói v là đỉnh kề của đỉnh u,
u được gọi là đỉnh đầu, v là đỉnh cuối.
Bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với đỉnh đó và ký hiệu là
deg(v).
Ví dụ: Ta có deg(a) = 3; deg(b) = 2; deg(c) = 2; deg(d) =5; deg(e) = 2; deg(f) = 3; deg(g) = 1; deg(h) = 0 53 Chú ý:
Nếu đỉnh có khuyên thì mỗi khuyên được cộng thêm 2 đơn vị vào bậc của đỉnh đó Nếu đỉnh có bậc bằng 1 gọi là đỉnh treo.
Đỉnh có bậc bằng 0 gọi là đỉnh cô lập.
Nếu đồ thị có mọi đỉnh đều cô lập thì được gọi là đồ thị rỗng
Ta gọi bán bậc ra (bán bậc vào) của đỉnh v trong đồ thị có hướng là số cung của đồ thị đi
ra khỏi nó (đi vào nó) và ký hiệu deg+(v) (deg- (v)) Tổng tất cả các bán bậc ra (bán bậc vào) của một đỉnh được gọi là bậc của đỉnh đó. a b f e d c Nếu deg+(v) + deg- (v) = 0 thì v là đỉnh cô lập
Nếu deg+(v)=1 và deg- (v) = 0 hoặc deg+(v) = 0 và deg- (v) = 1. Thì v được gọi là đỉnh
treo.
Nếu đỉnh có khuyên thì được tính 1 đơn vị cho bán bậc ra và 1 đơn vị cho bán bậc vào.
Ví dụ: G1: Liên thông G2: Không liên thông Ta có: deg+(a) = 3; deg-(a) = 0
deg+(b) = 2; deg-(b) = 2
deg+(c) = 2; deg-(c) = 1
deg+(d) = 1; deg-(d) =3
deg+(e) = 1; deg-(e) = 2
deg+(f) =1; deg-(f) = 2
3.2.2. Đường đi và chu trình
Cho đồ thị G = (V, E), đường đi từ s tới t có độ dài n là một dãy liên tiếp các đỉnh v0,
v1,..,vn mà xuất phát là s = v0, kết thúc t = vn, các cạnh ei=(vi-1,vi) i=1,..,n là đôi một khác
nhau.
Độ dài của đường đi là số cạnh tham gia trong đường đi đó (đối với đồ thị không có trọng
số)
Nếu đồ thị có trọng số thì độ dài của đường đi sẽ là tổng độ dài của các cạnh thuộc đường
đi đó.
Một đường đi được gọi là đường đi đơn nếu như trong đường đi đó các đỉnh chỉ xuất hiện
một lần trừ đỉnh đầu và đỉnh cuối.
Chu trình là một đường đi khép kín mà đỉnh đầu và đỉnh cuối trùng nhau.
3.2.3. Tính liên thông của đồ thị
Một đồ thị vô hướng G = (V, E) được gọi là liên thông nếu tồn tại một đường đi giữa mọi
cặp đỉnh của nó.
Nếu một đồ thị không liên thông thì một đồ thị con liên thông cực đại của nó được gọi là
một thành phần liên thông
Ví dụ: 54 Một đồ thị là liên thông nếu nó chỉ có một thành phần liên thông. Đồ thị có từ hai thành
phần liên thông trở lên gọi là rừng. Một đỉnh trong đồ thị G mà khi xoá đi nó và tất cả các cạnh liên thuộc với nó ta nhận
được đồ thị con mới có nhiều thành phần liên thông hơn đồ thị G được gọi là đỉnh cắt
hay điểm khớp. Việc xoá đỉnh cắt khỏi một đồ thị liên thông sẽ tạo ra một đồ thị con
không liên thông. Hoàn toàn tương tự, một cạnh mà khi ta bỏ nó đi sẽ tạo ra một đồ thị
có nhiều thành phần liên thông hơn so với đồ thị xuất phát được gọi là cạnh cắt hay là
cầu. x y z u v w s t Ví dụ: Trong đồ thị trên, các đỉnh cắt là v, w, s và các cầu là (x,v), (w,s). Đồ thị G có hướng được gọi là liên thông mạnh nếu mọi cặp đỉnh (u,v) của nó đều tồn tại
một đường đi từ u tới v và một đường đi từ v tới u.
Đồ thị G có hướng không liên thông mạnh thì một đồ thị con liên thông mạnh cực đại của
G được gọi là một thành phần liên thông mạnh của đồ thị Đồ thị có hướng G được gọi là liên thông yếu nếu đồ thị vô hướng nền của nó là liên
thông. Đồ thị có hướng G được gọi là liên thông một chiều nếu với hai đỉnh phân biệt bất kỳ
u và v của G đều có đường đi từ u tới v hoặc đường đi từ v tới u. u w v w u v x x t y s y t s Ví dụ: G G’ Đồ thị G là liên thông mạnh nhưng đồ thị G’ là liên thông yếu (không có đường đi từ u
tới x cũng như từ x tới u). Định lý: Nếu G là một đơn đồ thị vô hướng n đỉnh, m cạnh, k thành phần liên thông. Khi
đó ta có mối quan hệ 55 Chứng minh: Bất đẳng thức
được chứng minh bằng quy nạp theo m. Nếu
m=0 thì k=n nên bất đẳng thức đúng. Giả sử bất đẳng thức đúng đến m1, với m 1.
Gọi G’ là đồ thị con bao trùm của G có số cạnh m0 là nhỏ nhất sao cho nó có k thành
phần liên thông. Do đó việc loại bỏ bất cứ cạnh nào trong G’ cũng tăng số thành phần
liên thông lên 1 và khi đó đồ thị thu được sẽ có n đỉnh, k+1 thành phần liên thông và
m01 cạnh. Theo giả thiết quy nạp, ta có m01 n(k+1) hay m0 nk. Vậy m n-k. Bổ sung cạnh vào G để nhận được đồ thị G’’ có m1 cạnh sao cho k thành phần liên
thông là những đồ thị đầy đủ. Ta có m m1 nên chỉ cần chứng minh . m1 Giả sử Gi và Gj là hai thành phần liên thông của G’’ với ni và nj đỉnh và ni nj >1 (*).
Nếu ta thay Gi và Gj bằng đồ thị đầy đủ với ni+1 và nj1 đỉnh thì tổng số đỉnh không
thay đổi nhưng số cạnh tăng thêm một lượng là: . Thủ tục này được lặp lại khi hai thành phần nào đó có số đỉnh thoả (*). Vì vậy m1 là
lớn nhất (n, k là cố định) khi đồ thị gồm k-1 đỉnh cô lập và một đồ thị đầy đủ với n-
k+1 đỉnh. Từ đó suy ra bất đẳng thức cần tìm. Chú ý: + Nếu G liên thông thì ta có k = 1. Khi đó ta có + Nếu G là một đơn đồ thị vô hướng, liên thông thì số thành phần liên thông của nó là 1 3.2.4. Các định lý cơ bản về đồ thị
Định lý 1: (Định lý bắt tay) Cho G là một đồ thị vô hướng có m cạnh. Khi đó tổng số bậc
của tất cả các đỉnh bằng 2 lần số cạnh. deg(v) = 2*m (v V). Định lý 2: Trong một đồ thị vô hướng thì số đỉnh bậc lẻ luôn là một số chẵn.
Chứng minh: Gọi v1 là tập đỉnh bậc chẵn; v2 là tập đỉnh bậc lẻ Theo định lý 1: Số các đỉnh bậc lẻ của đồ thị phảilà một số chẵn
3.3. Các phương pháp duyệt đồ thị Có hai phương pháp duyệt đồ thị đó là phương pháp duyệt đồ thị theo chiều rộng Việc giải quyết các vấn đề của lý thuyết đồ thị đòi hỏi ta phải xem xét tất cả các
đỉnh và tất cả các cung của đồ thị theo một hệ thống nào đó. Vì vậy các kỹ thuật duyệt đồ
thị để thăm tất cả các đỉnh và các cung của đồ thị đóng vai trò quan trọng trong việc thiết
kế các thuật toán trên đồ thị.
và phương pháp duyệt đồ thị theo chiều sâu.
3.3.1. Bài toán tổng quát
Cho một đồ thị G = (V, E) vô hướng. Hãy thăm tất cả các đỉnh của đồ thị, mỗi đỉnh đúng
một lần. Để thăm các đỉnh của đồ thị người ta tiến hành theo hai thuật toán Duyệt đồ thị theo chiều rộng (BFS: Breadth First Search)
Duyệt đồ thị theo chiều sâu (DFS: Depth First Search) 56 3.3.2. Thuật toán duyệt đồ thị theo chiều rộng (BFS: Breadth First Search)
a. Nguyên tắc duyệt
Chọn một đỉnh v0 của đồ thị làm đỉnh xuất phát
Thăm đỉnh v0 rồi lần lượt thăm tất cả các đỉnh v là lân cận của v0 mà chưa được thăm.
Sau đó đỉnh v nào được thăm trước thì các đỉnh lân cận của nó sẽ được thăm trước và quá
trình sẽ lại được tiếp tục. Nếu còn đỉnh nào chưa được thăm thì chọn ra một đỉnh để thăm và quá trình diễn ra như
đối với v0.
Mỗi đỉnh chỉ được thăm một lần và kết thúc khi tất cả các đỉnh đều được thăm.
b. Thuật toán Trong thuật toán có sử dụng:
1. Một danh sách Q như một hàng đợi (lấy một phần tử ra ở đầu Queue, chèn một phần tử mới vào cuối Queue) 2. Sử dụng hàm Visited(v) để thực hiện việc thăm đỉnh v Nếu Visited(v) = 1 thì đỉnh v đã được thăm
Nếu Visited(v) = 0 thì đỉnh v chưa được thăm + Đặt w vào cuối danh sách Q
+ Visited(w):= 1; + Loại đỉnh u ở đầu Q ra ngoài
+ For Begin 1. For u:= 1 to n do Visited(u):= 0; {khởi tạo trạng thái ban đầu của đồ thị là 2. For u:= 1 to n do If Visited(u) = 0 then BFS(u); Dựa vào thủ tục BFS(v0) thì thuật toán duyệt đồ thị theo chiều rộng như sau:
mọi đỉnh đều chưa được thăm} End; A C E G F B D Ví dụ: 57 Khi thăm đến đỉnh v nào đó mà tất cả các đỉnh kề của v đều đã được thăm (hoặc v không
có đỉnh kề) thì quay lại đỉnh u mà từ u đã đến thăm v.
Nếu u có đỉnh kề là v’ mà chưa được thăm thì một phép duyệt theo chiều sâu bắt đầu từ v’
được thực hiện
Mỗi đỉnh chỉ được thăm một lần và kết thúc khi tất cả các đỉnh đều được thăm.
b. Thuật toán 1. Visited(v0) : = 1; {thăm đỉnh v0}
2. For Trong thuật toán có sử dụng:
1. Sử dụng hàm Visited(v) để thực hiện việc thăm đỉnh v
Nếu Visited(v) = 1 thì đỉnh v đã được thăm
Nếu Visited(v) = 0 thì đỉnh v chưa được thăm
2. Một thủ tục DFS(v0): Duyệt đồ thị theo chiều sâu xuất phát từ đỉnh v0
Procedure DFS(v0);
Begin
End;
Dựa vào thủ tục DFS(v0) thì thuật toán duyệt đồ thị theo chiều sâu như sau:
Begin 1. For u:= 1 to n do Visited(u):= 0; {khởi tạo trạng thái ban đầu của đồ thị là A C E G F B D 2. For u:= 1 to n do If Visited(u) = 0 then DFS(u); mọi đỉnh đều chưa được thăm} End. Ví dụ: K1 K2 K3 K4 58 Đồ thị đầy đủ Kn có tất tả n(n-1)/2 cạnh, đó là đơn đồ thị có nhiều cạnh nhất 3.4.2. Đồ thị vòng (Chu trình): Đồ thị vòng Cn , n 3 gồm n đỉnh v1, v2, ... , vn và các C5 C3 C4 cạnh (v1, v2), (v2, v3) , ..., (vn-1, vn) , (vn , v1) ( là một chu trình ) 3.4.3. Đồ thị bánh xe Ký hiệu là Wn thu được từ Cn bằng cách bổ xung vào một đỉnh mới nối với tất cả các đỉnh
của Cn 3.4.4. Đồ thị phân đôi: Khi các đỉnh của đồ thị có thể chia làm hai tập con sao cho mỗi v1 v6 v2 v5 v3 v4 v2
v4
v6 v1
v3
v5 cạnh nối một đỉnh của tập con này với một đỉnh của tập con kia V1 = v1 , v3 , v5; V2 = v2 , v4 , v6 Đồ thị phân đôi đầy đủ: Km , n , trong đó |V1| = m , |V2| = n sao cho mỗi đỉnh trong V1 59 được nối với mỗi đỉnh trong V2 K1,8 3.4.5. Đồ thị lập phương: Qn có 2n đỉnh và mỗi đỉnh được biểu diễn bởi một xâu bit độ 1
0 1
1 0 1 1
1
0
- 1
1
1
- 0
0 0
1 1
0
1
- 1
0
0
- dài n sao cho 2 đỉnh kề nhau chỉ khác nhau một bit 0
1
1
- 0
1
0
-
Q3 0
0
1
- 0
0
0
- Q1
Q2 3.4.6. Một vài ứng dụng của các đồ thị đặc biệt
a. Các mạng cục bộ LAN: Một số mạng cục bộ dùng cấu trúc hình sao, trong đó tất cả các thiết bị được nối với
thiết bị điều khiển trung tâm. Mạng cục bộ kiểu này có thể biểu diễn bằng một đồ thị
phân đôi đầy đủ K1,n. Các thông báo gửi từ thiết bị này tới thiết bị khác đều phải qua
thiết bị điều khiển trung tâm.Mạng cục bộ cũng có thể có cấu trúc vòng tròn, trong đó
mỗi thiết bị nối với đúng hai thiết bị khác. Mạng cục bộ kiểu này có thể biểu diễn bằng
một đồ thị vòng Cn. Thông báo gửi từ thiết bị này tới thiết bị khác được truyền đi theo
vòng tròn cho tới khi đến nơi nhận. 60 Có thể một số mạng cục bộ dùng cấu trúc hỗn hợp của hai cấu trúc trên. Các thông báo
được truyền vòng quanh theo vòng tròn hoặc có thể qua thiết bị trung tâm. Sự dư thừa
này có thể làm cho mạng đáng tin cậy hơn. Mạng cục bộ kiểu này có thể biểu diễn
bằng một đồ thị bánh xe Wn. v
2 v
3 v
4 v
2 v
3 v
1 v
2 v
8 v
3 v
9 v
4 v
5 v
1 v
6 v
1 v
4 v
7 v
8 v
9 v
8 v
5 v
7 v
6 v
5 v
6 v
7 Cấu trúc hình sao Cấu trúc vòng tròn Cấu trúc hỗn hợp b. Xử lý song song: Các thuật toán để giải các bài toán được thiết kế để thực hiện
một phép toán tại mỗi thời điểm là thuật toán nối tiếp. Tuy nhiên, nhiều bài toán với số
lượng tính toán rất lớn như bài toán mô phỏng thời tiết, tạo hình trong y học hay phân
tích mật mã không thể giải được trong một khoảng thời gian hợp lý nếu dùng thuật
toán nối tiếp ngay cả khi dùng các siêu máy tính. Ngoài ra, do những giới hạn về mặt
vật lý đối với tốc độ thực hiện các phép toán cơ sở, nên thường gặp các bài toán không
thể giải trong khoảng thời gian hợp lý bằng các thao tác nối tiếp. Vì vậy, người ta phải
nghĩ đến kiểu xử lý song song. Khi xử lý song song, người ta dùng các máy tính có nhiều bộ xử lý riêng biệt, mỗi
bộ xử lý có bộ nhớ riêng, nhờ đó có thể khắc phục được những hạn chế của các máy
nối tiếp. Các thuật toán song song phân chia bài toán chính thành một số bài toán con
sao cho có thể giải đồng thời được. Do vậy, bằng các thuật toán song song và nhờ việc
sử dụng các máy tính có bộ đa xử lý, người ta hy vọng có thể giải nhanh các bài toán
phức tạp. Trong thuật toán song song có một dãy các chỉ thị theo dõi việc thực hiện
thuật toán, gửi các bài toán con tới các bộ xử lý khác nhau, chuyển các thông tin vào,
thông tin ra tới các bộ xử lý thích hợp. Khi dùng cách xử lý song song, mỗi bộ xử lý có thể cần các thông tin ra của các bộ
xử lý khác. Do đó chúng cần phải được kết nối với nhau. Người ta có thể dùng loại đồ
thị thích hợp để biểu diễn mạng kết nối các bộ xử lý trong một máy tính có nhiều bộ
xử lý. Kiểu mạng kết nối dùng để thực hiện một thuật toán song song cụ thể phụ thuộc
vào những yêu cầu với việc trao đổi dữ liệu giữa các bộ xử lý, phụ thuộc vào tốc độ
mong muốn và tất nhiên vào phần cứng hiện có. Mạng kết nối các bộ xử lý đơn giản nhất và cũng đắt nhất là có các liên kết hai
chiều giữa mỗi cặp bộ xử lý. Các mạng này có thể mô hình bằng đồ thị đầy đủ Kn,
trong đó n là số bộ xử lý. Tuy nhiên, các mạng liên kết kiểu này có số kết nối quá
nhiều mà trong thực tế số kết nối cần phải có giới hạn. P
2 P
4 P
5 P
6 P
1 P
3 61 Các bộ xử lý có thể kết nối đơn giản là sắp xếp chúng theo một mảng một chiều.
Ưu điểm của mảng một chiều là mỗi bộ xử lý có nhiều nhất 2 đường nối trực tiếp với
các bộ xử lý khác. Nhược điểm là nhiều khi cần có rất nhiều các kết nối trung gian để
các bộ xử lý trao đổi thông tin với nhau. P P P P P P P P P P P P P P P P (
0
,
0
(
)
1
,
0
)
(
2
,
0
(
)
3
,
0
) (
0
,
1
(
)
1
,
1
)
(
2
,
1
)
(
3
,
1
) (
0
,
3
)
(
1
,
3
)
(
2
,
3
)
(
3
,
3
) (
0
,
2
)
(
1
,
2
)
(
2
,
2
)
(
3
,
2
) Mạng kiểu lưới (hoặc mảng hai chiều) rất hay được dùng cho các mạng liên kết. Trong
một mạng như thế, số các bộ xử lý là một số chính phương, n=m2. Các bộ xử lý được
gán nhãn P(i,j), 0 i, j m1. Các kết nối hai chiều sẽ nối bộ xử lý P(i,j) với bốn bộ
xử lý bên cạnh, tức là với P(i,j1) và P(i1,j) chừng nào các bộ xử lý còn ở trong lưới. P
1 P
4 P
5 P
2 P
3 P
6 P
7 P
0 Mạng kết nối quan trọng nhất là mạng kiểu siêu khối. Với các mạng loại này số các
bộ xử lý là luỹ thừa của 2, n=2m. Các bộ xử lý được gán nhãn là P0, P1, ..., Pn-1. Mỗi bộ
xử lý có liên kết hai chiều với m bộ xử lý khác. Bộ xử lý Pi nối với bộ xử lý có chỉ số
biểu diễn bằng dãy nhị phân khác với dãy nhị phân biểu diễn i tại đúng một bit. Mạng
kiểu siêu khối cân bằng số các kết nối trực tiếp của mỗi bộ xử lý và số các kết nối gián
tiếp sao cho các bộ xử lý có thể truyền thông được. Nhiều máy tính đã chế tạo theo
mạng kiểu siêu khối và nhiều thuật toán đã được thiết kế để sử dụng mạng kiểu siêu
khối. Đồ thị lập phương Qm biểu diễn mạng kiểu siêu khối có 2m bộ xử lý. 3.5. Đồ thị Euler Có thể coi năm 1736 là năm khai sinh lý thuyết đồ thị, với việc công bố lời giải
“bài toán về các cầu ở Konigsberg” của nhà toán học lỗi lạc Euler (1707-1783). Thành
phố Konigsberg thuộc Phổ (nay gọi là Laliningrad thuộc Nga) được chia thành bốn vùng
bằng các nhánh sông Pregel, các vùng này gồm hai vùng bên bờ sông, đảo Kneiphof và
một miền nằm giữa hai nhánh của sông Pregel. Vào thế kỷ 18, người ta xây bảy chiếc cầu
nối các vùng này với nhau. Vào chủ nhật người dân ở đây thường đi bộ dọc theo các phố,
họ tự hỏi không biết có thể xuất phát tại một địa điểm nào trong thành phố đi qua tất cả
các cầu, mỗi chiếc cầu đi đúng một lần, rồi lại trở về điểm xuất phát được không? Nếu ta
coi mỗi khu vực A, B, C, D như một đỉnh và mỗi cầu qua lại khu vực là một cạnh nối hai
đỉnh thì ta có sơ đồ của Konigsberg là một đa đồ thị G như hình dưới. Bài toán tìm đường đi qua tất cả các cầu mỗi cầu chỉ đi qua một lần có thể được B B D A D A 62 C C G biểu diễn bằng mô hình đa đồ thị như sau: 3.5.1. Định nghĩa: Định nghĩa 1: Đồ thị liên thông G được gọi là đồ thị Euler nếu tồn tại một chu trình đi qua tất cả các cạnh của đồ thị mỗi cạnh đúng một lần. Định nghĩa 2: Chu trình Euler trong đồ thị G là chu trình đi qua tất cả các cạnh của Định nghĩa 3: Đường đi Euler trong đồ thị G là đường đi qua tất cả các cạnh của Định nghĩa 4: Đồ thị liên thông G gọi là đồ thị nửa Euler nếu tồn tại một đường đi đồ thị, mỗi cạnh đúng một lần.
đồ thị, mỗi cạnh đúng một lần.
Từ định nghĩa trên ta thấy rằng mỗi chu trình Euler là một đường Euler đóng.
trong G đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần. 6 1 2 6 5 1 2 3 4 7 3 4 7 5 G2: Euler G1: Euler 1 2 1 2 5 6 3 4 3 4 G4: 1/2 Euler (tồn tại đường đi Euler) G3: Không Euler Ví dụ: 63 3.5.2. Định lý cơ bản
Định lý 1: Đồ thị liên thông G là đồ thị Euler khi và chỉ khi mọi đỉnh của G đều có bậc
chẵn.
Để chứng minh được định lý này trước hết ta chứng minh bổ đề sau:
Bổ đề: Nếu bậc của mỗi đỉnh của đồ thị G không nhỏ hơn 2 thì G chứa chu trình đơn.
Chứng minh: Nếu G có cạnh bội hoặc có khuyên thì khẳng định của bổ đề là hiển nhiên.
Vì vậy giả sử G là đơn đồ thị, gọi v là một đỉnh nào đó của đồ thị G. Ta sẽ xây dựng theo
quy nạp đường đi
v -> v1 -> v2 ->....
trong đó v1 là đỉnh kề với đỉnh v, còn với i 1 chọn vi+1 kề với vi và vi+1 vi-1 (có thể chọn
như vậy vì deg(vi 2). Do tập đỉnh của G là hữu hạn, nên sau một số hữu hạn bước ta
phải quay lại một đỉnh đã xuất phát trước đó. Gọi k là số nguyên dương đầu tiên để vk = vi
(0 i < k). Khi đó, đường đi vi, vi+1,..,vk-1, vk (=vi) là một chu trình đơn cần tìm.
Chứng minh định lý:
Điều kiện cần: Giả sử G là đồ thị Euler tức là tồn tại chu trình Euler P trong G. Khi đó cứ
mỗi lần chu trình P đi qua 1 đỉnh nào đó của G thì bậc của đỉnh đó tăng lên 2. Mặt khác mỗi cạnh của đồ thị xuất hiện trong P đúng một lần, suy ra mỗi đỉnh của đồ thị đều có bậc
chẵn.
Điều kiện đủ:
Quy nạp theo số cạnh của G. Do G là liên thông và deg(v) là số chẵn nên bậc của mỗi
đỉnh của nó không nhỏ hơn 2. Theo bổ đề thì G phải chứa chu trình C. Nếu C đi qua tất cả
các cạnh của G thì nó chính là chu trình Euler. Giả sử C không đi qua tất cả các cạnh của
G, khi đó loại bỏ khỏi G tất cả các cạnh thuộc C. Ta thu được một đồ thị mới H (không
nhất thiết liên thông). Lúc này mỗi đỉnh của H cũng có bậc chẵn. Theo giả thiết quy nạp
trong mỗi thành phần liên thông của H đều tìm được chu trình Euler. Do G là liên thông
nên mỗi thành phần trong H có ít nhất một đỉnh chung với chu trình C. Vì vậy ta có thể
xây dựng chu trình Euler trong G như sau:
Bắt đầu từ một đỉnh nào đó của chu trình C, đi theo các cạnh của chu trình C chừng nào
chưa gặp phải đỉnh không cô lập của H. Nếu gặp phải đỉnh như vậy thì ta đi theo chu trình
Euler của thành phần liên thông của H chứa đỉnh đó. Sau đó lại tiếp tục đi theo cạnh của
C cho đến khi gặp phải đỉnh không cô lập của H....Quá trình sẽ kết thúc khi ta trở về đỉnh
xuất phát, tức là thu được chu trình đi qua mỗi cạnh của đồ thị đúng 1 lần.
Hệ quả: Đồ thị liên thông G là nửa Euler khi và chỉ khi nó có không quá 2 đỉnh bậc lẻ.
Chứng minh:
Nếu G không quá 2 đỉnh bậc lẻ thì số đỉnh bậc lẻ của nó chỉ có thể là 0 hoặc 2. Nếu G
không có đỉnh bậc lẻ nào thì theo định lý 1 nó là đồ thị Euler. Giả sử G có hai đỉnh bậc lẻ
là u và v. Gọi H là đồ thị thu được từ G bằng cách thêm vào G một đỉnh mới và hai cạnh :
(w,u) và (w,v). Khi đó tất cả các đỉnh của đồ thị H đều là bậc chẵn, vì thế theo định lý 1
nó có chu trình Euler C. Xoá bỏ khỏi chu trình này đỉnh w và hai cạnh kề nó ta thu được
đường đi Euler trong đồ thị G.
Định lý 2: Cho G = (V, E) là đồ thị liên thông. Điều kiện cần và đủ để đồ thị có đường đi Euler là số đỉnh bậc lẻ trong đồ thị phải là 0 hoặc 2. G2 G1 Ví dụ Đồ thị G1 liên thông và có hai đỉnh bậc lẻ do đó có đường đi Euler
Đồ thị G2 là liên thông, nhưng số đỉnh bậc lẻ là 4 do đó không có đường Euler
3.5.3. Thuật toán Flor xác định chu trình Euler
Bài toán: Cho G = (V, E), hãy xây dựng chu trình Euler của G (nếu có) Thuật toán Flor .2
Bước 1: Kiểm tra xem G có phải là đồ thị liên thông hay không? + Nếu G là đồ thị liên thông thì chuyển sang bước 2.
+ Nếu G không liên thông thì dừng thuật toán và kết luận là đồ thị không có chu 64 trình Euler.
Bước 2: Kiểm tra xem mọi đỉnh của G đều có bậc chẵn hay không? + Nếu mọi đỉnh của G đều bậc chẵn thì chuyển sang bước 3.
+ Nếu mọi đỉnh của G không phải bậc chẵn thì dừng thuật toán và kết luận rằng đồ thị không có chu trình Euler.
Bước 3: Xây dựng các chu trình đơn trong G sao cho tất cả các cạnh của đồ thị đều có chu
trình đơn đi qua và mỗi cạnh chỉ đi qua đúng một lần. Sau đó ghép các chu trình đơn tại
các điểm chung thì ta được chu trình Euler cần tìm.
Cụ thể:
+ Xuất phát từ một đỉnh v của đồ thị, người ta xây dựng chu trình đơn p1. Sau đó
người ta đánh dấu xoá các cạnh của chu trình đơn p1. Nếu trong quá trình đánh dấu xoá
tạo nên các đỉnh cô lập mới thì ta loại bỏ các đỉnh cô lập này ra khỏi đồ thị và ta thu G1
G + Tiếp tục lặp lại quá trình trên tại một đỉnh chung của p1 và G1 để xây dựng chu + Cuối cùng ghép p1, p2,..,pk tại các đỉnh chung ta thu được chu trình Euler cần tìm. + y:= <Đỉnh đầu tiên trong danh sách đỉnh kề của x>;
+ S y;{ Đưa đỉnh y vào S}
+ S:= S - [x]; CE: =CE +[x]; x:= Top(S); {x là đỉnh đầu tiên của Stack}
If (x) then
Else Begin
End; 65 1. S:= ; CE: =;
2. Chọn u V của đồ thị làm đỉnh xuất phát;
3. S u; {đưa u vào S}
4. While S <> do
Begin
End; trình đơn p2 và cứ như vậy ta xây dựng được chu trình đơn pk
Thủ tục để xác định chu trình Euler
Procedure Euler (G liên thông, mọi đỉnh đều bậc chẵn);
{S: Stack: Lưu các đỉnh của đồ thị được xét đến; CE: Tập lưu các đỉnh của chu trình
Euler; (x): Tập lưu danh sách các đỉnh kề của đỉnh x}
Begin
End; 5 2 1 4 3 Ví dụ: Dùng thuật toán Flor xác định chu trình Euler trong đồ thị sau Ban đầu u = 4; S = 4; x = 4; (4) = 1, 2, 3, 5 y = 1; S = 14 Xoá (4,1) x = 1; (1) = 2,3,5 Xoá (1,2) y = 2; S =214 x = 2; (2) = 3,4,5 Xoá (2,3) y = 3; S =3214 x = 3; (3) = 1,4,5 y = 1; S =13214 Xoá (3,1) x = 1; (1) =5 y = 5; S =513214 Xoá (1,5) x = 5; (5) =2,3,4 y = 2; S =2513214 Xoá (5,2) x =2; (2) =4 y = 4; S =42513214 Xoá (2,4) x = 4; (4) =3,5 66 y = 3; S =342513214 Xoá (4,3) x = 3; (3) =5 y = 5; S =5342513214 Xoá (3,5) x = 5; (5) =4 y = 4; S =45342513214 Xoá (5,4) x = 4; (4) = S =5342513214; CE = 4 x = 5; (5) = S =342513214; CE = 4,5 v.v… CE = 4,5,3,4,2,5,1,3,2,1,4 S = dừng 2 5 1 4 3 Ta có chu trình sau 3.5.4 Định lý: Đồ thị có hướng liên thông yếu G là đồ thị Euler khi và chỉ khi mọi
đỉnh của G đều có bậc vào bằng bậc ra. Chứng minh: Chứng minh coi như bài tập với các sinh viên, có sử dụng bổ đề sau a. Bổ đề: Nếu bán bậc vào và bán bậc ra của mỗi đỉnh của đồ thị có hướng G không
nhỏ hơn 1 thì G chứa chu trình đơn. b. Hệ quả: Đồ thị có hướng liên thông yếu G là nửa Euler (mà không là Euler) khi và
chỉ khi tồn tại hai đỉnh x và y sao cho: deg-(x) = deg+(x)+1, deg+(y) = deg-(y)+1, deg+(v) = deg-(v), vV, v x, v y. 67 3.6. Đồ thị Hamilton Xuất phát từ trò chơi đố vui “Vòng quanh thế giới” do William Rowan Hamington,
nhà toán học người Ailen đưa ra năm 1857. Cho một hình thập nhị diện đều (đa diện
đều có 12 mặt, 20 đỉnh và 30 cạnh), mỗi đỉnh của hình mang tên một thành phố nổi
tiếng, mỗi cạnh của hình là đường đi lại giữa hai thành phố tương ứng. Xuất phát từ
một thành phố, hãy tìm đường đi thăm tất cả các thành phố khác, mỗi thành phố đúng
một lần, rồi trở về thành phố xuất phát. Trước Hamilton, từ thời Euler, người ta đã biết đến một câu đố hóc búa về “đường đi
của con mã trên bàn cờ”. Trên bàn cờ, con mã chỉ có thể đi theo đường chéo của hình
chữ nhật 2 x 3 hoặc 3 x 2 ô vuông. Giả sử bàn cờ có 8 x 8 ô vuông. Hãy tìm đường đi
của con mã qua được tất cả các ô của bàn cờ, mỗi ô chỉ một lần rồi trở lại ô xuất phát.
Bài toán này được nhiều nhà toán học chú ý, đặc biệt là Euler, De Moivre,
Vandermonde, ... Hiện nay đã có nhiều lời giải và phương pháp giải cũng có rất nhiều, trong đó có
quy tắc: mỗi lần bố trí con mã ta chọn vị trí mà tại vị trí này số ô chưa dùng tới do nó
khống chế là ít nhất. Một phương pháp khác dựa trên tính đối xứng của hai nửa bàn
cờ. Ta tìm hành trình của con mã trên một nửa bàn cờ, rồi lấy đối xứng cho nửa bàn cờ
còn lại, sau đó nối hành trình của hai nửa đã tìm lại với nhau. Trò chơi và câu đố trên dẫn tới việc khảo sát một lớp đồ thị đặc biệt, đó là đồ thị
Hamilton. a b b a b a d c d d c c e G1 G2 G3 Định nghĩa 1: Đồ thị liên thông G được gọi là đồ thị Hamilton nếu tồn tại một chu trình
đi qua tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần.
Định nghĩa 2: Chu trình Hamiltơn trong đồ thị G = (V, E) là chu trình đi qua tất cả các
đỉnh của đồ thị, mỗi đỉnh đúng một lần.
Định nghĩa 3: Đường đi Hamiltơn trong đồ thị G = (V, E) là đường đi qua tất cả các đỉnh
của đồ thị, mỗi đỉnh đúng một lần.
Ví dụ 1: 68 G1 có chu trình Hanmilton a, b, c, d, e, c, a
G2 không có chu trình Hamilton nhưng có đường đi Hamilton a, b, c, d
G3 có chu trình Hamilton a, c, b, d, a C J I K D B L H O P N Q M G R S T F A E Ví dụ 2: Đồ thị Hamilton (hình thập nhị diện đều biểu diẽn trong mặt phẳng) với chu trình
Hamilton A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, A (đường tô đậm). Đường đi Hamilton tương tự đường đi Euler trong cách phát biểu: Đường đi Euler qua
mọi cạnh (cung) của đồ thị đúng một lần, đường đi Hamilton qua mọi đỉnh của đồ thị
đúng một lần. Tuy nhiên, nếu như bài toán tìm đường đi Euler trong một đồ thị đã
được giải quyết trọn vẹn, dấu hiệu nhận biết một đồ thị Euler là khá đơn giản và dễ sử
dụng, thì các bài toán về tìm đường đi Hamilton và xác định đồ thị Hamilton lại khó
hơn rất nhiều. Đường đi Hamilton và đồ thị Hamilton có nhiều ý nghĩa thực tiễn và đã
được nghiên cứu nhiều, nhưng vẫn còn những khó khăn lớn và là vấn đề mở cho các
nhà khoa học. Người ta chỉ mới tìm được một vài điều kiện đủ để nhận biết một lớp rất nhỏ các đồ
thị Hamilton và đồ thị nửa Hamilton. Sau đây là một vài kết quả. Định lý (Rédei): Nếu G là một đồ thị có hướng đầy đủ thì G là đồ thị nửa Hamilton. Chứng minh: Giả sử G=(V,E) là đồ thị có hướng đầy đủ và =(v1,v2, ..., vk-1, vk) là
đường đi sơ cấp bất kỳ trong đồ thị G. Nếu đã đi qua tất cả các đỉnh của G thì nó là một đường đi Hamilton của G.
Nếu trong G còn có đỉnh nằm ngoài , thì ta có thể bổ sung dần các đỉnh này vào và cuối cùng nhận được đường đi Hamilton. Thật vậy, giả sử v là đỉnh tuỳ ý không nằm trên . 69 a) Nếu có cung nối v với v1 thì bổ sung v vào đầu của đường đi để được 1=(v, v1,
v2, ..., vk-1, vk). b) Nếu tồn tại chỉ số i (1 i k-1) mà từ vi có cung nối tới v và từ v có cung nối tới
vi+1 thì ta chen v vào giữa vi và vi+1 để được đường đi sơ cấp 2=(v1, v2, ..., vi, v, vi+1,
..., vk). c) Nếu cả hai khả năng trên đều không xảy ra nghĩa là với mọi i (1 i k) vi đều có
cung đi tới v. Khi đó bổ sung v vào cuối của đường đi và được đường đi 3=(v1, v2,
..., vk-1, vk, v).
Nếu đồ thị G có n đỉnh thì sau n-k bổ sung ta sẽ nhận được đường đi Hamilton. Định lý (Dirac, 1952): Nếu G là một đơn đồ thị có n đỉnh và mọi đỉnh của G đều có bậc không nhỏ hơn thì G là một đồ thị Hamilton. y b a a' b
’ Chứng minh: Định lý được chứng minh bằng phản chứng. Giả sử G không có chu
trình Hamilton. Ta thêm vào G một số đỉnh mới và nối mỗi đỉnh mới này với mọi đỉnh
của G, ta được đồ thị G’. Giả sử k (>0) là số tối thiểu các đỉnh cần thiết để G’ chứa
một chu trình Hamilton. Như vậy, G’ có n+k đỉnh. Gọi P là chu trình Hamilton ayb ...a trong G’, trong đó a và b là các đỉnh của G,
còn y là một trong các đỉnh mới. Khi đó b không kề với a, vì nếu trái lại thì ta có thể
bỏ đỉnh y và được chu trình ab ...a, mâu thuẩn với giả thiết về tính chất nhỏ nhất của k. Ngoài ra, nếu a’ là một đỉnh kề nào đó của a (khác với y) và b’ là đỉnh nối tiếp
ngay a’ trong chu trình P thì b’ không thể là đỉnh kề với b, vì nếu trái lại thì ta có thể
thay P bởi chu trình aa’ ...bb’ ... a, trong đó không có y, mâu thuẩn với giả thiết về tính
chất nhỏ nhất của k. Như vậy, với mỗi đỉnh kề với a, ta có một đỉnh không kề với b, tức là số đỉnh
không kề với b không thể ít hơn số đỉnh kề với a (số đỉnh kề với a không nhỏ hơn +k). Mặt khác, theo giả thiết số đỉnh kề với b cũng không nhỏ hơn +k. Vì không có đỉnh nào vừa kề với b lại vừa không kề với b, nên số đỉnh của G’ không ít hơn 2( +k)=n+2k, mâu thuẩn với giả thiết là số đỉnh của G’ bằng n+k (k>0). Định lý được chứng minh. Hệ quả: Nếu G là đơn đồ thị có n đỉnh và mọi đỉnh của G đều có bậc không nhỏ hơn 70 thì G là đồ thị nửa Hamilton. Chứng minh: Thêm vào G một đỉnh x và nối x với mọi đỉnh của G thì ta nhận được đơn đồ thị G’ có n+1 đỉnh và mỗi đỉnh có bậc không nhỏ hơn . Do đó theo Định lý 4.2.3, trong G’ có một chu trình Hamilton. Bỏ x ra khỏi chu trình này, ta nhận được
đường đi Hamilton trong G. Định lý (Ore, 1960): Nếu G là một đơn đồ thị có n đỉnh và bất kỳ hai đỉnh nào không
kề nhau cũng có tổng số bậc không nhỏ hơn n thì G là một đồ thị Hamilton. Định lý *: Nếu G là đồ thị phân đôi với hai tập đỉnh là V1, V2 có số đỉnh cùng bằng n (n 2) và bậc của mỗi đỉnh lớn hơn thì G là một đồ thị Hamilton. e d
a e f d c a b a b c g f h g Ví dụ: Đồ thị G này có 8 đỉnh, đỉnh nào cũng Đồ thị G’ này có 5 đỉnh bậc 4 và 2 đỉnh có bậc 4, nên theo Định lý Dirac, G là bậc 2 kề nhau nên tổng số bậc của hai
đỉnh đồ thị Hamilton. không kề nhau bất kỳ bằng 7 hoặc 8, nên a b b theo Định lý Ore, G’ là đồ thị Hamilton. d f Đồ thị phân đôi này có bậc của mỗi đỉnh bằng 2
hoặc 3 (> 3/2), nên theo Định lý *, nó là đồ thị
Hamilton. 71 //Các chu trình Hamilton thu được bằng việc phát triển dãy đỉnh v[1],….,v[k-1] của đồ thị
cho bởi danh sách ke(u), uV; Hàm chuaxet[v] nhận True nếu v chưa được xét đến, nhận
fasle nếu v đã được xét; v0 là đỉnh xuất phát bất kỳ của chu trình}
Procedure Hamilton(k);
Begin
For u ke(v[k-1]) do
If chuaxet[u] then
Begin
v[k]:=u;
chuaxet[u]:=false; If (k=n+1) and(u=v0) then ghinhan (v[1],..,v[n],v0) Else Hamilton(k+1); Trong thực tế để đi từ địa điểm A đến địa điểm B trong thành phố, có nhiều Đồ thị có trọng số là đồ thị G=(V,E) mà mỗi cạnh (hoặc cung) eE được gán bởi Cho đơn đồ thị liên thông, có trọng số G=(V,E). Tìm khoảng cách l(a,z) từ một Có một số thuật toán tìm đường đi ngắn nhất; ở đây, ta có thuật toán do E. Dijkstra, Phương pháp của thuật toán Dijkstra là: xác định tuần tự đỉnh có khoảng cách đến 72 chuaxet[y]:=true;
End;
End;
//* Main program *//
Begin
For v V do chuaxet[v]:=true;{Khởi đầu mọi đỉnh của đồ thị đều chưa được xét}
v[1]:=v0 ; chuaxet[v0]:=false;
Hamilton(2);
End.
3.7. Thuật toán tìm đường đi ngắn nhất
đường đi, nhiều cách đi, có lúc ta chọn đường đi ngắn nhất (theo nghĩa khoảng cách), có
lúc lại cần chọn đường đi nhanh nhất (theo nghĩa thời gian) và có lúc phải cân nhắc để
chọn đường đi tốt nhất ( theo nghĩa chi phí), v.v...
Có thể coi sơ đồ của đường đi từ A đến B trong thành phố là một đồ thị, với đỉnh
là các địa điểm (A và B coi như điểm xuất phát và điểm đích cần tới), cạnh là đoạn đường
nối địa điểm. Trên mỗi cạnh của đồ thị này, ta gán một số dương mang ý nghĩa tùy theo
bài toán ứng dụng (có thể là chiều dài của đoạn đường hoặc thời gian đi đoạn đường hay
cước phí di chuyển trên đoạn đường đó, ...), giá trị này được gọi là trọng số của cạnh.
một số thực c(e), gọi là trọng số của cạnh (hoặc cung) e.
Không mất tính tổng quát ta coi trọng số của mỗi cạnh là một số dương mang ý
nghĩa là chiều dài của cạnh đó. Mỗi đường đi từ đỉnh u đến đỉnh v, có chiều dài là l(u,v),
bằng tổng chiều dài các cạnh mà nó đi qua. Khoảng cách d(u,v) giữa hai đỉnh u và v là
chiều dài đường đi ngắn nhất (theo nghĩa d(u,v) nhỏ nhất) trong các đường đi từ u đến v.
Có thể xem một đồ thị G bất kỳ là một đồ thị có trọng số mà mọi cạnh đều có chiều
dài 1. Khi đó, khoảng cách l(u,v) giữa hai đỉnh u và v là chiều dài của đường đi từ u đến v
ngắn nhất, tức là đường đi qua ít cạnh nhất.
3.7.1. Bài toán tìm đường đi ngắn nhất:
đỉnh a cho trước đến một đỉnh z bất kỳ của G và tìm đường đi ngắn nhất từ a đến z.
nhà toán học người Hà Lan, đề xuất năm 1959.
u0 từ nhỏ đến lớn. Trong các ứng dụng thực tế, bài toán tìm đường đi ngắn nhất giữa hai đỉnh của một
đồ thị liên thông có một ý nghĩa to lớn. Ví dụ, bài toán chọn một hành trình tiết kiệm nhất
(theo tiêu chuẩn khoảng cách hoặc thời gian hoặc chi phí) trên một mạng giao thông
đường bộ, đường thuỷ hoặc đường không. Bài toán lựa chọn đường truyền tin với chi phí
nhỏ nhất trong mạng thông tin v.v.. Bài toán được phát biểu như sau:
Cho G = (V, E) đơn đồ thị với trọng số dương, V= v1, v2,...., vn, E = e1, e2,...., em
Mỗi cặp ei = (vi,vj) được gán với một trọng số dương Cij xác định như sau Trọng số thực nếu (vi,vj) E 0 nếu vi vj Cij = nếu (vi,vj) E Giả thiết: Đồ thị G không tồn tại chu trình âm tức là một chu trình mà tổng trọng số trên
chu trình đó nhỏ hơn không. Phần này chúng ta sẽ đi nghiên cứu cách tìm đường đi ngắn
nhất trên đồ thị có trọng số dương và không tồn tại chu trình âm.
Chúng ta sẽ xét ba vấn đề sau: 1. Tìm đường đi ngắn nhất từ một đỉnh nguồn tới một đỉnh đích trên đồ thị
2. Tìm đường đi ngắn nhất từ một đỉnh nguồn tới các đỉnh còn lại trên đồ thị
3. Tìm đường đi ngắn nhất giữa mọi cặp đỉnh trên đồ thị . 3.7.2. Đường đi ngắn nhất từ một đỉnh nguồn tới một đỉnh đích, thuật toán Dijkstra
Tư tưởng của thuật toán Dijkstra là tìm độ dài của đường đi ngắn nhất từ a tới đỉnh đầu
tiên, độ dài của đường đi ngắn nhất từ a tới đỉnh thứ 2, v.v... cho tới khi tìm được độ dài
của đường đi ngắn nhất từ đỉnh a tới đỉnh z. Thuật toán dựa trên một dãy các bước lặp.
Một tập đỉnh đặc biệt tập S được xây dựng qua các lần lặp, mỗi bước lặp được công thêm
một đỉnh, kèm theo đó là thủ tục gán nhãn được thực hiện trong mỗi lần lặp. Trong thủ tục
gán nhãn này, nhãn của một đỉnh v bất kỳ sẽ là độ dài của đường đi ngắn nhất từ a tới v và
chỉ đi qua các đỉnh thuộc tập S. Một đỉnh được thêm vào S nếu nó có nhãn nhỏ nhất trong
số các đỉnh chưa có mặt trong S.
Đầu tiên gán cho đỉnh a nhãn bằng 0, các đỉnh khác là . Kí hiệu là:
Tập đỉnh đặc biệt S=
Sau đó ta sẽ xây dựng tập đỉnh S. Gọi Sk là tập đỉnh sau bước lặp thứ k của thủ tục gán
nhãn. Tập Sk được tạo thành từ Sk-1 bằng cách thêm vào đỉnh u Sk-1 và có nhãn nhỏ nhất,
khi đỉnh u được đưa vào Sk cần sửa lại nhãn cho các đỉnh v không thuộc Sk sao cho nhãn
Lk(v) là độ dài đường đi ngắn nhất từ a tới v và chỉ đi qua các đỉnh thuộc Sk. Ta có Thủ tục này được lặp bằng cách thêm liên tiếp các đỉnh vào tập S cho tới khi kết nạp được
đỉnh z. Khi thêm được đỉnh z vào tập S thì nhãn của z chính là độ dài của đường đi ngắn
nhất từ a tới z. Thuật toán này đã được chứng minh là đúng. Thủ tục của thuật toán:
Procedure Dijkstra( G: đơn đồ thị, liên thông có trọng số dương);
{a: đỉnh nguồn; z: đỉnh đích}
BEGIN 1. For i:=1 to n do l(vi)=;
2. L(a):=0; S:=;
3. while zS do 73 Begin u:=<đỉnh S và có nhãn L(u) nhỏ nhất>;
S:=S{u}; If L(u)+c(u,v)< L(v) then L(v):= L(u)+c(u,v) For 2 5 3 3 1 2 6 1 5 8 6 1 3 3 4 4 2 5 7 4 6
Tìm đường đi ngắn nhất từ đỉnh 1 tới đỉnh 8 của đồ thị. Lập bảng gắn nhãn theo thuật END;
Ví dụ 1: Cho đồ thị với biểu diễn hình:
7 toán: 1 2 3 4 5 6 7 8 u S ST T lặp [0,1] [3,1] [5,1] [2,1] {1} [,1] [,1] [,1] [,1] 1 * * [3,1] [5,1] [5,4] [8,4] {1,4} - - [,1] [,1] 4 - * [4,2] [10,2 [5,4] [8,4] {1,4,2} - - [,1] 2 * ] - - - [10,2 [5,4] [8,4] {1,4,2,3} - [,1] 3 - * ] - - - [7,6] [8,4] [11,6 6 {1,4,2,3,6} - ] * - - - [8,4] [10,5 5 {1,4,2,3,6,5} - - - ] * - - - - [10,5 7 {1,4,2,3,6,5,7} - - - ] 8 {1,4,2,3,6,5,7,8 74 } Đường đi ngắn nhất từ 1 8 có giá 10; vết 1 5 8 1 6 5 8 1 46 5 8 Ví dụ 2: Cho đồ thị được biểu diễn bởi ma trận trọng số C Tìm đường đi ngắn nhất từ đỉnh 1 đến đỉnh 6 Lập bảng gắn nhãn theo thuật toán: STT 1 2 3 4 5 6 u S lặp [0,1]* [1,1]* [5,1] {1} [,1] [,1] [,1] 1 - - [5,1] [3,2]* {1,2} [,1] [,1] 2 - - [5,1] - [5,4] [5,4]* 4 {1,2,4} - - - - 6 {1,2,4,6} 1 2 4 6 Đường đi ngắn nhất từ 1 6 có giá 5; vết 1 4 6
Định lý: Thuật toán Dijkstra tìm được đường đi ngắn nhất giữa 2 đỉnh trong đơn đồ thị vô
hướng liên thông có trọng số.
Chứng minh:
Ta dùng lý luận qui nạp toán học để chứng minh thuật toán Dijkstra luôn cho độ dài
đường đi ngắn nhất giữa các đỉnh a và z trong một số đồ thị vô hướng liên thông có trọng
số. Tại bước k, ta có giả thiết qui nạp: 1. Nhãn của đỉnh v trong S là độ dài của đường đi ngắn nhất từ đỉnh a tới đỉnh v và 2. nhãn của đỉnh v không thuộc S là độ dài của đường đi ngắn nhất từ a tới v và đường đi này chỉ chứa các đỉnh thuộc S. 75 Khi k=0, tức là chưa có bước lặp nào được thực hiện, S={a}, vì thế độ dài của đường đi
ngắn nhất từ a tới các đỉnh khác a là và độ dài đường đi ngắn nhất từ a tới a bằng 0. Vì
vậy bước cơ sở là đúng.
Giả sử giả thiết quy nạp là đúng với bước k.
Goi v là đỉnh thêm vào S ở bước k+1, vì vậy vS ở cuối bước k có nhãn nhỏ nhất.Từ giả
thiết qui nạp ta thấy trước khi vào vòng lặp thứ k+1 các đỉnh thuộc tập S đã được gán
nhãn bằng độ dài của đường đi ngắn nhất từ a, đỉnh v cũng vậy. Nếu điều này không xảy ra, thì ở cuối bước lặp thứ k sẽ có đường đi với độ dài nhỏ hơn Lk(v) chứa cả đỉnh không
thuộc S. Gọi u là đỉnh đầu tiên của đường đi này không thuộc S, đó là đường đi với độ dài
nhỏ hơn Lk(v) từ a tới u chỉ chứa các đỉnh của S, điều này trái với cách chọn v, vì thế 1
vẫn còn đúng ở cuối bước lặp thứ k+1.
Goi u là đỉnh không thuộc S sau bước lặp thứ k+1, đường đi ngắn nhất từ a tới u chỉ chứa
các đỉnh thuộc S sẽ hoặc là chứa v hoặc là không. Nếu nó không chứa v thì theo giả thiết
qui nạp độ dài của nó là Lk(u). Nếu nó chứa v thì nó sẽ tạo thành đường đi từ a tới v với
độ dài có thể ngắn nhất và chỉ chứa các đỉnh của S khác v, kết thúc bằng cạnh từ v từ u.
Khi đó độ dài của nó sẽ là Lk(v)+c(v,u). Điều này chứng tỏ 2 là đúng, vì Thực vậy, thuật toán dúng không quá n-1 bước lặp, vì một đỉnh được thêm vào tập Định lý: Thuật toán Dijkstra dùng O(n2) phép toán ( cộng và so sánh) để tìm độ dài của
đường đi ngắn nhất giữa 2 đỉnh trong đồ thị đơn vô hướng có trọng số.
S tại mỗi bước lặp.
Ta có thể xác định một đỉnh không thuộc Sk có nhãn nhỏ nhất nhờ không quá n-1 phép so
sánh. Sau đó dùng phép cộng và so sánh để sửa nhãn cho các đỉnh không thuộc Sk. Từ đó
có không quá 2(n-1) phép toán được dùng trong mỗi bước lặp, vì có không quá n-1 nhãn
cần sửa trong mỗi lần lặp.
Như vậy, ta dùng không quá n-1 bước lặp, mỗi bước lặp dùng không quá 2(n-1) phép toán
do đó độ phức tạp của thuật toán là O(n2).
3.7.3. Đường đi ngắn nhất từ một đỉnh nguồn tới nhiều đỉnh đích, thuật toán
Dijkstra mở rộng Giả thiết như bài toán tìm đường đi ngắn nhất một nguồn 1 đích, tuy nhiên yêu cầu
là khác, xác định đường đi ngắn nhất từ một đỉnh nguồn tới các đỉnh còn lại trên đồ thị.
Để giải quyết bài toán này người ta vẫn sử dụng thuật toán Dijkstra nhưng quá trình tìm
kiếm đỉnh đích không dừng lại một đỉnh z nào đó mà phải đi hết tập đỉnh V của đồ thị.
Trong thuật toán có thay đổi cách dùng kí hiệu: Đỉnh xuất phát là đỉnh a; d[v] lưu độ dài
đường đi ngắn nhất từ đỉnh nguồn a tới đỉnh v. Dùng mảng P[2..n] để lưu vết đường đi,
P[v]=u nếu đỉnh u là đỉnh đi trước đỉnh v trong đường đi ngắn nhất từ a tới v.
Procedure Dijkstra1n( G: đơn đồ thị, liên thông có trọng số dương);{a: đỉnh nguồn}
BEGIN 1. S:={a}; d[a]:=0; For v (V-{a}) Do d[v]:=c[a,v]; 2. While S <>V Do u:=<đỉnh (V-S) và có d(u) nhỏ nhất>;
S:=S{u};
For d(v):= d(u)+c(u,v); p[v]:=u; Begin
Begin
End;
End; END;
NhËn xÐt: - Thuật toán trên chắc chắn dừng, vì mỗi lần lặp thì bớt đi một đỉnh. Do số đỉnh 76 là hữu hạn nên sau một số lần lặp thuật toán sẽ dừng. - Thuật toán trên chắc chắn sẽ chỉ ra đường đi ngắn nhất , vì mỗi lần lặp ta luôn xác
định được đường đi ngắn nhất từ đỉnh nguồn tới đỉnh v được kết nạp vào S. Do đó sau
một số hữu hạn bước lặp khi v đỉnh đích thì ta có được đường đi ngắn nhất cần tìm. 7 2 5 3 3 1 2 6 1 5 8 6 1 3 3 4 4 2 5 7 4 6
Tìm đường đi ngắn nhất từ đỉnh 1 tới các đỉnh còn lại của đồ thị. Lâp bảng gắn nhãn: - Độ phức tạp của thuật toán nặng nhất ở các vòng For. Vòng for dầu tiên cần thời
gian O(n). Với S có n phần tử , thì V - S có n-i phần tử, do đó dòng lệnh for thứ hai cần
thời gian (n-i)O(1). Như vậy , vòng lặp While đòi hỏi thời gian O(n2). Do đó thời gian
thực hiện thuật toán Dijkstra mở rộng là O(n2)
Ví dụ 1: Cho đồ thị được biểu diễn bởi hình vẽ: u D[u] d[2] d[3] d[4] d[5] d[6] d[7] d[8] P[2 3 4 5 6 7 8] S {1} 1 0 5 2* ∞ ∞ ∞ ∞ 1 1 1 1 1 1 1 {1,4} 4 2 3
3* - ∞ 5 8 ∞ 1 1 1 1 4 4 1 {1,4,2} 2 3 - 5
4* - 10 8 ∞ 1 2 1 2 4 4 1 {1,4,2,3} 3 4 - - - 5
5* 8 ∞ 1 2 1 2 4 4 1 {1,4,2,3,6} 6 5 - - - 10
7* - 11 1 2 1 6 4 4 1 {1,4,2,3,6,5} 5 7 - - - - - 8
8* 1 2 1 6 4 4 5 {1,4,2,3,6,5,7} 7 8 - - - - - - 10
10* 1 2 1 6 4 4 5 {1,4,2,3,6,5,7,8} 8 10 - - - - - - - 1 2 1 6 4 4 5 1 6 5 8 1 46 5 8 77 1 4 65 Đường đi ngắn nhất từ 1 8 có giá 10; vết 1 5 8
Đường đi ngắn nhất từ 1 7 có giá 8; vết 1 4 7
Đường đi ngắn nhất từ 1 5 có giá 7; vết 1 6 5
Ví dụ 2: Cho đồ thị được biểu diễn bởi ma trận trọng số C Tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại Lập bảng gắn nhãn theo thuật toán: S u D[u] d[2] d[3] d[4] d[5] d[6] P[ 2 3 4 5 6] - {1} 1 0 1* 5 ∞ 3 ∞ 1 1 1 1 1 {1,2} 2 1 5 3* 8 ∞ 1 1 2 2 1 {1,2,4} 4 3 - 5* - 6 7 1 1 2 4 4 {1,2,4, 3} 3 5 - - - 6* 7 1 1 2 4 4 {1,2,4, 3, 5} 5 6 - - - - 7* 1 1 2 4 4 {1,2,4, 3, 5, 6} 6 7 - - - - - 1 1 2 4 4 1 2 4 6 1 2 4 5 Đường đi ngắn nhất từ 1 6 có giá 7; vết 1 4 6
Đường đi ngắn nhất từ 1 5 có giá 6; vết 1 4 5
3.7.4. Thuật toán Floyd tìm đường đi ngắn nhất giữa mọi cặp đỉnh trên đồ thị 78 Với các giả thiết như đối với bài toán tìm đường đi ngắn nhất một nguồn một đích,
yêu cầu có khác hơn là xác định đường đi ngắn nhất giữa mọi cặp đỉnh của đồ thị. Thuật
sau được Floyd thiết kế và đưa ra theo kỹ thuật quy hoạch động và dựa trên nguyên lý tối
ưu của Bellman.
a. Tư tưởng
Nếu đỉnh k nằm trên đường đi ngắn nhất từ đỉnh i tới đỉnh j thì đoạn đường từ i tới k và từ
k tới j phải là đường đi ngắn nhất từ i tới k và từ k tới j tương ứng.
Do đó ta sử dụng ma trận A để lưu độ dài đường đi ngắn nhất giữa mọi cặp đỉnh.
Ban đầu ta đặt A[i,j] = C[i,j], tức là ban đầu A chứa độ dài đường đi trực tiếp (không đi
qua đỉnh nào cả).
Sau đó thực hiện n lần lặp, sau lần lặp thứ k, ma trận A sẽ chứa độ dài đường đi ngắn nhất
giữa mọi cặp đỉnh chỉ đi qua các đỉnh thuộc tập {1,2,..,k}. Như vậy, sau n lần lặp ta nhận
được ma trận A chứa độ dài các đường đi ngắn nhất giữa mọi cặp đỉnh của đồ thị.
Ký hiệu Ak là ma trận A sau lần lặp thứ k, tức là Ak[i,j] là độ dài đường đi ngắn nhất từ i
đến j chỉ đi qua các đỉnh thuộc {1, 2,.., k}. Ak[i,j] được tính theo công thức như sau:
Ak[i,j] = min {Ak -1[i,j], Ak-1[i,k] + Ak-1[k,j]}.
Trong quá trình lặp ta phải lưu lại vết đường đi, tức là đường đi ngắn nhất đi qua các đỉnh
nào. Khi đó ta sử dụng mảng phụ P[nxn], trong đó P[i,j] lưu đỉnh k nếu đường đi ngắn
nhất từ i đến j đi qua đỉnh k. Ban đầu P[i,j]=0 với mọi i,j, vì lúc đó đường đi ngắn nhất là
đường đi trực tiếp, không đi qua đỉnh nào cả. Với các phân tích như trên ta thấy ở bước lặp thứ k thì giá trị của ma trận A ở dòng k và
cột k là không thay đổi.
b. Thủ tục thuật toán
Procedure Floyd(G:đơn đồ thị, n đỉnh, có trọng số);
Var i,j, k: Integer;
Begin for i:=1 to n do for j:=1 to n do Begin A[i,j]:= C[i,j];
P[i,j]:= 0; End; for k:=1 to n do for i:=1 to n do if A[i,k] + A[k,j] < A[i,j] then for j:=1 to n do Begin A[i,j]:= A[i,k] + A[k,j];
P[i,j]:= k; End; 15 4 1 End;
Ví dụ 30 5 50 5 50 5 2 3 15 Cho đồ thị Tìm đường đi ngắn nhất giữa mọi cặp đỉnh của đồ thị. Giải: Ta có ma trận trọng số biểu diễn đồ thị + Bước 0(k = 0) 79 + Bước 1(k = 1) + Bước 2(k = 2) + Bước3 (k = 3) + Bước 4( k = 4) Nhìn vào bảng trên ta có đường đi ngắn nhất của một số cặp đỉnh như sau:
Đường đi ngắn nhất từ 1 đến 3 là 15 theo vết 124 3.
Vì C[1,3] = 15 và P[1,3] = 4; P[1,4] = 2, P[4,3] = 0
Đường đi ngắn nhất từ 2 đến 4 là 5, vết đường đi là trực tiếp.
Đường đi ngắn nhất từ 3 đến 4 là 40, vết đường đi là: 3 1 2 4
Nhận xét: Dễ dàng nhận thấy rằng thuật toán Floyd đòi hỏi thời gian thực hiện là O(n3)
đối với đồ thị n đỉnh.
3.8. Cây và cây khung của đồ thị 80 Năm 1857, nhà toán học người Anh Athur Cayley dùng cây để xác định những
dạng khác nhau của hợp chất hoá học. Cây hay được sử dụng trong tin học, người ta dùng
cây để xây dựng những thuật toán rất hiệu quả để định vị các phần tử trong một dạh sách.
Cây cũng dùng để xây dựng các mạng máy tính với chi phí rẻ nhất cho các đường điện
thoại nối các mấy phân tán. Dùng cây có thể mô hình các thủ tục mà để thi hành nó cần
dùng một dãy các quyết định. Vì vậy cây đặc biệt có giá trị khi nghiên cứu các thuật toán
sắp xếp. a a d c b b c g g e e f f 3.8.1. Cây và các tính chất cơ bản của cây
Định nghĩa 1: Cây là một đồ thị vô hướng liên thông và không chứa chu trình đơn.
Ví dụ: G1: Là cây G2: Không là cây 1 7 2 3 Nhận xét:
- Vì cây không chưa chu trình đơn nên cây không chứa cạnh bội, không chưa khuyên. Do
đó mọi cây là đồ thị đơn.
- Nếu đồ thị không có chu trình đơn và không liên thông thì gọi là rừng. Rừng là một đồ
thị mà mỗi thành phần liên thông của nó là một cây.
Ví dụ 8 10 9 12 13 4 6 5 11 Rừng a d b c g e f - Trong nhiều ứng dụng một đỉnh đặc biệt của cây được gọi là gốc và khi đã xác định rõ
gốc thì người ta gán cho mỗi một cạnh một hướng: Hướng từ gốc đi ra. Cây cùng với gốc
sinh ra một đồ thị có hướng gọi là cây có gốc.
Ví dụ: Cây có gốc a 81 - Giả sử T là một cây có gốc, nếu v là một đỉnh khác đỉnh gốc của T. Khi đó cha của đỉnh
v là u sao cho có một cạnh hướng từ u v và u được gọi là cha của v, v là con của u,
những đỉnh cùng cha gọi là các đỉnh anh em.
- Tổ tiên của một đỉnh khác đỉnh gốc là các đỉnh nằm trên đường đi từ gốc tới đỉnh này.
- Con cháu của một đỉnh v là các đỉnh có v như là tổ tiên. - Đỉnh có con được gọi là đỉnh trong
- Đỉnh không có con được gọi là lá
- Cây có gốc gọi là cây m - phân nếu tất cả các đỉnh trong của nó không có nhiều hơn m -
con
- Cây m - phân gọi là cây m - phân đầy đủ nếu tất cả các đỉnh trong của nó có m - con.
Với m=2 ta có cây nhị phân.
3.8.2. Các tính chất của cây
a. Định lý 1: Một đồ thị vô hướng là cây nếu giữa mọi cặp đỉnh của nó luôn tồn tại một
đường đi đơn duy nhất.
Chứng minh : Ta giả sử T là một cây, theo định nghĩa ta có T là một đồ thị liên thông không chứa
chu trình. Gọi u, v là hai đỉnh thuộc T, vì T là cây nên có một đường đi đơn giữa hai đỉnh
này (kết quả về tính liên thông của đồ thị vô hướng). Đường đi này là duy nhất vì nếu có
đường đi thứ hai từ u tới v thì đường đi tạo bởi hợp của đường đi thứ nhất từ u tới v và
đường đi từ v tới u nhận được bằng cách đảo ngược đường đi thứ hai từ u tới v sẽ tạo ra
một chu trình và tạo ra một chu trình đơn trong T. Vì thế giữa 2 đỉnh bất kỳ của T luôn có
đường đi đơn duy nhất. c. Định lý sáu mệnh đề tương đương: Giả sử T là một cây, khi đó các mệnh đề Ta giả sử, giữa 2 đỉnh bất kỳ của đồ thị T luông có đường đi đơn duy nhất, khi đó
T là liên thông. Tiếp theo T không thể chứa chu trình đơn, giả sử ngược lại T có chu trình
đơn chứa 2 đỉnh u, v của T. Khi đó có 2 đường đi giữa u và v, vì đường đi thứ nhất chính
là phần của chu trình từ u đến v, đường thứ hai là phần còn lại của chu trình nhưng theo
thứ tự ngược lại, tứ là giữa u và v có hai đường đi đơn, điều này là vô lý. Do đó T là đồ
thị liên thông và không chứa chu trình đơn hay T là một cây.
b. Định lý 2: Cây với n đỉnh có đúng (n -1) cạnh
Chứng minh : Chọn đỉnh r làm gốc của cây. Ta xây dựng phép tương ứng một-một giữa
các cạnh với các đỉnh khác r bằng cách gán đỉnh cuối của một cạnh với chính cạnh này.
Vì có n-1 đỉnh khác r nên ta có n-1 cạnh.
sau 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.
5. Hai đỉnh bất kỳ của T được nối với nhau bởi đúng một đường đi đơn (dây truyền). 6. T không chứa chu trình nhưng nếu thêm vào một cạnh nối hai đỉnh không kề nhau
thì xuất hiện duy nhất một chu trình. 82 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 là cây T không chứa chu trình, ta sẽ chứng minh có n-1
cạnh. Ta chứng minh bằng quy nạp theo số đỉnh n khẳng định: Số cạnh của cây có n đỉnh
là n-1 cạnh.
Thật vậy với n=1 suy ra đúng.
Với n >1 ta thấy rằng trong mọi cây T có n đỉnh luôn tìm được một đỉnh treo (nghĩa là
đỉnh có bậc là 1). 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 (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ị, loại bỏ v1 và cạnh b c b c b c a a a d d d e e e (v1, v2) khỏi T ta thu được cây có n-1 đỉnh mà theo giả thiết quy 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 không chứa chu trình nên mỗi Ti (i=1..k) cũng không chứa chu trình. Vì
thế mỗi Ti là cây. Do đó nếu gọi n(Ti) và e(Ti) theo thứ tự là số các đỉnh và cạnh của Ti, ta
có:
e(Ti) = n(Ti) - 1; i=1..k
Suy ra
n -1 =e(T)= e(T1) + e(T2) +...+e(Tk)
=n(T1) + n(2) + ...+n(Tk) - k
=n(T)-k < n-1
Mâu thuẫn chứng tỏ T liên thông.
(3) =>(4) Việc loại bỏ một cạnh bất kỳ khỏi T dẫn đến đồ thị với n đỉnh và n-2 cạnh rõ
ràng là đồ thị không liên thông. Vậy mọi cạnh trong T đều là cầu.
(4) =>(5) Do T 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 T có hai đường đi đơn khác nhau nối chúng thì từ đó 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ứa chu trình, bởi vì nếu có chu trình thì ta tìm ra đượ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 nào đó của T. Khi đó cạnh này cùng với đường đi đơn nối hai đỉnh đó sẽ tạo thành
chu trình trong T. Chu trình tìm đượ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 nhất hai 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 suy ra điều phải chứng
minh.
3.8.3 Cây khung của đồ thị
Định nghĩa 2: Giả sử G = (V, E) là một đồ 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.
Một đơn đồ thị có cây khung sẽ là một đồ thị liên thông vì có đường đi trong cây khung
giữa hai đỉnh bất kỳ. Điều ngược lại cũng đúng, tức là mọi đồ thị liên thông đều có cây
khung.
Để xây dựng cây khung, có thể áp dụng các thuật toán duyệt đồ thị tương ứng. Cây khung
ứng với phép duyệt theo chiều rộng được gọi là cây khung theo bề rộng, tương tự có cây
khung theo chiều sâu nếu dùng phép duyệt theo chiều sâu.
Ví dụ Đồ thị và các cây khung của nó 83 a.Bài toán cây khung nhỏ nhất Bài toán cây khung nhỏ nhất có khá nhiều ứng dụng trong thực tế, các ứng dụng rất thông
dụng và được giải quyết theo các thuật toán của lý thuyết đồ thị, chẳng hạn ta xét một số
bài toán thực tế sau:
Bài toán xây dựng hệ thống đường sắt: Cần xây dựng một hệ thống đường sắt nối n thành phố sao cho hành khách có thể
đi từ bất kỳ một thành phố nào đến bất kỳ một trong các thành phố còn lại. Mục tiêu là
phải xây dựng sao cho chi phí xây dựng hệ thống đường sắt là nhỏ nhất.
Bài toán nối mạng máy tính: Cần nối mạng một hệ thống mạng truyền thông nối n trung tâm máy tính với nhau.
Bất kỳ hai trung tâm nào cũng có thể được kết nối với nhau bằng điện thoại. Cần phải kết
nối như thế nào để đảm bảo giữa hai trung tâm máy tính bất kỳ luôn có đường truyền
thông sao cho tổng số tiền thuê bao của toàn mạng là tối thiểu.
Để giải quyết hiệu quả các bài toán thực tế trên, cần có một hệ thống lý thuyết và các
thuật toán nghiên cứu về cây khung và cây khung nhỏ nhất.
Định nghĩa 3: Cây khung nhỏ nhất trong một đồ thị liên thông có trọng số là một cây
khung có tổng trọng số trên các cạnh của nó là nhỏ nhất. Hay cho G = (V, E) là đồ thị vô hướng, liên thông có trọng số, mỗi cạnh e E có trọng số m(e) 0. Giả sử T = (VT, ET) là cây khung của đồ thị G. Ta gọi (m(T) là tổng trọng số trên các cạnh tạo thành cây khung T) Bài toán đặt ra là trong số các cây khung của đồ thị G, hãy tìm cây khung có m(T)
nhỏ nhất. Cây khung như vậy được gọi là cây khung nhỏ nhất của đồ thị và bài toán đặt ra
được gọi là bài toán tìm cây khung nhỏ nhất.Trong phần này, chúng ta nghiên cứu 2 thuật
toán xây dựng cây khung nhỏ nhất. Cả hai thuật toán đều được tiến hành bằng cách gép
các cạnh có trọng số nhỏ nhất trong số các cạnh có một tính chất nào đó mà chưa được
dùng, các thuật toán này được thiết kế theo kỹ thuật tham lam tìm ra lời giải tối ưu cho bài
toán cần giải quyết.
b.Thuật toán KRUSKAL. Thuật toán do Joseph Kruskal phát minh năm 1956, ý tưởng của thuật toán được
xuất hiện sớm hơn. Thuật toán được thực hiện bằng cách chọn cạnh có trọng số nhỏ nhất
của đồ thị đưa vào cây khung, sau đó lần lượt ghép thêm vào cây khung cần xây dựng các
cạnh có trọng số tối thiểu và không tạo ra chu trình với các cạnh đã chọn. Thuật toán dừng
khi n-1 cạnh đã được chọn ( với đồ thị G có n đỉnh) Với đồ thị G=(V,E); V=n, ta xây dựng cây khung nhỏ nhất T=( VT, ET); điều
quan trọng là xây dựng được tập cạnh vì ta đã có VT=V, ta sẽ xây dựng tập các cạnh ET
của T dần từng bước. Xuất phát từ ET bằng rỗng, trong mỗi bước lặp ta sẽ chọn một cạnh
(u,v) "tốt nhất", nghĩa là cạnh được chọn ở mỗi bước phải là cạnh có trọng số nhỏ nhất và
không tạo thành chu trình với các cạnh đã chọn.
Thuật toán KRUSKAL: Input: Đồ thị G = (V,E);
Output: Tập các cạnh ET của cây khung nhỏ nhất. Tư tưởng Bước 1: Sắp xếp các cạnh của đồ thị G theo thứ tự tăng dần của trọng số cạnh Cij
Bước 2: Chọn cạnh có trọng số nhỏ nhất đưa vào tập cạnh ET 84 Bước 3: Lần lượt ghép thêm vào tập ET các cạnh có trọng số nhỏ nhất và không tạo
thành chu trình với các cạnh đã ghép trong ET. Thuật toán dừng khi (n - 1) cạnh đã được ghép vào cây khung. Thủ tục của thuật toán Procedure Kruskal(G: liên thông, n đỉnh, có trọng số); BEGIN
1. Sắp xếp các cạnh của đồ thị theo chiều tăng dần của trọng số, ET:=
2. For i:= 1 to n - 1 do
Begin e = End; END; Chú ý:
Trong quá trình xây dựng cây khung theo thuật toán Kruskal thì việc kiểm soát không tạo
thành chu trình là khá quan trọng. Việc kiểm soát được thực hiện dưa trên cơ sở sau:
Gọi A là tập đỉnh của cây khung, giả sử A = A1 A2 … Ak với Ai là liên thông
(i = 1,..,k), Ai Aj , khi đó sẽ liên thông + Nếu (vi, vj) Aj thì nếu kết nạp (vi, vj) vào cây khung thì sẽ tạo thành chu trình.
+ Nếu vi Aj và vj Am thì
+ Nếu vi, vj Ak với k thì phát sinh ra một tập mới A’ 1 4 4 Mỗi bài toán có thể tồn tại nhiều cây khung nhỏ nhất, điều nảy sảy ra nếu các cạnh có
cùng trọng số với nhau.
Bài toán tìm cây khung lớn nhất có thể đưa về bài toán tìm cây khung nhỏ nhất bằng cách
đổi dấu tất cả các trọng số của Ci,j, hoặc có thể cài đặt một cách độc lập bằng cách kết nạp
dần vào cây từ cạnh lớn đến cạnh nhỏ nhất.
Khối lượng tính toán nhiều nhất của thuật toán là ở bước sắp xếp các cạnh, vì vậy độ phức
tạp tính toán của thuật toán là O(n2).
Ví dụ 1 3 2 8 7 4 4 8 6 6 4 5 9 9 18 4 10 7 Cho đồ thị G như hình vẽ Thực hiện theo thuật toán như sau 85 STT Cạnh Trọng số A T 1 {1,8} (1,8) (1,8) 1 2 {1,3,8} (1,8)(3,8) (3,8) 2 3 {1,2,3,8} (1,8)(3,8)(8,2) (8,2) 3 4 Loại vì tạo thành chu trình (1,3) 4 5 Loại vì tạo thành chu trình (1,2) 4 6 {1,2,3,6,8} (1,8)(3,8)(8,2) (3,6) (3,6) 4 7 Loại vì tạo thành chu trình (6,8) 4 8 {1,2,3,6,7,8} (1,8)(3,8)(8,2) (3,6) (6,7) (6,7) 4 9 {1,2,3,5,6,7,8} (1,8)(3,8)(8,2) (3,6) (6,7) (8,5) (8,5) 6 10 {1,2,3,4,5,6,7,8} (1,8)(3,8)(8,2) (3,6) (6,7) (8,5) (8,4) (8,4) 7 11 (2,4) 8 12 (5,6) 9 13 (5,4) 9 14 (4,7) 10 15 (5,7) 18 Vậy: Cây khung nhỏ nhất của đồ thị là T=(V, ET) với 1 1 2 3 2 8 3 6 4 7 5 6 4 4 7 ET = {(1,8),(3,8),(8,2), (3,6), (6,7), (8,5), (8,4)} 86 Giá nhỏ nhất bằng 27
Thuật toán Kruskal làm việc kém hiệu quả đối với những đồ thị đầy đủ (đồ thị có số cạnh
là n(n-1)/2). Trong trường hợp đó người ta xây dựng một thuật toán hiệu quả hơn đó là
thuật toán Prim. Thuật toán Prim còn được gọi là thuật toán lân cận gần nhất ( người láng
giềng gần nhất). c. Thuật toán Prim
Tư tưởng: Thuật toán bắt đầu bằng việc lựa chọn một cạnh bất kỳ có trọng số nhỏ nhất
và đặt nó vào cây khung, sau đó lần lượt ghép vào cây các cạnh có trọng số tối thiểu liên
thuộc với một đỉnh của cây và không tạo ra chu trình trong cây. Thuật toán sẽ dừng khi đã
ghép được n-1 cạnh vào cây. d[v]:= C[u,v];
near[v]:= u; Cụ thể hơn là xuất phát từ một đỉnh u bất kỳ của đồ thị người ta nối đỉnh lân cận
gần u nhất là s (u, s) có trọng số nhỏ nhất, sau đó tiếp tục trong số mỗi cạnh liên thuộc
với 2 đỉnh u và s cạnh có trọng số nhỏ nhất để ghép vào cây khung T. Quá trình tiếp tục
cho đến khi ta thu được một bộ cây gồm n đỉnh và (n - 1) cạnh. Cây này chính là cây
khung nhỏ nhất cần xây dựng.
Thuật toán
Giả sử G = (V, E) cho dưới dạng ma trận trọng số Cij (i, j = 1,2,..,n). Ta cần xây dựng cây
khung nhỏ nhất T=( V, ET), để thuận tiện cho việc lập chương trình ta gán nhãn cho các
đỉnh của đồ thị, nhãn của mỗi đỉnh v có hai phần: v[d[v],near[v]]
Trong đó: d[v] lưu độ dài nhỏ nhất trong số các độ dài cạnh nối đỉnh v với các đỉnh thuộc
ET
near[v]: Ghi nhận đỉnh của cây khung gần v nhất
Thuật toán Prim được mô tả đầy đủ trong thủ tục sau:
Procedure Prim (G:đơn đồ thị liên thông, n đỉnh, có trọng số ); BEGIN
1. Xuất phát u V bất kỳ; VT:= {u}; ET:=
d[u]:= 0; near[u]:= u; {gán nhãn cho đỉnh đầu tiên u[0,u]}
for v V- VT
Begin
End;
2. d[v]:= C[s,v];
near[v]:=s; End; 87 end;
END;
Nhận xét: - Sự giống nhau giữa thuật toán Prim và Kruskal là cả hai đều là thuật toán tìm cây khung nhỏ nhất. 1 4 5 1 5 6 4 5 2 5 4 4 3 2 3 7 8 9 6 7 - Sự khác nhau giữa thuật toán Prim và thuật toán Kruskal: Trong thuật toán Prim
ta chọn các cạnh có trọng số tối thiểu, liên thuộc với các đỉnh đã thuộc cây và không tạo
ra chu trình. Trong khi đó thuật toán Kruskal sẽ là chọn các cạnh có trọng số tối thiểu mà
không nhất thiết phải liên thuộc với các đỉnh của cây và không tạo thành chu trình.
Ví dụ: Tìm cây khung nhỏ nhất của đồ thị sau Giải: Lập một bảng để ghi nhãn của các đỉnh, đỉnh đánh dấu * là đỉnh được chọn để bổ sung vào cây khung. 1 2 3 4 5 6 7 ET VT [0,1]* [5,1] [4,1] [1,1]* {1} [,1] [,1] [,1] [5,1] [4,5]* [4,1] {1,5} {(5,1)} - - [,1] [,1] [4,3]* [7,3] [8,3] {1,5,3} {(5,1);(3,5)} - - [4,1] - - - - [4,1] - [3,2]* [8,3] {1,5,3,2} {(5,1);(3,5);(2,3)} - - - [4,1]* - - [8,3] {1,5,3,2,6} {(5,1);(3,5);(2,3); (6,2)} - - - - - - [2,4]* {1,5,3,2,6,4} {(5,1);(3,5);(2,3); (6,2);(4,1)} - - - - - - - {1,5,3,2,6,4,7} {(5,1);(3,5);(2,3); 88 (6,2);(4,1);(7,4)} 1 4 Như vậy cây khung nhỏ nhất có dạng: 1 4 5 T=(V,ET) với 2 2 4 4 7 3 ET={(5,1);(3,5);(2,3);(6,2);(4,1);(7,4)} 3 6 Giá nhỏ nhất: 18 3.8.4. Các phương pháp duyệt trên cây
Cây có gốc và được sắp thứ tự thường được dùng để lưu trữ thông tin. Chúng ta cần có
cách duyệt cây hay ‘thăm’ các đỉnh trên cây, sao cho mỗi đỉnh chỉ được thăm một lần. A D C B H G E F Các thủ tục duyệt tất cả các đỉnh của cây có gốc và được sắp thứ tự đều dựa trên
việc sắp thứ tự các đỉnh con. Trong các cây có gốc và được sắp thứ tự, khi vẽ đồ thị có
hướng của chúng, các con của một đỉnh trong được thể hiện từ trái sang phải.
Các thuật toán duyệt cây
Định nghĩa 1: Giả sử T là một cây có gốc và được sắp thứ tự với gốc r. Nếu T chỉ có r thì
r là cách duyệt theo thứ tự trước (Preorder) của T. Nếu không, thì gọi T1, T2, ..,Tn là các
cây con tại r từ trái qua phải của T. Duyệt theo thứ tự trước sẽ thăm r đầu tiên. Tiếp tục
duyệt cây con T1 theo thứ tự trước, sau đó duyệt cây con T2 theo kiểu thứ tự trước, cứ như
vậy cho đến khi Tn được duyệt theo thứ tự trước.
Ví dụ: Thứ tự duyệt theo thứ tự trước của cây là A B E F C G D H 89 Định nghĩa 2: Giả sử T là một cây có gốc và được sắp thứ tự với gốc r. Nếu T chỉ có r thì
r là cách duyệt theo thứ tự giữa (Inorder) của T. Nếu không, thì gọi T1, T2, ..,Tn là các cây
con tại r từ trái qua phải của T. Duyệt theo thứ tự giữa sẽ bắt đầu bằng việc duyệt T1 theo
thứ tự giữa, sau đó thăm r. Tiếp tục duyệt T2 theo thứ tự giữa, tiếp tục duyệt T3 theo thứ tự
giữa, cứ như vậy cho đến khi Tn được duyệt theo thứ tự giữa.
Ví dụ: Thứ tự duyệt theo thứ tự giữa của cây là E B F A G C H D
Định nghĩa 3: Giả sử T là một cây có gốc và được sắp thứ tự với gốc r. Nếu T chỉ có r thì
r là cách duyệt theo thứ tự sau (Postorder) của T. Nếu không, thì gọi T1, T2, ..,Tn là các
cây con tại r từ trái qua phải của T. Duyệt theo thứ tự sau sẽ bắt đầu bằng việc duyệt T1
theo thứ tự sau, sau đó duyệt T2 theo thứ tự sau, cứ như vậy cho đến khi Tn được duyệt
theo thứ tự sau và cuối cùng kết thức bằng việc thăm r.
Ví dụ: Thứ tự duyệt theo thứ tự sau của cây là E F B G C H D A TÀI LIỆU THAM KHẢO [1] K.H. Rosen, Toán rời rạc và ứng dụng trong tin học, KHKT, 1999 [2] Đỗ Đức Giáo, Toán học rời rạc, Đại học quốc gia Hà Nội, 1999 [3] Đinh Mạnh Tường, Cấu trúc dữ liệu và giải thuật, NXB Giáo dục, 2002 [4] Đỗ Đức Giáo, Bài tập Toán học rời rạc, Đại học quốc gia Hà Nội, 2002 [5] Nguyễn Tô Thành, Nguyễn Đức Nghĩa, Toán rời rạc, ĐH Bách Khoa Hà Nội, 1997 90 Thái nguyên, ngày 03 tháng 02 năm 2015X
XX
X
X
H
Với đồ thị như hình vẽ thì thứ tự duyệt đồ thị theo chiều rộng:
Xuất phát từ đỉnh A: A B C D F E G H
Xuất phát từ đỉnh D: D B C F A E G H
.1.1 3.3.3. Thuật toán duyệt đồ thị theo chiều sâu (DFS: Depth First Search)
a. Nguyên tắc duyệt
Chọn một đỉnh v0 của đồ thị làm đỉnh xuất phát
Thăm đỉnh v0, sau đó nếu v0 có đỉnh lân cận là v mà chưa được thăm thì quá trình diễn ra
tương tự như đối với v0.
H
Với đồ thị như hình vẽ thì thứ tự duyệt đồ thị theo chiều sâu:
Xuất phát từ đỉnh A: A B C D F E G H
Xuất phát từ đỉnh D: D B A C F E G H
3.4. Một số đơn đồ thị đặc biệt
3.4.1. Đồ thị đầy đủ:
Đồ thị đầy đủ n đỉnh, ký hiệu bởi Kn là đơn đồ thị vô hướng mà giữa hai đỉnh bất kỳ của
nó luôn có cạnh nối
e
Thuật toán liệt kê các chu trình Hamilton:
Thuật toán liệt kê tất cả các chu trình Hamilton của đồ thị, dựa trên cơ sở thuật toán quay
lui.
![Bài giảng Toán rời rạc 1: Bài toán đếm - Ngô Xuân Bách [Mới nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2024/20241231/tambang1206/135x160/431735607183.jpg)
![Đề thi kết thúc học phần Nguyên lí Hóa học 2 [mới nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2025/20251014/anhinhduyet000/135x160/69761760428591.jpg)
