Giáo trình Toán rời rạc

110 trang vanle 3170

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_toan_roi_rac.pdf

Nội dung text: Giáo trình Toán rời rạc

ĐẶNG NGỌC HOÀNG THÀNH
ĐẶNG NGỌC HOÀNG THÀNH GIÁO TRÌNH TOÁN RỜI RẠC Huế, 2011
CHƯƠNG 1. MỞ ĐẦU MỤC LỤC CHƯƠNG 1. MỞ ĐẦU 4 1.1. Tập hợp 4 1.2. Phép chứng minh quy nạp to|n học 10 1.3. Sơ lược về tổ hợp 16 CHƯƠNG 2. BÀI TOÁN ĐẾM 29 2.1. Giới thiệu b{i to|n 29 2.2. Nguyên lý bù trừ 31 2.3. Công thức truy hồi 33 CHƯƠNG 3. BÀI TOÁN TỒN TẠI 41 3.1. Giới thiệu b{i to|n 41 3.2. Phương ph|p phản chứng 44 3.2. Nguyên lý Dirichlet 46 CHƯƠNG 4. BÀI TOÁN LIỆT KÊ 48 4.1. Giới thiệu b{i to|n 48 4.2.Thuật to|n quay lui 49 CHƯƠNG 5. BÀI TOÁN TỐI ƯU 53 5.1. Ph|t biểu b{i to|n 53 5.2. Thuật to|n nh|nh v{ cận 53 CHƯƠNG 6. LÝ THUYẾT ĐỒ THỊ 72 6.1. Sơ lược về lý thuyết đồ thị 72 6.1.1. C|c kh|i niệm về Đồ thị 73 6.1.2. Đồ thị con 76 6.1.3. C|c phép tìm kiếm trên đồ thị 81 6.1.4. Hành trình và chu trình 82 6.2. Đồ thị ph}n đôi v{ C}y 90 6.2.1. Đồ thị ph}n đôi v{ c}y 90 6.2.2. C}y khung của đồ thị. 93 6.2.3. C|c phép duyệt c}y 95 6.3. Đồ thị Euler v{ Đồ thị Hamilton 96 6.3.1. Đồ thị Euler 96 6.3.2. Đồ thị Hamilton 97 6.4. Đồ thị phẳng 98 2
CHƯƠNG 1. MỞ ĐẦU TÀI LIỆU THAM KHẢO 101 3
CHƯƠNG 1. MỞ ĐẦU CHƯƠNG 1. MỞ ĐẦU 1.1. Tập hợp 1.1.1. Khái niệm tập hợp Tập hợp l{ một kh|i niệm nguyên thủy. Người ta thừa nhận kh|i niệm n{y như một lẽ tất yếu m{ không đưa ra một định nghĩa cụ thể. C|c đối tượng trong thế giới hợp th{nh một tập hợp. Tập c|c sinh viên trong một lớp học. Tập c|c số tự nhiên. Tập c|c đường thẳng trong mặt phẳng. Tập c|c quốc gia trong một ch}u lục. Tập c|c c}y trong rừng. Tập c|c ph}n tử nước trong một giọt nước . V{ h{ h{ng sa số những ví dụ về tập hợp. Trong tập hợp, c|c yếu tố bên trong nó được xem l{ các phần tử của tập hợp. Một tập hợp có thể không chứa phần tử n{o, cũng có thể chứa hữu hạn phần tử hoặc vô hạn c|c phần tử. Một tập hợp đôi khi còn được gọi tắt là tập. Ví dụ tập hợp A hay tập A. Cho một tập hợp A, và một phần tử a của tập hợp A. Ta nói rằng, phần tử a thuộc tập hợp A. Kí hiệu Đọc l{: phần tử A thuộc tập hợp A hoặc phần tử a thuộc tập A. Ngược lại, nếu phần tử b không phải l{ phần tử của tập hợp A thì ta nói rằng, phần tử b không thuộc tập hợp A và kí hiệu Các cách biểu diễn tập hợp Để biểu diễn một tập hợp, thông thường người ta sử dụng một trong hai c|ch sau: a) Liệt kê c|c phần tử của tập hợp Đối với phương ph|p n{y, ta liệt kê tất cả hoặc một phần các phần tử trong tập hợp đó. * + - Tập các số tự nhiên chẵn * + – Tập 3 kí tự a, b v{ c. b) Sử dụng c|c mô tả về tập hợp
CHƯƠNG 1. MỞ ĐẦU Thông thường, c|ch mô tả tập hợp n{y |p dụng cho tập có vô hạn c|c phần tử. Ta sẽ không liệt kê tất cả các phần tử của nó mà chỉ nêu các tính chất đặc trưng của tập hợp. * + Hay * + 1.1.2. Tập hợp con, Tập hợp rỗng và Tập hợp bao trùm a. Tập hợp con. Tập hợp A được gọi l{ con của tập hợp B, nếu mọi phần tử của tập hợp A thuộc vào tập hợp B. Kí hiệu . Nếu tập hợp A là con của tập hợp B, thì ta cũng gọi tập hợp B là cha của tập hợp A. Khi đó, kí hiệu sẽ được thay bằng kí hiệu . ( ) ( ) Nếu tập hợp và thì ta nói rằng tập . Nếu tập hợp hoặc thì ta nói A là tập con hoặc bằng B và kí hiệu . Trong nhiều trường hợp, đôi khi người ta sẽ gọi – tập A là con của tập B và – tập A l{ con đúng của tập B hay nằm lọt trong B. b. Tập hợp rỗng. Một tập hợp có thể không chứa một phần tử n{o, có thể chứa hữu hạn phần tử hoặc vô hạn c|c phần tử. Trong trường hợp không chứa phần tử, ta gọi tập hợp n{y l{ tập hợp rỗng. *+ c. Tập hợp bao trùm. Tập hợp chứa tất cả c|c tập hợp kh|c gọi l{ tập hợp bao trùm (hay tập vũ trụ). Tập hợp bao trùm thường được kí hiệu là . Theo định nghĩa của tập hợp rỗng và tập bao trùm, ta có một số chú ý sau đ}y: + Tập hợp rỗng là con của mọi tập hợp bởi tập hợp rỗng không chứa phần tử nào. + Mọi tập hợp đều là tập con của tập bao trùm. 5
CHƯƠNG 1. MỞ ĐẦU Lực lượng của tập hợp. Số lượng các phần tử của một tập hợp được gọi là lực lượng của tập hợp. Kí hiệu - đọc là lực lượng của tập hợp A. Một tập hợp có n phần tử, thì có tập hợp con. Ví dụ: Cho tập hợp A = {1, 2, 3}. Khi đó, sẽ có tập con của A. Các tập hợp này bao gồm: + * + * + * + * + * + * + * ++ Tập các tập hợp con của tập hợp A được kí hiệu là ( ). 1.1.3. Các phép toán trên tập hợp Để minh họa cho c|c phép to|n trên tập hợp, ta sẽ sử dụng giản đồ sau đ}y để minh họa (còn được gọi l{ giản đồ Venn). A B 1 3 2 Hình 1.1 – Minh họa c|c phép to|n trên Tập hợp a. Phép toán hợp. Hợp của hai tập hợp A v{ B l{ một tập hợp chứa tất cả c|c phần tử của tập hợp A v{ c|c phần tử của tập hợp B. Kí hiệu . * + Trong hình minh họa ở trên, hợp của hai tập hợp A và B là tập hợp chứa ba phần 1, 2 và 3. Ví dụ: Giả sử ta có tập hợp A và B. Yêu cầu tìm hợp của hai tập hợp A và B. * + * + * + 6
CHƯƠNG 1. MỞ ĐẦU Cần lưu ý rằng, tập hợp không có sự ph}n biệt thứ tự giữa c|c phần tử. Nếu tập hợp A l{ con của tập hợp B, thì hợp của hai tập hợp A v{ B chính l{ tập hợp B. b. Phép toán giao. Giao của hai tập hợp A v{ B l{ một tập hợp chỉ chứa c|c phần tử chung của cả hai tập hợp. Kí hiệu * + Trong hình minh họa ở trên, giao của hai tập hợp A và B là tập hợp chứa phần 3. Ví dụ: Giả sử ta có tập hợp A và B. Yêu cầu tìm hợp của hai tập hợp A và B. * + * + * + * + Nếu tập hợp A l{ con của tập hợp B, thì giao của hai tập hợp A v{ B chính l{ tập hợp A. c. Phép toán hiệu. Hiệu của hai tập hợp A v{ B l{ một tập hợp chỉ chứa c|c phần tử thuộc tập hợp A m{ không thuộc tập hợp B. Kí hiệu \ hoặc –. Trong một số gi|o trình có sự phân biệt giữa hai kí hiệu này1. * + Trong hình minh họa ở trên, hiệu của hai tập hợp A và B là tập hợp chứa phần 1. Ví dụ: Giả sử ta có tập hợp A và B. Yêu cầu tìm hiệu của hai tập hợp A và B. * + * + * + * + Nếu tập hợp A là con của tập hợp B, thì hiệu của hai tập hợp A và B là tập hợp rỗng. Phần bù tập hợp. Giả sử tập hợp A là con của tập hợp B và nằm lọt hẳn trong tập hợp B. 1 Nếu A thì hiệu của A và B được kí hiệu là A\B. Nếu thì hiệu của A và B được kí hiệu là A-B. 7
CHƯƠNG 1. MỞ ĐẦU B A 2 1 Hình 1.2 – Minh họa phần bù trên Tập hợp Khi đó, gi| trị được gọi l{ phần bù của tập hợp A đối với tập hợp B (hay đơn giản là phần bù của B). Kí hiệu . Nếu tập hợp B là tập bao trùm, ta có thể kí hiệu phần bù của tập hợp A là . d. Phép toán hiệu đối xứng. Hiệu đối xứng của hai tập hợp A v{ B l{ một tập hợp chỉ chứa các phần tử thuộc tập hợp A mà không thuộc tập hợp B và các phần tử thuộc tập hợp B mà không thuộc tập hợp A. Kí hiệu . ( ) ( ) Trong hình minh họa 1 ở trên, hiệu đối xứng của hai tập hợp A v{ B l{ tập hợp chứa phần 1 và 2. Ví dụ: Giả sử ta có tập hợp A và B. Yêu cầu tìm hiệu đối xứng của hai tập hợp A và B. * + * + * + * + ( ) ( ) * + Nếu tập hợp A l{ con của tập hợp B, thì hiệu đối xứng của hai tập hợp A v{ B l{ phần bù của tập hợp A đối với tập hợp B. 1.1.4. Các tính chất của các phép toán trên tập hợp 8
CHƯƠNG 1. MỞ ĐẦU Chúng ta thừa nhận một số tính chất sau đ}y của c|c phép to|n trên tập hợp m{ không chứng minh. Việc chứng minh c|c tính chất n{y có thể thực hiện theo c|c luật trong logic mệnh đề. Định lý. Giả sử A, B, C là các tập hợp. E là tập bao trùm. Khi đó, ta sẽ có các tính chất sau đ}y: a) Luật giao hoán b) Luật kết hợp ( ) ( ) ( ) ( ) c) Luật phân phối + Phân phối trái ( ) ( ) ( ) ( ) ( ) ( ) + Phân phối phải ( ) ( ) ( ) ( ) ( ) ( ) d) Luật đồng nhất e) Luật nuốt f) Luật làm đầy g) Luật lũy đẳng 9
CHƯƠNG 1. MỞ ĐẦU h) Luật hấp thụ ( ) ( ) i) Luật bù ̿ ̅ j) Luật De-Morgan ̅̅̅ ̅̅̅ ̅ ̅ ̅ ̅̅̅ ̅̅̅ ̅ ̅ ̅ 1.1.5. Khái niệm về tích Descartes Định nghĩa. Giả sử A và B là hai tập hợp. Một tập hợp gồm các cặp (a, b) với và , sao cho với hai cặp (a, b)=(c, d) khi và chỉ khi a=c, b=d, được gọi là tích Descartes của hai tập hợp A và B. Kí hiệu AxB hay A.B. Ví dụ: Cho A={1, 2} v{ B={3, 4}. Khi đó, tích Descartes của hai tập A và B gồm các cặp sau đ}y: *( ) ( ) ( ) ( )+ Tổng quát, tích Descartes của n tập hợp là tập hợp gồm các cặp ( ) với và ( ) ( ) khi và chỉ khi . Kí hiệu . Giả sử tập lần lượt có phần tử. Khi đó, tích Descartes của n tập hợp trên sẽ có phần tử, hay ta có thể viết ∏ Trong đó, phép l{ kí hiệu cho lực lượng của tập hợp (tức l{ số phần tử của tập hợp đó). 1.2. Phép chứng minh quy nạp toán học 1.2.1. Phương pháp quy nạp toán học Phương ph|p chứng minh quy nạp trải qua ba bước: 10
CHƯƠNG 1. MỞ ĐẦU Bước 1. Kiểm tra công thức có đúng với trường hợp đầu tiên của chỉ số hay không. Nếu đúng ta thực hiện bước 2. Nếu sai, ta kết luận công thức sai. Bước 2. Giả sử công thức đúng với n=k. Ta cần chứng minh công thức đúng với n=k+1. Nếu chứng minh đúng thì chuyển sang bước 3, nếu sai kết luận công thức sai. Bước 3. Kết luận công thức đúng với mọi n. Phép chứng minh quy nạp to|n học có thể được minh họa bằng sơ đồ khối như sau: S Đúng với n0 Đ Đúng với n=k Đúng với n=k+1 Đ S CT sai CT đúng Hình 1.3 – Sơ đồ khối của phép quy nạp to|n học Ví dụ. Chứng minh đẳng thức ( ) ∑ Bước 1. Với n = 0. Ta có Vế trái VT = ∑ Vế phải VP = 0 Công thức đúng với n=0. 11
CHƯƠNG 1. MỞ ĐẦU Bước 2. Giả sử công thức đúng với n=k, tức là ( ) ∑ ( ) Ta cần chứng minh, công thức đúng với n = k+1, tức là ( )( ) ∑ Ta có ∑ ∑ ( ) bởi vì ∑ ⏟ ( ) ∑ Kết hợp với giả thiết quy nạp (*), ta có ( ) ( )( ) ∑ ( ) Bước 3. Vậy, công thức đúng Bài tập. Chứng minh các công thức sau bằng quy nạp toán học. ( )( ) ) ∑ ( ) ) ∑ ) ∑ ( ) ) ∑ ( ) ( ) ) ) 12
CHƯƠNG 1. MỞ ĐẦU ) 1.2.2. Phương pháp quy nạp hoàn toàn Trong khoa học m|y tính, việc chứng minh c|c công thức bằng phép quy nạp nêu trên rất khó |p dụng. Nhiều b{i to|n trong thực tế, người ta sử dụng một phương pháp khác có thể áp dụng trên m|y tính điện tử một cách dễ d{ng đó l{ phương pháp quy nạp hoàn toàn. Giả sử ta cần chứng minh b{i to|n P(n) đúng với các giá trị . Phương pháp quy nạp hoàn toàn sẽ thực hiện kiểm tra tính đúng đắn của bài toán P(n) = Q(n) với mọi giá trị . Khi đó, ta có thể x}y dựng giải thuật như sau: bool QuyNapHoanToan(int n0, int n1) { for (int i=n0; i #include using namespace std; double P(int n) { double S = 0; for (int i=0; i<=n; i++) S+=powl(i, 2); return S; } double Q(int n) { return (double)(n)*(n+1)*(2*n+1)/6; 13
CHƯƠNG 1. MỞ ĐẦU } bool QuyNapHoanToan(int n0, int n1) { for (int i=n0; i<=n1; i++) if (P(i)!=Q(i)) return false; return true; } int main() { if(QuyNapHoanToan(0, 9999)) cout<<"Dang thuc dung voi moi 0<=n<=9999"; else cout<<"Dang thuc sai"; return 0; } Hãy viết giải thuật quy nạp hoàn toàn cho các bài tập còn lại. 1.2.3. Phép đệ quy và Cơ sở toán học của nó. Trong lập trình chúng ta thường bắt gặp kh|i niệm đệ quy. Đệ quy đó l{ c|ch thức xác định một d~y c|c phần tử m{ c|c phần tử sau được x|c định thông qua phần tử trước đó. Khái niệm n{y tương tự như hệ thức truy hồi trong toán học. Một ví dụ điển hình đó l{ mô hình tính giai thừa. { ( ) Với mỗi biểu thức truy hồi, ta có thể thực hiện một phép đệ quy để x|c định c|c phần tử của d~y. Đối với trường hợp giai thừa, ta có - Với n=0. Ta có giai thừa của 0 là 1. - Với n=1, ta có 1!=1.0!=1.1=1. - Với n=2, ta có 2!=2.1!=2.1=1. - Với n=k, ta có k!=k.(k-1)! Từ c|ch suy diễn n{y, ta dễ d{ng thấy được rằng, bản chất to|n học của phép đệ quy đó chính l{ phép quy nạp to|n học. 14
CHƯƠNG 1. MỞ ĐẦU Thiết kế giải thuật đệ quy. Giả sử ta cần x}y dựng giải thuật để thực hiện một thuật to|n tương ứng với một gi| trị n cho trước. Khi đó, ta sẽ tiến h{nh ph}n tích b{i to|n như sau: Bước 1. Nếu rơi vào trường hợp suy biến, thì thực hiện trường hợp suy biến. Bước 2. Nếu ngược lại, ta tiến hành thực hiện giải thuật gọi lại hàm đệ quy. Ví dụ 1. Tính tổng Bước 1. Trường hợp suy biến n=1 thì S=1. Bước 2. S(n)=n+S(n-1) Giải thuật để giải b{i to{n n{y có thể được viết như sau: long S(int n) { if(n==1) return 1; else return n+S(n-1); } Ví dụ 2. Tìm kiếm một phần tử có gi| trị x trong danh s|ch liên kết đơn. Bước 1. Trường hợp suy biến khi head->data == x. Bước 2. Nếu ngược lại, ta chuyển sang tìm kiếm ở head->next. Giải thuật để giải b{i to{n n{y có thể được viết như sau: struct Link { int data; Link* next; }; Link* head; Link* search(int x, Link* head) { if(head->data==x) return head; else return search(int x, head->next); } Đệ quy có một ứng dụng to lớn trong khoa học m|y tính. Nhiều b{i to|n khi thiết kế giải thuật đệ quy đơn giản hơn rất nhiều so với việc tìm kiếm một giải thuật kh|c. Dù 15
CHƯƠNG 1. MỞ ĐẦU việc x}y dựng một giải thuật lặp để khử đệ quy l{ ho{n to{n có thể thực hiện được. Trong nội dung của gi|o trình n{y, ta sẽ tiến h{nh nghiên cứu một ứng dụng quan trọng của đệ quy |p dụng cho c|c b{i to|n đếm, đó l{ hệ thức truy hồi. Tuy nhiên, chúng ta sẽ nghiên cứu c|ch giải một hệ thức truy hồi thay vì viết giải thuật đệ quy để giải nó. Việc giải hệ thức truy hồi sẽ được thảo luận trong trong phần tiếp theo của b{i to|n đếm. 1.3. Sơ lược về tổ hợp 1.3.1. Các quy tắc tính toán 1.3.1.1. Quy tắc cộng Quy tắc cộng. Giả sử cần thực hiện n công việc. C|c công việc thực hiện độc lập không ảnh hưởng lẫn nhau. Để thực hiện công việc thứ i, i=1, 2, , n ta có cách. Khi đó, để thực hiện một công việc trong n công việc ở trên, ta sẽ có cách. Dấu hiệu nhận biết. Để nhận biết một b{i to|n |p dụng quy tắc cộng, ta sẽ xem xét trong số c|c công việc thực hiện nó có quan hệ với nhau hay không. Nếu chúng ho{n to{n độc lập thì ta |p dụng quy tắc cộng. C|c ví dụ. Bài 1. Cho hai danh s|ch liên kết đơn A v{ B. Danh s|ch A có n node, danh s|ch B có m node. Hỏi khi ghép hai danh s|ch trên lại với nhau thì danh s|ch mới thu được có bao nhiêu node. Giải. Việc ghép nối hai danh s|ch liên kết đơn không l{m thay đổi số node của mỗi danh s|ch. Danh s|ch mới thu được sẽ được khởi tạo từ c|c node của mỗi danh s|ch A v{ B. Tiến trình tạo danh s|ch ghép nối sẽ được thực thi qua hai giai đoạn: sao chép to{n bộ c|c node trong danh s|ch A v{ sao chép to{n bộ c|c node trong danh s|ch B. Do đó, danh s|ch ghép nối thu được, sẽ có n + m node. Bài 2. Giả sử tổ bộ môn công nghệ phần mềm có 10 giảng viên, tổ kĩ thuật lập trình có 12 giảng viên. Việc chọn một giảng viên đi dự hội thảo khoa học có thể thực hiện bằng c|ch chọn một giảng viên bất kì trong c|c giảng viên của hai tổ nói trên. Hỏi có bao nhiêu c|ch chọn giảng viên đi dự hội thảo khoa học. 16
CHƯƠNG 1. MỞ ĐẦU Giải. Chúng ta sẽ ph}n tích b{i to|n n{y để thấy rõ dấu hiệu |p dụng quy tắc cộng. Việc tiến h{nh chọn một giảng viên đi dự hội thảo khoa học sẽ được tiến h{nh theo hai công việc độc lập: hoặc chọn một giảng viên của tổ công nghệ phần mềm, hoặc chọn một giảng viên của tổ kĩ thuật lập trình. Hai công việc chọn lựa n{y l{ ho{n to{n không ảnh hưởng đến nhau. Do đó, ta sẽ |p dụng quy tắc cộng. - Công việc chọn 1 giảng viên trong số 10 giảng viên của tổ công nghệ phần mềm sẽ có 10 c|ch chọn. - Công việc chọn 1 giảng viên trong số 12 giảng viên của tổ kĩ thuật lập trình sẽ có 12 c|ch chọn. Vậy sẽ có 10+12 c|ch chọn một giảng viên thuộc hai tổ kh|c nhau đi dự hội thảo khoa học. Quy tắc cộng liên hệ với phép hợp trong lý thuyết tập hợp. Nếu ta gọi A l{ tập hợp c|c giảng viên của tổ bộ môn công nghệ phần mềm, B là tập hợp các giảng viên của tổ bộ môn kĩ thuật lập trình, thì khi đó, công việc chọn của chúng ta sẽ chính là lực lượng của tập . Ta có . Bài 3. Môn To|n rời rạc của khoa Công nghệ thông tin được giảng dạy cho 5 lớp và được 5 giảng viên kh|c nhau đảm nhận. Mỗi giảng viên ra hai đề thi v{ nộp cho Tổ khảo thí v{ Đảm bảo chất lượng gi|o dục của trường. Hỏi có bao nhiêu c|ch chọn ra một đề thi để tổ chức thi chung cho cả 5 lớp nói trên. Giải. Ho{n to{n tương tự ở trên, việc tiến h{nh chọn một đề trong số hai đề thi của mỗi giảng viên l{ độc lập. Do đó, ta |p dụng quy tắc cộng. Để chọn một đề thi trong hai đề thi của mỗi giảng viên có 2 c|ch. Vì vậy, ta có 2 + 2 + 2 + 2 + 2 = 10 c|ch. Bài 4. Cho tập hợp A có 3 phần tử. Hỏi có bao nhiêu tập con của tập A. Giải. C|c phần tử trong tập hợp l{ kh|c nhau, không ph}n biệt thứ tự. C|c tập con của tập A bao gồm: - Tập rỗng. - Tập có 1 phần tử. - Tập có hai phần tử. 17
CHƯƠNG 1. MỞ ĐẦU - Tập có 3 phần tử. C|c tập hợp n{y ho{n to{n kh|c nhau (điều kiện cần để hai tập hợp bằng nhau l{ lực lượng của chúng phải bằng nhau). Do đó, ta |p dụng quy tắc cộng. - Số lượng tập rỗng: 1 tập. - Số lượng tập 1 phần tử: 3 tập. - Số lượng tập 2 phần tử: 3 tập. - Số lượng tập 3 phần tử: 1 tập. Vậy có 1+3+3+1 = 8 tập con của tập A. 1.3.1.2. Quy tắc nhân Quy tắc nhân. Giả sử cần thực hiện một công việc. Công việc này có thể chia ra làm n bước. Để thực hiện công việc ở bước thứ i, i=1, 2, , n ta có c|ch. Khi đó, để thực hiện công việc ở trên, ta sẽ có cách. Dấu hiệu nhận biết. Để nhận biết một b{i to|n |p dụng quy tắc nhân, ta sẽ xem xét trong số c|c công việc thực hiện ở mỗi bước có quan hệ với nhau hay không. Nếu chúng ảnh hưởng lẫn nhau (hoặc mỗi c|ch lựa chọn kh|c nhau khi mỗi bước lựa chọn l{ kh|c nhau – tương ứng với tích Descartes) thì ta |p dụng quy tắc nhân. C|c ví dụ. Bài 1. Trang phục của một sinh viên khi đi picnic bao gồm: |o sơ mi, quần }u, giầy v{ mũ. Giả sử rằng, Nam có 3 |o sơ mi, 3 quần }u, 2 đôi giầy v{ 2 chiếc mũ. Hỏi có bao nhiêu trang phục m{ Nam có thể mặc khi đi picnic. Giải. Hai bộ trang phục được gọi l{ kh|c nhau, khi có ít nhất một th{nh phần trong trang phục đó l{ kh|c nhau. Việc tiến h{nh chọn c|c th{nh phần trong trang phục l{ có quan hệ với nhau. Việc chọn 1 quần }u, sau đó kết hợp với |o sơ mi kh|c nhau, giầy kh|c nhau v{ mũ kh|c nhau cũng tạo th{nh một trang phục mới. Nam không thể mặc thiếu một th{nh phần n{o trong số c|c th{nh phần nêu trên, bởi lẽ khi đó, Nam không mặc một trang phục ho{n chỉnh để tham gia đi picnic. Điều n{y có nghĩa l{ chúng ta |p dụng quy tắc nh}n. Việc chọn trang phục sẽ tiến h{nh theo 4 bước: . Chọn |o sơ mi – có 3 cách; . Chọn quần }u – có 3 cách; 18
CHƯƠNG 1. MỞ ĐẦU . Chọn giầy – có 2 cách; . Chọn mũ – có 2 cách. Vậy theo quy tắc nh}n, ta có 3.3.2.2=36 bộ trang phục ho{n chỉnh. Bài 2. Giả sử trong một trường đại học, c|ch đ|nh chỉ số giảng đường được quy định như sau: phần chữ v{ phần số. Phần chữ bao gồm một trong c|c kí tự sau: A, B, C, D, E, F, X, Y; phần số bao gồm c|c số từ 1 cho đến 50. Hỏi có bao nhiêu c|ch đặt tên cho c|c giảng đường. Giả sử số giảng đường không giới hạn. Giải. Việc tiến h{nh đặt tên cho giảng đường phải tiến h{nh theo hai phần: phần đặt chữ v{ phần đặt số. C|ch đặt chữ v{ đặt số có quan hệ với nhau: một chữ có thể kết hợp với nhiều số để đặt tên cho c|c giảng đường. Hai giảng đường kh|c nhau khi có ít nhất l{ phần chữ hoặc phần số l{ kh|c nhau. Do đó, ta |p dụng quy tắc nh}n. Số c|ch đặt chữ - có 8 c|ch. Số c|ch đặt số - có 50 c|ch. Vậy có 8.50=400 c|ch đặt tên cho c|c giảng đường. Bài 3. Giả sử trong một bảng m~ có 20 kí tự. Cần tạo một mật khẩu có độ d{i 5. Mật khẩu không ph}n biệt chữ hoa v{ chữ thường, không có một sự r{ng buộc n{o. Hỏi có bao nhiêu mật khẩu có thể chọn. Giải. Việc chọn mật khẩu sẽ được tiến h{nh theo 5 bước – tương ứng với 5 kí tự trong mật khẩu. Chọn kí tự đầu tiên trong d~y mật khẩu – có 20 c|ch. Vì mật khẩu có thể chứa c|c kí tự trùng lặp, do đó trong c|c kí tự tiếp theo của mật khẩu vẫn có 20 c|ch chọn lựa cho mỗi vị trí. Vậy, theo quy tắc nhân, ta có 20.20.20.20.20=32.105 mật khẩu được tạo th{nh. 1.3.2. Các cấu hình tổ hợp 1.3.2.1. Hoán vị không lặp và Hoán vị vòng a. Hoán vị. Ho|n vị không lặp (hay chính x|c hơn l{ ho|n vị không lặp tuyến tính, hay gọi tắt l{ ho|n vị) của n phần tử kh|c nhau l{ số c|ch sắp xếp có thứ tự tuyến tính của n phần tử đó. 19
CHƯƠNG 1. MỞ ĐẦU Giả sử, ta có n phần tử cần sắp xếp v{o n vị trí thẳng h{ng. Để tiến h{nh công việc sắp xếp, ta sẽ lần lượt sắp xếp c|c phần tử một v{o c|c vị trí thứ nhất, thứ hai, - Chọn phần tử đầu tiên v{ xếp v{o vị trí đầu tiên: có n c|ch. - Chọn phần tử thứ hai v{ xếp v{o vị trí thứ hai: có n-1 c|ch (vì không cho phép chọn lại phần tử trước đó). . - Chọn phần tử thứ n v{ xếp v{o vị trí cuối cùng: có 1 c|ch. C|c công việc chọn lựa n{y có quan hệ với nhau: hai cách sắp xếp là khác nhau khi hai phần tử cùng chỉ số là khác nhau. Vậy theo quy tắc nhân, ta có n.(n-1) 1=n! c|ch sắp xếp. Bài toán hoán vị của n phần tử có n! cách sắp xếp. Công thức tính số hoán vị. Hoán vị thường được kí hiệu là , b. Hoán vị vòng. Ho|n vị vòng (hay chính x|c hơn l{ ho|n vị vòng không lặp) của n phần tử kh|c nhau l{ trường hợp khi ta ho|n vị n phần tử đó trên một đường tròn. Giả sử trên một đường tròn có n vị trí, ta cần xếp n phần tử kh|c nhau n{y lên c|c vị trí trên đường tròn. Khi đó, với phần tử đầu tiên ta có thể đặt nó v{o mộ vị trí bất kì trên đường tròn n{y m{ không có một sự ph}n biệt n{o. Khi đặt phần tử thứ 2 v{o khi đó mới có sự ph}n biệt – vị trí đặt phần tử thứ hai liền kề với phần tử thứ nhất l{ ho{n to{n kh|c biệt với việc đặt phần tử thứ hai c|ch phần tử thứ nhất một khoảng trống. Kể từ phần tử thứ hai n{y, mới có sự kh|c biệt. C|c phần tử tiếp theo cũng tương tự như trường hợp phần tử thứ hai. Do đó, về bản chất, thì ho|n vị vòng của n phần tử có thể quy về hoán vị tuyến tính của n-1 phần tử. Nghĩa l{ b{i to|n ho|n vị vòng của n phần tử sẽ có (n-1)! cách sắp xếp. Công thức tính số hoán vị vòng. Hoán vị vòng thường được kí hiệu là ̃ . ̃ ( ) Chú ý. Cần lưu ý đến một số điểm sau đ}y khi sử dụng cấu hình ho|n vị: - Khi một b{i to|n yêu cầu tìm số c|ch sắp xếp của n phần tử v{o n vị trí hay tính số c|ch ho|n đổi vị trí của n cặp phần tử n{o đó thì ta sẽ chọn cấu hình ho|n vị. Nếu vị 20
CHƯƠNG 1. MỞ ĐẦU trí sắp xếp trên đường thẳng, ta |p dụng ho|n vị tuyến tính. Nếu sắp xếp trên đường tròn, ta |p dụng ho|n vị vòng. - C|c cấu hình ho|n vị nêu trên chỉ |p dụng cho c|c phần tử kh|c nhau. Trường hợp c|c phần tử có thể trùng lặp sẽ liên quan đến một cấu hình tổ hợp kh|c m{ chúng ta sẽ khảo s|t sau. C|c ví dụ. Bài 1. Có ba quả bóng xanh, đỏ v{ v{ng. Có ba sọt được đặt theo thứ tự thẳng h{ng. Hỏi có bao nhiêu c|ch xếp ba quả bóng trên v{o ba sọt. Giải. Rõ r{ng đ}y l{ b{i to|n sắp xếp ba vật v{o ba vị trí thẳng h{ng, nên ta sẽ |p dụng cấu hình ho|n vị. Nghĩa l{ có 3!=6 c|ch sắp xếp. C|c c|ch sắp xếp đó l{ (xanh, đỏ, v{ng), (xanh, v{ng, đỏ), (đỏ, xanh, v{ng), (đỏ, v{ng, xanh), (v{ng, xanh, đỏ) v{ (v{ng, đỏ, xanh). 1. x đ v 2. x v đ 3. đ x v 4. đ v x 5. v x đ 6. v đ x Bài 2. Nếu ba sọt trên được xếp th{nh vòng tròn, thì có bao nhiêu c|ch sắp xếp. Giải. Rõ r{ng đ}y l{ b{i to|n ho|n vị vòng, nghĩa l{ có (3-1)!=2 cách. v v x đ đ x C|c c|ch đó l{ (v{ng, đỏ, xanh) v{ (v{ng, xanh, đỏ). Một số c|ch khác trong ho|n vị tuyến tính trở nên trùng lặp trong ho|n vị vòng. 21
CHƯƠNG 1. MỞ ĐẦU Bài 3. Có bao nhiêu c|ch sắp xếp 5 vị đại biểu của c|c quốc gia kh|c nhau v{o một hội nghị b{n tròn. Biết rằng số ghế tương ứng với số đại biểu. Giải. Ho|n vị vòng. Số c|ch sắp xếp l{: 4!=24 c|ch. Bài 4. Trong một lớp học có 40 học sinh. Hỏi có bao nhiêu c|ch sắp xếp chỗ ngồi cho c|c học sinh. Biết rằng, bất kì hai học sinh n{o cũng đồng ý ngồi cùng nhau. Giải. Ho|n vị. Số c|ch sắp xếp l{ 40! c|ch. 1.3.2.2. Chỉnh hợp không lặp và Chỉnh hợp lặp a. Chỉnh hợp không lặp. Chỉnh hợp không lặp chập k (chập k có nghĩa l{ chọn ra k phần tử) của n phần tử l{ số bộ gồm có k phần tử có thứ tự kh|c nhau của n phần tử đó. Giả sử ta có n phần tử. Yêu cầu tìm số bộ k phần tử có thứ tự kh|c nhau từ n phần tử. Đó l{ một b{i to|n đơn giản. Chúng ta dễ d{ng tìm được lời giải cho b{i to|n n{y nhờ v{o quy tắc nh}n. Việc chọn ra k phần tử có thứ tự, tương ứng với việc chọn ra k phần tử v{ sắp xếp v{o k vị trí thẳng h{ng. Trước tiên, ta chọn ra phần tử thứ nhất v{ xếp v{o vị trí thứ nhất – có n c|ch chọn, với phần tử thứ 2, ta có n-1 cách chọn, ., với phần tử thứ k, ta có n-k+1 cách chọn. Việc tiến hành chọn ở mỗi bước có quan hệ với nhau. Theo quy tắc nhân, ta có ( ) ( ) ( ) ( ) ( ) ( ) Vậy bài toán chỉnh hợp không lặp chập k có bộ phần tử. ( ) Công thức tính số chỉnh hợp không lặp chập k của n phần tử. Chỉnh hợp không lặp chập k của n phần tử thường được kí hiệu là . ( ) 22
CHƯƠNG 1. MỞ ĐẦU b. Chỉnh hợp lặp. Chỉnh hợp lặp chập k (chập k có nghĩa l{ chọn ra k phần tử) của n phần tử l{ số bộ gồm có k phần tử có thứ tự của n phần tử đó và c|c phần tử n{y có thể lặp lại. Giả sử ta có n phần tử. Yêu cầu tìm số bộ k phần tử có thứ tự, v{ c|c phần tử n{y có thể lặp lại cũng ho{n to{n tương tự như b{i to|n chỉnh hợp không lặp ở trên. Chúng ta dễ d{ng tìm được lời giải cho b{i to|n n{y nhờ v{o quy tắc nh}n. Việc chọn ra k phần tử có thứ tự, tương ứng với việc chọn ra k phần tử v{ sắp xếp v{o k vị trí thẳng h{ng. Trước tiên, ta chọn ra phần tử thứ nhất v{ xếp v{o vị trí thứ nhất – có n c|ch chọn, với phần tử thứ 2, theo giả thiết c|c phần tử có thể lặp lại, nên ta có thể chọn lại phần tử ban đầu, nghĩa l{ ta có n c|ch chọn, ., với phần tử thứ k, ta có cũng có n c|ch chọn. Việc tiến h{nh chọn ở mỗi bước có quan hệ với nhau. Theo quy tắc nhân, ta có ⏟ Vậy bài toán chỉnh hợp lặp chập k có bộ phần tử. Công thức tính số chỉnh hợp lặp chập k của n phần tử. Chỉnh hợp lặp chập k của n ̇ phần tử thường được kí hiệu là . ̇ Chú ý. Cần lưu ý đến một số điểm sau đ}y khi sử dụng cấu hình chỉnh hợp. - Chỉnh hợp được |p dụng cho b{i to|n có ph}n biệt thứ tự giữa c|c phần tử. - Nếu c|c phần tử cho phép lặp lại thì chỉnh hợp được |p dụng l{ chỉnh hợp lặp chập k của n phần tử; ngược lại, nếu c|c phần tử kh|c nhau thì chỉnh hợp được sử dụng sẽ l{ chỉnh hợp không lặp chập k của n phần tử. C|c ví dụ. Bài 1. Một đội hình thi đấu cầu lông hai người thường ph}n biệt vận động viên bên tr|i v{ vận động viên bên phải. Giả sử rằng trong c}u lạc bộ cầu lông có 10 người v{ c|c vận động viên n{y có khả năng đảm nhiệm vị trí chơi tr|i v{ phải l{ như nhau. Hỏi có bao nhiêu c|ch chọn ra một cặp vận động viên để đi thi đấu. Giải. Chúng ta cần lưu ý đến một số điểm sau đ}y: 23
CHƯƠNG 1. MỞ ĐẦU - Không gian chọn của chúng ta l{ 10 người. Bạn có thể chọn bất kì nhưng chỉ được chọn trong số 10 vận động viên n{y. - Chúng ta sẽ chọn ra 2 vận động viên để đi thi đấu, như vậy k=2. - Mỗi cặp vận động viên được chọn l{ có thứ tự (bởi có ph}n biệt tr|i phải). Do đó, ta |p dụng cấu hình chỉnh hợp. - Một vận động viên không cho phép lặp lại (bởi họ không thể phân thân thành 2). Từ những nhận xét trên, ta sẽ chọn chỉnh hợp không lặp để áp dụng cho bài toán này với k v{ n như đ~ nêu. Vậy, ta có cách chọn c|c cặp vận động viên để thi đấu. Bài 2. Quay lại với b{i tập 3 trong quy tắc nh}n, ta có nhận xét sau: - Không gian chọn c|c kí tự cho mật khẩu l{ 20 kí tự trong bảng m~, tức n=20. - Số kí tự cần chọn l{ 5, tức k=5. - C|c kí tự trong mật khẩu có ph}n biệt thứ tự, nên ta |p dụng chỉnh hợp. - C|c kí tự có thể lặp lại, nên ta |p dụng chỉnh hợp lặp. Kết quả ho{n to{n trùng khớp với kết quả ở trên mật khẩu. Bài 3. Có bao nhiêu số có 4 chữ số khác nhau được lấy trong tập {1, 2, , 9}. Giải. Dễ nhận thấy n=9, k=4. C|c số có phân biệt thứ tự và không thể lặp lại, nên ta áp dụng chỉnh hợp không lặp. Vậy có số. Nếu b{i to|n không yêu cầu c|c chữ số kh|c nhau thì ta sẽ |p dụng chỉnh hợp lặp. Bài 4. Trong một cuộc thi Olympic To|n học thế giới, có 8 thí sinh của 8 nước tham dự: Việt Nam, Nga, Nhật Bản, Hoa Kỳ, Ph|p, Trung Quốc, Anh v{ Canada. C|c quốc gia sẽ tranh nhau ba giải huy chương: v{ng, bạc v{ đồng. Hỏi có bao nhiêu khả năng xảy ra. Giả sử rằng, không có trường hợp hai thí sinh đạt cùng th{nh tích. Giải. Dễ nhận thấy n=8, k=3. Việc chọn ra 3 quốc gia l{ có thứ tự (vì sẽ lần lượt nhận c|c huy chương v{ng, bạc v{ đồng) – nên ta sử dụng chỉnh hợp, mỗi quốc gia chỉ có 24
CHƯƠNG 1. MỞ ĐẦU một thí sinh dự thi, do đó họ không thể nhận đồng thời 2 giải - tức không lặp. Vậy có khả năng. 1.3.2.3. Tổ hợp không lặp và Tổ hợp lặp a. Tổ hợp không lặp. Tổ hợp không lặp chập k của n phần tử l{ số bộ gồm k phần tử kh|c nhau không ph}n biệt thứ tự từ n phần tử đó. Số tổ hợp không lặp chập k của n phần tử được kí hiệu là . Ta sẽ đối chiếu tổ hợp không lặp với chỉnh hợp không lặp. Ta nhận thấy rằng, trường hợp tổ hợp không lặp chỉ l{ một trường hợp riêng của chỉnh hợp không lặp. Nếu ta lấy tất cả c|c kết quả của chỉnh hợp không lặp v{ ho|n đổi vị trí của các phần tử (thực hiện phép hoán vị k phần tử) thì ta sẽ thu được k! Lần số tổ hợp không lặp tương ứng. Điều đó có nghĩa l{ số chỉnh hợp không lặp gấp k! lần số tổ hợp không lặp. Từ đó, ta nhận được công thức tính số tổ hợp không lặp. Công thức tính số tổ hợp không lặp chập k của n phần tử. ( ) b. Tổ hợp lặp. Tổ hợp lặp chập k của n phần l{ số bộ gồm có k phần tử từ n phần tử đó, không ph}n biệt thứ tự v{ c|c phần tử có thể lặp lại. Ta dễ nhận thấy rằng, trường hợp tổ hợp không lặp chỉ l{ một trường hợp riêng của tổ hợp lặp. Nếu ta loại bỏ c|c trường hợp lặp trong tổ hợp lặp, thì ta thu được tổ hợp không lặp. Ta sẽ tính số tổ hợp lặp chập k của n phần tử thông qua số tổ hợp không lặp. Giả sử ban đầu, chúng ta chọn ra 1 phần tử. Khi đó, vì nó l{ phần tử duy nhất nên hiển nhiên không lặp. Ta cần chọn tiếp k-1 phần tử nữa. Bởi vì k-1 phần tử n{y trong trường hợp tổ hợp không lặp l{ kh|c với phần tử đầu tiên, nhưng với trường hợp tổ hợp không lặp thì cho phép trùng lặp. Do đó, ta có thể bổ sung v{o k-1 phần tử bất kì, v{ tiến h{nh lựa chọn theo cấu hình tổ hợp không lặp (h{m ý không lặp nhưng thật chất l{ lặp). Nghĩa l{ ta sẽ có số tổ hợp không lặp chập k của n+k-1 phần tử (vì 25
CHƯƠNG 1. MỞ ĐẦU ̇ bổ sung thêm k-1 phần tử). Nếu ta kí hiệu số tổ hợp lặp chập k của n phần tử là , ta ̇ sẽ có số tổ hợp lặp . Công thức tính số tổ hợp lặp chập k của n phần tử. ( ) ̇ ( ) Chú ý. Cần lưu ý đến một số điểm sau đ}y khi sử dụng cấu hình tổ hợp: - Tổ hợp được |p dụng cho b{i to|n không có ph}n biệt thứ tự giữa c|c phần tử. - Nếu c|c phần tử cho phép lặp lại thì tổ hợp được |p dụng l{ tổ hợp lặp chập k của n phần tử; ngược lại, nếu c|c phần tử kh|c nhau thì tổ hợp được sử dụng sẽ l{ tổ hợp không lặp chập k của n phần tử. C|c ví dụ. Bài 1. Có một giỏ hoa quả gồm có 5 loại quả l{ t|o, lê, mận, nho v{ cam. Số lượng hoa quả mỗi loại l{ không hạn chế. Hỏi có bao nhiêu c|ch chọn ra 4 quả bất kì để đặt v{o đĩa. Giải. Dễ nhận thấy không gian loại quả là 5, tức n=5; số quả cần lấy ra là 4, tức k=4. Ta sẽ chọn ra 4 quả bất kì để đặt v{o đĩa, nghĩa l{ không ph}n biệt thứ tự (tổ hợp) và có thể lặp lại. Vậy, ta có số cách chọn là cách. Bài 2. Cho phương trình . Hỏi có bao nhiêu nghiệm nguyên thỏa mãn điều kiện . Giải. Nếu ta chia tập c|c lựa chọn th{nh 3 nhóm 1, 2 v{ 3. B{i to|n quy về chọn x phần tử nhóm 1, y phần tử nhóm 2 v{ z phần tử nhóm 3. Sao cho tổng các phần tử được chọn của cả ba nhóm l{ 30. Theo như điều kiện ràng buộc, ta cần chọn ra ít nhất 5 phần tử của nhóm 1 ( ), 4 phần tử của nhóm 2 ( ) và 3 phần tử của nhóm 3 ( ). V{ tiếp tục chọn c|c phần tử của mỗi loại để đạt đến số 30 phần tử. Nghĩa l{ ta cần tiếp tục chọn thêm 30-5-4-3=18 phần tử, tức k=18, ta cần chọn các phần tử trong 3 nhóm, tức n=3. Việc tiến h{nh chọn c|c phần tử ở mỗi nhóm l{ không ph}n biệt thứ tự (bạn có thể chọn nhóm n{o trước cũng đều thỏa m~n) v{ c|c phần tử có thể lặp lại. Vì vậy, ta sử dụng cấu hình tổ hợp lặp chập k của n phần tử, tức là nghiệm thỏa m~n. 26
CHƯƠNG 1. MỞ ĐẦU Bài 3. Có bao nhiêu c|ch chọn 10 đại biểu trong 100 đại biểu để bầu v{o đo{n đại biểu Trưng Ương. Giả sử c|c vị trí trong đo{n đại biểu không ph}n biệt chức vụ. Mỗi đại biểu chỉ được bầu 1 lần. Giải. Dễ d{ng nhận thấy việc chọn 10 đại biểu trong 100 đại biểu sẽ tương ứng với n =100, k=10. C|c vị trí trong đo{n không ph}n biệt thứ tự, v{ không được phép lặp, nên ta |p dụng tổ hợp không lặp. Ta có cách. 1.3.2.4. Hoán vị lặp Bài toán. Giả sử có phần tử loại 1, phần tử loại 2, ., phần tử loại k. Hỏi có bao nhiêu c|ch sắp xếp tất cả c|c phần tử trên (sắp xếp tuyến tính). Giải. Ta dễ nhận thấy rằng bài toán này là hoán vị lặp. Ta thực hiện sắp xếp phần tử vào vị trí. Mỗi nhóm phần tử có thể lặp lại. Để giải b{i to|n ho|n vị lặp dạng n{y, ta tiến h{nh ph}n tích và chọn lựa theo từng nhóm một. - Chọn vị trí để đặt các phần tử của nhóm 1 từ n phần tử có cách. - Khi đó, sẽ còn phần tử. Chọn vị trí để đặt các phần tử nhóm 2 có cách. - Chọn vị trí để đặt nhóm k có cách (bởi vì đ}y l{ nhóm cuối cùng). Theo quy tắc nhân ta có cách. Ta có, ( ) ( ) ( ) Vậy, số hoán vị lặp trong trường hợp này là . 27
CHƯƠNG 1. MỞ ĐẦU BẢNG SO SÁNH CÁC QUY TẮC TÍNH TOÁN VÀ CÁC CẤU HÌNH TỔ HỢP Quy tắc cộng Quy tắc nhân C|c công việc độc lập, không có quan hệ C|c công việc có liên quan nhau. với nhau. Hoán vị Chỉnh hợp Tổ hợp Tính chất Tuyến Không Vòng Lặp Lặp Không lặp tính lặp Phân biệt thứ tự + + + + - - Cho phép lặp - - + - + - Điều kiện n=k + + - - - - ( ) Công thức ( ) ( ) ( ) ( ) 28
CHƯƠNG 2. BÀI TOÁN ĐẾM CHƯƠNG 2. BÀI TOÁN ĐẾM 2.1. Giới thiệu bài toán B{i to|n đếm l{ một dạng b{i to|n có ứng dụng to lớn trong thực tiễn. Ng{nh khoa học chuyên nghiên cứu về c|c b{i to|n đếm l{ to|n học tổ hợp – một ph}n ng{nh của to|n học rời rạc. Hiện nay, tốc độ xử lý của bộ vi xử lý m|y tính ng{y c{ng tăng nhanh, nên việc giải quyết b{i to|n đếm đ~ có một công cụ hữu hiệu để giải quyết. Không phải b{i to|n đếm n{o cũng có lời giải. Đối với những b{i to|n chưa tìm ra được lời giải, người ta thường nghiên cứu kĩ thuật để đếm c|c cấu hình nghiệm của b{i to|n đó. Bên cạnh đó, có những b{i to|n đếm có thể giải quyết được bằng c|ch sử dụng c|c cấu hình tổ hợp: ho|n vị, chỉnh hợp, tổ hợp v{ kết hợp với c|c quy tắc cộng, nh}n. C|c ví dụ Bài 1. Một biển số xe gồm 2 phần, phần đầu gồm 2 kí tự (từ A Z), phần sau gồm 3 chữ số (0 9). Hỏi có thể tạo được bao nhiêu biển số theo c|ch đ|nh như trên. Giải. Mỗi biển số gồm 2 phần: phần chữ v{ phần số. Phần chữ có 262 khả năng, phần số có 103 khả năng. Theo nguyên lý nh}n, số biển số xe tạo được sẽ l{ 262.103 = 676000. Bài 2. Một đội tuyển dự bị học sinh giỏi của một trường nọ gồm có 3 nhóm: To|n, Lý v{ Hóa. Nhóm To|n gồm có 10 học sinh, nhóm Lý gồm có 8 học sinh, nhóm Hóa gồm có 7 học sinh. Giả sử không có một học sinh n{o nằm trong hai nhóm dự bị. Học lực của mỗi học sinh l{ như nhau. Hỏi có bao nhiêu c|ch chọn một đổi tuyển tham dự kì thi học sinh giỏi. Biết rằng, mỗi đội tuyển tham dự cần có 2 học sinh thi To|n, 2 học sinh thi Lý v{ 2 học sinh thi Hóa. Giải. Để chọn một đội tuyển tham dự học sinh giỏi, ta cần chọn 2 học sinh trong nhóm dự bị môn Toán, 2 học sinh trong nhóm dự bị môn Lý và 2 học sinh trong nhóm dự bị môn Hóa. Nghĩa l{ ta sẽ có lần lượt và c|ch chọn 2 học sinh To|n, Lý v{ Hóa. Theo quy tắc nhân, ta có c|ch chọn. Một số bài tập tự giải.
CHƯƠNG 2. BÀI TOÁN ĐẾM 1) Có 5 quả bóng được đ|nh số thứ tự 1 đến 5. Hỏi có bao nhiêu c|ch sắp xếp để: a) Quả bóng 1 đứng ở chính giữa. b) Quả bóng 1 v{ 2 luôn đứng cạnh nhau. 2) Một t{i khoản người dùng gồm có username v{ password. Giả sử username có 5-8 kí tự, password có 8-10 kí tự. C|c kí tự n{y bao gồm c|c chữ số từ 0-9, c|c chữ c|i trong bảng m~ tiếng anh. Biết rằng, username không ph}n biệt chữ hoa v{ chữ thường, cho phép lặp. Password có ph}n biệt chữ hoa v{ chữ thường, cho phép lặp cục bộ, nhưng không cho lặp ho{n to{n (tức không cho phép c|c kí tự ho{n to{n giống nhau). Hỏi có bao nhiêu t{i khoản có thể tạo ra. 3) Việc xử lý thông tin trong CPU được quản lý bởi hệ điều h{nh v{ thực hiện theo nguyên tắc h{ng đợi. Giả sử, hệ điều h{nh ấn định thời gian xử lý thông tin cho một tiến trình l{ 5s. Sau thời gian n{y, nếu tiến trình chưa thực thi xong, thì nó sẽ rời h{ng đợi v{ quay lại cuối h{ng đợi để chờ được phục vụ tiếp. Nếu một tiến trình đ~ được phục vụ xong nhưng thời gian của nó vẫn chưa hết, thì tiến trình tiếp theo sẽ được đưa v{o phục vụ tương ứng với khoảng thời gian còn thừa đó m{ không cung cấp thêm 5s tiếp theo. Giả sử, có 5 tiến trình với thời gian cần xử lý lần lượt l{ 23s, 35s, 22s, 43s, 12s. Hỏi có bao nhiêu c|ch sắp xếp c|c tiến trình để tối ưu số lần phục vụ. 4) Cho một đa gi|c lồi có n cạnh. Hỏi đa gi|c n{y có bao nhiêu đường chéo. 5) Cho hai mặt phẳng song song (P) v{ (Q). Trên mặt phẳng (P) cho 5 điểm trong đó, không có bất kì 3 điểm n{o thẳng h{ng. Trên mặt phẳng (Q) cho 4 điểm, cũng không có bất kì 3 điểm n{o thẳng h{ng. Hỏi có bao nhiêu tứ diện có thể tạo ra. 6) Trong siêu thị, tại gian h{ng b|n hoa quả có 10 vị trí đặt sọt được bố trí th{nh hai h{ng, mỗi h{ng có 5 sọt. Có 10 sọt hoa quả trong đó có 8 sọt kh|c loại, hai sọt còn lại cùng loại v{ kh|c với 8 sọt kia. Hỏi có bao nhiêu c|ch sắp xếp c|c sọt hoa quả v{o c|c vị trí nói trên. 7) Nước A có 10 th{nh phố, nước B có 15 th{nh phố. Giữa c|c th{nh phố trong một nước luôn có đường giao thông nối với nhau. Giữa hai nước A v{ B chỉ có hai đường giao thông nối với nhau. Hỏi có bao nhiêu đường đi để đi qua tất cả c|c th{nh phố của hai nước nói trên. 30
CHƯƠNG 2. BÀI TOÁN ĐẾM 2.2. Nguyên lý bù trừ Nguyên lý bù trừ. Giả sử cho A và B là hai tập hữu hạn phần tử. Khi đó, ta có công thức sau đ}y: Trong trường hợp A và B là hai tập rời nhau, ta có , do đó, ta nhận được công thức: Nguyên lý bù trừ dạng tổng quát. Giả sử cho là các tập hợp hữu hạn phần tử. Khi đó, nguyên lý quy bù trừ dạng tổng quát sẽ được cho bởi công thức sau: |⋃ | ∑ ∑ | | ∑ | | ( ) |⋂ | Chứng minh. Để chứng minh công thức này, ta sử dụng nguyên lý quy nạp toán học. Bước 1. Dễ dàng kiểm tra thấy rằng, công thức đúng với n=1, bởi vì Bước 2. Giả sử công thức đúng với , tức là |⋃ | ∑ ∑ | | ∑ | | ( ) |⋂ | Ta cần chứng minh công thức đúng với , tức là |⋃ | ∑ ∑ | | ∑ | | ( ) |⋂ | Ta có, |⋃ | |⋃ | Áp dụng giả thiết quy nạp cho trường hợp hai phần tử, ta có 31
CHƯƠNG 2. BÀI TOÁN ĐẾM |⋃ | |⋃ | | | |⋃ | Theo giả thiết quy nạp và áp dụng tính chất phân phối, ta nhận được |⋃ | ∑ ∑ | | ∑ | | ( ) |⋂ | Có nghĩa l{ công thức đúng với . Bước 3. Vậy công thức đúng . Mệnh đề: Trong đoạn , - cho trước, có ⌊ ⌋ số chia hết cho n. Trong đó, phép to|n ⌊ ⌋ là phép lấy sàn của một số. Chứng minh. Một số chia hết cho sẽ có dạng , với là một số nguyên. Theo giả thiết , suy ra có ( ) số . Điều n{y cũng có nghĩa l{ sẽ có ⌊ ⌋ số thỏa m~n. Ví dụ 1. Trong tập X = {1,2, , 100} có bao nhiêu số chia hết cho 3 hoặc cho 5 hoặc cho 7. Giải. Gọi Ai = {x X: x chia hết cho i} với i = 3, 5, 7. Khi đó tập là tập các số trong N chia hết cho ít nhất một trong 3 số 3, 5, 7. Áp dụng nguyên lý bù trừ, ta có: ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ Vậy có 55 số thỏa m~n. Ví dụ 2. Trong một hội nghị b{n tròn của công ty A, c|c cổ đông cần đưa ra ý kiến thông qua một điều lệ của công ty bằng một cuộc bỏ phiếu kín. Một cổ đông chỉ có 32
CHƯƠNG 2. BÀI TOÁN ĐẾM thể hoặc đồng ý, hoặc không đồng ý. Nếu cổ đông chọn cả hai phương |n hoặc phiếu trắng thì xem như không hợp lệ. Biết rằng có 45 cổ đông đồng ý, 20 cổ đông không đồng ý, 50 cổ đông hoặc đồng ý hoặc không đồng ý. Hỏi có bao nhiêu phiếu không hợp lệ. Giải. Gọi * + * + Theo giả thiết, ta có Theo nguyên lí bù trừ, ta nhận được Vậy có 15 phiếu không hợp lệ. 2.3. Công thức truy hồi 2.3.1. Khái niệm hệ thức truy hồi Đôi khi ta rất khó định nghĩa một đối tượng một c|ch tường minh. Nhưng có thể dễ d{ng định nghĩa đối tượng n{y qua chính nó. Kỹ thuật n{y được gọi l{ đệ quy mà ta đ~ thảo luận ở trên, v{ người ta có thể dùng kỹ thuật n{y để giải c|c b{i to|n đếm. Kỹ thuật đệ quy còn được dùng để tìm c|c phần tử của một d~y số, trong đó, phần tử sau sẽ được x|c định thông qua c|c phần tử trước đó m{ ta gọi nó l{ hệ thức truy hồi. Ví dụ về hệ thức truy hồi. a. Biểu thức tính giai thừa { ( ) b. Dãy Fibonacci ( ) { ( ) ( ) c. Lãi kép (l~i suất tích lũy) 33
CHƯƠNG 2. BÀI TOÁN ĐẾM Giả sử một người gửi 10.000 đô la v{o t{i khoản của mình tại một ng}n h{ng với l~i suất kép 11% mỗi năm. Sau 30 năm anh ta có bao nhiêu tiền trong t{i khoản của mình. Gọi Pn l{ tổng số tiền có trong t{i khoản sau n năm. Vì số tiền có trong t{i khoản sau n năm bằng số có sau n 1 năm cộng lãi suất của năm thứ n, nên ta thấy dãy {Pn} thoả mãn hệ thức truy hồi sau: với điều kiện đầu P0 = 10.000 đô la. Từ đó suy ra Pn = (1,11)n.10.000. Thay n = 30 cho ta P30 = 228922,97 đô la. 2.3.2. Giải các hệ thức truy hồi Định nghĩa. Một hệ thức truy hồi tuyến tính thuần nhất bậc k với hệ số hằng là hệ thức truy hồi có dạng: , trong đó là các hằng số thực và . Theo nguyên lý của quy nạp toán học thì dãy số thỏa mãn hệ thức truy hồi nêu trong định nghĩa được x|c định duy nhất bằng hệ thức truy hồi n{y v{ k điều kiện đầu: . Phương ph|p cơ bản để giải hệ thức truy hồi tuyến tính thuần nhất hệ số hằng là tìm nghiệm dưới dạng , trong đó r l{ hằng số. Chú ý rằng là nghiệm của hệ thức truy hồi nếu v{ chỉ nếu Chia hai vế của phương trình n{y cho , ta nhận được – Phương trình n{y được gọi l{ phương trình đặc trưng của hệ thức truy hồi tuyến tính hệ số hằng. Nghiệm của nó gọi l{ nghiệm đặc trưng của hệ thức truy hồi. Định lý. (Về mối quan hệ giữa nghiệm của hệ thức truy hồi thuần nhất tuyến tính hệ số hằng với nghiệm của phương trình đặc trưng của nó). 34
CHƯƠNG 2. BÀI TOÁN ĐẾM Cho là các hằng số thực. Giả sử rằng phương trình đặc trưng – có k nghiệm phân biệt . Khi đó dãy {an} là nghiệm của hệ thức truy hồi , nếu và chỉ nếu trong đó là các hằng số. Để tìm các hằng số ta cần thế c|c nghiệm thu được v{o các điều kiện đầu v{ giải nó. Đơn giản hơn, ta sẽ nghiên cứu chi tiết về hệ thức truy hồi tuyến tính thuần nhất bậc hai với hệ số hằng một c|ch kĩ lưỡng. Đối với hệ thức truy hồi tổng qu|t, ta chỉ khảo s|t một số ví dụ m{ không đi sâu vào từng trường hợp cụ thể. Định lý. (Về mối quan hệ giữa nghiệm của hệ thức truy hồi thuần nhất tuyến tính hệ số hằng bậc 2 với nghiệm của phương trình đặc trưng của nó). Cho là các số thực. Xét phương trình đặc trưng của hệ thức truy hồi Khi đó, nếu a) Phương trình đặc trưng có hai nghiệm thực phân biệt thì hệ thưc truy hồi có nghiệm dưới dạng: b) Phương trình đặc trưng có nghiệm kép thì hệ thức truy hồi có nghiệm dưới dạng: c) Phương trình đặc trưng không có nghiệm thực, nhưng có hai nghiệm phức liên hợp . Khi đó, hệ thức truy hồi được gọi là không giải được trên trường số thực, nhưng có thể giải được trên trường số phức. Nghiệm sẽ được biểu diễn dưới dạng: Để giải quyết trường hợp số phức, thông thường ta biểu diễn các số phức dưới dạng lượng giác hoặc dạng lũy thừa e. 35
CHƯƠNG 2. BÀI TOÁN ĐẾM Các hệ số trong công thức ở trường hợp a) b) và c) là các hằng số. Các hệ số này sẽ được tìm nhờ v{o c|c điều kiện ban đầu. Các ví dụ. a. Giải hệ thức truy hồi của dãy Fibonacci. ( ) { ( ) ( ) Ta có thể biểu diễn nó dưới dạng Phương trình đặc trưng của hệ thức này là Phương trình n{y có hai nghiệm đặc trưng l{ √ √ Do đó, số hạng tổng quát của dãy Fibonacci là √ √ 4 5 4 5 Ta sẽ tìm các hệ số nhờ v{o điều kiện ban đầu . Ta có hệ phương trình sau √ √ { Giải hệ này, ta nhận được √ √ Vậy số hạng tổng quát của dãy Fibonacci là √ √ 4 5 4 5 √ √ b. Tìm số hạng tổng quát của hệ thức truy hồi sau: { Công thức trên có thể viết lại như sau 36
CHƯƠNG 2. BÀI TOÁN ĐẾM Phương trình đặc trưng của hệ thức truy hồi là Phương trình đặc trưng n{y có hai nghiệm phân biệt . Theo định lý ở trên, nghiệm của hệ thức truy hồi có dạng ( ) Theo điều kiện đầu ta nhận được hệ phương trình sau đ}y để tìm giá trị của . { Giải hệ phương trình này, ta nhận được { Vậy nghiệm của hệ thức truy hồi là ( ) c. Tìm nghiệm của hệ thức truy hồi sau: { Công thức trên có thể viết lại như sau Phương trình đặc trưng của hệ thức truy hồi Phương trình có nghiệm kép là . Do đó, công thức nghiệm tổng quát sẽ là Sử dụng điều kiện đầu, ta nhận được { Giải hệ này, ta nhận được Vậy nghiệm của hệ thức truy hồi trên là ( ) d. Tìm nghiệm của hệ thức truy hồi sau: 37
CHƯƠNG 2. BÀI TOÁN ĐẾM 2 Công thức trên có thể viết lại như sau Phương trình đặc trưng của nó có dạng Phương trình n{y có hai nghiệm phức √ √ Công thức nghiệm tổng quát có dạng √ √ 4 5 4 5 Để thuận lợi cho việc tính toán, ta sẽ biểu diễn hai số phức n{y dưới dạng lượng giác. √ √( * 4 5 √ ( ) √ √ ( ) √ Khi đó, nghiệm có thể biểu diễn dưới dạng 0( . / . /)1 0 ( . / . /)1 hay . . / . // . . / . // hay ( ) . / ( ) . / Sử dụng điều kiện đầu, ta nhận được ( ) { √ ( ) ( ) 38
CHƯƠNG 2. BÀI TOÁN ĐẾM Từ đó, ta nhận được √ √ Vậy nghiệm của công thức truy hồi là √ ( ) e. Tìm nghiệm của hệ thức truy hồi sau: { Hệ thức truy hồi có thể được viết lại Phương trình đặc trưng của hệ thức truy hồi Phương trình đặc trưng có 3 nghiệm . Công thức nghiệm tổng quát Sử dụng điều kiện đầu, ta nhận được hệ { Hệ này có nghiệm . Vậy, nghiệm của hệ thưc truy hồi là 2.3.3. Quy về bài toán đơn giản Để giải quyết c|c b{i to|n đếm phức tạp, ta thường ph}n tích b{i to|n để đưa về c|c b{i to|n con đơn giản hơn. Kĩ thuật ph}n chia n{y còn được biết đến với tên gọi l{ chia để trị. Bởi lẽ quy tắc n{y được |p dụng l{ vì, không phải lúc n{o b{i to|n cũng đếm cũng dễ d{ng giải quyết được. Nhưng sự ph}n chia để nhận được các bài toán nhỏ hơn cũng đòi hỏi người phân tích phải hiểu một cách sâu sắc về cấu hình cần đếm. 39
CHƯƠNG 2. BÀI TOÁN ĐẾM Giải sử ta xét b{i to|n đếm phức tạp, b{i to|n được phân tách thành bài toán con. Giả sử rằng, n l{ kích thước của b{i to|n đếm, và mỗi b{i to|n con có kích thước được giảm đi lần, tức kích thươc của nó là . Gọi là hàm số phép toán cần thiết để giải bài toán con, nó là hàm theo biến số kích thước; l{ h{m c|c phép to|n cần thiết để thực hiện việc ph}n chia b{i to|n ban đầu về các bài toán con, nó là hàm theo biến kích thước. Khi đó, ta có ( ) ( * ( ) Phát biểu: số phép to|n cần thiết để giải b{i to|n ban đầu bằng tổng số c|c phép to|n cần thiết để giải mỗi b{i to|n con v{ số phép to|n cần thiết để thực hiện phép chuyển từ b{i to|n ban đầu sang c|c b{i to|n con. 2.3.4. Phương pháp liệt kê Việc giải c|c b{i to|n đếm dưới dạng tổng qu|t v{ nhận được một công thức cụ thể l{ một điều cực kì khó khăn. Cho đến nay, rất nhiều b{i to|n đếm chưa có lời giải dưới dạng một công thức cụ thể. Đối với những b{i to|n như thế, chúng ta cần sử dụng một phương ph|p liệt kê. Dù nó không chỉ ra một kết quả cụ thể, nhưng có thể sử dụng công cụ m|y tính để thực hiện phép đếm. 40
CHƯƠNG 3. BÀI TOÁN TỒN TẠI CHƯƠNG 3. BÀI TOÁN TỒN TẠI 3.1. Giới thiệu bài toán Trong nhiều b{i to|n tổ hợp, việc chỉ ra một cấu hình thỏa m~n c|c tính chất cho trước l{ một việc l{m khó khăn. Đối với b{i to|n dạng n{y, để giải quyết, chúng ta cần khảo s|t sự tồn tại của nó. Chúng được gọi l{ b{i to|n tồn tại. Một b{i to|n tồn tại tổ hợp được xem như giải xong, nếu hoặc chỉ ra một c|ch x}y dựng cấu hình hoặc chứng minh chúng không tồn tại. Bài toán 1. Bài toán về 36 sĩ quan . Có một lần người ta triệu tập từ 6 trung đo{n, mỗi trung đo{n 6 sĩ quan thuộc 6 cấp bậc kh|c nhau: thiếu uý, trung uý, thượng uý, đại uý, thiếu t|, trung t| về tham gia duyệt binh ở sư đo{n bộ. Hỏi rằng, có thể xếp 36 sĩ quan n{y th{nh một đội ngũ hình vuông sao cho trong mỗi h{ng ngang cũng như mỗi h{ng dọc đều có đại diện của cả sáu trung đo{n v{ của 6 cấp bậc. Để đơn giản ta sẽ dùng các chữ c|i in hoa A, B, C, D, E, F để chỉ phiên hiệu của c|c trung đo{n, c|c chữ c|i in thường a, b, c, d, e, f để chỉ cấp bậc. Bài toán này có thể tổng quát hoá nếu thay 6 bởi n. Trong trường hợp n = 4 một lời giải của bài toán 16 sĩ quan l{: Ab Dd Ba Cc Bc Ca Ad Db Cd Bb Dc Aa Da Ac Cb Bd Một lời giải với n = 5 là: Aa Bb Cc Dd Ee Cd De Bd Ab Bc Eb Ac Bd Ce Da Be Ca Db Ec Ad
CHƯƠNG 3. BÀI TOÁN TỒN TẠI Dc Ed Ae Ba Cb Do lời giải bài toán có thể biểu diễn bởi hai hình vuông với các chữ cái la tinh hoa v{ la tinh thường nên bài toán tổng qu|t đặt ra còn được biết với tên gọi “hình vuông la tinh trực giao”. Trong hai ví dụ trên ta có hình vuông la tinh trực giao cấp 4 và 5. Euler đ~ mất rất nhiều công sức để tìm ra lời giải cho b{i to|n 36 sĩ quan thế nhưng ông đ~ không th{nh công. Vì vậy, ông giả thuyết là cách sắp xếp như vậy không tồn tại. Giả thuyết n{y đ~ được nhà toán học pháp Tarri chứng minh năm 1901 bằng cách duyệt tất cả mọi khả năng xếp. Euler căn cứ vào sự không tồn tại lời giải khi n=2 v{ n = 6 còn đề ra giả thuyết tổng qu|t hơn l{ không tồn tại hình vuông trực giao cấp 4n + 2. Giả thuyết n{y đ~ tồn tại hai thế kỷ, m~i đến năm 1960 ba nh{ toán học Mỹ là Bore, Parker, Srikanda mới chỉ ra được một lời giải với n = 10 và sau đó chỉ ra phương ph|p x}y dựng hình vuông trực giao cho mọi n = 4k + 2 với k > 1. Tưởng chừng b{i to|n chỉ mang ý nghĩa thử th|ch trí tuệ con người thuần tuý như một b{i to|n đố. Nhưng gần đ}y, người ta ph|t hiện những ứng dụng quan trọng của vấn đề trên v{o qui hoạch, thực nghiệm v{ hình học xạ ảnh. Bài toán 2. Bài toán 4 màu. Có nhiều b{i to|n m{ nội dung của nó có thể giải thích được với bất kỳ ai, lời giải của nó ai cũng cố gắng thử tìm nhưng khó có thể tìm được. Ngo{i định lý Fermat thì b{i to|n bốn m{u cũng l{ một b{i to|n như vậy. B{i to|n có thể được ph|t biểu như sau: Chứng minh rằng mọi bản đồ đều có thể tô bằng 4 m{u sao cho không có hai nước l|ng giềng n{o lại bị tô bởi cùng một m{u. Trong đó, mỗi nước trên bản đồ được coi l{ một vùng liên thông, hai nước được gọi l{ l|ng giềng nếu chúng có chung đường biên giới l{ một đường liên tục. 42
CHƯƠNG 3. BÀI TOÁN TỒN TẠI 1 4 2 3 Hình 3.1 – Bài toán 4 màu Con số bốn màu không phải là ngẫu nhiên. Người ta đ~ chứng minh được rằng mọi bản đồ đều được tô bởi số màu lớn hơn 4, còn với số m{u ít hơn 4 thì không thể tô được, chẳng hạn bản đồ gồm 4 nước như trên hình 2.2 không thể tô được với số m{u ít hơn 4. B{i to|n n{y xuất hiện v{o những năm 1850 từ một l|i buôn người Anh l{ Gazri khi tô bản đồ h{nh chính nước Anh đ~ cố gắng chứng minh rằng nó có thể tô bằng bốn m{u. Sau đó, năm 1852, ông đ~ viết thư cho De Morgan để thông b|o về giả thuyết n{y. Năm 1878, Keli trong một b{i b|o đăng ở tuyển tập c|c công trình nghiên cứu của Hội to|n học Anh có hỏi rằng b{i to|n n{y đ~ được giải quyết hay chưa? Từ đó b{i to|n trở nên nổi tiếng, trong suốt hơn một thế kỷ qua, nhiều nh{ to|n học đ~ cố gắng chứng minh giả thuyết n{y. Tuy vậy, m~i tới năm 1976 hai nh{ to|n học Mỹ l{ K. Appel v{ W. Haken mới chứng minh được nó nhờ m|y tính điện tử. Bài toán 3. Hình lục giác thần bí. Năm 1890 Clifford Adams đề ra b{i to|n hình lục gi|c thần bí sau: trên 19 ô lục gi|c h~y điền c|c số từ 1 đến 19 sao cho tổng theo 6 hướng của lục gi|c l{ bằng nhau (v{ đều bằng 38). Sau 47 năm trời kiên nhẫn cuối cùng Adams cũng đ~ tìm được lời giải. Sau đó vì sơ ý đ|nh mất bản thảo ông đ~ tốn thêm 5 năm để khôi phục lại. Năm 1962 Adams đ~ công bố lời giải đó. Nhưng thật không thể ngờ được đó l{ lời giải duy nhất. 43
CHƯƠNG 3. BÀI TOÁN TỒN TẠI Hình 3.2 – B{i to|n hình lục gi|c thần bí 3.2. Phương pháp phản chứng Ý tưởng: Phương ph|p chứng minh phản chứng dựa trên hệ luật logic sau: ( ) ( ) Có nghĩa l{, để chứng minh mệnh đề l{ đúng, ta có thể chứng minh mệnh đề . Quy trình chứng minh. Để chứng minh một khẳng định theo phương ph|p phản chứng, ta cần thực thi c|c bước sau: . Bước 1. Giả sử hệ quả đ~ cho l{ sai. . Bước 2. Chứng minh quy tắc suy luận từ hệ quả sai sẽ dẫn đến một giả thiết tr|i ngược với giả thiết đ~ cho ban đầu. . Bước 3. Khẳng định đúng. Ví dụ 1. Cho 7 đoạn thẳng có độ dài lớn hơn 10 v{ nhỏ hơn 100. Chứng minh rằng ta luôn luôn tìm được 3 đoạn để có thể ghép lại thành một tam giác. Giải. Điều kiện cần v{ đủ để 3 đoạn là cạnh của một tam giác là tổng của hai cạnh phải lớn hơn một cạnh. Ta sắp c|c đoạn thẳng theo thứ tự tăng dần của độ dài và chứng minh rằng d~y đ~ xếp luôn tìm được 3 đoạn mà tổng của hai đoạn đầu lớn hơn đoạn cuối. Bước 1. Giả sử không tìm được ba đoạn nào mà tổng của hai đoạn nhỏ hơn một đoạn. 44
CHƯƠNG 3. BÀI TOÁN TỒN TẠI Bước 2. Theo tính chất của bất đẳng thức tam giác: ( ) ( ) ( ) ( ) ( ) M}u thuẫn (vì tất cả c|c cạnh đều có độ d{i nhỏ hơn 100). Bước 3. Vậy, ta luôn tìm được 3 đoạn thẳng thỏa m~n yêu cầu. Ví dụ 2. C|c đỉnh của một thập gi|c đều được đ|nh số bởi các số nguyên 0, 1, , 9 một cách tuỳ ý. Chứng minh rằng luôn tìm được ba đỉnh liên tiếp có tổng các số là lớn hơn 13. Giải. Gọi x1, x2, , x10 là các số g|n cho c|c đỉnh của thập gi|c đều. Bước 1. Giả sử ngược lại ta không tìm được 3 đỉnh liên tiếp nào thoả mãn khẳng định trên. Bước 2. Theo giả thiết ta có: Cộng các bất đẳng thức trên theo vế: ( ) ( ) 45
CHƯƠNG 3. BÀI TOÁN TỒN TẠI Bất đẳng thức sai, suy ra m}u thuẩn. Bước 3. Khẳng định được chứng minh. 3.2. Nguyên lý Dirichlet 3.2.1. Phát biểu nguyên lý 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 có nhiều hơn một con chim. Nguyên lý n{y dĩ nhiên l{ có thể |p dụng cho c|c đối tượng không phải l{ chim bồ c}u v{ chuồng chim. Nguyên lý. Nếu có k+1 (hoặc nhiều hơn) đồ vật được đặt v{o trong k hộp thì tồn tại một hộp có ít nhất hai đồ vật. Chứng minh. Chúng ta sử dụng phương ph|p phản chứng. Giả sử rằng mỗi hộp chứa tối đa l{ 1 đồ vật. Ta có k hộp, nghĩa l{ có k đồ vật. Điều n{y tr|i với giả thiết có k+1 đồ vật. Các ví dụ 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 có ng{y sinh nhật giống nhau bởi vì chỉ có tất cả 366 ng{y sinh nhật kh|c nhau. Ví dụ 2. Trong kỳ thi học sinh giỏi, điểm b{i thi được đ|nh gi| bởi một số nguyên trong khoảng từ 0 đến 100. Hỏi rằng ít nhất 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? Theo nguyên lý Dirichlet, số học sinh cần tìm l{ 102, vì ta có 101 kết quả điểm thi kh|c nhau. 3.2.2. Nguyên lý Dirichlet tổng quát Nguyên lý. Nếu có N đồ vật được đặt vào trong k hộp thì sẽ tồn tại một hộp chứa ít nhất ⌈ ⌉ đồ vật. Trong đó, h{m ⌈ ⌉ dùng để lấy trần của một số (nghĩa l{ số nguyên cận trên đúng của nó). Cần lưu ý rằng, trong c|c phép to|n l{m tròn số, ta có , - - Phép lấy phần nguyên. ⌈ ⌉ - Phép làm tròn lên (hay phép lấy trần) hay hàm (). ⌊ ⌋ - Phép làm tròn xuống (hay phép lấy sàn) hay hàm (). 46
CHƯƠNG 3. BÀI TOÁN TỒN TẠI Các ví dụ Ví dụ 1. Trong 100 người, có ít nhất 9 người sinh cùng một th|ng. Xếp những người sinh cùng th|ng v{o một nhóm. Một năm có 12 th|ng. Vậy theo nguyên lý Dirichlet, tồn tại một nhóm có ít nhất ⌈ ⌉ ⌈ ⌉ người. Ví dụ 2. Có năm loại học bổng kh|c nhau. Hỏi rằng phải có ít nhất bao nhiêu sinh viên để chắc chắn rằng có ít ra l{ 6 người cùng nhận học bổng như nhau. Gọi N là số sinh viên, khi đó ⌈ ⌉ khi v{ chỉ khi 5 < N div 5 6 hay 25 < N 30. C|c số thỏa m~n điều kiện n{y bao gồm 26, 27, 28, 29 v{ 30. Nhưng yêu cầu tìm số sinh viên ít nhất, do đó số N cần tìm l{ 26. Tổng quát: Nếu cần tìm nhỏ nhất, sao cho ⌈ ⌉ thì ( ) Ví dụ 3. Trong một hình vuông cạnh 1. H~y chứng tỏ rằng nếu gieo v{o đó 5 điểm thì có ít nhất hai điểm có khoảng c|ch nhỏ hơn √ . Nếu ta chia hình vuông cạnh 1 th{nh 4 hình vuông con. Thì khoảng c|ch tối đa của hai điểm trong một hình vuông nhỏ không vượt qu| độ d{i của đường chéo l{ √ . Nếu ta gieo v{o 5 điểm trong hình vuông, thì sẽ có ít nhất ⌈ ⌉ điểm nằm trong một hình vuông nhỏ. Suy ra, sẽ luôn tồn tại hai điểm có khoảng c|ch nhỏ hơn √ . Ví dụ 4. Cho hình thang c}n, có đ|y lớn l{ 2, đ|y bé l{ 1, chiều cao l{ 1. Người ta gieo v{o đó 13 điểm. H~y chứng minh rằng, luôn tồn tại ít nhất 3 điểm m{ diện tích của hình tạo bởi ba điểm đó nhỏ hơn ¼. Dễ d{ng chứng tỏ được rằng mỗi phần được chia như trên có diện tích ¼. Khi gieo v{o 13 điểm, sẽ có ít nhất ⌈ ⌉ điểm nằm trong 1 phần. Suy ra 3 điểm nằm trong một vùng diện tích ¼ thì diện tích tạo bởi chúng nhỏ hơn ¼. 47
CHƯƠNG 4. BÀI TOÁN LIỆT KÊ CHƯƠNG 4. BÀI TOÁN LIỆT KÊ 4.1. Giới thiệu bài toán Bài toán đưa ra danh s|ch tất cả các cấu hình tổ hợp có thể có được gọi là bài toán liệt kê tổ hợp. Khác với b{i to|n đếm là tìm kiếm một công thức cho lời giải, bài toán liệt kê lại cần x|c định một thuật to|n để theo đó có thể xây dựng được lần lượt tất cả các cấu hình cần quan tâm. Một thuật toán liệt kê phải đảm bảo hai nguyên tắc: Không được lặp lại một cấu hình Không được bỏ sót một cấu hình Ví dụ 1. Cho tập hợp các số a1, a2, , an và số M. Hãy tìm tất cả các tập con k phần tử của dãy số {an} sao cho tổng số các phần tử trong tập con đó đúng bằng M. Giải. Như chúng ta đ~ biết, số các tập con k phần tử của tập gồm n phần tử là . Như vậy chúng ta cần phải duyệt trong số tập k phần tử để lấy ra những tập có tổng các phần tử đúng bằng M. Vì không thể x|c định được có bao nhiêu tập k phần tử từ tập n phần tử có tổng các phần tử đúng bằng M nên chúng ta chỉ còn cách liệt kê các cấu hình thoả m~n điều kiện đ~ cho. Ví dụ 2. Một thương nh}n đi b|n h{ng tại tám thành phố. Chị ta có thể bắt đầu hành trình của mình tại một thành phố n{o đó nhưng phải qua 7 thành phố kia theo bất kỳ thứ tự nào mà chị ta muốn. Hãy chỉ ra lộ trình ngắn nhất mà chị ta có thể đi. Giải. Vì thành phố xuất ph|t đ~ được x|c định. Do vậy thương nh}n có thể chọn tuỳ ý 7 thành phố còn lại để h{nh trình. Như vậy, tất cả số hành trình của thương nh}n có thể đi qua l{ 7! = 5040 cách. Tuy nhiên trong 5040 cách chúng ta phải duyệt toàn bộ để chỉ ra một hành trình là ngẵn nhất. Có thể nói phương ph|p liệt kê l{ biện ph|p cuối cùng nhưng cũng l{ biện ph|p phổ dụng nhất để giải quyết c|c b{i to|n tổ hợp. Khó khăn chính của phương ph|p n{y l{ sự bùng nổ tổ hợp. Để x}y dựng chừng 1 tỷ cấu hình, giả sử cần 1 gi}y để liệt kê một cấu hình thì chúng ta cũng cần 31 năm mới giải quyết xong. Tuy nhiên với sự ph|t triển nhanh chóng của m|y tính, bằng phương ph|p liệt kê, nhiều b{i to|n khó của lý
CHƯƠNG 4. BÀI TOÁN LIỆT KÊ thuyết tổ hợp đ~ được giải quyết v{ góp phần thúc đẩy sự ph|t triển của nhiều ng{nh to|n học. 4.2.Thuật toán quay lui Để giải quyết những bài toán tổ hợp phức tạp, người ta thường dùng thuật toán quay lui (Back Track) sẽ được trình b{y dưới đ}y. Nội dung chính của thuật toán này là 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. Giả sử cần phải tìm một cấu hình của bài toán x = (x1, x2, , xn) mà i-1 thành phần x1, x2, , xi-1 đ~ được x|c định, bây giờ ta x|c định thành phần thứ i của cấu hình bằng cách duyệt tất cả các khả năng có thể có v{ đ|nh số các khả năng từ 1 ni. Với mỗi khả năng j, kiểm tra xem j có chấp nhận được hay không. Khi đó có thể xảy ra hai trường hợp: Nếu chấp nhận j thì x|c định xi theo j, nếu i=n thì ta được một cấu hình cần tìm, ngược lại x|c định tiếp thành phần xi+1. Nếu thử tất cả các khả năng m{ không có khả năng n{o được chấp nhận thì quay lại bước trước đó để x|c định lại xi-1. Điểm quan trọng nhất của thuật to|n l{ phải ghi nhớ lại mỗi bước đ~ đi qua, những khả năng n{o đ~ được thử để tr|nh sự trùng lặp. Để nhớ lại những bước duyệt trước đó, chương trình cần phải được tổ chức theo cơ chế ngăn xếp (Last in first out). Vì vậy, thuật to|n quay lui rất phù hợp với những phép gọi đệ qui. Thuật to|n quay lui x|c định th{nh phần thứ i có thể được mô tả bằng thủ tục Try(i) như sau: void Try( int i ) { int j; for ( j = 1; j ) { if (i==n) ; 49
CHƯƠNG 4. BÀI TOÁN LIỆT KÊ else Try(i+1); } } Có thể mô tả quá trình tìm kiếm lời giải theo thuật toán quay lui bằng cây tìm kiếm lời giải sau: Gốc Khả năng chọn x1 Khả năng chọn x2 Khả năng chọn x3 Khả năng chọn x4 Hình 4.1 – C}y tìm kiếm thuật to|n quay lùi Bài tập áp dụng Ví dụ 1. Liệt kê các xâu nhị ph}n độ dài n. Giải. Biểu diễn c|c x}u nhị ph}n dưới dạng b1, b2, , bn, trong đó bi {0, 1 }. Thủ tục đệ qui Try(i) x|c định bi với c|c gi| trị đề cử cho bi là 0 và 1. Chẳng hạn với n =3, c}y tìm kiếm lời giải được thể hiện như sau. Gốc 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Hình 4.2 – C}y tìm kiếm x}u nhị ph}n độ d{i 3 50
CHƯƠNG 4. BÀI TOÁN LIỆT KÊ Ví dụ 2. Liệt kê các tập con k phần tử của tập n phần tử. Giải. Biểu diễn tập con k phần tử dưới dạng c1, c2, , ck, trong đó 1< c1<c2 ≤n. Từ đó suy ra các giá trị đề cử cho ci là từ ci-1 + 1 cho đến n - k + i. Cần thêm vào c0 = 0. C}y tìm kiếm lời giải b{i to|n liệt kê tập con k phần tử của tập n phần tử với n=5, k=3 được thể hiện như dưới đ}y. Gốc 1 2 3 2 3 4 3 4 4 3 4 5 4 5 5 4 5 5 5 Hình 4.3 – C}y tìm kiếm c|c tập con 3 phần tử của tập 5 phần tử Ví dụ 4. Bài toán Xếp Hậu. Liệt kê tất cả các cách xếp n quân hậu trên bàn cờ sao cho chúng không ăn được nhau. Giải. Bàn cờ có n h{ng được đ|nh số từ 0 đến n-1, n cột được đ|nh số từ 0 đến n-1; Bàn cờ có n*2 -1 đường chéo xuôi được đ|nh số từ 0 đến 2*n -2, 2 *n -1 đường chéo ngược được đ|nh số từ 2*n -2. Ví dụ: với bàn cờ 8 x 8, chúng ta có 8 h{ng được đ|nh số từ 0 đến 7, 8 cột được đ|nh số từ 0 đến 7, 15 đường chéo xuôi, 15 đường chéo ngược được đ|nh số từ 0 15. Vì trên mỗi hàng chỉ xếp được đúng một quân hậu, nên chúng ta chỉ cần quan tâm đến quân hậu được xếp ở cột nào. Từ đó dẫn đến việc x|c định bộ n thành phần x1, x2, , xn, trong đó xi = j được hiểu là quân hậu tại dòng i xếp vào cột thứ j. Giá trị của i được nhận từ 0 đến n-1; giá trị của j cũng được nhận từ 0 đến n-1, nhưng thoả mãn điều kiện ô (i,j) chưa bị quân hậu khác chiếu đến theo cột, đường chéo xuôi, đường chéo ngược. 51
CHƯƠNG 4. BÀI TOÁN LIỆT KÊ Việc kiểm so|t theo h{ng ngang l{ không cần thiết vì trên mỗi h{ng chỉ xếp đúng một qu}n hậu. Việc kiểm so|t theo cột được ghi nhận nhờ d~y biến logic aj với qui ước aj=1 nếu cột j còn trống, cột aj=0 nếu cột j không còn trống. Để ghi nhận đường chéo xuôi v{ đường chéo ngược có chiếu tới ô (i,j) hay không, ta sử dụng phương trình i + j = const và i - j = const, đường chéo thứ nhất được ghi nhận bởi d~y biến bj, đường chéo thứ 2 được ghi nhận bởi d~y biến cj với qui ước nếu đường chéo n{o còn trống thì gi| trị tương ứng của nó l{ 1 ngược lại l{ 0. Như vậy, cột j được chấp nhận khi cả 3 biến aj, bi+j, ci+j đều có gi| trị 1. C|c biến n{y phải được khởi đầu gi| trị 1 trước đó, g|n lại gi| trị 0 khi xếp xong qu}n hậu thứ i v{ trả lại gi| trị 1 khi đưa ra kết quả. Dưới đ}y l{ số cách xếp hậu ứng với n. n 4 7 8 9 10 11 12 13 14 Hn 2 40 92 352 724 2680 14200 73712 365596 52
CHƯƠNG 5. BÀI TOÁN TỐI ƯU CHƯƠNG 5. BÀI TOÁN TỐI ƯU 5.1. Phát biểu bài toán “Trong tất cả các cấu hình tổ hợp chấp nhận được của một bài toán tổ hợp, hãy tìm cấu hình tổ hợp có giá trị sử dụng tốt nhất (theo một mục đích nào đó)”. B{i to|n ta vừa nêu l{ b{i to|n tối ưu tổ hợp. Tối ưu tổ hợp cũng l{ một ph}n ng{nh của Tối ưu hóa v{ cũng l{ một ph}n ng{nh của To|n rời rạc. B{i to|n tối ưu tổ hợp có thể ph|t biểu tổng qu|t như sau: Tìm cực tiểu (hay cực đại) của h{m: f(x) min (hoặc max), với x D; trong đó D l{ tập hữu hạn phần tử. H{m f(x) được gọi l{ h{m mục tiêu của b{i to|n, mỗi phần tử x D được gọi l{ một phương |n, còn tập D gọi l{ tập c|c phương |n của b{i to|n. Phần tử x D m{ với phần tử n{y, h{m mục tiêu đạt gi| trị tối ưu được gọi l{ phương |n tối ưu. 5.2. Thuật toán nhánh và cận 5.2.1. Bài toán Tìm min{f(x) : x D} với D l{ tập hữu hạn phần tử. Giả sử D được mô tả như sau: D = {x = (x1, x2, ,xn) A1 A2 An: x thoả m~n tính chất P}, với A1 A2 An l{ c|c tập hữu hạn, còn P l{ tính chất cho trên tích Đềc|c A1 A2 An . Thuật to|n nh|nh v{ cận có thể giải b{i to|n n{y nếu như có thể tìm được một h{m g thoả m~n bất đẳng thức sau: g(a1,a2, ,ak) min{f(x) : x D, xi = ai, i = 1,2, ,k}, với k = 1,2, 5.2.2. Thuật toán nhánh và cận void Try(k) { for ak Ak
CHƯƠNG 5. BÀI TOÁN TỐI ƯU if { xk = ak; if (k==n) ; else Try(k+1); } } void Nhanh_can() { f = + ; Try(1); if ( f ; else ; } 5.2.3. Ví dụ a. Bài toán cái túi Phát biểu. Có n loại đồ vật, đồ vật thứ j có trọng lượng aj và giá trị sử dụng là ( ). Cần chất c|c đồ vật n{y v{o một c|i túi có khả năng chứa trọng lượng tối đa là b sao cho tổng giá trị sử dụng của c|c đồ vật chất trong túi là lớn nhất. Mô hình toán. Giả sử rằng ( ) là vector trạng thái của c|c đồ vật. Thành phần có khả năng nhận một trong hai giá trị là 0 hoặc 1. Nếu nhận giá trị 0, có nghĩa l{ vật thứ j sẽ không có trong túi, ngược lại nhận giá trị 1, có nghĩa l{ vật thứ j sẽ có trong túi. Nếu nhận một giá trị lớn hơn 1, có nghĩa l{ đồ vật thứ sẽ chứa nhiều hơn 1 lần trong túi. Gọi f(x) l{ gi| trị sử dụng của c|c đồ vật. Khi đó, ta có 54
CHƯƠNG 5. BÀI TOÁN TỐI ƯU ( ) ∑ H{m n{y được gọi là hàm mục tiêu. Trọng lượng của c|c đồ vật có trong túi là ∑ Theo yêu cầu của bài toán, ta cần tìm bộ ( ) sao cho hàm ( ) . Do đó, mô hình to|n của bài toán cái túi nhận được là ( ) ∑ ( ) ∑ , - { Có nhiều phương ph|p để giải bài toán cái túi: phương ph|p lặp đơn hình (Simplex method), giải thuật tham lam (greedy approximation algorithm) Tuy nhiên, trong chương n{y, chúng ta chỉ nghiên cứu phương ph|p nh|nh cận. Phương pháp giải. Ta cần tìm hàm ( ) sao cho ( ) ∑ ( ) ( ) ∑ { Kí hiệu M là tập c|c phương |n của bài toán (1). Không giảm tổng quát ta giả thiết rằng c|c đồ vật được đ|nh số sao cho bất đẳng thức sau được thoả mãn: ( ) Để xây dựng hàm tính cận dưới, cùng với bài toán cái túi (1), ta xét bài toán cái túi biến liên tục sau: 55
CHƯƠNG 5. BÀI TOÁN TỐI ƯU ( ) ∑ ( ) ( ) ∑ { Lưu ý. Tập là tập số nguyên dương (không chứa số 0), tập l{ tập số tự nhiên (chứa số 0). Mệnh đề. Phương án tối ưu của bài toán (3) là vectơ x (x1, x2 , , xn ) với các thành phần được xác định bởi công thức: b x1 , x2 x3 xn 0 a1 và giá trị tối ưu là g* = . Giả sử ta có phương |n bộ phận cấp k là ̅ ( ̅ ̅̅ ̅ ̅̅ ̅). Khi đó gi| trị sử dụng của c|c đồ vật đang có trong túi l{: ∑ ̅ và trọng lượng còn lại của cái túi là: ∑ ̅ Khi đó, công thức (3) có thể viết lại như sau: ( ) {∑ ∑ , -} {∑ ∑ ∑ ∑ , -} 56
CHƯƠNG 5. BÀI TOÁN TỐI ƯU { ∑ ∑ , -} Vì giá trị l{ phương |n tối ưu bộ phận cấp , nên giá trị là cố định, do đó ( ) { ∑ ∑ , -} Khi chuyển sang bước lặp tiếp theo, ta xét trường hợp khi đó: ( ) * + Đặt và công thức này cho phép ta tính cận trên cho phương |n bộ phận cấp Mô tả thuật toán ̅ Bước 1. Đặt ̅ ( ̅ ̅̅ ̅ ̅̅ ̅). Khởi tạo giá trị k=1. Bước 2. Thực hiện thuật toán rẽ nhánh theo phương |n tối ưu bộ phận từ gốc .̅ Tương ứng với gốc này, ta rẽ nhánh theo các phần tử ̅ ̅̅ ̅ ̅̅ ̅. 57
CHƯƠNG 5. BÀI TOÁN TỐI ƯU ̅ k=1 ̅ ( ) ̅ ( ) k=2 ̅ ( ) ̅ ( ) ̅ ( ) ̅ ( ) Hình 5.1 – Cây tìm kiếm thuật toán nhánh cận cho bài toán cái túi Bước 3. Tại các nút nhánh, ta thực hiện tính toán các giá trị ∑ ̅ ∑ ̅ tương ứng với c|c phương |n bộ phận ̅. Bước 4. Tăng gi| trị k v{ quay lại bước 2. Thuật to|n sẽ dừng nếu gi| trị k=n. Trong qu| trình tính to|n, nếu tại một nút nh|nh n{o đó, gi| trị hoặc thì ta sẽ không tiến hành rẽ nh|nh theo nh|nh n{y. Trong đó, gọi là kỉ lục. Nó là giá trị lớn nhất trong các giá trị mà ta đ~ tính to|n trước đó. Gi| trị kỉ lục n{y phải được cập nhật thường xuyên sau mỗi phương |n được tìm thấy. Nếu tại một nút nào 58
CHƯƠNG 5. BÀI TOÁN TỐI ƯU đó, việc rẽ nh|nh không được thực thi, ta không cần cập nhật lại kỉ lục trong bước lặp này. Ví dụ. Giải bài toán cái túi sau theo thuật toán nhánh và cận ( ) { Giải. Qu| trình giải b{i to|n được mô tả trong c}y tìm kiếm trong hình sau. Thông tin về một phương |n bộ phận trên c}y được ghi trong c|c ô trên hình vẽ. Gốc 풇̅ x1=1 x1=0 (1): 1=10; (0): 1=0; k=1 w1=3; g1=15 w1=8; g1=40/3 x2=1 x2=0 (1,1): 2=15; (1,0): 2=10; Loại vì cận trên < kỷ w2=0; g2=15 w2=3; g2=14,5 lục k=2 x3=0 (1,1,0): 3=15; w3=0; g3=15 k=3 x4=0 풙̅=(1,1,0,0); Thu được phương |n của bài toán. 풇̅=15 Cập nhật lại kỷ lục k=4 Hình 5.2 – Tiến trình thực thi giải thuật nh|nh cận cho bài toán cái túi Kết thúc thuật to|n, ta thu được phương |n tối ưu l{ x* = (1, 1, 0, 0) v{ gi| trị tối ưu là f * = 15. b. Bài toán người du lịch 59
CHƯƠNG 5. BÀI TOÁN TỐI ƯU Phát biểu. Giả sử ta có n th{nh phố được đ|nh chỉ số l{ 1, 2, n. Người đi du lịch xuất ph|t tại một th{nh phố bất kì cần đi qua tất cả c|c th{nh phố còn lại, mỗi th{nh phố đi qua đúng một lần v{ quay lại th{nh phố ban đầu. H~y tìm một đường đi tối ưu nhất. Thông thường nguyên lý tối ưu trong trường hợp n{y l{ tối ưu về tổng chi phí bỏ ra, cũng chính là tổng trọng số của c|c đường đi từ . Trọng số này có thể hiểu là khoảng cách về không gian hay chi phí đường đi Vì vậy, với n thành phố, thì bài toán du lịch sẽ dẫn đến một ma trận trọng số ( ) – trong đó mỗi phần tử là chi phí bỏ ra để đi từ thành phố . Một c|ch tự nhiên, c|c phần tử trên đường chéo của ma trận chi phí sẽ không x|c định. B{i to|n người du lịch có một ứng dụng rất lớn trong thực tiễn, rất nhiều b{i to|n đếm trong lí thuyết tổ hợp đều được đưa về dạng b{i to|n n{y. Thuật toán nhánh cận để giải bài toán người du lịch. Nếu sử dụng phương ph|p liệt kê, ta cần khảo s|t đến n! cấu hình tổ hợp. Tuy nhiên, trong lộ trình đi, người du lịch xuất ph|t tại một th{nh phố bất kì v{ quay trở lại th{nh phố ban đầu nên nếu ta cố định một thành phố ban đầu là , thì ta chỉ phải xét đến ( ) cấu hình tổ hợp. Mô hình toán của bài toán người du lịch Gọi ( ) l{ h{m mục tiêu tương ứng với độ d{i của lộ trình. Khi đó b{i to|n sẽ biểu diễn dưới dạng mô hình to|n sau: ( ) ∑ Phương pháp giải Gọi { | } là cận dưới chi phí. Giả sử ta đ~ tìm ra được k thành phố v{ khi đó, h{nh trình bộ phận qua k thành phố này là ( ) ( ) ( ) Trong đó, là k thành phố trong n thành phố . 60
CHƯƠNG 5. BÀI TOÁN TỐI ƯU Chi phí cho hành trình bộ phận này là ( ) ( ) ∑ Để x}y dựng một h{nh trình ho{n chỉnh, ta cần đi qua n-k th{nh phố còn lại v{ sau đó quay lại thành phố ban đầu. Nghĩa l{ cần đi qua thêm n-k+1 thành phố. Do đó, cận dưới của phương |n bộ phận này là ( ) ( ) ( ) Để tr|nh rườm rà, trong thuật toán, ta sẽ sử dụng và để thay thế cho ( ) và ( ). Thuật toán ̅ Bước 1. Cố định đỉnh 1, tính * +. Đặt ̅ ( ) . Khởi tạo gi| trị k=1. Bước 2. Thực hiện thuật to|n rẽ nh|nh theo phương |n tối ưu bộ phận từ gốc .̅ Tương ứng với gốc này, ta rẽ nhánh theo các phần tử . ̅ ̅ ( ) k=1 ̅ ( ) ̅ ( 푛) k=2 k=3 Hình 5.3 – Cây tìm kiếm thuật toán nhánh cận cho b{i to|n người du lịch 61
CHƯƠNG 5. BÀI TOÁN TỐI ƯU Bước 3. Tại các nút nhánh, ta thực hiện tính toán các giá trị ∑ ( ) tương ứng với c|c phương |n bộ phận ̅. Bước 4. Tăng gi| trị k và quay lại bước 2. Thuật toán sẽ dừng nếu giá trị k=n. Trong quá trình tính toán, nếu tại một nút nh|nh n{o đó, gi| trị thì ta sẽ không tiến h{nh rẽ nh|nh theo nh|nh n{y. Trong đó, gọi là kỉ lục. Nó là giá trị lớn nhất trong các giá trị m{ ta đ~ tính to|n trước đó. Ví dụ: Giải b{i to|n người du lịch với ma trận chi phí cho sau đ}y: ( ) Trong phương |n (1, 2, 3, 4, 5, 1), ta có . Với phương |n (1, 2, 3, 5, 4, 1), ta có . Do đó, ta chọn phương |n tối ưu cục bộ l{ 22 – cũng l{ kỉ lục hiện tại. C|c phương |n còn lại bị loại như hình vẽ. 62
CHƯƠNG 5. BÀI TOÁN TỐI ƯU ( ) ̅ 풌 ( ) 휕 ( ) 휕 ( ) 휕 ( ) 휕 풌 ( ) 휕 ( ) 휕 ( ) 휕 풌 ( ) ( ) 휕 휕 풌 ퟒ Loại vì ̅ ( ) 휕 ( ) 휕 풌 Hình 5.4 – Tiến trình thực thi giải thuật nh|nh cận cho b{i to|n người du lịch Kĩ thuật giảm nhánh cho thuật toán nhánh cận để giải bài toán người du lịch. Giả sử chúng ta cần tìm gi| trị tối thiểu của h{m mục tiêu Z f (x) min x  ở đó  – l{ tập hữu hạn c|c phương |n X. Để sử dụng phương ph|p nh|nh cận, ta cần thực hiện c|c bước chính sau đ}y a) Bước tạo nhánh. Giải sử tồn tại một quy tắc để phân hoạch tập th{nh c|c tập л (1) (1) (1) con: 1 , ,k sao cho i . Ta tiếp tục qu| trình ph}n hoạch c|c tập con i 1 cho đến khi thu được tập con không thể phân hoạch được (gọi l{ đỉnh treo). 63
CHƯƠNG 5. BÀI TOÁN TỐI ƯU . Hình 5.5 – Sơ đồ phân nhánh trong giải thuật thu gọn b) Tính cận dưới của hàm mục tiêu. Với mỗi tập con , ta nhận được kết quả ph}n nh|nh để tính to|n cận dưới của h{m mục tiêu trên tập con n{y. Nghĩa l{ (k ) , sao cho f (x) (k )x k . c) Tính lại đánh giá. Nếu hai tập 1 và 2 thỏa điều kiện 1  2 , thì rõ ràng, hàm mục tiêu sẽ thỏa bất đẳng thức sau: min f (x) min f (x) x 1 x 2 Chúng ta có thể coi rằng, với mỗi phân hoạch tập thành các tập con thì phương ph|p tính cận dưới cần thỏa m~n( i ) ( ) nghĩa l{, việc ph}n nh|nh sẽ l{m cho cận dưới luôn tăng. d) Xây dựng phương án. Nếu trong một mắc xích n{o đó của đồ thị ph}n nh|nh, ta tìm được một đỉnh mà không thể tiếp tục ph}n nh|nh, thì cần có một mắc xích để x}y dựng nên phương |n tương ứng cho nó. Phương ph|p cụ thể để x}y dựng sẽ tùy thuộc v{o c|c đặc trưng của mỗi bài toán. e) Dấu hiệu nhận biết tính tối ưu. Đối với mỗi bài toán cụ thể, cần áp dụng nguyên lí sau: nếu tại một bước ph}n nh|nh, ta tìm được một phương |n tối ưu ̅ và f (X ) (i ) min(k ), ở đó, cực tiểu được chọn tương ứng với đỉnh treo của đồ thị ph}n nh|nh, nên phương |n n{y l{ phương |n tối ưu. V{ không thể có một cận dưới nhỏ hơn cận dưới của phương |n tối ưu n{y. 64
CHƯƠNG 5. BÀI TOÁN TỐI ƯU f) Phương pháp giảm thiểu việc phân nhánh. Về cơ bản, chúng ta cần tìm một phương |n n{o đó trong tập . Phương |n n{y gọi l{ kỉ lục. V{ chúng ta sẽ không khảo s|t những đỉnh treo m{ cận dưới của nó vượt kỉ lục. Thuật toán nhánh cận để giải bài toán người du lịch. Thuật to|n n{y được giới thiệu đầu tiên bởi nh{ to|n học Lit năm 1963. Giả sử ma trận chi phí l{ Cc []ij n n . Kí hiệu nghĩa l{ không tồn tại đường đi từ . Thuật to|n sẽ thực hiện c|c bước sau đ}y: Bước 1. Tìm trên mỗi dòng ma trận C phần tử nhỏ nhất v{ trừ tất cả c|c phần tử trên c|c dòng n{y cho phần tử nhỏ nhất tương ứng. Nếu ta nhận được một ma trận mà trên một cột bất kì không chứa phần tử 0 thì ta tiếp tục tìm phần tử nhỏ nhất trên mỗi cột và trừ tất cả các phần tử trên cột đó cho phần tử nhỏ nhất này. Kết quả, ta nhận được một ma trận m{ mỗi dòng, mỗi cột của nó đều có ít nhất một phần tử 0. Bước 2. Tính tổng của tất cả các phần tử đ~ trừ ở bước 1. Rõ ràng rằng, tổng này là cận dưới của tập , mà ta sẽ chọn làm gốc để phân nhánh. Bước 3. Chọn cung ( ) sao cho (xk , x l ) max ( x k , x l ) , (1) ()ij ở đó  (xk , xl ) – là tổng phần tử nhỏ nhất ở dòng (trừ ) và phần tử nhỏ nhất ở cột (trừ ) mà . Xét tính chất Pij : Lộ trình không chứa cung ( ) và Lộ trình chứa cung ( ). Đối với lộ trình không chứa cung ( ) ta sẽ bỏ đi dòng và cột . Còn đối với lộ trình chứa cung ( ) ta sẽ thay phần tử . Bước 4. Tính (xk , xl ) theo công thức (1) v{ cộng thêm nó v{o cận của đỉnh tương ứng của c}y bên phải. Tổng n{y sẽ l{ cận cho đỉnh mới được x|c định theo tính chất Pkl . Bước 5. Tương tự, như ở bước 4, ta nối với đỉnh ở c}y bên phải x|c định theo tính chất Pkl : Lộ trình sử dụng cung (xk , xl ) . Xóa dòng k v{ cột l của ma trận và thay bằng phần tử cho gi| trị tương ứng với cung n{y. 65
CHƯƠNG 5. BÀI TOÁN TỐI ƯU Bước 6. Thực hiện như bước 1 đối với ma trận mới thu được ở bước 5. Bước 7. Thực hiện như ở bước 2 đối với ma trận nhận được ở bước 6. Bổ sung tổng nhận được thêm cho cận. Bước 8. Nếu trong bước 5 ta nhận được ma trận bậc 1, thì tiến trình kết thúc. Ngược lại, chuyển sang bước 9. Bước 9. Trong số c|c đỉnh treo của c}y bên phải đ~ x}y dựng, ta chọn đỉnh có cận nhỏ nhất (nếu có nhiều đỉnh có cùng cận, ta chọn một đỉnh bất kì). Bước 10. Nếu chọn được một đỉnh ở bước 9 thỏa tính chất Pij , thì ta chuyển sang bước 3, ngược lại chuyển sang bước 11. Bước 11. Giá trị của phần tử của ma trận tương ứng với đỉnh treo được chọn ở bước 10 chuyển th{nh . Tại dòng thứ cũng như cột , ta tìm phần tử bé nhất v{ trừ tất cả c|c phần tử của dòng hoặc cột n{y cho nó. Chuyển sang bước 3. Ví dụ. Đầu tiên, ta tìm trên mỗi dòng của ma trận phần tử nhỏ nhất. i j 1 2 3 4 5 min 1 M 90 80 40 100 40 2 60 M 40 50 70 40 3 50 30 M 60 20 20 4 10 70 20 M 50 10 5 20 40 50 20 M 20 Sau đó, trừ tất cả c|c phần tử trên mỗi dòng cho phần tử nhỏ nhất của dòng đó. Sau bước n{y, ta nhận được ma trận m{ mỗi dòng đều có phần tử 0. i j 1 2 3 4 5 1 M 50 40 0 60 2 20 M 0 10 30 3 30 10 M 40 0 4 0 60 10 M 40 66
CHƯƠNG 5. BÀI TOÁN TỐI ƯU 5 0 20 30 0 M Thực hiện qu| trình trên đối với cột. i j 1 2 3 4 5 1 M 50 40 0 60 2 20 M 0 10 30 3 30 10 M 40 0 4 0 60 10 M 40 5 0 20 30 0 M dj 0 10 0 0 0 i j 1 2 3 4 5 1 M 40 40 0 60 2 20 M 0 10 30 3 30 0 M 40 0 4 0 50 10 M 40 5 0 10 30 0 M Sau khi thực hiện qu| trình n{y, ta nhận được ma trận có c|c dòng v{ cột đều chứa phần tử 0. Cận dưới =140. Tương ứng với mỗi đỉnh khi ph}n nh|nh, ta có hai tập con l{ tập chứa cạnh đó v{ tập không chứa cạnh đó. Tại mỗi ô có gi| trị 0 của ma trận, ta tính một hằng số l{ tổng của phần tử nhỏ nhất theo dòng v{ nhỏ nhất theo cột tương ứng với nó. Gi| trị hằng n{y được ghi trong dấu ngoặc đơn. i j 1 2 3 4 5 di 1 M 40 40 0(40) 60 40 2 20 M 0(20) 10 30 10 67
CHƯƠNG 5. BÀI TOÁN TỐI ƯU 3 30 0(10) M 40 0(30) 0 4 0(10) 50 10 M 40 10 5 0(0) 10 30 0(0) M 0 dj 0 10 10 0 30 0 d(1,4) = 40 + 0 = 40; d(2,3) = 10 + 10 = 20; d(3,2) = 0 + 10 = 10; d(3,5) = 0 + 30 = 30; d(4,1) = 10 + 0 = 10; d(5,1) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0; Gi| trị hằng lớn nhất l{ 40 tương ứng với (1,4). Nghĩa l{ tập đỉnh ph}n th{nh hai tập con: tập chứa cạnh (1, 4) v{ tập không chứa cạnh (1, 4). Cận dưới của tập con chứa cạnh (1, 4) là 140 + 40 = 180. Đối với tập không chứa cạnh (1, 4), để loại cạnh (1, 4), ta cần thay phần tử 0 tại ô này bằng . i j 1 2 3 4 5 di 1 M 40 40 M 60 40 2 20 M 0 10 30 0 3 30 0 M 40 0 0 4 0 50 10 M 40 0 5 0 10 30 0 M 0 dj 0 0 0 0 0 40 Đối với tập chứa (1,4), ta loại tất cả c|c phần tử dòng 1 v{ cột 4 v{ thay thế phần tử (4, 1) bằng . Kết quả, ta nhận được ma trận cấp 4x4. i j 1 2 3 5 di 2 20 M 0 30 0 3 30 0 M 0 0 4 M 50 10 40 10 5 0 10 30 M 0 dj 0 0 0 0 10 68
CHƯƠNG 5. BÀI TOÁN TỐI ƯU Cận dưới của tập con (1,4) là 140 + 10 = 150 < 180. Vì cận dưới của tập con (1, 4) nhỏ hơn, nên lộ trình không chứa cạnh (1, 4). Lại tiến h{nh c|c bước trên với ma trận 4x4 thu được. i j 1 2 3 5 di 2 20 M 0(20) 30 20 3 30 0(10) M 0(30) 0 4 M 40 0(30) 30 30 5 0(30) 10 30 M 10 dj 20 10 0 30 0 d(1,3) = 20 + 0 = 20; d(2,2) = 0 + 10 = 10; d(2,4) = 0 + 30 = 30; d(3,3) = 30 + 0 = 30; d(4,1) = 10 + 20 = 30; Tổng hằng lớn nhất l{ (0 + 30) = 30 tương ứng với (3,5), kết quả tập được chia th{nh hai tập con: chứa (3, 5) v{ không chứa (3, 5). Cận dưới của tập không chứa (3, 5) l{ 150 + 30. Đối với tập không chứa (3, 5) ta thay phần tử n{y bằng . i j 1 2 3 5 di 2 20 M 0 30 0 3 30 0 M M 0 4 M 40 0 30 0 5 0 10 30 M 0 dj 0 0 0 30 30 Đối với tập chứa (3, 5), ta cần loại tất cả c|c phần tử của dòng 3 v{ cột 5. Đồng thời, phần tử (5, 3) được thay bằng . Kết quả ta nhận được ma trận 3x3: i j 1 2 3 di 2 20 M 0 0 4 M 40 0 0 5 0 10 M 0 69
CHƯƠNG 5. BÀI TOÁN TỐI ƯU dj 0 10 0 10 Cận dưới của tập con (3,5) là 150 + 10 = 160 < 180. Bởi vì cận dưới của tập chứa (3, 5) nhỏ hơn, nên lộ trình tối ưu sẽ chứa (3, 5). Tiếp tục qu| trình n{y i j 1 2 3 di 2 20 M 0(20) 20 4 M 30 0(30) 30 5 0(20) 0(30) M 0 dj 20 30 0 0 d(1,3) = 20 + 0 = 20; d(2,3) = 30 + 0 = 30; d(3,1) = 0 + 20 = 20; d(3,2) = 0 + 30 = 30; Tổng lớn nhất (30 + 0) = 30 tương ứng với cạnh (4,3), do đó, tập cạnh lại chia th{nh: tập con chứa (4, 3) v{ không chứa (4, 3). Cận dưới của tập không chứa (4, 3) l{ 160 + 30 = 190. Với tập không chứa cạnh (4, 3), ta thay phần tử (4, 3) bằng . i j 1 2 3 di 2 20 M 0 0 4 M 30 M 30 5 0 0 M 0 dj 0 0 0 30 Trong tập con chứa (4, 3), ta loại dòng 4 v{ cột 3. Sau đó thay phần tử (3, 4) bằng . Kết quả ta nhận được ma trận 2x2. i j 1 2 di 2 20 M 20 5 0 0 0 dj 0 0 20 Cận dưới của tập con (4, 3) l{ 160 + 20 = 180 < 190. Bởi vì cận dưới của tập chứa (4, 3) nhỏ hơn tập không chứa (4, 3) nên lộ trình chứa cạnh (4, 3). Tương ứng với 70
CHƯƠNG 5. BÀI TOÁN TỐI ƯU ma trận n{y, ta bổ sung thêm hai cạnh (5, 2) v{ (2, 1). Cuối cùng, lộ trình tối ưu l{: (1,4), (4,3), (3,5), (5,2), (2,1). Độ d{i của lộ trình tối ưu l{ 180. 71
CHƯƠNG 6. LÝ THUYẾT ĐỒ THỊ CHƯƠNG 6. LÝ THUYẾT ĐỒ THỊ 6.1. Sơ lược về lý thuyết đồ thị Lý thuyết đồ thị được nhắc đến lần đầu tiên v{o năm 1736, khi Euler khảo s|t b{i to{n cầu Konigsberg. H nh 6.1 – B{i to|n cầu Konigsberg Bài toán. Ở th{nh phố Konigsberg, có một con sông chảy qua v{ chia vùng đất th{nh 4 phần. Có bảy c}y cầu nối c|c vùng đất lại với nhau (như trên hình minh họa). Liệu chăng có tồn tại một đường đi xuất ph|t từ một vùng đất bất kì, đi qua tất cả c|c c}y cầu, mỗi c}y cầu chỉ đi qua đúng một lần? Cho m~i đến năm 1936, b{i to|n c}y cầu Konigsberg mới được nhắc đến trong cuốn s|ch lí thuyết đồ thị (bằng tiếng Đức v{ được dịch sang tiếng Anh v{o năm 1990). Cũng từ thời điểm n{y, lí thuyết đồ thị đ~ có một bước ph|t triển mạnh mẽ. Nó có một ứng dụng to lớn không chỉ trong to|n học, khoa học m|y tính cũng như c|c lĩnh vực có ứng dụng to|n học m{ còn cả trong c|c lĩnh vực phi khoa học. Lí thuyết đồ thị l{ một ví dụ điển hình cho lớp b{i to|n NP đầy đủ. Một b{i to|n gọi l{ nằm trong lớp P nếu có một thuật to|n hữu hiệu để tìm ra nghiệm. Một b{i to|n gọi l{ nằm trong lớp NP nếu có một ước đo|n hữu hiệu để tìm ra đ|p |n v{ một phương pháp hữu hiệu để kiểm tra tính đúng của nó. Nói chung . Điều n{y vẫn còn l{ một ẩn số trong to|n học. Nó l{ một b{i to|n lớn trong to|n học hiện đại v{ lý thuyết khoa học m|y tính. Nếu ta ước đo|n được b{i to|n trong lớp NP có thể được giải bằng một thuật toán hữu hiệu, thì . Nếu lớp NP hoàn chỉnh nằm trong P thì .
CHƯƠNG 6. LÝ THUYẾT ĐỒ THỊ Ghi chú: một thuật to|n gọi l{ hữu hiệu nếu nó có độ phức tạp trong thời gian đa thức (còn được gọi l{ thuật to|n tất định). Một thuật to|n gọi l{ ước đo|n hữu hiệu nếu nó có chứa một sự ước đo|n bên trong nó (v{ cũng gọi là thuật toán không tất định). 6.1.1. Các khái niệm về Đồ thị Giả sử V là một tập hữu hạn, ta kí hiệu ( ) + + là tập con của V với mỗi cặp phần tử khác nhau. Định nghĩa. Một cặp ( ) với ( ) gọi là đồ thị. Các phần tử của V gọi là đỉnh, các phần tử của E gọi là cạnh. Tập các đỉnh của đồ thị G được kí hiệu là hay đơn thuần là V và tập các cạnh của đồ thị G được kí hiệu là hay đơn thuần là E. Một cạnh * + trong đồ thị gắn kết hai đỉnh và của đồ thị, v{ nó được kí hiệu là hay (nếu không có sự phân biệt thứ tự và ). Trong cả hai trường hợp, ta nói đỉnh liền kề với đỉnh . Đồ thị không có sự ph}n biệt thứ tự c|c đỉnh trong mỗi cạnh gọi l{ đồ thị vô hướng, ngược lại gọi l{ đồ thị có hướng. b a d c Hình 6.2 – Đồ thị vô hướng G1 b a d c Hình 6.3 – Đồ thị có hướng G2 73
CHƯƠNG 6. LÝ THUYẾT ĐỒ THỊ Định nghĩa. Đối với mỗi đồ thị G, ta kí hiệu Số gọi là cấp của đồ thị G và số gọi là kích thước của đồ thị. Ví dụ đồ thị và ở trên có cấp l{ 4 v{ kích thước l{ 5. Định nghĩa. Nếu một cạnh có điểm đầu và điểm cuối trùng nhau thì nó được gọi là khuyên. Nếu hai cặp đỉnh bất kì trong đồ thị có nhiều hơn một cặp cạnh nối chúng, thì ta gọi nói l{ đa đồ thị. Ngược lại, ta gọi l{ đơn đồ thị. Một đồ thị có chứa khuyên được gọi l{ giả đồ thị. Đồ thị có hướng thường được kí hiệu l{ D. Nếu trên mỗi cạnh của đồ thị được g|n một gi| trị thực thì nó được gọi l{ đồ thị có trọng số. Trọng số của đồ thị biểu thị cho giá trị, chi phí, lực liên kết. để giữa hai đỉnh liên thuộc trên cạnh này. Định nghĩa. Hàm là số màu tô cho đỉnh của đồ thị G xác định bởi tập màu K. Hàm là số màu tô cho cạnh của đồ thị G xác định bởi tập màu K. Nếu , thì gọi là hàm trọng lượng hay hàm khoảng cách. Định nghĩa. Hai đồ thị G và H được gọi là đẳng cấu và kí hiệu là , nếu tồn tại một song ánh sao cho ( ) ( ) với mọi . Để chỉ ra hai đồ thị G v{ H l{ đẳng cấu, ta cần chỉ ra một song ánh biến đồ thị G thành H hoặc ngược lại. Hình 6.4 – Hai đồ thị đẳng cấu G và H Hai đồ thị được cho ở trên l{ đẳng cấu. Ta dễ dàng chỉ ra song ánh: * + 74
CHƯƠNG 6. LÝ THUYẾT ĐỒ THỊ Bài toán đồ thị đẳng cấu. Liệu có tồn tại một thuật toán hiệu quả để kiểm tra hai đồ thị l{ đẳng cấu hay không đẳng cấu ? Bảng sau đ}y liệt kê con số đồ thị có n đỉnh v{ số lượng đồ thị không đẳng cấu tương ứng. n 1 2 3 4 5 6 7 Đồ thị 1 2 8 64 1024 32768 2097152 Không Đẳng cấu 1 2 4 11 34 156 1044 Nói chung không tồn tại một thuật to|n hiệu quả để kiểm tra hai đồ thị có l{ đẳng cấu hay không. Các dạng biểu diễn của đồ thị. Để biểu diễn một đồ thị, ta có thể thực hiện theo nhiều c|ch. Chúng ta đ~ tìm hiểu một c|ch thức để biểu diễn đồ thị đó l{ sử dụng hình minh họa. Tuy nhiên, phương ph|p n{y lại không hiệu quả trong lập trình. Trong lập trình, ta thường biểu diễn đồ thị dưới dạng ma trận. Đ}y l{ một c|ch thức hữu hiệu cho việc viết chương trình trên m|y tính. Ma trận kề. Giả sử * + là một bộ sắp thứ tự. Ma trận kề của G là một ma trận M cấp với { Ví dụ: 퐯 퐯 퐯 퐯ퟒ Hình 6.5 – Biểu diễn đồ thị bằng ma trận kề Ma trận kề tương ứng với đồ thị có dạng ( ) 75
CHƯƠNG 6. LÝ THUYẾT ĐỒ THỊ Ta cũng cần chú ý rằng, ma trận kề luôn l{ ma trận đối xứng. Định lý. Hai đồ thị G và H gọi là đẳng cấu, nếu và chỉ nếu chúng có cùng ma trận kề. Hơn thế nữa, hai đồ thị đẳng cấu có cùng tập ma trận kề. C|c đồ thị có thể được biểu diễn dưới dạng tập hợp. Ví dụ * + là tập các tập con của tập X, và x|c định đồ thị giao l{ đồ thị với c|c đỉnh là và cạnh với mọi ( ) và . Định lý. Mọi đồ thị là một đồ thị giao của các tập con. Chứng minh. Giả sử G là một đồ thị x|c định với mọi , và tập + + Khi đó, nếu và chỉ nếu Giả sử ( ) l{ kích thước nhỏ nhất của tập X và G có thể được biểu diễn l{ đồ thị giao của các tập con của X, khi đó ( ) { | + ( ) nhỏ như thế nào thì có thể so sánh với (hoặc ) của đồ thị ? Người ta đ~ chỉ ra rằng, đ}y l{ một bài toán thuộc lớp NP hoàn chỉnh. Chúng ta cũng lưu ý rằng, ma trận kề và ma trận liên thuộc đối với đơn đồ thị thực chất là 1. Trong đa đồ thị, ma trận kề sẽ được x|c định như sau: ( ) Trong đó, mỗi phần tử là số cạnh nối đỉnh với đỉnh . Nói chung, ma trận kề đối với đồ thị có hướng không phải là ma trận đối xứng. Nếu ta khảo s|t đồ thị có trọng số, thì mỗi phần tử tương ứng với trọng số của cạnh nối đỉnh với đỉnh . Quy ước: giá trị trọng số tương ứng với cạnh ( ) được quy ước như sau ( ) { 6.1.2. Đồ thị con Với một đồ thị có kích thước lớn, việc giải quyết b{i to|n trên đồ thị dạng n{y l{ rất khó khăn. Thông thường, người ta sẽ chia c|c đồ thị n{y th{nh c|c phần nhỏ hơn 76
CHƯƠNG 6. LÝ THUYẾT ĐỒ THỊ dựa trên c|c đặc tính bộ phận của nó, v{ tiến h{nh giải quyết b{i to|n trên c|c phần n{y. Sau đó, kết hợp c|c thông tin ban đầu để đưa ra kết quả cho đồ thị đ~ cho. Mỗi phần đồ thị sau khi ph}n chia như trên gọi l{ đồ thị con. Bậc của đỉnh. Định nghĩa. Giả sử là một đỉnh của đồ thị G. Đỉnh liền kề với v là tập hợp ( ) * + Bậc của v là số đỉnh liền kề với nó hay theo ngôn ngữ tập hợp, nó là lực lượng của tập các đỉnh liền kề với v: ( ) ( ) Nếu ( ) , thì ta nói là đỉnh cô lập, nếu ( ) thì ta nói là đỉnh treo (hay lá) của đồ thị. Bậc cực tiểu của đồ thị G được kí hiệu là ( ), bậc cực đại của đồ thị được kí hiệu là ( ). Ví dụ. Cho đồ thị sau G: 퐯 퐯 퐯 퐯ퟒ Hình 6.6 – Bậc của đỉnh trong đồ thị G Bậc của c|c đỉnh v1, v3 l{ 2. Bậc của đỉnh v2, v4 l{ 3. Bậc cực tiểu của đồ thị G l{ 2, bậc cực đại của đồ thị G là 3. Năm 1736, Euler đ~ chỉ ra rằng, trong một buổi tiệc, nếu mỗi người đều bắt tay nhau, thì số lượt bắt là một số chẵn. Bổ đề (Bổ đề bắt tay). Với mọi đồ thị G, ta luôn có ∑ ( ) Hơn nữa, số đỉnh bậc lẻ trong đồ thị G là một số chẵn. 77
CHƯƠNG 6. LÝ THUYẾT ĐỒ THỊ Chứng minh. Mỗi một cạnh của đồ thị đều có hai điểm mút tương ứng. Do đó, tổng bậc của tất cả c|c đỉnh sẽ gấp đôi số cạnh. Trong mỗi đồ thị G sẽ có c|c đỉnh bậc chẵn v{ c|c đỉnh bậc lẻ: ∑ ( ) ∑ ( ) ∑ ( ) ( ) ( ) Tổng bậc chẵn luôn l{ một số chẵn v{ tổng ở vế tr|i cũng l{ một số chẵn, nên tổng đỉnh bậc lẻ cũng l{ một số chẵn. Suy ra số đỉnh bậc lẻ l{ một số chẵn Định nghĩa. Một đồ thị ( ) gọi là đồ thị có hướng nếu mỗi phần tử là một cặp có thứ tự, có nghĩa là . Định nghĩa. Giả sử là một đồ thị có hướng. Khi đó, là Đồ thị con của nó nếu và , Đồ thị con thu gọn của nó , - nếu và ( ) Định nghĩa. Bậc vào và bậc ra của đỉnh trong đồ thị có hướng được xác định như sau: ( ) * + ( ) * + Hay nói cách khác, bậc vào của đỉnh là tổng số cạnh kết thúc ở , và bậc ra của đỉnh là tổng các cạnh xuất phát từ . Các dạng đồ thị đặc biệt. Định nghĩa. Một đồ thị ( ) là tầm thường nếu nó có một đỉnh, ngược lại gọi là đồ thị không tầm thường. Định nghĩa. Đồ thị là một đồ thị hoàn chỉnh trên V nếu mỗi cặp đỉnh trong đồ thị là liền kề nhau. Mọi đồ thị hoàn chỉnh cấp n l{ đẳng cấu với nhau v{ ta thường kí hiệu là . Hình 6.7 – Đồ thị ho{n chỉnh K6 78
CHƯƠNG 6. LÝ THUYẾT ĐỒ THỊ Định nghĩa. Phần bù của đồ thị G là đồ thị trên , ở đó * ( ) +. Phần bù của đồ thị hoàn chỉnh là một đồ thị rời rạc. Trong đồ thị rời rạc, tập cạnh l{ một tập rỗng. C|c đồ thị rời rạc kích thước n l{ đẳng cấu với nhau. Định nghĩa. Đồ thị G gọi là chính quy, nếu mọi đỉnh của G có cùng bậc. Nếu bậc này bằng thì ta gọi G là đồ thị chính quy bậc hay đơn giản là đồ thị chính quy. Đồ thị rời rạc l{ đồ thị chính quy bậc 0 v{ đồ thị hoàn chỉnh là chính quy ( ). Đồ thị ho{n chỉnh l{ đồ thị có số cạnh lớn nhất trong tất cả c|c đồ thị có cùng cấp n: ( ) ( ) và với mọi đồ thị . Ví dụ. Đồ thị Petersen l{ một đồ thị cấp n v{ nó l{ đồ thị chính quy bậc 3. Hình 6.8 – Đồ thị Petersen chính quy bậc 3 Ví dụ. Giả sử là một số nguyên, và giả sử rằng là tập các xâu nhị ph}n độ dài . Ví dụ, * +. Đặt là khối k - lập phương, trong đó, và , nếu v{ chỉ nếu và chỉ kh|c nhau đúng một vị trí. Hình 6.9 – Đồ thị lập phương k – chính quy Cấp của là , chính là số xâu kí tự độ dài . Ta dễ dàng nhận thấy, là một đồ thị k – chính quy. Theo bổ đề bắt tay, . Ví dụ. Giả sử là một số chẵn. Chúng ta chỉ ra tồn tại một đồ thị 3 – chính quy G với . Chú ý rằng, tất cả c|c đồ thị 3 – chính quy có cấp là một số chẵn. 79
CHƯƠNG 6. LÝ THUYẾT ĐỒ THỊ Nếu n=4, khi đó l{ một đồ thị 3 – chính quy. Giả sử đồ thị 3 – chính quy có cấp , và . Đặt * + và ( * +) * +. Khi đó, l{ đồ thị 3 – chính quy cấp . Hình 6.10 – Đồ thị 3 – chính quy có cấp l{ số chẵn Định nghĩa. Một đồ thị là đồ thị con của đồ thị và kí hiệu là , nếu và . Một đồ thị con gọi là đồ thị con khung của G nếu mọi đỉnh của là trong H, hay nói cách khác . Đồ thị con l{ một đồ thị con thu gọn, nếu ( ). Trong trường hợp n{y, H được thu gọn bởi tập đỉnh . Trong một đồ thị con thu gọn , tập chứa tất cả c|c đỉnh và ( ). Với mỗi tập con khác rỗng , có một đồ thị con thu gọn duy nhất , - ( ( )) Mỗi tập con của c|c đỉnh có một đồ thị con khung duy nhất , - ( ) Cho đồ thị G. Hình 6.11 – Đồ thị G Một đồ thị con của G. 80
CHƯƠNG 6. LÝ THUYẾT ĐỒ THỊ Hình 6.12 – Đồ thị con của đồ thị G Một đồ thị con khung của G. Hình 6.13 – Đồ thị con khung của đồ thị G Một đồ thị con thu gọn của G. Hình 6.14 – Đồ thị con thu gọn của đồ thị G Với tập đỉnh , đặt , - l{ đồ thị con của G nhận được bằng cách bỏ đi cạnh trong đồ thị G. Hay nói cách khác, đồ thị nhận được bằng cách loại bỏ cạnh . Tương tự, chúng ta viết , nếu mỗi cạnh với ( ) được bổ sung vào . Với tập con của tập đỉnh , đặt l{ đồ thị con thu gọn bởi , hay , - và nhận được từ G bằng cách bỏ đi đỉnh cùng các các cạnh có nối với . Rất nhiều b{i to|n đồ thị con thu gọn có độ phức tạp lớn. Ví dụ, để tìm một đồ thị con ho{n chỉnh lớn nhất (theo bậc) của đồ thị G cho trước l{ b{i to|n thuộc lớn NP. 6.1.3. Các phép tìm kiếm trên đồ thị a) Tìm kiếm theo chiều sâu: Thuật toán bắt đầu từ một đỉnh n{o đó. Tiếp tục chọn đỉnh bất kì liền kề với đỉnh . Quá trình này lại tiếp tục. Nếu tại một bước n{o đó, tất cả c|c đỉnh kế cận với đều đ~ được xét duyệt, nhưng vẫn tồn tại một số đỉnh trong đồ thị chưa được xét đến, thì khi đó, chúng ta cần quay lại đỉnh liền trước đỉnh (tức đỉnh ở bước lặp trước đó). Thuật to|n dừng khi tất cả đỉnh cần tìm được xét duyệt. 81
CHƯƠNG 6. LÝ THUYẾT ĐỒ THỊ b) Tìm kiếm theo chiều rộng: Thuật to|n bắt đầu từ một đỉnh n{o đó. Giả sử tại một bước lặp n{o đó, là tập đỉnh đ~ xét, là tập đỉnh đ~ được duyệt. Ta đưa v{o các đỉnh của m{ c|c đỉnh n{y không có đỉnh kề nào nữa trong chưa được xét. Tiếp theo, ta thay thế bằng tập c|c đỉnh không thuộc nhưng kề với . Quá trình này thực hiện cho đến khi rỗng. Ví dụ trong đồ thị bên dưới. Ta áp dụng hai thuật toán nêu trên: - Tìm kiếm theo chiều s}u: a b c d e h g f i j k l - Tìm kiếm theo chiều rộng: a b l c i k d h j e g f f b g c a e d k h i l j Hình 6.15 –Tìm kiếm theo chiều x}u v{ theo chiều rộng 6.1.4. Hành trình và chu trình Khi tiến h{nh giải quyết c|c b{i to|n như tìm đường đi ngắn nhất trong mạng, tìm luồng cực đại chúng ta cần khảo s|t c|c kh|i niệm liên quan đến đường đi v{ chu trình. Những dạng b{i to|n n{y tương đối khó, hay chính x|c hơn l{ những bài toán không tầm thường, bởi thường có nhiều lựa chọn để tìm ra một nghiệm tối ưu. Định nghĩa. Giả sử là các cạnh của G với , -. Ở đó, và là liên thông với mọi , -. Dãy thứ tự gọi là đường đi độ dài k từ đến . 82
CHƯƠNG 6. LÝ THUYẾT ĐỒ THỊ Thông thường, ta viết đường đi như sau: hay Độ dài của đường đi được kí hiệu là . Định nghĩa. Đặt ( ) là đường đi. là khép kín, nếu . là hành trình, nếu với mọi . là chu trình, nếu nó khép kín và với trừ . là hành trình tầm thường, nếu độ dài của nó là 0. Lộ trình tầm thường không chứa bất kì cạnh nào. gọi là hành trình đảo ngược của nếu . Bổ đề. Mỗi đường đi với chứa một hành trình , mà nó nhận được bằng cách bỏ đi một số cạnh và đỉnh trong . Chứng minh. Đặt . Giả sử và . Nếu không tồn tại một cặp như vậy, thì sẽ là một h{nh trình. Ngược lại, trong đường đi đường đi l{ đường đi ngắn hơn. Bằng cách lặp đối số này, chúng ta nhận được một dãy của đường đi với . Khi thủ tục này dừng, ta nhận được một hành trình Định nghĩa. Nếu tồn tại một đường đi (hay một hành trình) từ vào trong đồ thị , đặt ( ) * + là khoảng cách từ đến . Nếu không tồn tại đường đi , đặt ( ) . Một đồ thị là liên thông, nếu ( ) với mọi ; ngược lại, nó gọi là không liên thông. Số đồ thị con liên thông cực đại của đồ thị gọi là các thành phần liên thông của nó. Kí hiệu: ( ) l{ số th{nh phần liên thông của đồ thị . 83
CHƯƠNG 6. LÝ THUYẾT ĐỒ THỊ Nếu ( ) , thì hiển nhiên l{ đồ thị liên thông. Đồ thị con gọi là liên thông cực đại, nếu bất kì một đồ thị con x|c định trên tập đỉnh * +, với mọi đỉnh không l{ đồ thị liên thông. Định nghĩa. Giả sử là một cạnh của đồ thị có trọng số với hàm trọng số xác định trên tập cạnh. Với đồ thị con , đặt ( ) ∑ ( ) là tổng trọng số của . Trong trường hợp riêng, nếu là hành trình, thì trọng số của nó là ( ) ∑ ( ) Khoảng cách có trọng số nhỏ nhất giữa hai đỉnh của đồ thị là ( ) 2 ( )| 3 Trong các bài toán tối ưu hóa, chúng ta cần tìm một đồ thị con tối ưu thỏa mãn một số điều kiện. Trong thực tế, chúng ta cần chú ý đến một số tính chất sau: - Trong c|c b{i to|n x}y dựng, mạng giao thông , thì trọng số trên mỗi cạnh của đồ thị có thể l{ khoảng c|ch, chi phí vận chuyển, mức đ|nh gi| ưu tiên trong mạng này. - Trong một hệ thống c|c kênh thông tin hoặc kiến trúc m|y tính, thì trọng số có thể là tỉ suất không đ|ng tin hoặc tần số kết nối. - Trong mô hình ph}n tử hóa học, thì trọng số tương ứng với lực liên kết ph}n tử. Trong những trường hợp n{y, chúng ta tìm một đồ thị con nối hai đỉnh cho trước hoặc nối tất cả c|c đỉnh với trọng số nhỏ nhất. Trong một số trường hợp kh|c, nếu đồ thị biểu diễn một mạng lưới c|c ống dẫn (dẫn dầu, khí đốt ), thì trọng số có thể l{ dung tích hoặc sức truyền tải, v{ khi đó, ta cần tìm đồ thị có trọng số lớn nhất. Chúng ta khảo sát bài toán cực tiểu. Đối với bài toán này, giả sử cho đồ thị với hàm trọng số . Trong trường hợp này, ta gọi ( ) l{ độ dài của hành trình . Bài toán tìm hành trình (đường đi) ngắn nhất: Cho đồ thị liên thông với h{m trọng lượng , ta cần tìm ( ) với mọi Hay, có thể phát biểu dưới ngôn ngữ tự nhiên: cho một đồ thị liên thông , hãy tìm hành trình ngắn nhất giữa hai đỉnh cho trước. 84
CHƯƠNG 6. LÝ THUYẾT ĐỒ THỊ Có nhiều thuật to|n để giải b{i to|n tìm hành trình ngắn nhất. Trong phạm vi của gi|o trình n{y, chúng ta sẽ khảo s|t hai thuật to|n: Dijkstra v{ Floyd. a) Thuật toán Dijkstra. - Thuật to|n Dijkstra chỉ |p dụng cho đồ thị có trọng số dương. Thuật to|n Dijkstra l{ thuật to|n có tốc độ thực thi cao nhất trong các thuật toán cùng loại. Thuật toán. Thuật toán Dijkstra có thể chia làm hai chiều: + Chiều thuận: x|c định độ dài ngắn nhất từ đỉnh nguồn đến c|c đỉnh còn lại. + Chiều nghịch: x|c định c|c đỉnh nằm trên đường đi ngắn nhất. Chiều thuận. + Đặt ( ) và ( ) với mọi . + Với mỗi , - với mỗi * +, ta thay ( ) bằng * ( ) ( ) ( )+ Đặt * + l{ đỉnh bất kì có giá trị nhỏ nhất ( ). + Kết luận ( ) ( ). Điều kiện dừng: + Nếu yêu cầu tìm đường đi ngắn nhất giữa hai đỉnh bất kì, thì thuật toán dừng khi đường đi ngắn nhất đến đỉnh đích đã được tìm thấy (đỉnh đích đã được đánh dấu). + Nếu yêu cầu tìm đường đi ngắn nhất giữa đỉnh nguồn với tất cả các đỉnh còn lại, thì thuật toán dừng khi tất cả các đường đi ngắn nhất đã được tìm thấy. Chiều nghịch. Giả sử độ dài của hành trình ngắn nhất đến đỉnh 풗 là ( ) . x1 x2 v x3 x4 Hình 6.15 – Thuật to|n tìm đỉnh liền trước trong h{nh trình ngắn nhất Ta tiến hành kiểm tra: 85
CHƯƠNG 6. LÝ THUYẾT ĐỒ THỊ ( ) ( ) ( ) Nếu đỉnh nào thỏa m~n đẳng thức trên, thì đỉnh đó nằm ngay trước đỉnh trong hành trình ngắn nhất. Ví dụ. Tìm hành trình ngắn nhất từ đỉnh đến trong đồ thị sau đ}y: Hình 6.16 – Tìm hành trình ngắn nhất bằng thuật toán Dijkstra Xác định đường đi ngắn nhất đến mỗi đỉnh. . ( ) ( ) . ( ) * + ( ) * + c|c đỉnh còn lại bằng . Do đó, chọn . . ( ) * ( ) ( )+ * + ( ) ( ) ( ) Do đó, chọn . . ( ) * + ( ) * + ( ) * + Do đó, chọn . . ( ) * + ( ) * + Do đó, chọn . . ( ) * + Thuật toán dừng. Vậy, các hành trình ngắn nhất đến mỗi đỉnh của đồ thị là ( ) ( ) ( ) ( ) ( ) Xác định các đỉnh nằm trên hành trình ngắn nhất. C|c đỉnh nằm trong hành trình ngắn nhất đến . C|c đỉnh liền trước gồm . Trong đó, ( ) ( ) ( ) Kiểm tra điều kiện (*): ( ) ( ) ( ) ( ) ( ) ( ) 86
CHƯƠNG 6. LÝ THUYẾT ĐỒ THỊ ( ) ( ) ( ) Nên đỉnh liền ngay trước trong hành trình ngắn nhất là hoặc . . Nếu chọn , ta l{m tương tự như trên v{ dễ d{ng x|c định được đỉnh liền trước trong hành trình ngắn nhất là . . Nếu chọn , ta cũng thực hiện tương tự v{ x|c định được đỉnh liền trước là . Liền trước là . Như vậy, ta có thể thấy theo thuật to|n Dijkstra, ta đ~ x|c định được hai đường đi ngắn nhất từ Chú ý: Để thuận tiện cho việc biểu diễn thuật to|n, ta có thể thực hiện thuật to|n Dijkstra theo lược đồ được mô tả bên dưới (풗 ) (풗 ) (풗 ) (풗 ) (풗 ) (풗 ) 0* 2* 3 3 3* 5 3* 5 4* 4 4* Trong bảng n{y, gi| trị độ d{i của h{nh trình được ghi v{o ô tương ứng với đỉnh. Trong mỗi bước lặp, ta chọn ra một đỉnh có hành trình nhỏ nhất v{ đ|nh dấu đỉnh đó. Nếu một đỉnh đ~ được đ|nh dấu, thì c|c bước lặp tiếp theo, ta không cần khảo s|t đến nó. Giá trị độ dài của hành trình luôn cập nhật trong mỗi bước lặp theo công thức tính * ( ) ( ) ( )+ Thuật to|n Dijkstra có độ phức tạp ( ). b) Thuật toán Floyd. Thuật to|n Floyd |p dụng cho cả đồ thị có trọng số }m lẫn trọng số dương. Thuật to|n Floyd thường được thực thi trên ma trận trọng số, do đó, nó còn được gọi là thuật toán ma trận. Thuật toán dựa trên một dãy n ma trận . Cho đồ thị , và ma trận trọng số tương ứng ( ) . Đặt là trọng số của cạnh nối đỉnh , nếu không tồn tại cạnh nối đỉnh . Thuật toán. Thuật toán Floyd được thực hiện thông qua c|c bước sau: 87
CHƯƠNG 6. LÝ THUYẾT ĐỒ THỊ . Đặt với . . Tăng . . Với mỗi sao cho , và với mỗi sao cho , ta thực hiện tính toán * +. . Kiểm tra điều kiện dừng. Nếu thỏa mãn thì thuật toán dừng, ngược lại, quay lại bước 2. Điều kiện dừng.  Nếu tại một bước n{o đó mà trong tồn tại một chu trình có độ dài }m đi qua đỉnh . Thuật to|n dừng. Không tồn tại nghiệm, b{i toán không chuẩn mực.  Nếu tất cả các phần tử và . Thuật toán dừng. Mỗi phần tử xác định hành trình ngắn nhất từ . Thuật to|n n{y cho phép ta x|c định độ d{i ngắn nhất của h{nh trình nhưng không chỉ ra c|c đỉnh nằm trên h{nh trình n{y. Để giải quyết vấn đề này, ta cần bổ sung thêm một ma trận để tìm c|c đỉnh nằm trong hành trình ngắn nhất này. Ma trận này sẽ được tính toán song song với ma trận trọng số. Ban đầu, Trong qu| trình tính to|n ma trận trọng số, nếu phần tử nào có giá trị thay đổi, thì phần tử có cùng chỉ số tương ứng trong ma trận cũng sẽ thay đổi theo: { Mỗi phần tử sẽ x|c định phần tử liền trước nó. Ví dụ. X|c định h{nh trình ngắn nhất từ đỉnh 1 đến đỉnh 3 trong đồ thị sau: 2 2 -2 1 1 4 2 5 3 88