Bài giảng Toán rời rạc (Chuẩn kiến thức)

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 TÀI LIỆU THAM KHẢO 90 2 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: xA (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: xA (x không thuộc A). 1.1.2.Một số tập hợp đặc biệt a.Tập con 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: AB hoặc BA 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*NZQR Hai tập A và B được gọi là bằng nhau nếu AB và BA. Ký hiệu là A=B Nếu AB và AB 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 AB 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 | AX} 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 AX đặt AC = X\A hay AXX \ gọi là phần bù của A trong X. Ta có: AAC = X hay XAA  ; AAC =  hay  AA  3 Theo tính chất ta có: (AB)C = ACBC (AB)C = ACBC 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 = {xX | P(x)} Ví dụ : A = {xR | x2 – 4x + 3 = 0} B = {nN | n là ước của 20} C = {nN* | 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} 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à AB, như vậy AB = {a | aA hoặc aB}. 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à AB, như vậy AB = {a | aA và aB}. Nếu không có phần tử nào vừa thuộc A vừa thuộc B thì AB = . Trong trường hơp này ta nói A và B rời nhau hoặc không giao nhau. 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. N A .2 .10 .8 .4 .6 2 A\B = {a | aA và aB}. 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à AB. A  B = {(A\B) (B\A)}. Ví dụ 1: Cho A ={0, 1, 2, 4, 6} B = {1, 3, 5, 6} AB = {0, 1, 2, 3, 4, 5, 6} AB = {0,6} A\B = {1, 2, 4} B\A = {3, 5} AB = {1, 2, 4, 3, 5} Ví dụ 2: A = {xN | x chia hết cho 2}; B = {xN | x chia hết cho 3} AB = {xN | 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: AB = BA và AB = BA 2.Tính chất kết hợp: (AB)C = A(BC) (AB)C = A(BC) 3.Tính chất phân phối: A(BC) = (AB)(AC) A(BC) = (AB)(AC) 4.Luật đối ngẫu Demorgan: BABA   BABA   5.Luật nuốt: nếu AB thì AB = B, AB = 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(BC) = (AB)(AC) Thật vậy với aA(BC)  aA hoặc aBC  aA hoặc aB và aC  aA hoặc aB và aA hoặc aC  aAB và aAC  a (AB)(AC) Tức là có tính chất 3. Lưu ý: Vì A và AA với A nên: A = A, A = , AA = A, AA = 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ó:  A1A2 A3 = (A1A2)A3  ni n i AAAA ... 21 1    = nn AAAA   )... ( 121  A1A2 A3 = (A1A2)A3  ni n i AAAA ... 21 1    = nn AAAA   )... ( 121 b.Mở rộng tính chất 3 Cho các tập hợp X, A1, A2,, An ta có: 3   i n i i n i AXAX         11    i n i i n i AXAX         11  c.Mở rộng tính chất 4 Cho các tập hợp X, A1, A2,, An ta có:  i n i i n i AA 11     i n i i n i AA 11    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 aA, bB. 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 AB gồm các cặp (a, b) với aA, bB AB = {(a,b) | aA, bB} Tích đề các AA ký hiệu là A2 (Bình phương đề các) Ví dụ: = {1, 2, 3}; B = {a, b} thì: AB = {(1, a); (1, b); (2, a); (2, b); (3, a); (3, b)} BA = {(a, 1); (a, 2); (a, 3); (b, 1); (b, 2); (b, 3)} AA = A2 = {(1, 1); (1, 2); (1, 3); (2, 1); (2, 2); (2, 3); (3, 1); (3, 2); (3, 3)} BB = 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 =   nnni n i AaAaaaA   ,,/,, 111 1  Hai bộ (a1, a2, , an) và (b1,b2, , bn) gọi là bằng nhau nếu: a1 = b1; a2 = b2 ; ; an = bn Nếu A1 = A2 = = An thì ký hiệu n i n i AA  1 và gọi là luỹ thừa đề các bậc n của tập hợp 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 Định lý 1: Cho A, B là hai tập hữu hạn, khi đó: 1. |AB| = |A| + |B| – |AB| 2. |A\B| = |A| – |AB| 4 3. |AB| = |A| + |B| – 2|AB| 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 AB = : AB = {a1, a2, , am, b1, b2, , bn} do đó |AB| = m + n = |A| + |B| Trường hợp AB có k phần tử. Đặt AB = {a1, a2, , ak}. Khi đó: A = {a1, a2, , ak, ak+1, , am}; B = {b1, b2, , bk, bk+1,, bn} Vì AB = {a1, a2, , ak, ak+1, , am, bk+1,, bn} nên: |AB| = m + (n – k) = m + n – k = |A| + |B| – |AB| 1.Do A = (A\B)  (AB) mà (A\B)  (AB) =  nên theo (1) ta có: |A| = |A\B| + |AB|  |A\B| = |A| – |AB| 2.Vì (A\B)(B\A) =  nên áp dụng (1) và sau đó áp dụng (2) ta có: |AB| = |(A\B)(B\A)| = |A\B| + |B\A| = |A| – |AB| + |B| – |BA| = |A| + |B| – 2|AB| Lưu ý theo tính chất (2) nếu BA 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à AiAj = . Với ij. Theo định lý 1, nếu A1A2 =  thì |A1A2|= |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 đó, |A1A2 An| = |A1| + |A2| + + |An| Định lý 3: Với  tập hợp A, B ta có: |AB| = |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ì AB = )}({ 1 Bai m i    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ó: |AB| = |{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 đó |A1A2 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 tử có quan hệ với nhau là một phần tử của   m m AAAA  . Các nhóm gồm m phần tử 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ì {(a,b) , }R a A b B   . Nếu ( , )a b R hay aRb thì ta nói a,b có R-quan hệ với nhau. Nếu ( , )a b R thì ta 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ệ. 5 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 xA ta có xRx ii.Tính chất đối xứng nếu: vớix, yA: xRy thì yRx. iii.Tính chất phản đối xứng nếu : vớix, yA: xRy  yRx thì x=y. iv.Tính chất bắc cầu nếu: vớix, y, zA: 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, bA :aRb  a+b =2k kZ, khi đó: 1. R có tính chất phản xạ: aA ta có a+a=2a  aRa hay (a,a)R 2. R có tính chất đối xứng: a, bA 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 xy (x tương đương y). Vậy  là một quan hệ tương đương trên A nếu với x, y, zA ta có:  xx (tính phản xạ)  xy  yx (tính đối xứng)  xy  yz  xz (tính bắc cầu) 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, bA :aRb  a-b =3k kZ, khi đó R là quan hệ tương đương, thực vậy: 1. R có tính chất phản xạ: aA ta có a-a=0=3.0  aRa hay (a,a)R 2. R có tính chất đối xứng: a, bA và a-b=3k b-a=3(-k)=3k’ bRa 6 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 xA, tập      yRxxyxx R | gọi là lớp tương đương chứa x. Đị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  x và  y có  x   y =  ta chỉ cần chứng minh  x =  y . Chọn z   x   y vì z   x nên xRz, vì z   y nên zRy.  t   x  tRx  tRy  t   y . Vậy  x =  y . Từ định lý ta có:       yxxy  và    yxxRy   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à:    ZkkR  |30 các số chia hết cho 3    ZkkR  |131 các số chia cho 3 dư 1    ZkkR  |232 các số chia cho 3 dư 2 Vậy Z =       RRR 2,1,0 Quan hệ tương đương trên gọi là quan hệ đồng dư theo modul 3, ký hiệu là ab (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 xy (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ý hiệu là (A, ). 7 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 ( ) trong tập P(A) = 2 A ( tập các tập con của tập A) là quan 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. 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 8 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à  p hay p . Bảng giá trị chân lý của phép phủ định được cho bởi bảng: p p 0 1 1 0 Ví dụ 1: Cho mệnh đề p: 5<3  p : 5 3 Giá trị chân lý của p là 0 Giá trị chân lý của p là 1 Ví dụ 2: Chỉ ra rằng p 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) p p p 0 1 0 1 0 1 Qua bảng giá trị chân lý của mệnh đề ta nhận thấy rằng p và p luôn có cùng giá trị chân lý nên ta có thể nói rằng là p tương đương logic với p b.Phép hội Cho p, q là 2 mệnh đề. Ta ký hiệu mệnh đề “p và q” là pq. Phép hội được định nghĩa bởi bảng giá trị chân lý sau đây. p q pq 0 0 0 0 1 0 1 0 0 1 1 1 9 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ó: pq = 0; pr = 1 qr = 0; 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à pp luôn có cùng giá trị chân lý. 2.Mệnh đề p  p luôn có giá trị chân lý bằng 0 (tức là một mệnh đề luôn sai) 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à pq. Phép tuyển hay phép hoặc được định nghĩa bởi bảng chân lý sau: p q pq 0 0 0 0 1 1 1 0 1 1 1 1 Ví dụ 1: Với các mệnh đề p, q, r đã cho ta có: pq = 1; pr = 1 Ví dụ 2: Lập bảng giá trị chân lý ta luôn có mệnh đề pp là luôn đúng. 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 : pp là luôn đúng  nó là hằng đúng. p  p 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 q p XOR q 0 0 0 0 1 1 1 0 1 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: p q p  q 0 0 1 0 1 1 1 0 0 1 1 1 10 Ví dụ : với nN, 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) pq  (2) qp  (3) pq  (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/    pqqp  ii/    qppq  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 q p  q 0 0 1 0 1 0 1 0 0 1 1 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. ,  Trong đó các toán tử liệt kê trên cùng dòng có cùng độ ưu tiên. Ví dụ : 1. yx có nghĩa là   yx  2. qpyx  có nghĩa      qpyx  1.3.3.Biểu thức logic (công thức logic) 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ố 11 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ì P , QP  , QP  , QP  , QP  là 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) =     rqpx  là một biểu thức logic với các biến mệnh đề x, p, q, r. 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    rqrprqp  Giải: ta lập bảng giá trị chân lý như sau: p q r qp  rp  rq  rqp     rqrp  0 0 0 0 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 1 1 1 Nhìn vào giá trị chân lý trên 2 cột cuối ta thấy:    rqrprqp  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ụ :  ( rqp  ) được viết là pq  r    rqp  được viết là rqp  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ụ : 1 pp nên ta có một luật = pp . Luật = pp gọi là luật bài trung: Trong hai mệnh đề phủ định lẫn nhau, có ít nhất một mệnh đề đúng. 12 Các luật logic cơ bản 1. Luật phủ định kép: pp  2. Luật giao hoán: p q q p   , p q q p   3. Luật kết hợp:   rqprqp  )( ,   rqprqp  )( 4. Luật phân phối:    rqqprqp  )( ,    rqqprqp  )( 5. Luật Demorgan: p q p q   , p q p q   6. Luật về mối liên hệ giữa p với chính nó, với p , với 0 và 1: pppppp  ppp  0 00 11 1  ppp 1 0  pppp 7. Luật kéo theo: qpqp  8. Luật tương đương:    p q p q q p     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    rqrprqp  Ta biến đổi vế trái về vế phải như sau: Vế trái   )()()()()( rqrprqrprqprqp Vế phả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 đề 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 ii pq  (i = 1 n). Ví dụ: Biểu thức xyz hoặc zyx  hoặc zyx  là các biểu thức hội cơ bản theo 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 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.        zyxzyxzyxzyxE ,,        4321432143214321 ,,, ppppppppppppppppF  Đị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} 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:      , ,E x y z x z x y             yzxxzxyxzxzyxE ,,    zyxzx  13     zyxzyyx       zyxzyxzyx     zyxzyx  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: F = q1 q2   qn với qi = pi hoặc ii pq  (i = 1 n). Ví dụ: Biểu thức x y z hoặc zyx  hoặc zyx  là các biểu thức tuyển cơ bản theo 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.        zyxzyxzyxzyxE ,,        4321432143214321 ,,, ppppppppppppppppF  Đị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:      tzzyyxtzyxE ,,,      tzyyxxttzyxxttzzyxtzyxE ,,,       tzyxtzyxtzyxtzyxtzyxtzyx        tzyxtzyxtzyxtzyxtzyxtzyx        tzyxtzyxtzyxtzyxtzyxtzyx    tzyxtzyx  Ví dụ 2: Tìm chính tắc tuyển của biểu thức:    x y z y       yzyx      yyxzyx   yyyxzyzx   yxzyzx        zzyxzyxxzyyx   zyxyzxzyxzyxzyxzyx   yzxzyxzyxzyx  1.3.5.Vị từ, lượng từ a.Vị từ (Hàm mệnh đề) 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 xX 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. 14 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ể aX 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 mN* 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 EP(x)={ aX P(a) là mệnh đề đúng} Ví dụ: 1. P(x): x 2 -6x+5=0 với x R có EP(x)={ 1,5} 2. P(x): x 2 -6x+50 với x R có EP(x)= ),5()1,(  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): x 2+1>0 là hằng đúng trên R 2. P(x): x 2+1=0 là hằng sai trên R 3. P(x): 3x-4=0 là thực hiện được t...a nhận thấy: a nếu b=0 30 USCLN(a, b)= USCLN(b, phần dư a/b ) nếu b0 Do vậy hàm USCLN có thể viết đệ qui như sau: Function USCLN(a, b:Integer): Integer; Begin If b=0 then uscln:=a Else Uscln:=uscln(b, a mod b); End; Hay Function USCLN(a, b:Integer): Integer; Var r: integer; Begin r:= a mod b; If r=0 then uscln:=a Else Uscln:=uscln(b, r); End; 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 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,... 31 1 nếu n  2 fn – 2 + fn - 1 nếu n > 2 Dãy số 1 1 2 3 5 8 13 21được gọi là dãy số Fibonaci Xây dựng hàm đệ quy tính fn Function Fibo (n: byte): Word; Begin If n <= 2 then Fibo: = 1 Else Fibo: = Fibo (n - 1) + Fibo (n - 2); End; 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 BA 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 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 fn = 32 If n = 1 then writeln(A, ‘’,B) Else Begin chuyen (n - 1, A, C, B); chuyen (1, A, B, C); chuyen (n - 1, C, B, A); 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 (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 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 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: 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). 0 0 1 1 1 0 1 0 0 1 0 1 1 000 001 010 011 100 101 110 111 33 Để 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  do if then Begin If i = n then else Try (i+1); End; End; 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. 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, 34 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); 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 35 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 dùng mảng logic b: array[1..n] of Boolean; - 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 Else Try (i+1); {xây dựng thành phần thứ i + 1} b[j]: = True; {trả lại trạng thái cũ} End; End; 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; 36 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 : 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 (ij ,i,j=1,..,n) thì sẽ có tất cả nmmm  ...21 cách chọn đối tượng naaa  ...21 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. 37 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 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ả nmmm  ...21 cách chọn đối tượng ),...,,( 21 naaa 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  A2  ...  Am ) = N(A1) N(A2) ...N(Am) 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? k:= 0; for i1 :=1 to n1 for i2:=1 to n2 ... for im :=1 to nm Do k:=k+1; 38 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 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  kN / vật Chứng minh: Giả sử không có hộp nào trong k hộp chứa nhiều hơn  kN / = 1 vật. Khi đó tổng số vật được chứa trong các hộp nhiều nhất là: k(  kN / -1) < k(((N/k)+1)-1) = N (*) trong đó ta đã dùng bất đẳng thức  kN / < (N/k) + 1. Bất đẳng thức (*) trái với giả thiết. 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  12/48 =4 người cùng tháng sinh X X XX X 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ó  38/677 =18 phòng học 2.4.5. Nguyên lý bù trừ Một số bài toán đếm phức tạp hơn, được dựa vào nguyên lý tổng quát của nguyên lý cộng. Nếu không có giả thiết 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 đó N(A1A2  ...Am) = N1 – N2 +... +(-1) m-1 Nm 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  C) = N1 – N2 + N3 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  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 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  C) = N(A) + N(B) + N(C) - N(AB) - N(A C) - N(BC) + 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  C) =500 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 N là số phần tử cần đếm, N là số phần tử của X, ta có: N = N - N(A1A2  ...Am) = N - N1 + N2 -... +(-1) m Nm ( nguyên lý bù 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 40 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. Mặt khác, ta có 1!=1 Vậy P1=1! Hay công thức (1) đúng với n=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! 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: knA là số chỉnh hợp chập k của tập A gồm n phần tử. Định lý 1: Số chỉnh hợp chập k của tập có n phần tử là knA = n(n - 1)(n - 2)...(n – k + 1) = )!( ! kn n  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: 41 k nA = n*(n – 1)*(n – 2)*... *(n – k + 1) = )!( ! kn n  Đặc biệt khi k = n thì ta có Akn= n! 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ử.  3 10A = )!310( !10  =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 0abcd Chọn a, b, c, d{1, 2, 3, 4, 5} có m1=A 4 5=1.2.3.4.5=120 (số) 2. Dạng 2abcd 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= A 3 4=4.3.2=24 (Cách) Với trường hợp này ta có tất cả m1x m2=4.24=96 (số) 3. Dạng 4abcd 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= A 3 4=4.3.2=24 (Cách) Với trường hợp này ta có tất cả m1x m2=4.24=96 (số) 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à k nA Đị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: k nA = n k 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ử thứ k. Theo quy tắc nhân ta được: k nA = n k 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 42 Đị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) = !!...! ! 21 skkk m (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)= 2520 !5!3!2 !10  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 kn. 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 : k nC là Số tổ hợp chập k của n phần tử Định lý : k nC = )!(! ! knk n  n, k nguyên dương , 0 k  n 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 Ckn và A k n. Ta có tất cả Ckn 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 xếp chúng thành một dãy có thứ tự. Như vậy có tất cả Ckn .k! cách sắp xếp k phần tử của 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à Akn , do đó Ckn.k!= A k n = )!( ! kn n  Suy ra : )!(! ! knk n C kn   Hệ quả: Cho n , k là các số nguyên không âm sao cho k n. Khi đó knn k n CC  Nhận xét:  Nếu k=0, k=n thì C0n=1, C n n=1  Ckn=C k n-1 + C k-1 n-1 với 0 k  n 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 tuyển chính là số tổ hợp chập 5 của 10 phần tử: 252 )!510(!5 !105 ... 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ó vucuaLvaLvaL kkk )},(),(),,(min{),( 11   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 zS do Begin u:=; S:=S{u}; Cij = 74 For do If L(u)+c(u,v)< L(v) then L(v):= L(u)+c(u,v) End; END; Ví dụ 1: Cho đồ thị với biểu diễn hình: 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 toán: ST T lặp 1 2 3 4 5 6 7 8 u S [0,1] * [3,1] [5,1] [2,1] * [,1] [,1] [,1] [,1] 1 {1} - [3,1] * [5,1] - [,1] [5,4] [8,4] [,1] 4 {1,4} - - [4,2] * - [10,2 ] [5,4] [8,4] [,1] 2 {1,4,2} - - - - [10,2 ] [5,4] * [8,4] [,1] 3 {1,4,2,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 } 1 3 6 8 2 5 4 7 3 7 1 1 6 5 2 3 4 6 3 5 2 4 75 Đường đi ngắn nhất từ 1  8 có giá 10; vết 1  5 8 1  6 5 8 1  46 5 8 Ví dụ 2: Cho đồ thị được biểu diễn bởi ma trận trọng số C 0 1 5 1 0 7 2 5 7 0 4 6 2 4 0 2 2 6 2 0 5 2 5 0 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 lặp 1 2 3 4 5 6 u S [0,1]* [1,1]* [5,1] [,1] [,1] [,1] 1 {1} - - [5,1] [3,2]* [,1] [,1] 2 {1,2} - - [5,1] - [5,4] [5,4]* 4 {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 1  2 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. 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 vS ở 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 76 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ì uvcvLuLuL kkk )},()(),(min{)(1  Đị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ố. 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 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 Begin u:=; S:=S{u}; For Do If d(u)+c(u,v)< d(v) then Begin d(v):= d(u)+c(u,v); p[v]:=u; 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 là hữu hạn nên sau một số lần lặp thuật toán sẽ dừng. 77 - 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. - Độ 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ẽ: 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: S 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] {1} 1 0 3 5 2 * ∞ ∞ ∞ ∞ 1 1 1 1 1 1 1 {1,4} 4 2 3 * 5 - ∞ 5 8 ∞ 1 1 1 1 4 4 1 {1,4,2} 2 3 - 4 * - 10 5 8 ∞ 1 2 1 2 4 4 1 {1,4,2,3} 3 4 - - - 10 5 * 8 ∞ 1 2 1 2 4 4 1 {1,4,2,3,6} 6 5 - - - 7 * - 8 11 1 2 1 6 4 4 1 {1,4,2,3,6,5} 5 7 - - - - - 8 * 10 1 2 1 6 4 4 5 {1,4,2,3,6,5,7} 7 8 - - - - - - 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 Đường đi ngắn nhất từ 1  8 có giá 10; vết 1  5 8 1  6 5 8 1  46 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 1  4 65 Ví dụ 2: Cho đồ thị được biểu diễn bởi ma trận trọng số C 1 3 6 8 2 5 4 7 3 7 1 1 6 5 2 3 4 6 3 5 2 4 78 0 1 5 3 2 0 7 2 7 5 7 0 3 6 4 2 4 0 2 3 2 1 0 5 6 1 2 7 0 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 Đường đi ngắn nhất từ 1  6 có giá 7; vết 1  4 6 1  2 4 6 Đường đi ngắn nhất từ 1  5 có giá 6; vết 1  4 5 1  2 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ị 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ả. 79 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 for j:=1 to n do if A[i,k] + A[k,j] < A[i,j] then Begin A[i,j]:= A[i,k] + A[k,j]; P[i,j]:= k; End; End; Ví dụ 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ị 0 5 50 0 15 5 30 0 50 15 5 0 C              + Bước 0(k = 0) 0 5 50 0 15 5 30 0 50 15 5 0 A              0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 P             + Bước 1(k = 1) 1 2 3 4 5 50 15 15 5 5 50 30 80 0 5 50 0 15 5 30 35 0 50 15 20 5 0 A              0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 P             + Bước 2(k = 2) 0 5 20 10 50 0 15 5 30 35 0 40 15 20 5 0 A             0 0 2 2 0 0 0 0 0 1 0 2 0 1 0 0 P             + Bước3 (k = 3) 0 5 20 10 45 0 15 5 30 35 0 40 15 20 5 0 A             0 0 2 2 3 0 0 0 0 1 0 2 0 1 0 0 P             + Bước 4( k = 4) 0 5 15 10 20 0 10 5 30 35 0 40 15 20 5 0 A             0 0 4 2 4 0 4 0 0 1 0 2 0 1 0 0 P             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 124 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ị 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. 81 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ụ: 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ụ - 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 - 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. Rừng 1 2 3 4 5 6 7 8 10 9 11 12 13 G2: Không là cây a b c e f g G1: Là cây a b c e f g d a b c e f g d 82 - Đỉ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. 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. c. Định lý sáu mệnh đề tương đương: Giả sử T là một cây, khi đó các mệ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. 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 83 (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ụ a.Bài toán cây khung nhỏ nhất a b c d e a b c d e a b c d e Đồ thị và các cây khung của nó 84 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 ( ) ( ) Te E m T m e    (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 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. 85  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 = <cạnh bất kỳ có trọng số nhỏ nhất và không tạo thành chu trình trong T khi ghép nó vào ET >; ET := ET  {e}; E:= E \{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 đó + 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ì j mA A A  sẽ liên thông + Nếu vi, vj  Ak với k thì phát sinh ra một tập mới A ’ 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ụ Cho đồ thị G như hình vẽ Thực hiện theo thuật toán như sau STT Cạnh Trọng số A T 1 2 8 3 6 7 5 4 4 1 4 8 7 4 4 6 9 9 10 4 18 86 1 (1,8) 1 {1,8} (1,8) 2 (3,8) 2 {1,3,8} (1,8)(3,8) 3 (8,2) 3 {1,2,3,8} (1,8)(3,8)(8,2) 4 (1,3) 4 Loại vì tạo thành chu trình 5 (1,2) 4 Loại vì tạo thành chu trình 6 (3,6) 4 {1,2,3,6,8} (1,8)(3,8)(8,2) (3,6) 7 (6,8) 4 Loại vì tạo thành chu trình 8 (6,7) 4 {1,2,3,6,7,8} (1,8)(3,8)(8,2) (3,6) (6,7) 9 (8,5) 6 {1,2,3,5,6,7,8} (1,8)(3,8)(8,2) (3,6) (6,7) (8,5) 10 (8,4) 7 {1,2,3,4,5,6,7,8} (1,8)(3,8)(8,2) (3,6) (6,7) (8,5) (8,4) 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 ET = {(1,8),(3,8),(8,2), (3,6), (6,7), (8,5), (8,4)} 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). 1 8 3 2 5 4 6 7 2 3 1 6 7 4 4 87 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. 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 d[v]:= C[u,v]; near[v]:= u; End; 2. Stop:= False; While not Stop Do Begin + Tìm s  V- VT thoả mãn d[s] = min{d[v]: v  V- VT} + VT:= VT  {s}; ET:= ET {(s, near[s])}; + If ET = (n - 1) then Begin T:= (VT, ET) là cây khung nhỏ nhất cần xây dựng Stop:= True; End Else for v  V- VT do If d[v] > C[s,v] then begin d[v]:= C[s,v]; near[v]:=s; end; End; END; Nhận xét: 88 - 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. - 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 VT ET [0,1]* [5,1] [,1] [4,1] [1,1]* [,1] [,1] {1}  - [5,1] [4,5]* [4,1] - [,1] [,1] {1,5} {(5,1)} - [4,3]* - [4,1] - [7,3] [8,3] {1,5,3} {(5,1);(3,5)} - - - [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); (6,2);(4,1);(7,4)} 2 6 3 5 1 4 7 5 5 5 2 9 8 4 4 4 6 1 3 7 89 Như vậy cây khung nhỏ nhất có dạng: T=(V,ET) với ET={(5,1);(3,5);(2,3);(6,2);(4,1);(7,4)} 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. 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 Đị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 7 4 1 5 3 2 6 3 4 4 4 1 2 D A C F B E G H 90 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 Thái nguyên, ngày 03 tháng 02 năm 2015