Đề tài Nghiên cứu một số vấn đề ứng dụng của đồ thị trong tin học

LỜI NÓI ĐẦU Bước sang năm bản lề của thế kỷ 21, nhìn lại thế kỷ 20 là thế kỷ mà con người đạt được nhiều thành tựu khoa học rực rỡ nhất, một trong những thành tựu đó là sự bùng nổ của ngành khoa học máy tính. Sự phát triển kỳ diệu của máy tính trong thế kỷ này gắn liền với sự phát triển toán học hiện đại, đó là toán rời rạc. Toán học rời rạc nghiên cứu các cấu trúc có tính chất rời rạc không liên tục. Toán rời rạc bao gồm các lĩnh vực như quan hệ, lý thuyết đồ thị, lôgíc toán, ngôn ngữ hình thức... trong đó lý thuyết đồ thị là một bộ phận trọng tâm với nhiều khối lượng kiến thức khá lý thú và được nghiên cứu nhiều nhất. Toán rời rạc nói chung và lý thuyết đồ thị nói riêng là công cụ thiết yếu cho nhiều ngành khoa học kỹ thuật, và là một thành phần quan trọng trong học vấn đối với sinh viên các ngành kỹ thuật đặc biệt sinh viên ngành Tin học. Lý thuyết đồ thị, với cách tiếp cận đối tượng nghiên cứu và phương pháp tư duy khá độc đáo thực sự ngày càng hữu ích có nhiều ứng dụng phong phú và gây không ít bất ngờ. Máy tính mà bản thân nó với các quá trình làm việc mang tính rời rạc, nên điều này tương hợp gắn chặt lý thuyết đồ thị với công nghệ máy tính trong việc nghiên cứu các đối tượng có tính chất rời rạc. Lý thuyết đồ thị có nhiều ứng dụng thực tiễn đặc biệt là trong lĩnh vực Tin học, muốn hiểu biết sâu sắc các vấn đề Tin học cần nắm vững các kiến thức về Toán học rời rạc mà trong đó đặc biệt là lý thuyết đồ thị. Từ những nhận thức trên, với đề tài "Một số vấn đề ứng dụng của đồ thị trong Tin học" đây không chỉ là nhiệm vụ em phải thực hiện trong kỳ bảo vệ luận văn tốt nghiệp mà thực sự đây là đề tài mà em rất quan tâm và say mê nghiên cứu. Với tấm lòng biết ơn sâu sắc, em xin chân thành cảm ơn Thầy giáo Pgs. Ts Đỗ Đức Giáo là người trực tiếp, tận tình, chu đáo giảng dạy và hướng dẫn em hoàn thành cuốn luận văn này. Nhân dịp này em cũng xin cảm ơn sự giúp đỡ, dạy bảo tận tình của các thầy cô giáo, cán bộ Khoa Công Nghệ Thông Tin trường Đại học Dân lập Đông Đô và những bạn học đã đóng góp những ý kiến bổ ích cho bản luận văn này. Do trình độ hiểu biết còn hạn chế, thời gian chuẩn bị không nhiều, bản luận văn này còn nhiều sai sót và chưa đầy đủ, em rất mong nhận được sự góp ý của các thầy cô và các bạn quan tâm. Hà Nội 6/2000 Sinh viên: Phan Thanh Long GIỚI THIỆU ĐỀ TÀI "Một số vấn đề ứng dụng của đồ thị trong Tin học" là đề tài mang tính nghiên cứu lý thuyết, có tầm quan trọng và có ý nghĩa thiết thực cao. Khái niệm đồ thị ở đây khác với những đồ thị thông thường đã biết, đây là 1 lĩnh vực về lý thuyết đồ thị nghiên cứu những cấu trúc mang tính rời rạc là 1 bộ phận quan trọng của Toán học rời rạc. Lý thuyết đồ thị có nhiều ứng dụng trong các ngành kỹ thuật và đã được nghiên cứu nhiều với khối lượng kiến thức khá đồ sộ. Đề tài được thực hiện trước tiên sẽ đề cập tới những vấn đề chủ yếu của Lý thuyết đồ thị, sau đó tuỳ từng nội dung cũng sẽ xoay quanh tới những ứng dụng của đồ thị trong Tin học, giải quyết các bài toán trong Tin học như xác định xem hai máy tính trong mạng có thể truyền tin được hay không nhờ mô hình đồ thị của mạng máy tính, hay là bài toán nối mạng máy tính sao cho tổng chi phí là nhỏ nhất hoặc việc khắc phục những gói tin bị truyền sai nhờ các giải thuật đã nghiên cứu về đồ thị. Có những ứng dụng của đồ thị không đi trực tiếp vào các lĩnh vực trong Tin học, ví dụ như bài toán lập lịch trong công tác hành chính, xác định đường đi ngắn nhất giữa 2 điểm nút giao thông, ta cũng xem đó là ứng dụng 1 cách gián tiếp trong Tin học vì nếu được mô hình tốt những bài toán đó bằng đồ thị thì sẽ giải quyết chúng dễ dàng bằng máy tính, hoặc là về chơi cờ Ca rô tuy chỉ là môn chơi về trí tuệ nhưng đồ thị cũng hỗ trợ tốt cho nhưng ai muốn lập trình chơi cờ Ca rô trên máy tính khi đã mô hình được các thế cờ bằng đồ thị. Đề tài được thực hiện xong bao gồm những nội dung sau đây: Chương 1 Một số vấn đề cơ bản của đồ thị Nhằm trình bày những khái niệm cơ bản nhất về lý thuyết đồ thị, là cơ sở tìm hiểu sâu sắc hơn các vấn đề tiếp theo. Ngoài các định nghĩa, tính chất cơ bản của đồ thị, chương này có trình bày đến 1 vấn đề quan trọng, đó là cách lưu trữ, biểu diễn và xử lý đồ thị trên máy tính khi đã xét những mô hình biểu diễn hình học. Cấu trúc dữ liệu liên quan chặt chẽ đến giải thuật, việc biểu diễn đồ thị trên máy tính như thế nào sẽ ảnh hưởng đến cách giải các bài toán ứng dụng bằng máy tính. Trong chương có trình bày một số phương pháp biểu diễn đồ thị trên máy tính, mỗi phương pháp đều có những ưu và khuyết điểm riêng, vì vậy cần lựa chọn phương pháp sao cho phù hợp với đặc điểm từng bài toán và đạt được hiệu quả về thuật toán. Khi đưa các ví dụ minh họa, nhất là về phần đồ thị đặc biệt ta sẽ thấy được ứng dụng của đồ thị trong mô hình về mạng máy tính. Chương 2 Số ổn định và tô màu đồ thị Số ổn định của đồ thị bao gồm số ổn định trong, số ổn định ngoài và nhân đồ thị, nghiên cứu vấn đề này ta sẽ thấy được mối quan hệ giữa các tập đỉnh của một đồ thị. Một ứng dụng khá lý thú khi đề cập tới vấn đề này đó là xây dựng mô hình đồ thị cho bài toán lập trình chơi cờ carô, có sử dụng đến tập ổn định ngoài của đồ thị. Ở chương này ta cũng sẽ gặp đến một ứng dụng khá thiết thực khi bàn đến vấn đề tô màu của đồ thị, hay còn gọi là sắc số của đồ thị, ứng dụng đó là bài toán lập lịch. Lập lịch là công tác hành chính phổ biến, hay gặp ở các cơ quan, xí nghiệp, trường học... cũng đã có nhiều sản phẩm phần mềm phục vụ cho việc lập lịch. Chương 3 Chu trình, đường đi Euler và Hamilton trong đồ thị Trình bày những khái niệm về chu trình Euler, đường Euler, chu trình Hamilton, đường Hamilton các tính chất của chúng đồng thời đưa ra 1 số thuật toán ứng dụng để tìm các đường, chu trình Euler, Hamilton. Chương 4 Đường đi ngắn nhất trong đồ thị Bài toán đường đi ngắn nhất hay được đề cập tới trong lý thuyết đồ thị, đây cũng là loại bài toán tối ưu có nhiều ứng dụng rộng rãi. Trong đồ thị thường đặt ra các loại tìm đường đi ngắn nhất như sau: - Đường đi ngắn nhất nhất giữa 1 cặp đỉnh đã được xác định trước. - Đường đi ngắn nhất giữa 1 đỉnh với tất cả các đỉnh còn lại. - Đường đi ngắn nhất giữa tất cả các cặp đỉnh bất kỳ. Để giải quyết các loại bài toán này, trong chương sẽ trình bày 1 số thuật toán chính hay được sử dụng như: Dijkstra, Ford-Bellman và Floyd. Về mặt ứng dụng, trong chương sẽ nêu ra giải thuật Viterbi cho ứng dụng khá quan trọng trong lĩnh vực Tin học đó sửa gói tin sai khi truyền tin trong mạng máy tính. Khi nói đến đường đi ngắn nhất, người ta cũng hay nói đến mở rộng của bài toán đường đi ngắn nhất thành đường đi dài nhất. Trong vấn đề này ta lại có 1 ứng dụng nữa trong công tác lập lịch, đó là sơ đồ mạng PERT cho việc lập dự án thi công một công trình. Ứng dụng này rất thực tiễn và đã đem lại nhiều hiệu quả cao cho việc thi công một công trình. Chương 5 Một số vấn đề về cây Đây là chương cuối cùng và là chương sẽ đề cập tới nhiều ứng dụng nhất. Cây là một trường hợp riêng của đồ thị, để nghiên cứu hết các tính chất, khái niệm về cây cần cả 1 khối lượng kiến thức đồ sộ và đã có những đề tài cấp luận văn hoặc hơn thế nữa nghiên cứu về cây. Trong chương này chỉ đề cập tới những điểm chính nhất, cơ bản nhất về cây và tập trung khai thác những ứng dụng của nó. Những ứng dụng của cây thì rất nhiều, trong chương chỉ đề cập tới những ứng dụng cơ sở nhất nhưng cũng thiết thực nhất, đó là 1 số ứng dụng của cây nhị phân như mã tiền tố, cây biểu diễn biểu thức, cây quyết định, cây sắp xếp và tìm kiếm. Trong lý thuyết đồ thị, khi nói về cây thì cây bao trùm là vấn đề không thể thiếu, vì đây cũng là đặc điểm rất hay của đồ thị. Trong cây bao trùm lại có cây bao trùm bé nhất, lớn nhất và đây lại là 1 dạng của bài toán tối ưu. Trong chương cũng sẽ giới thiệu ứng dụng thực tiễn của cây bao trùm nhỏ nhất trong việc kết nối mạng sao cho chi phí nhỏ nhất, đồng thời đưa ra 1 số thuật toán tìm cây bao trùm, đặc biệt có những thuật toán rất cơ sở được nêu ra, được dùng nhiều trong việc giải quyết các bài toán đồ thị trên máy tính như là kỹ thuật quay lui, tìm kiếm ưu tiên theo chiều rộng và chiều sâu. Chương 1 MỘT SỐ VẤN ĐỀ CƠ BẢN CỦA ĐỒ THỊ I. CÁC ĐỊNH NGHĨA ĐỒ THỊ 1. Định nghĩa đồ thị Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này, các loại đồ thị khác nhau được phân biệt bởi kiểu và số lượng cạnh nối hai đỉnh nào đó của đồ thị. Giả sử X là tập hữu hạn, không rỗng các phần tử nào đó và U Í X´X. Bộ G = được gọi là đồ thị hữu hạn. Mỗi phần tử xÎX gọi là một đỉnh và mỗi phần tử u = (x,y) Î U gọi là một cạnh của đồ thị G = . Xét một cạnh u Î U khi đó tồn tại 2 đỉnh x, y Î X sao cho u = (x, y), ta nói rằng x nối với y hoặc x và y thuộc u. x y u - Nếu cạnh u = (x, y) mà x và y là hai đỉnh phân biệt thì ta nói x, y là hai đỉnh kề nhau. - Nếu u = (x, x) thì u là cạnh có hai đỉnh trùng nhau ta gọi đó là một khuyên. - Nếu u = (x, y) mà x,y là cặp đỉnh có phân biệt thứ tự hay có hướng từ x đến y thì u là một cung, khi đó x là gốc còn y là ngọn hoặc x là đỉnh ra, y là đỉnh vào. - Khi giữa cặp đỉnh (x, y) có nhiều hơn một cạnh thì ta nói những cạnh cùng cặp đỉnh là những cạnh song song hay là cạnh bội y x y x y a) b) c) a. Tại đỉnh y có một khuyên b. Một cung có hướng từ x sang y c. Cặp đỉnh (x, y) có 2 cạnh song song Hình 1.1 Trong thực tế ta có thể gặp nhiều vấn đề mà có thể dùng mô hình đồ thị để biểu diễn, như sơ đồ một mạng máy tính, sơ đồ mạng lưới giao thông, sơ đồ thi công một công trình. Ví dụ: Xét một mạng máy tính, có thể biểu diễn mạng này bằng một mô hình đồ thị, trong đó mỗi máy là một đỉnh, giữa các máy được nối với nhau bằng các dây truyền, chúng tương ứng là các cạnh của đồ thị. Một mô hình mạng máy tính như hình 1.2 trong đó có các máy tính A, B, C, D tương ứng là các đỉnh, giữa 2 máy được nối trực tiếp với nhau thì tương ứng với 1 cặp đỉnh kề nhau. A B C D Hình 1.2 Ví dụ về một đồ thị 2. Đồ thị đơn Đồ thị G = được gọi là đồ thị đơn nếu giữa hai đỉnh bất kỳ được nối với nhau bởi không quá một cạnh (cung), tức là đồ thị không có cạnh bội, không có khuyên. Hình 1.2 là một ví dụ về đồ thị đơn 3. Đa đồ thị Đồ thị G = được gọi là đa đồ thị nếu nó có ít nhất một cặp đỉnh được nối với nhau bởi hai cạnh (hai cung) trở lên. 4. Giả đồ thị Là đồ thị có ít nhất một khuyên, có thể chứa cạnh bội, cạnh đơn. Tóm lại đây là loại đồ thị tổng quát nhất. A B C D A B C D a) b) Hình 1.3 a. Đa đồ thị b. Giả đồ thị II. CÁC LOẠI ĐỒ THỊ 1. Đồ thị vô hướng Đồ thị G= được gọi là đồ thị vô hướng nếu tất cả các cạnh e Î U mà cặp đỉnh thuộc nó e = (x,y) Î X không phân biệt thứ tự. Đồ thị vô hướng là đồ thị không có bất kỳ một cung nào. Ví dụ: như hình 1.3.a là biểu diễn của một đồ thị vô hướng. 2. Đồ thị có hướng Đồ thị G = được gọi là đồ thị có hướng nếu tất cả các cạnh e Î U mà cặp đỉnh thuộc nó e = (x, y) Î X có phân biệt thứ tự. Đồ thị có hướng là đồ thị mà mọi e = (x, y) Î X đều là cung. A B C Hình 2.1 Đồ thị có hướng 3. Đồ thị hỗn hợp Đồ thị G= vừa có cạnh vô hướng, vừa có cạnh có hướng thì nó được gọi là đồ thị hỗn hợp, loại đồ thị này rất ít khi được dùng tới. Chú ý rằng vấn đề phân chia đồ thị và các thuật ngữ về đồ thị chỉ mang tính tương đối, hiện nay vẫn còn chưa mang tính thống nhất chuẩn trên nhiều tài liệu. III. MỘT SỐ KHÁI NIỆM VÀ TÍNH CHẤT CƠ BẢN CỦA ĐỒ THỊ 1. Bậc đồ thị 1.1 Bậc đồ thị vô hướng Cho đồ thị vô hướng G = . Xét 1 đỉnh x Î X đặt m(x) là số cạnh thuộc đỉnh x khi đó m(x) được gọi là bậc của đỉnh x. Nếu x có một khuyên thì m(x) được cộng thêm 2. x x m(x) = 3 m(x) = 2 - Nếu m(x) = 0 thì đỉnh x được gọi là đỉnh cô lập - Nếu m(x) = 1 thì đỉnh x được gọi là đỉnh treo Ta đặt thì m(G) được gọi là bậc của đồ thị vô hướng G = 1.2 Bậc đồ thị có hướng Cho đồ thị có hướng G= xét 1 đỉnh x Î X, ta ký hiệu m+(x) là số các cung vào của đỉnh x, còn m-(x) là số các cung ra khỏi x. Khi đó ta gọi m+(x) là bậc vào của đỉnh x còn m-(x) là bậc ra của đỉnh x. - Nếu m+(x) + m-(x) = 0 thì đỉnh x được gọi đỉnh là cô lập - Nếu m+(x) + m-(x) = 1 thì đỉnh x được gọi là đỉnh treo Ta đặt Khi đó m(G) được gọi là bậc của đồ thị có hướng G = . Trong đồ thị có hướng thì m+(x) = m-(x) = çU ç Ví dụ: - Xét đồ thị vô hướng như trong hình 1.3.a ta có: m(G) = m(A) + m(B) + m(C) + m(D) = 2 + 5 + 2 + 1 = 10 - Xét đồ thị có hướng trong hình 2.1 ta có: m(G) = [m+(A) + m+(B) + m+(C) ] + [m-(A) + m-(B) + m-(C)] = [1 + 2 + 1] + [2 + 1 +1] = 8 Định lý: Cho đồ thị hữu hạn G = khi đó bậc của đồ thị G bằng 2 lần số cạnh của đồ thị, tức là m(G) = 2çU ç. Chứng minh: Ta thấy một cạnh thuộc 2 đỉnh, nếu xoá một cạnh thì bậc của G giảm đi 2, nếu xoá một khuyên u = (x, x) thì bậc của G cũng giảm đi 2, còn nếu xoá hết cạnh, hết khuyên thì bậc của đồ thị bằng 0. Từ đó suy ra định lý. Hệ quả: Số đỉnh bậc lẻ của đồ thị G = là một số chẵn Chứng minh: Gọi A và B tương ứng là tập đỉnh bậc lẻ và tập đỉnh bậc chẵn của đồ thị. Ta có: Do vế trái chẵn nên tổng vế phải cũng là số chẵn. Mà tổng bậc của các đỉnh bậc chẵn (xÎA) là số chẵn nên tổng bậc của các đỉnh bậc lẻ (xÎB) phải là số chẵn, do tất cả các số hạng của nó là số lẻ, nên tổng này phải gồm một số chẵn các số hạng. Vì vậy số đỉnh bậc lẻ phải là số chẵn. 2. đường đi và chu trình 2.1 Đường đi Xét đồ thị G = với - Tập đỉnh X = {x1,x2,...,xn} - Tập cạnh U = {u1,u2,...,um} Tập hợp các đỉnh kề nhau từ xi đến xj được gọi là 1 đường đi, kí hiệu xixi1xi2 ... xj º xiuixi1ui1xi2ui2 ... ujxj Trong đó các cạnh, các đỉnh trong đường đi có thể lặp lại Độ dài của đường đi bằng số các cạnh (hoặc cung) trong đường đi đó. *Chú ý rằng trong đồ thị có hướng, trên một cung uv chẳng hạn thì đường đi chỉ có thể đi từ gốc (u) đến ngọn (v) không thể đi ngược lại. 2.2 Chu trình Xét một đường đi từ xi - xj. Nếu xi º xj thì đường đi này được gọi là một chu trình. Như vậy chu trình là một đường đi có đỉnh xuất phát và đỉnh kết thúc trùng nhau. Chú ý rằng đường đi trong đồ thị có hướng không được đi ngược chiều mũi tên - Đường đi (chu trình) được gọi là đơn nếu nó đi qua mỗi cạnh không quá một lần. - Đường đi (chu trình) được gọi là sơ cấp nếu nó đi qua mỗi đỉnh đúng một lần A B C D E Hình 3.1 Ví dụ như ở hình 3.1 ADBE là một đường đi sơ cấp từ A đến E độ dài 3; ABCDBE là đường đi không sơ cấp ( qua B 2 lần) từ A đến E độ dài 5; ABDAB là một đường đi không đơn (chứa cạnh AB 2 lần) từ A đến B độ dài 4; ABDA Là 1 chu trình đơn và sơ cấp độ dài 3; CC là đường đi độ dài 0. Xét đồ thị có hướng như hình 2.1 thì ABCB là một đường đi độ dài 3; CBA không là một đường đi vì không có cung đi từ B đến A. Định lý: Nếu trong đồ thị G = các đỉnh đều có bậc không nhỏ hơn 2 ( "x Î X | m(x) ³ 2 ) thì trong G tồn tại ít nhất một chu trình. Chứng minh: Xét tất cả các đường đi đơn. Vì đồ thị là hữu hạn cho nên số các đường đi đơn là hữu hạn. Chọn một đường đi là dài nhất nào đó ví dụ từ xi1 đến xij +1 (xem hình vẽ dưới đây). Theo giả thiết m(x) ³ 2 nên tồn tại ít nhất một đỉnh xi0 và một cạnh nối đỉnh xi1 và xi0. Đỉnh xi0 thuộc một trong các đỉnh trên đường đi đã chọn chẳng hạn xij vì đường đi là dài nhất, nên chứng tỏ tồn tại một chu trình trong đường đi. xi0 xi1 xi2 xi3 xij xij+1 3. Đồ thị liên thông Cho đồ thị G = . Hai đỉnh phân biệt x,y Î X được gọi là liên thông nếu tồn tại một đường đi nối các đỉnh x, y với nhau. Đồ thị G được gọi là liên thông nếu với hai đỉnh phân biệt bất kỳ trong đồ thị đều là liên thông. Ví dụ như hình 3.1 là một đồ thị liên thông vì luôn có đường đi nối hai đỉnh bất kỳ của đồ thị, còn đồ thị như hình 3.2 là không liên thông vì không có đường đi từ A tới D hoặc từ D tới F v.v.. Xét 2 đồ thị liên thông G1 = và G2 = Trong đó: X1 Ç X2 = Æ và U1 Ç U2 = Æ Khi đó: X = X1 È X2 U = U1 È U2 Thì G = là đồ thị có 2 thành phần liên thông G1, G2. A B F C E D Hình 3.3 Ví dụ như đồ thị trong hình 3.3 có ba thành phần liên thông sau: G1 = với X1= {A,B,C} và U1 = {AB, AC, CB} G2 = với X2= {D, E} và U2 = {DE} G3 = với X3= {F} và U3 = Æ Cho đồ thị có hướng G = - G được gọi là đồ thị liên thông yếu nếu đồ thị vô hướng tương ứng với nó là liên thông - G là liên thông một chiều nếu với hai đỉnh x,y khác nhau bất kỳ của G luôn có đường đi x - y hoặc đường đi y - x. - G là liên thông mạnh (liên thông 2 chiều) nếu hai đỉnh x,y khác nhau bất kỳ của G đều có đường đi x - y và đường đi y - x. A B C D A B C D A B C D H1 H2 H3 Hình 3.4 Ở hình 3.4 đồ thị H1 là liên thông mạnh, giả sử cặp đỉnh (A,C) ta có chiều đi từ C tới A, và đồng thời cũng có chiều đi từ A tới C, và bất kỳ các cặp đỉnh khác cũng tương tự như vậy. H2 là liên thông một chiều vì xét cặp đỉnh (A,D) có chiều đi từ D tới A nhưng không có chiều đi từ A tới D. H3 là liên thông yếu vì tồn tại cặp đỉnh (B,C) không có chiều đi B - C cũng không có chiều đi C - B, nhưng đồ thị vô hướng tương ứng là liên thông. 4. Đồ thị con và đồ thị bộ phận Cho đồ thị G = - Nếu trong đồ thị đó ta bỏ đi một số đỉnh nào đó và các cạnh xuất phát từ đỉnh đó thì phần còn lại của đồ thị được gọi là đồ thị con của đồ thị G đã cho, hoặc là nếu D = là đồ thị con của G = thì X' Í X và U' Í U - Nếu trong đồ thị G ta bỏ đi một số cạnh nhưng giữ nguyên các đỉnh thì phần còn lại của đồ thị được gọi là đồ thị bộ phận của đồ thị G. IV. CÁC DẠNG BIỂU DIỄN CỦA ĐỒ THỊ 1. Biểu diễn hình học của đồ thị Để có cái nhìn trực quan ta thường biểu diễn đồ thị bằng hình học, một đồ thị có thể biểu diễn trên một mặt phẳng hoặc trong không gian. Phương pháp biểu diễn như sau: Biểu diễn các đỉnh của đồ thị bằng các điểm (hay vòng tròn nhỏ, ô vuông nhỏ) và nối hai điểm bằng một đường (cong, thẳng, mũi tên) khi cặp điểm đó ứng với một cạnh (cung) của đồ thị. Ví dụ 1: Cho đồ thị G = trong đó X = {A, B, C, D, E} và U = {AB, AC, AD, AE, BD, CD, CE} C D E B A A B D E C a) b) Hình 4.1 Hình 4.1.a và hình 4.1.b đều là biểu diễn hình học của đồ thị G đã cho ở trên 2. Sự đẳng cấu Với mỗi đồ thị thì có thể có nhiều dạng biểu diễn hình học, có nhiều đồ thị tưởng chừng khác nhau nhưng đó là cách biểu diễn hình học khác nhau của cùng một đồ thị, sự đẳng cấu cho phép chúng ta kết luận được điều đó. Định nghĩa: Xét 2 đồ thị G1 = (X1, U1) và G2 = Hai đồ thị này được gọi là đẳng cấu với nhau nếu tồn tại 1 song ánh từ X1 vào X2 và từ U1 vào U2 sao cho nếu có cạnh e = (u, v) Î U1 tương ứng với cạnh e' = (u', v') Î U2 thì cặp đỉnh u, v Î X1 cũng là tương ứng cặp đỉnh u', v' Î X2 Ví dụ xét 2 đồ thị G1 và G2 như hình 4.2 a b c d m n p q G1 G2 Hình 4.2 Ta có f : G1 ® G2 f(a) = m f(c) = n f(d) = q f(b) = p Nếu a, b Î X1 kề nhau thì f(a), f(b) Î X2 kề nhau. Vậy đây là 2 đồ thị đẳng cấu với nhau, ta có thể xem G1 và G2 thực chất chỉ là 1 chỉ có điều biểu diễn ở dạng hình học khác nhau, các tên đỉnh khác nhau. Để xét 2 đồ thị có đẳng cấu không là việc khó, tuy nhiên để xét 2 đồ thị không đẳng cấu với nhau thì đơn giản hơn. Đối với 2 đồ thị đẳng cấu thì các đồ thị đó có những tính chất bất biến như sau: - Số đỉnh bằng nhau - Số cạnh bằng nhau - Bậc các đỉnh tương ứng cùng như nhau - 2 Ma trận kề cũng như nhau - Các chu trình cũng như nhau 3. Một số đồ thị đặc biệt Do tính chất, dạng biểu diễn có những nét đặc thù riêng biệt nên ta phân loại một số đồ thị thành các dạng đặc biệt sau: 3.1 Đồ thị đều Là một đồ thị mà mọi đỉnh có cùng bậc, nếu bậc này bằng k thì đó là đồ thị k - đều a) b) c) d) Hình 4.3 a: G- 1 đều; b: G - 2 đều; c: G - 2 đều; d: G - 3 đều. Trường hợp riêng như đồ thị hình 4.3.b và hình 4.3.c là những đồ thị vòng ký hiệu Cn (n là số đỉnh) 3.2 Đồ thị đầy đủ Đồ thị đầy đủ n đinh, ký hiệu Kn là đơn đồ thị vô hướng mà mọi cặp đỉnh phân biệt luôn kề nhau. Xem ví dụ như hình 4.4 dưới đây hoặc 1 trường hợp riêng của đồ thị đều G - 3 là những đồ thị đầy đủ a) b) Hình 4.4 a - đồ thị đầy đủ K2 ; b - đồ thị đầy đủ K4 3.3 Đồ thị bánh xe: Ký hiệu Wn, thu được từ đồ thị vòng có n đỉnh bằng cách bổ sung một đỉnh mới nối tất cả các đỉnh đã có. W4 W5 W6 Hình 4.5 Các dạng đồ thị bánh xe 3.4 Một vài ứng dụng của đồ thị đặc biệt Ở các mạng cục bộ (LAN), các máy tính thường được kết nối theo một cách thức nào đó gọi là hình trạng (topolopy). Dựa theo đặc điểm của các totolopy này mà ta có thể mô hình bằng 1 số dạng đồ thị đặc biệt. Ví dụ với mạng LAN các máy tính được kết nối theo topolopy hình sao (Star) sau đây: Hình 4.6 Ở dạng này, tất cả các máy được nối vào một thiết bị trung tâm có nhiệm vụ nhận tín hiệu từ các máy và chuyển đến máy đích của tín hiệu. Từ đặc điểm này có thể mô hình bằng một đồ thị bộ phận của đồ thị bánh xe W6 như hình 4.7.a a) b) c) d) a) Dạng sao b) dạng vòng c) dạng hỗn hợp d) dạng đầy đủ (Complete) Hình 4.7 Một số topolopy của LAN Ở mạng LAN ta cũng thường có các dạng topolopy khác như dạng chu trình (loop) hoặc gọi là vòng. Ở dạng này mỗi máy nối đúng với 2 máy khác. Mạng cục bộ với cấu trúc vòng tròn được mô hình bằng các đồ thị đặc biệt dạng vòng Cn như hình 4.7.b, thông báo gửi từ máy này sang máy khác theo chu trình vòng tròn cho tới khi tới được máy đích. Hoặc 1 dạng nữa là dạng hỗn hợp, đó là sự kết hợp của dạng hình sao và hình vòng. Topolopy kiểu này là một đồ thị bánh xe Wn (hình 4.7.c). Mạng cục bộ dạng bánh xe các máy có thể truyền vòng quanh theo vòng tròn hoặc có thể qua bộ phận trung tâm. Ngoài ra người ta cũng thường hay bố trí mạng sao cho các máy đều kết nối trực tiếp với nhau, với kiểu này có thể mô hình bằng đồ thị đầy đủ Kn (hình 4.7.d) 4. Biểu diễn đồ thị trên máy tính Lĩnh vực đồ thị có nhiều ứng dụng trong thực tế, có thể mô hình nhiều ứng dụng bằng đồ thị và sử dụng máy tính để giải quyết các bài toán về ứng dụng đó. Nên việc biểu diễn và lưu trữ đồ thị trên máy tính là một vấn đề khá trọng tâm, phương thức biểu diễn từng loại đồ thị trên máy tính ảnh hưởng đến các giải thuật, phương pháp giải quyết các ứng dụng trên máy tính. 4.1 Biểu diễn bằng ma trận kề Phương pháp này dựa trên mối quan hệ giữa các cặp đỉnh, mỗi đồ thị được đặt tương ứng với một ma trận vuông cấp n (n là số đỉnh của đồ thị). Gọi ma trận kề là A = (aij ) i,j = 1...n. + Trường hợp G = là đồ thị vô hướng với X = {x1, x2,...,xn} khi đó mỗi phần tử aij của ma trận A được xác định như sau: aij = aji = d, nếu cặp đỉnh (xi, xj) có d cạnh nối với nhau. Khi cặp đỉnh (xi, xj) không có cạnh nào nối với nhau thị aij = 0. Ta thấy ma trận kề của đồ thị vô hướng là ma trận đối xứng. + Trường hợp G = là đồ thị có hướng với X = {x1, x2,...,xn} thì mỗi phần tử aij của A được xác định như sau: đối với mỗi cặp đỉnh (xi, xj) từ xi đến xj nếu có d cung thì aij = d. Chú ý aji = 0 nếu không có cung nào hướng từ xj đến xi. Ma trận kề trong trường hợp này là không đối xứng. Trong 2 trường hợp trên ta chú ý nếu đỉnh xi có một khuyên thì phần tử tương ứng của ma trận kề là aii = 1 A C B D A B C D G1 G2 Hình 4.8 Ta có thể dùng ma trận kề biểu diễn đồ thị G1 và G2 trong hình 4.8 như sau: Đối với đồ thị có trọng số mỗi cạnh e = (xi, xj) được gán một trọng số l(e) (còn viết là l(xi, xj) ) thì ma trận kề của nó được thay bằng ma trận có trọng số, khi đó mỗi phần tử của ma trận bằng trọng số của cạnh tương ứng: aij = l(xi, xj) Ưu điểm của phương pháp này là dễ dàng xác định được các cặp đỉnh có kề nhau hay không hoặc rất thuận tiện khi tìm số bậc của mỗi đỉnh. Việc truy cập phần tử của ma trận kề qua chỉ số không phụ thuộc vào số đỉnh của đồ thị. Nhược điểm lớn nhất của phương pháp này là không phụ thuộc vào số cạnh của đồ thị, ta luôn phải sử dụng n2 đơn vị bộ nhớ để lưu trữ ma trận kề của nó. Định lý: s lần Nếu G = là đa đồ thị với A = (aij) là ma trận kề tương ứng, thì số đường đi khác nhau từ đỉnh xi đến đỉnh xj có độ dài s bằng phần tử Pij của ma trận tích A´A´...´A = As = (Pij) Xét ví dụ ứng dụng: Trong một số hệ thống thông tin khi được mô hình bằng đồ thị có thể thực hiện tốt một số công tác kiểm kỹ thuật. Ví dụ khi biểu diễn một mạng máy tính bằng đồ thị, giả sử có 2 máy nào đó mà thông tin truyền giữa chúng là quan trọng, cần tiến hành kiểm tra xem đã có đường truyền dự phòng giữa chúng không. Xét ở góc độ đồ thị thì cần kiểm tra xem số đường đi giữa cặp đỉnh tương ứng với 2 máy đó, nếu số đường đi lớn hơn 1 là đã có đường truyền dự phòng. * Chương trình viết bằng PASCAL sau tính số đường đi độ dài l nhập từ bàn phím Type MaTran = Array[1..20,1..20] Of Integer; Var a, b, aa: MaTran; n,l,x1,x2: Integer; Procedure InputMt(Var Mt: Matran); Var i, j: Integer; Begin For i:=1 to n do For j:=1 to n do Begin Write('a',i,j,'= '); Readln(Mt[i,j]); End; End; Procedure Gan(Mt1: MaTran; Var Mt2: MaTran); {Mt2 <-- Mt1} Var i,j:Integer; Begin For i:=1 to n do For j:=1 to n do Mt2[i,j]:=Mt1[i,j]; End; Procedure TichMt(mt1,mt2: Matran; Var MtKq: MaTran); { MtKq = Mt1*Mt2 } Var i,j,k: Integer; Begin For i:=1 to n do For j:=1 to n do Begin MtKq[i,j]:=0; For k:=1 to n do MtKq[i,j]:=MtKq[i,j]+Mt1[i,k]*Mt2[k,j]; End; End; Procedure LthuaMt(m: Integer); {aa = a ^m (m: do dai duong di, m>=2) } Var i: Integer; Begin Gan(a,b); For i:=1 to m-1 do Begin TichMt(b,a,aa); Gan(aa,b); End; End; Procedure FindWay(i,j: Integer); { Tim so duong di tu dinh i-->j } Begin If aa[i,j]0 then Writeln('So duong di do dai ',l,' tu x',x1,' --> ','x2 ','la: ',aa[i,j]) Else Writeln('Khong co duong di tu dinh ',i,' toi dinh ',j,' voi do dai ',l); End; BEGIN Writeln('Nhap ma tran ke cho do thi:'); Write('So dinh do thi: '); Readln(n); InputMt(a); Write('Dinh xuat phat: '); Readln(x1); Write('Dinh ket thuc: '); Readln(x2); Write('Do dai duong di: '); Readln(l); LthuaMt(l); FindWay(x1,x2); END. 4.2 Danh sách cạnh (cung) Cho đồ thị G = với số cạnh m, số đỉnh n. Nếu m < 6n thì G thường được biểu diễn dưới dạng danh sách cạnh (cung). Theo cách này danh sách tất cả các cạnh (cung) của đồ thị vô hướng (có hướng). Mỗi cạnh (cung) e = (x, y) của đồ thị tương ứng với hai biến Dau[e], Cuoi[e]. 1 2 3 4 1 2 4 3 G1 G2 Hình 4.9 Dau Cuoi 1 2 1 3 2 3 2 4 3 4 Danh sách cạnh G1 Dau Cuoi 1 2 2 3 3 1 4 1 4 2 Danh sách cung G2 Ví dụ: Hình 4.9 đồ thị G1 và G2 được biểu diễn bằng danh sách cạnh (cung) như sau: Như vậy để lưu trữ đồ thị cần sử dụng 2m đơn vị bộ nhớ. Nhược điểm của phương pháp này là để xác định những đỉnh nào của đồ thị là kề với một đỉnh cho trước chúng ta phải làm cỡ m phép so sánh. 4.3 Danh sách kề Phương pháp biểu diễn bằng danh sách kề cũng được sử dụng khá phổ biến và thường hay dùng cho đồ thị có hướng. Danh sách kề cho đỉnh xi là danh sách gồm tất cả các đỉnh kề của xi theo thứ tự các đỉnh trong tập đỉnh X. Ta có thể biểu diễn đồ thị như một mảng FIRST, với phần tử FIRST[i] là con trỏ trỏ tới danh sách kề cho đỉnh xi. Ví dụ: ở hình 4.9 đồ thị G1 và G2 được biểu diễn bằng danh sách kề như sau: FIRST 2 1 1 2 3 Nil 3 2 3 Nil 4 Nil 4 Nil 1 2 3 4 a) Danh sách kề của đồ thị G1 FIRST 3 Nil 2 1 Nil 3 Nil 2 Nil 1 2 3 4 b) Danh sách kề đồ thị G2 Bộ nhớ sử dụng cho phương pháp biểu diễn danh sách kề là tỷ lệ thuận với tổng số đỉnh và các cạnh của đồ thị. Nhược điểm của cách biểu diễn này là thời gian cần thiết để xác định có một cạnh đi từ đỉnh xi tới đỉnh xj có hay không mất O(n). Cách biểu diễn này thích hợp cho các thuật toán mà cấu trúc đồ thị hay thay đổi như thêm hoặc bớt các cạnh. Chương 2 SỐ ỔN ĐỊNH VÀ TÔ MÀU ĐỒ THỊ I. SỐ ỔN ĐỊNH TRONG, SỐ ỔN ĐỊNH NGOÀI, NHÂN ĐỒ THỊ 1. Số ổn định trong Cho đồ thị vô hướng G = và A Í X. a) Tập A gọi là tập ổn định trong của đồ thị nếu hai đỉnh bất kỳ trong A là không kề nhau, tức là không có một cạnh nào của đồ thị chứa hai đỉnh x và y. b) Tập A gọi là tập ổn định trong cực đại của đồ thị G nếu: - A là tập ổn định trong - Nếu thêm vào A một đỉnh ngoài A thì A không phải là ổn định trong. Gọi L là tập hợp các tập ổn đỉnh trong của của G = . Khi đó ký hiệu a(G) = Max {ïAï / AÎ L} và a(G) được gọi là số ổn định trong của đồ thị G. Như vậy a(G) là số phần tử của 1 tập ổn định trong cực đại nào đó. 2. Số ổn định ngoài Cho đồ thị vô hướng G = và B Í X a) Tập B được gọi là tập ổn định ngoài của đồ thị nếu với mỗi phần tử y Î X \ B đều tồn tại x Î B sao cho có cạnh nối giữa x và y, B còn được gọi là tập thống trị của đồ thị. b) Tập B được gọi là tập ổn định ngoài cực tiểu nếu: - B là tập ổn định ngoài - Nếu bớt 1 phần tử bất kỳ của B thị B không còn là tập ổn định ngoài. Gọi M là tập của tất cả các tập ổn định ngoài của G = . Khi đó ký hiệu b(G) = Min {ïBï / BÎ M} và b(G) được gọi là số ổn định ngoài của đồ thị G. Đối với các tập ổn định ngoài, ta thường quan tâm đến tập ổn định ngoài có số phần tử ít nhất vì lực lượng của nó liên quan tới số ổn định ngoài của đồ thị. 3. Nhân đồ thị Cho đồ thị vô hướng G = . Nếu tập A Í X vừa là tập ổn định trong vừa là tập ổn định ngoài của đồ thị G thị A được gọi là nhân của đồ thị. Đối với nhân của đồ thị, ta quan tâm tới nhân có số phần tử ít nhất. 4 1 2 3 6 5 7 Hình 1.1 Ví dụ: xét đồ thị hình 1.1 ta có: Các tập ổn định trong của đồ thị là: A1 = {1, 5, 7} A6 = {2, 6, 7} A2 = {1, 6, 7} A7 = {4, 5, 7} A3 = {3, 5, 7} A8 = {4, 6, 7} A4 = {3, 6, 7} A9 = {2, 4, 5, 7} A5 = {2, 5, 7} A10 = {2, 4, 6, 7} Tập A9 và A10 là các tập ổn định trong cực đại có 4 phần tử vì nếu thêm 1 đỉnh mới nữa vào các tập đó thì chúng không còn là tập ổn định trong nữa. Số ổn định trong của đồ thị trên là a(G) = 4. Với đồ thị trên các tập ổn định ngoài cực tiểu là B1 = A1; B2 = A2; B3 = A3; B4 = A4. Vì các tập này nếu bớt đi 1 trong các phần tử của chúng thì tập còn lại không là tập ổn định ngoài nữa. Số ổn đỉnh ngoài của đồ thị này là b(G) = 3. Nhân của đồ thị trên là B1, B2, B3, B4 vì các tập này là tập ổn định trong và đồng thời cũng là tập ổn định ngoài. 4. Các thuật toán tìm các tập ổn định trong cực đại, ổn định ngoài cực tiểu. 4.1 Thuật toán tìm số ổn định trong - Bước 1: Tìm các tập ổn định trong có 2 phần tử bằng cách xét tất cả tổ hợp chập 2 của n phần tử (n số các đỉnh), kiểm tra những tập nào mà phần tử của ma trận kề tương ứng bằng 0 thì tập đó là ổn định trong. - Bước 2: Duyệt từng tập có 2 phần tử và bổ sung thêm phần tử thứ 3 và kiểm tra từng cặp như bước 1, tập nào thoả ta được tập ổn định trong 3 phần tử. ........ - Bước k: Giả sử đã tìm được m tập con ổn định trong có k + 1 phần tử + Duyệt từng tập và bổ sung vào các tập đó thêm 1 phần tử + Nếu không có tập nào bổ sung được nữa thì dừng 4.2 Thuật toán tìm số ổn định ngoài Xét G = với X = {x1, x2,....,xn} - Bước 1: Xác định các tập D(xi) i = 1..n với D(xi) = {xi và các đỉnh kề với xi} - Bước 2: Từ các tập D(x1), D(x2),..., D(xn) ta tìm tập B B = {xk1 , xk2 ,..., xkm} sao cho D(xk1) È D(xk2) È ... ÈD(xkm) = X Khi đó B là tập ổn định ngoài cực tiểu 5. Ứng dụng đồ thị trong lập trình chơi cờ Ca rô Ta xét một ứng dụng của đồ thị cho bài toán lập trình chơi cờ Ca rô trên máy tính. Cờ carô là loại cờ mà rất nhiều bạn trẻ đặc biệt giới sinh viên học sinh ưa thích. Quy tắc và cách thức chơi đơn giản, nhưng nó thực sự là bài toán tin rất hay, là bài lập trình thể hiện nhiều tư duy thuật toán, cũng như cơ sở về trí tuệ nhân tạo cho việc lập trình trò chơi giữa người và máy. Ta xét ứng dụng của đồ thị phục vụ cho bài toán lập trình trò chơi Carô. Xét một thế cờ Carô như hình 1.2.a 0 1 0 2 A = 0 0 2 2 0 2 0 0 1 0 0 1 o1 x1 x2 x4 x3 o2 o3 a) b) Hình 1.2 Cấu trúc dữ liệu cho thế cờ này có thể dùng bảng ma trận như hình 1.2.b, với 0 là vùng trắng, 1 là quân "o" và 2 là quân "x". Nhưng như vậy việc tính toán sẽ rất khó khăn, ta có thể dùng đồ thị làm cấu trúc dữ liệu cho thế cờ Carô, khi đó việc tính toán sẽ dễ dàng đi và tận dụng những tính chất đã nghiên cứu về đồ thị thì bài toán lập trình trò chơi carô sẽ trở nên thuận lợi hơn nhiều. a) Mô hình bằng đồ thị theo vị trí liền kề Ta xây dựng 1 đơn đồ thị theo nguyên tắc sau - Mỗi 1 quân "x" hoặc quân "o" thì tương ứng với một đỉnh - Hai đỉnh là kề nhau nếu tương ứng với 2 quân ở vị trí liên tiếp nhau - Mỗi một cạnh được gán một nhãn, nhãn cho biết 2 đỉnh kề nhau là kề đứng, kề chéo hay là kề ngang trong thế cờ. Ta gán tên nhãn như sau: thẳng ngang nhãn là 1, thẳng chéo trái là 2, thẳng dọc nhãn là 3, thẳng chéo phải là 4 (xem hình 1.3.a). x1 x2 x3 o2 o1 x4 o3 4 4 4 2 1 3 4 1 2 3 a) b) Hình 1.3 a) Cách đánh nhãn b) Đồ thị cho thế cờ hình 1.2.a Ví dụ đồ thị như hình 1.3.b là thể hiện cho thế cờ hình 1.2.a Trong luật chơi cờ carô nếu quân "x" đi trước thì ngay sau đó là quân "o" đi sau, tiếp tục lại "x" rồi lại "o"... Chính điều này ta có thể coi những quân "x" tương ứng là những đỉnh số lẻ, quân "o" tương ứng những đỉnh số chẵn hoặc ngược lại. Trong 1 thế cờ Carô nếu tồn tại 1 dãy 5 quân liên tiếp của "x" hoặc "o" được sắp thẳng hàng ngang, thẳng hàng dọc hoặc thẳng hàng chéo thì thắng. Với đồ thị nếu tồn tại một đường đi các cạnh cùng nhãn gồm 5 đỉnh số lẻ, hoặc số chẵn thì thế cờ thắng cho tương ứng quân "x" hoặc quân "o". Xét đồ thị hinh 1.3.b đã có 1 đường đi cùng nhãn 4 gồm 3 đỉnh cùng quân x1, x2, x3. Nếu ta thêm 1 đỉnh x6 kề với đỉnh o2 sao cho cạnh (o2, x6) có nhãn 4, sau cùng ta thay đỉnh o2 bằng đỉnh x5 thì bây giờ ta có 1 đường đi cùng nhãn 4 gồm 5 đỉnh quân "x" (x1, x2, x3, x5, x6) và ta có 1 thế cờ thắng cho quân x. Nhận xét: - Với mô hình này ta sẽ không thể thấy được đầy đủ mối quan hệ giữa các đỉnh, như đồ thị hình 1.3.b đỉnh o3 là đỉnh cô lập, trong thế cờ hình 1.2.a o1 có mối quan hệ thẳng hàng với x1 và x3 nhưng trong đồ thị tương ứng ta không nhìn thấy được mối quan hệ này nên khó tính toán được nước đi cho lần sau. Mà mối quan hệ "thẳng hàng" giữa các quân là quan trọng trong bài toán lập trình trò chơi carô. - Mô hình này chỉ thích hợp cho việc lập trình khi mà chỉ chơi giữa người với người, lúc này bài toán chỉ là tìm đường đi cùng nhãn gồm 5 đỉnh cùng quân, không phải là bài toán tính nước đi cho các bước tiếp theo. b) Mô hình bằng đồ thị theo mối quan hệ thẳng hàng. Cách xây dựng này tương tự như cách thứ nhất nhưng có những đặc điểm sau: - Hai đỉnh x và o là kề nhau nếu tương ứng với 2 quân x và o mà chúng có mối quan hệ là thẳng hàng với nhau. - Trên mỗi cạnh ngoài nhãn thể hiện mối quan hệ thẳng hàng, ta thêm 1 trọng số đường đi, trọng số của cạnh (x, o) là số ô đi thẳng hàng từ quân x đến quân o trong thế cờ. - Hai đỉnh x và o chỉ được kề nhau khi trọng số cạnh (x, o) không quá 4. x1 o1 x1 x2 x2 x3 x3 x4 o2 o3 x5 a) b) Hình 1.4 Ví dụ xét thế cờ như hình 1.4.a và hình 1.4.b thì đồ thị tương ứng của nó như hình 1.5.a và hình 1.5.b o1 x1 x2 x3 o2 o3 x1 x2 x3 x4 x5 a) b) Hình 1.5 Mỗi cạnh của đồ thị, nhãn đặt trước trọng số, trọng số đứng sau cách nhãn bởi dấu phẩy. Xét thế cờ 1.4.a từ quân x1 đến quân x2 cách nhau 1 ô nếu tính từ x1 nên trọng số cạnh (x1, x2) là 1, quân x1 cách x3 2 ô nên trọng số (x1, x3) là 2. Ta thấy x1, x2, x3 đều thẳng hàng dọc nên nhãn là 3, và tương tự đánh nhãn và trọng số cho các cạnh còn lại ta có đồ thị như hình 1.5.a. Như vậy nếu tồn tại 1 đường đi cùng nhãn và có trọng số 1 gồm 5 đỉnh cùng quân thì thế cờ thắng, ở đồ thị hình 4.a đường đi thắng cho quân x là (x1, x2, x3, x4, x5) Trong kỹ thuật chơi cờ Ca rô, nước đi có lợi nhất là nước có tạo được nhiều khả năng dẫn đến thế cờ thắng, ví dụ thế cờ như hình 1.4.b thì ví trí của o1 là 1 trong những nước có lợi nhất, vì nếu ta thay o1 bằng x4 thì quân x có thêm 3 khả năng phát triển nước dẫn đến thế cờ thắng như (x4, x2); (x4, x1); ( x4, x3), nếu với đồ thị tương ứng thì x4 là phần tử thống trị tập {x1, x2, x3}. Nếu vẫn giữ vị trí o1 như ban đầu thì quân "o" đã ngặn chặn đối phương có hiệu quả vì o1 đã thống trị {x1, x2, x3}, và ta thấy còn có o2 thống trị {x1, x2, x3} ngăn chặn được thế sắp thắng theo thẳng chéo {x1, x2, x3} (xem đồ thị hình 1.5.b). Như vậy ở góc độ đồ thị thì ta tìm tập thống trị (tập ổn định ngoài cực tiểu), ở đồ thị này {o1, o2} là 1 tập thống trị. Nhận xét: - Với mô hình này ta có ưu điểm là nhìn rõ trước được mối quan hệ giữa các đỉnh, tuy vậy nếu có 2 đỉnh không thẳng hàng thì chúng cô lập nhau, nhưng điều thường xảy ra khi số đỉnh là nhỏ ta dễ dàng kiểm soát được thế cờ. Hơn nữa hầu như ta chỉ quan tâm những quân có mối quan hệ thẳng hàng, để khắc phục nhược điểm ta có thể dựa vào mối quan hệ "tay ba" bằng cách đưa thêm đỉnh "ảo". - Khi số đỉnh càng lớn, càng thêm những đỉnh có mối quan hệ thẳng hàng thì số bậc của mỗi đỉnh tăng, nhưng quy luật cờ ca rô nên chỉ những đỉnh thẳng hàng mà cách nhau không quá 4 ô mới ảnh hưởng lẫn nhau, nên 2 đỉnh kề nhau nếu trọng số của chúng £ 4. Có 8 hướng thẳng hàng (xem hình 1.3.a), nên một đỉnh có tối đa là 8.4 = 32 bậc. - Khi một đỉnh có số bậc là 32 thì có thể loại bỏ khỏi đồ thị, vì nó không còn ảnh hưởng đến những đỉnh khác. Nhãn và trọng số của cạnh có thể là khoá phục vụ cho việc xử lý và tìm kiếm, tra cứu thông tin khi cần thiết. II. TÔ MÀU ĐỒ THỊ 1. Sắc số đồ thị Sắc số đồ thị G là số màu tối thiểu cần dùng để tô màu các đỉnh của đồ thị sao cho hai đỉnh kề nhau phải có màu khác nhau. Ta ký hiệu sắc số của đồ thị G là l(G). Định lý 1: Cho đồ thị n đỉnh G = . Nếu đồ thị là đầy đủ thì sắc số của nó bằng số đỉnh của đồ thị, tức là l(G) = n. Chứng minh: Với n = 1 thì l(G) = 1 Giả thiết đúng với n £ k cần chứng minh đúng với n = k +1 Xét đồ thị k + 1 đỉnh X = {x1, x2,....., xk, xk+1} Nếu trong đồ thị G ta bỏ đỉnh xk+1 còn lại là 1 đồ thị với k đỉnh. Đối với phần còn lại theo giả thiết quy nạp ta cần k màu. Xét đỉnh xk +1, vì đồ thị là đầy đủ nên đỉnh xk+1 nối với các đỉnh còn lại, cho nên để tô đỉnh xk+1 cần màu khác với màu đã tô nên số màu sẽ là k + 1 màu. Hệ quả: Nếu đồ thị G chứa một đồ thị con đẳng cấu với Km thì l(G) ³ m Định lý 2: Giả sử G = là đồ thị vô hướng l(G) = 2 khi và chỉ khi trong G không có chu trình độ dài lẻ. - Điều kiện đủ: Giả sử G không có chu trình độ dài lẻ. Ta chỉ ra l(G) = 2. Thật vậy, ta tô màu các đỉnh của G theo nguyên tắc sau: Nếu x Î X được tô màu xanh thì các đỉnh kề của x là y, z ... lại tô màu đỏ. Tiếp theo các đỉnh kề của y, z,... lại tô màu xanh. Cứ như vậy, do số đỉnh hữu hạn và G liên thông nên tất cả các đỉnh trong X sẽ được tô hoặc xanh hoặc đỏ và không có một đỉnh nào được tô cả hai màu xanh, đỏ đồng thời, vì nếu có điều đó xảy ra thì sẽ có một chu trình độ dài lẻ đi qua x (trái với giả thiết). Hay l(G) = 2. - Điều kiện cần: Giả sử l(G) = 2. Dễ thấy rằng chỉ dùng 2 màu để tô các đỉnh của G thì trong G phải không có chu trình độ dài lẻ, vì nếu có chu trình độ dài lẻ thì tô màu các đỉnh theo quy tắc trên sẽ có ít nhất một đỉnh được tô đồng thời cả 2 màu. Định lý được chứng minh. a b c e d a b c d G1 G2 Hình 2.1 Ví dụ: Hình 2.1 đồ thị G1 không có chu trình độ dài lẻ, còn G2 có chu trình độ dài lẻ. Trong G1 nếu ta tô đỉnh a bởi màu xanh thì đỉnh b, c tô màu đỏ. Vì b màu đỏ nên d, e tô màu xanh. Ta thấy G1 không có chu trình lẻ và l(G) = 2. Xét G2 có chu trình độ dài lẻ nên không thể tô bằng 2 màu, mà phải dùng 3 màu: xanh, đỏ và vàng. Định lý 3: Giả sử G = là đồ thị vô hướng với số đỉnh là n. Khi đó số ổn định trong a(G) và sắc số l(G) thoả mãn bất đẳng thức: a(G) . l(G) ³ n. Chứng minh: Đặt l(G) = s, theo định nghĩa của sắc số thì dùng s màu để tô các đỉnh trong X theo nguyên tắc hai đỉnh kề phải tô bằng 2 màu khác nhau. Cách tô màu như trên lập nên một phân hoạch tương đương trên tập X: X1 È X2 È...È Xs, Xi Ç Xj = Æ (i ¹ j), ở đây nếu ta đánh số các màu từ 1, 2,...,s thì Xi gồm các đỉnh cũng được tô màu i (i = 1,2,...,s). Mặt khác theo định nghĩa số ổn định trong thì ïXiï £ a(G) (i = 1,....,s). Từ đó ta có đánh giá: ïXï = n = ïX1ï + ïX2ï + ... + ïXiï +...+ ïXsï £ s.a(G) Hay a(G) . l(G) ³ n. Định lý được chứng minh. 2. Tô màu đồ thị phẳng 2.1 Đồ thị phẳng Xét đồ thị G = được gọi là phẳng nếu có thể biểu diễn được trên mặt phẳng sao cho bất kỳ hai cạnh nào cũng không cắt nhau ngoài đỉnh (nếu có) Ví dụ: Xét đồ thị như hình 2.2.a1 là đồ thị phẳng vì nó được biểu diễn cách khác ở dạng mặt phẳng không có cạnh cắt nhau như hình 2.2.a2 Tương tự đồ thị ở hình 2.2.b1 là đồ thị phẳng vì nó có thể biểu diễn ở dạng mặt phẳng như hình 2.2.b2 a b c d a b c d a1) a2) g a b f d c e h g a b f d c e h b1) b2) Hình 2.2 * Các cạnh của đồ thị phẳng chia mặt phẳng thành nhiều miền, mỗi miền gọi là một mặt của G. Những cạnh nằm bên trong mặt f nào đó hoặc là cạnh giới hạn của mặt f với một mặt khác gọi là cạnh biên của mặt f. 2.2 Định lý 5 màu (Kempe - Heawood) Mọi đồ thị phẳng đều có sắc số không lớn hơn 5. Chứng minh: Xét một đồ thị G có n đỉnh. Dùng phép chứng minh quy nạp trên n ta có: Trường hợp G có một đỉnh hiển nhiên đúng. Giả sử mọi đồ thị phẳng có n đỉnh (n ³ 1) đều có thể tô bằng 5 màu. Coi một đồ thị phẳng có n + 1 đỉnh. Có thể giả sử G là đơn đồ thị. Vì G phẳng nên có một đỉnh bậc £ 5. Loại bỏ đỉnh x này khỏi G, ta nhận được một đồ thị phẳng mới có n đỉnh. Tô màu cho đồ thị mới này bằng năm màu, do giả thiết qui nạp trên điều này thực hiện được. Bây giờ đưa đỉnh x vào lại đồ thị. Nếu các đỉnh kề với x được tô bằng ít hơn 5 màu thì tô màu x bằng một trong 5 năm khác màu các đỉnh kề với x là xong : đồ thị G đã được tô bằng 5 màu. a b c d e x 5 1 2 3 4 Vậy chỉ xét trường hợp m(x) = 5 và 5 đỉnh kề với x được tô bằng 5 màu như hình 2.3 sau: Hình 2.3 Xét tất cả các đường trong G bắt đầu từ a và gồm các đỉnh chỉ tô bằng màu 1 và màu 3, trong các đường này nếu không có đường nào đi qua đỉnh c thì ta có thể thày đổi màu các đỉnh trên, tất cả các đường nói trên theo cách đổi màu 1 thành màu 3 và có thể tô đỉnh x màu 1. Nếu có một đường từ a đên c gồm toàn các đỉnh chỉ tô bằng màu 1 và màu 3 thì đường này cộng thêm hai cạnh e1 = (x, a) và e2 = (c, x) sẽ tạo thành một chu trình. Hai đỉnh b, d không thể nằm cùng bên trong hoặc cùng bên ngoài chu trình này được. Suy ra không có đường nào từ b đến d gồm các đỉnh chỉ tô màu 2 và màu 4 theo cách đổi màu 2 thành màu 4 và ngược lại. Lúc này, b và d có cùng màu 4 và ta có thể tô đỉnh x bằng màu 2. 2.3 Bài toán 4 màu (Appel - Haken) Phát biểu: Mọi đồ thị phẳng đều có sắc số không lớn hơn 4. Bài toán 4 màu được phát biểu như trên được chứng minh bằng phép thử trên máy tính trong nỗ lực nhằm thay thế cho định lý 5 màu. 3. Ví dụ ứng dụng Vấn đề tô màu đồ thị cũng có nhiều ứng dụng thực tế như tô màu bản đồ, công tác lập lịch. Với đồ thị phẳng ta có thể mô hình cho một bản đồ, trong đó mỗi miền bản đồ thì tương ứng là một đỉnh, hai miền có chung đường biên thì tương ứng với 2 đỉnh kề nhau. Khi tô màu bản đồ thì 2 miền kề nhau (chỉ chung đường biên không kể chung điểm biên) phải có màu khác nhau. Như vậy vấn đề tìm số màu tối thiểu để tô bản đồ, tương ứng với việc tìm sắc số cho đồ thị phẳng. Vào năm 1850 người ta đã chỉ ra 1 cách tô bản đồ nước Anh chỉ cần 4 màu, điều này là 1 thể hiện cho bài toán 4 màu. * Trong nhiều bài toán tin học, ta hay bắt gặp bài toán lập lịch. Vấn đề tô màu đồ thị có thể ứng dụng để giải quyết bài toán này. Ta xét một ví dụ ứng dụng, trong một phòng về phần mềm có các nhóm lập trình như sau: 1 - Hệ thống: A, B, C 2 - Multimedia: A, F, G 3 - Thương mại: B, D, E 4 - Về mạng: C, F, A. Các chữ cái là tên cho các thành viên, mỗi thành viên có thể tham gia nhiều nhóm khác nhau. Hàng tháng mỗi nhóm họp một lần để thảo luận các dự án mới và phân chia công việc, hãy lập lịch họp cho các nhóm để sao cho không ai họp trùng nhiều nhóm trong cùng 1 thời gian. Như vậy sắp lịch sao cho những nhóm nào có chung ít nhất một thành viên thì không thể họp cùng một thời điểm. Gọi mỗi nhóm là một đỉnh của đồ thị, những nhóm nào cùng chung ít nhất một thành viên thì tương ứng 2 đỉnh kề nhau, ví dụ như nhóm 1 và 2 cùng chung thành viên A thì đỉnh 1 và 2 kề nhau, ta biểu diễn đồ thị như hình 2.4 1 4 2 3 Đ X V Đ Hình 2.4 Ta có thể tô màu đồ thị như trên với X: xanh; Đ: đỏ; V: vàng. Từ đồ thị ta có lịch sắp xếp các cuộc họp như sau: Đợt họp Tên nhóm I 1 II 2, 3 III 4 Mỗi màu tương ứng cho 1 đợt họp, những nhóm được tô cùng màu có thể họp trong cùng một đợt. Chương 3 CHU TRÌNH, ĐƯỜNG ĐI EULER VÀ HAMILTON TRONG ĐỒ THỊ Lý thuyết về chu trình, đường đi Euler và Hamilton đã có từ lâu và được nghiên cứu nhiều. Ta có thể bắt gặp nhiều bài toán trong thực tiễn mà có thể sử dụng các lý thuyết về chu trình, đường đi Euler và Hamilton để giải quyết, ví dụ sử dụng lý thuyết đường đi, chu trình Euler để tìm hành trình đường đi cho người phát thư, cho xe rửa đường... sao cho hành trình là tối ưu nhất. Hoặc là trong một hệ thống mạng, một máy đơn cần gửi 1 thông điệp đến tất cả các máy còn lại vậy thì đường truyền tin sẽ đi như thế nào để cho hiệu quả nhất, bài toán này có thể được giải quyết bằng cách vận dụng các lý thuyết chu trình và đường đi Hamilton. I. CHU TRÌNH VÀ ĐƯỜNG ĐI EULER 1. Chu trình Euler 1.1 Định nghĩa Cho đồ thị vô hướng G = . Một chu trình trong đồ thị G được gọi là chu trình Euler nếu nó đi qua tất cả các cạnh của G và đi qua mỗi cạnh đúng một lần. Định lý 1: Đồ thị vô hướng G = có chu trình Euler khi và chỉ khi G là liên thông và bậc của tất cả các đỉnh trong đồ thị G là số chẵn. Chứng minh - Điều kiện cần: Giả sử đồ thị G = có chu trình Euler. Ta cần chứng minh G là đồ thị liên thông và với mỗi x Î X có m(x) = 2k với k là một số nguyên dương nào đó. Thật vậy, giả sử G = không liên thông hay G có ít nhất hai thành phần liên thông G1 = và G2 = . Trong đó X1 È X2 = X , U1 È U2 = U, giữa các đỉnh trong X1 và trong X2 không có cạnh hoặc đường nối với nhau. Giả sử w là 1 chu trình Euler trong G. Theo định nghĩa của chu trình Euler thì w là chu trình đi qua tất cả các cạnh trong G, mỗi cạnh đúng 1 lần. Nếu w có đỉnh chung với G1 = thì w là chu trình nằm gọn trong đồ thị G1. Điều này mâu thuẫn với định nghĩa của w. Chứng tỏ đồ thị G = là liên thông. Bây giờ ta chứng minh mỗi đỉnh x Î X trong G đều có bậc chẵn, tức là cần chỉ ra m(x) = 2k, với k Î {1,2,...}. Trước hết thấy rằng k ¹ 0 bởi vì nếu k = 0 thì x là điểm cô lập trong G, tức là G không liên thông, trái với điều đã chỉ ra. Giả sử ngược lại tồn tại một đỉnh xi Î X mà m(xi) là một số lẻ, chẳng hạn m(xi) = 3. Đối với xi có 3 cạnh đi vào nó, giả sử đó là các cạnh (xi, xk), (xi, xj) và (xi, x1) Î U. Chu trình Euler w sẽ đi qua 3 cạnh đó. Khi đó một trong 3 cạnh trên có ít nhất một cạnh mà chu trình Euler w đi qua 2 lần. Điều đó mâu thuẫn với định nghĩa của chu trình w. Vậy m(x) là một số chẵn với mọi x Î X. - Điều kiện đủ: Giả sử G = là đồ thị liên thông và mỗi đỉnh x Î X đều có bậc chẵn: m(x) = 2k, k Î {1, 2,...} ta chứng minh trong đồ thị G tồn tại một chu trình Euler. Với giả thiết trên, trước hết ta chứng minh rằng tại mỗi đỉnh của G có tồn tại chu trình đơn (tức là chu trình đi qua các cạnh, mỗi cạnh đúng một lần). Đề chứng minh điều đó, ta lưu ý rằng không thể có một đỉnh x mà m(x) = 2. Điều đó đúng bởi vì khi đó tại đỉnh x có khuyên và do đó x cũng là một đỉnh cô lập, trái với giả thiết đồ thị G là liên thông. Giả sử x Î X là một đỉnh nào đó. Ta chỉ ra có chu trình đơn P qua x. Do m(x) > 2 suy ra tồn tại các đỉnh x1 sao cho x1 ¹ x và x kề với x1. Do m(x1) > 2 suy ra tồn tại các đỉnh xi sao cho xi ¹ xi-1 và xi kề với xi-1. Khi tới bước thứ i thì ta đã có một đường đi tư x đến xi, qua các cạnh, mỗi cạnh đúng một lần. Quá trình trên không thể kéo dài vô hạn do tính hữu hạn của đồ thị G. Giả sử số bước hữu hạn đó là i. Điều này chứng tỏ x và xi kề nhau, tức là có cạnh nối x và xi. Điều đó là đúng vì bước i là bước cuối cùng. Như vậy tại đỉnh x có chu trình đơn P đi qua. Bây giờ ta chứng minh rằng trong đồ thị G = có chu trình Euler. Theo chứng minh trên với đỉnh x Î X có chu trình đơn đi qua là P1 và P1 là chu trình trong đồ thị G. Hãy "đánh dấu xoá" các cạnh trong P1. Nếu sau khi "đánh dấu xoá" các cạnh trên đường P1 tạo ra một số đỉnh cô lập mới thì hãy "đánh dấu loại bỏ" các đỉnh cô lập mới đó. Kết quả thu được sẽ là một đồ thị mới G1 = là đồ thị con của đồ thị G = đã cho. Ta chỉ ra đồ thị G1 thoả mãn một số tính chất sau: - Chu trình P1 trong đồ thị G và G1 có đỉnh chung, bởi vì G là đồ thị liên thông. - Đồ thị G1 gồm các đỉnh x Î X1 có bậc chẵn. Thật vậy, nếu x Î X1 mà x không thuộc các đỉnh trong P1 thì m(x1) hiển nhiên là một số chẵn. Còn nếu x1 Î X1 mà x1 là đỉnh thuộc P1 thì sau khi "đánh dấu bỏ " hai cạnh của P1 chứa đỉnh đó thì bậc của đỉnh x1 sẽ giảm đi 2 đơn vị, do đó m(x1) cũng là chẵn. Tóm lại với mọi x Î X1 thì m(x) là một số chẵn. Ta có thể minh hoạ đồ thị với chu trình đơn P1 và đồ thị con G1 như hình vẽ dưới đây: G1 = x x1 x1 là đỉnh chung giữa P1 và G1. Đối với G1 = tại đỉnh x1 Î X1 có tồn tại chu trình đơn P2 mà cách xây dựng P2 cũng đối với P1. Trong P2 bỏ tất cả các cạnh, giữ lại các đỉnh có cạnh hoặc đường nối với các đỉnh khác trong G1 ta được đồ thị con G2 = của G1. Đồ thị cũng có tính chất như G1, là liên thông, mọi x Î X2 đều có bậc chẵn và G2 và P2 có điểm chung chẳng hạn x2 G2 = x x1 x2 Do tính hữu hạn của đồ thịi G, quá trình xây dựng các chu trình đơn sẽ dừng lại ở bước thứ k nào đó. Như vậy, trước khi sang bước thứ k ta đã có k - 1 chu trình đơn P1, P2, ..., Pk-1 và đồ thị Gk-1 = là đồ thị con của đồ thị Gk-2 = . Đồ thị Gk-1 là liên thông và mọi đỉnh x Î Xk-1 có bậc chẵn, đồng thời Gk-1 và Pk-1 có điểm chung là xk. Vì quá trình trên dừng lại sau k bước nên đồ thị Gk-1 là một chu trình đơn qua xk và bao gồm hết các cạnh trong đồ thị Gk-1. Vì nếu không sẽ dẫn tới mâu thuẫn do k là bước cuối cùng. x x1 x2 xk-1 P1 P2 Pk-1 Gk-1= Pk xk Ghép các chu trình đơn P1, P2,...,Pk tại các đỉnh chung ta được tập các chu trình Euler trong đồ thị G = . Định lý được chứng minh. Định lý 2: Cho đồ thị có hướng G = G có chu trình Euler khi và chỉ khi G là liên thông và mỗi đỉnh đều có bậc vào bằng bậc ra. 1.2 Thuật toán tìm chu trình Euler Cho đồ thị G = xây dựng thuật toán tìm chu trình Euler Bước 1: Kiểm tra xem G có là đồ thị liên thông hay không. Nếu G là liên thông thì chuyển sang bước 2. Ngược lại thì thuật toán dừng và kết luận rằng đồ thị không có chu trình Euler Bước 2: Kiểm tra xem tất cả các đỉnh trong G đều có bậc chẵn hay không. Nếu tất cả các đỉnh đều có bậc là chẵn thì chuyển sang bước tiếp theo. Nếu không dừng lại và kết luận đồ thị đã cho không có chu trình Euler. Bước 3: Xây dựng các chu trình đơn trong G sao cho tất cả các cạnh của đồ thị đều có các chu trình đơn đi qua và mỗi cạnh chỉ đi qua một lần. Ghép các chu trình đơn như trên tại các đỉnh chung nhau ta được tập các chu trình Euler cần tìm. 2. Đường đi Euler 2.1 Định nghĩa Đường Euler trong đồ thị G = là đường đi qua tất cả các cạnh của đồ thị, mỗi cạnh đi qua đúng một lần. Đinh lý 3: Cho G = là đồ thị vô hướng liên thông. Điều kiện cần và đủ để đồ thị có đường Euler là số đỉnh bậc lẻ trong đồ thị là 0 hoặc 2. Chứng minh: Trường hợp số đỉnh bậc lẻ bằng 0 thì G là đồ thị liên thông và mọi đỉnh đều có bậc chẵn. Theo định lý về chu trình Euler thì trong G có chu trình Euler, tức cũng là đường Euler. Nếu số đỉnh bậc lẻ là 2, chẳng hạn đó là các đinh x1 và x2. Hãy thêm vào một đỉnh mới x và hai cạnh (x, x1) và (x, x2) vào đồ thị G = . Ta có đồ thị mới G' = , ở đây X' = X È {x}, U' = U È {(x, x1), (x, x2)}. Rõ ràng là G' liên thông và mọi đỉnh đều có bậc chẵn. Theo định lý về chu trình Euler đã nêu ở trên thì trong G' có tồn tại chu trình Euler, cũng là đường Euler. Định lý 4: Cho đồ thị có hướng G = , điều kiện cần và đủ để có đường đi Euler từ x đến y (x, y Î X) là G liên thông và đỉnh x có bậc ra lớn hơn bậc vào 1 đơn vị, đỉnh y có bậc vào lớn hơn bậc ra 1 đơn vị, còn tất cả các đỉnh khác đều có bậc vào bằng bậc ra. 2.2 Thuật toán tìm đường Euler Bước 1: Kiểm tra xem đồ thị G có liên thông hay không. Nếu có thì chuyển sang bước 2. Ngược lại, thì dừng thuật toán và khẳng định rằng không có đường Euler. Bước 2: Kiểm tra xem mọi đỉnh trong G đều có bậc chẵn hay không. Nếu có chuyển sang bước 4. Nếu không chuyển sang bước 3. Bước 3: Kiểm tra xem số đỉnh bậc lẻ có bằng 2 hay không. Nếu có chuyển sang bước 4. Nếu không thì dừng lại và kết luận không có đường Euler. Bước 4: Xây dựng đường Euler trong G. II. CHU TRÌNH VÀ ĐƯỜNG ĐI HAMILTON 1. Chu trình Hamilton Định nghĩa: Giả sử G = là đồ thị vô hướng. Chu trình Hamilton là chu trình đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần. Định lý 1: Nếu đơn đồ thị liên thông G = , n đỉnh và n ³ 3 có bậc ở mỗi đỉnh không nhỏ hơn nửa số đỉnh của đồ thị, tức là mọi x Î X ta luôn có m(x) ³ n/2 thì trong đồ thị có tồn tại chu trình Hamilton. Chứng minh: Ta chứng minh định lý bằng phản chứng a b c d k g e h Giả sử G = có n đỉnh là đồ thị không có chu trình Hamilton. Ta thêm vào một số đỉnh mới và nối mỗi đỉnh mới này với mọi đỉnh của G, ta được đồ thị G'. Giả sử có số k > 0 là số tối thiểu các đỉnh cần thiết để G' chứa một chu trình Hamilton. Như vậy G' có n + k đỉnh. a y b a' b' a) b) Hình 2.1 Gọi P là chu trình Hamilton ayb...a trong G', trong đó a và b là các đỉnh của G, còn y là một trong các đỉnh mới. Thế thì b không kề với a, vì nếu trái lại thì ta có thể bỏ đỉnh y và được chu trình ab...a, mâu thuẫn với giả thiết về tính chất tối thiểu của k. Hơn nữa nếu a' là một đỉnh kề nào đó của a (khác với y) và b' là đỉnh nối tiếp ngay a' trong chu trình P (hình 2.1.b) thì b' không thể là đỉnh kề của b (nếu trái lại thì ta có thể thay P bởi chu trình aa'..bb'..a, trong đó không có y). Như vậy, với mỗi đỉnh kề với a ta có một đỉnh không kề với b, tức là số đỉnh không kề với b không thể ít hơn số đỉnh kề với a (số đỉnh kề với a không nhỏ hơn n/2 + k). Mặt khác, theo giả thiết, số đỉnh kề với b cũng không nhỏ hơn n/2 + k. Vì không có đỉnh nào vừa kề với b lại vừa không kề với b, nên số đỉnh của G' không ít hơn 2.(n/2 + k) = n + 2k, mâu thuẫn với giả thiết là số đỉnh của G' bằng n + k, (k > 0). Định lý được chứng minh. Ví dụ: Đồ thị trong hình 2.1.a có 8 đỉnh, đỉnh nào cũng có bậc 4. Vậy G có chu trình Hamilton. Có thể thấy một chu trình Hamilton a-g-c-k-d-h-b-e-a. 2. Đường Hamilton Định nghĩa: Đường Hamilton trong đồ thị G = là đường đi qua tất cả các đỉnh mỗi đỉnh đúng một lần. Định lý 2: Giả sử G = là đồ thị có hướng và đầy đủ khi đó trong đồ thị luôn tồn tại đường Hamilton. Chứng minh: Giả sử w = xi1 xi2 ... xik xik+1 .. xim - 1 xim là một đường sơ cấp bất kỳ trong đồ thị. Để đơn giản, ta chỉ viết các đỉnh mà không có các cạnh xen kẽ như định nghĩa. Nếu trong đường sơ cấp w mà tất cả các đỉnh trong X đều có mặt thì chính w là đường Hamilton. Còn nếu có những đỉnh trong X nhưng chưa có mặt trong w thì ta có thể bổ sung hết những đỉnh đó vào đường w sơ cấp để nó trở thành đường Hamilton theo nguyên tắc sau đây: Giả sử x Î X mà x không nằm trên đường sơ cấp w. Các trường hợp sau đây xảy ra do tính đầy đủ của đồ thị G: - Nếu x có cung tới xi1 thì bổ sung x vào đầu w và nó có dạng: x xi1 xi2 ... xik xik+1 .. xim - 1 xim - Nếu từ xik có cung tới x và từ x có cung tới xik+1 thì ta bổ sung x vào giữa hai đỉnh xik và xik+1. Khi đó w có dạng: xi1 xi2 ... xik x xik+1 .. xim - 1 xim - Nếu từ xik và xik+1 có cung đi tới x và từ x lại cung đi tới xik+2 thì ta bổ sung x vào giữa hai đỉnh xik + 1 và xik+2 ta được w có dạng: xi1 xi2 ... xik xik+1 x xik + 2 .. xim - 1 xim - Nếu mọi k Î [1, m - 1] mà từ xik và xik+1 có cung sang x thì ta bổ sung x vào cuối, khi đó nó có dạng: xi1 xi2 ... xik xik+1 x xik + 2 .. xim - 1 xim x Bằng cách đó ta có thể bổ sung vào w các đỉnh trong đồ thị mà chưa có mặt trong w để nó trở thành đường Hamilton. Định lý được chứng minh. Hệ quả: Giả sử G = là đồ thị đầy đủ có số đỉnh n ³ 3. Khi đó trong đồ thị luôn luôn tồn tại chu trình Hamilton. 4 1 3 2 2 1 3 4 5 6 a) b) Hình 2.2 Ví dụ đồ thị trong hình 2.2.a có chu trình Hamilton nhưng nó không phải là đồ thị đầy đủ. Còn đồ thị hình 2.2.b không có đường Hamilton. 3. Thuật toán liệt kê tất cả các chu trình Hamilton Thuật toán được xây dựng dựa trên cơ sở thuật toán quay lui cho phép liệt kê tất cả các chu trình Hamilton của đồ thị Procedure Hamilton(k); {Liệt kê các chu trình Hamilton thu được bằng việc phát triển dãy đỉnh x[1], ..., x[k-1] của đồ thị G = cho bởi danh sách kề Ke(v), v Î X } Begin For y Î Ke(x[k-1]) do if (k = n +1) and (y = v0) then GhiNhan(x[1],....,x[n],v0) Else if ChuaXet[y] then Begin x[k] := y; ChuaXet[y] := False; Hamilton(k+1); ChuaXet[y] := True; End; End; BEGIN For v Î X do ChuaXet[v] := True; x[1] := v0; {v0 là một đỉnh nào đó của đồ thị} ChuaXet[v0] := False; Hamilton(2); END. Chương 4 ĐƯỜNG ĐI NGẮN NHẤT TRONG ĐỒ THỊ Giới thiệu: Trong các ứng dụng thực tế bài toán tìm đường đi ngắn nhất giữa hai đỉnh của một đồ thị liên thông có ý nghĩa rất lớn. Bài toán tìm đường đi ngắn nhất được ứng dụng trong thực tế như để chọn một hành trình tiết kiệm nhất (về thời gian hoặc chi phí) trên một mạng giao thông đường thuỷ, đường bộ hoặc đường không. Bài toán lập lịch thi công các công đoạn trong một công trình thi công lớn. Bài toán lựa chọn đường truyền tin với chi phí nhỏ nhất trong mạng thông tin... Dùng thuật giải đường đi ngắn nhất trong đồ thị giải quyết bài toán sửa gói tin sai trong việc truyền tin... dưới đây ta xét một số thuật toán để tìm đường đi ngắn nhất trong đồ thị có trọng số và đồ thị không có trọng số. I. ĐƯỜNG ĐI NGẮN NHẤT TRONG ĐỒ THỊ KHÔNG CÓ TRỌNG SỐ 1. Định nghĩa: Đồ thị không có trọng số là đồ thị hữu hạn trên các cạnh không có trọng số. Bài toán tìm đường đi ngắn nhất giữa hai đỉnh a,b trong đồ thị không có trọng số G = là tìm đường đi giữa hai đỉnh a, b sao cho có số các cạnh (cung) là ít nhất. 2. Thuật toán: Bước 1: Tại đỉnh a ta ghi số 0 Các đỉnh có cạnh đi từ đỉnh a đến ta ghi số 1. Giả sử ta đã ghi tới i, tức là ta đã đánh số được các tập đỉnh là A(0) = {a}, A(1), A(2), ... , A(i) trong đó A(i) là tập tất cả các đỉnh được ghi bởi số i. Ta xác định tập đỉnh được đánh số bởi số i + 1 là A(i+1) = {x / x Î X, x Ï A(k) với k = 0, ...,i và tồn tại y Î A(i) sao cho từ y có cạnh (cung) tới x}. Do tính hữu hạn của đồ thị, sau một số hữu hạn các bước, thuật toán dừng lại và cho kết quả là tập các đỉnh có chứa b được đánh số bởi m là A(m). Bước 2: Do bước 1 thì đỉnh b được đánh số bởi m, điều này chứng tỏ đường đi từ a đến b có m cạnh (cung) và là đường ngắn nhất đi từ a đến b. Để tìm tất cả các đường có độ dài m ngắn nhất đi từ a đến b, ta xuất phát từ b đi ngược về a theo đúng nguyên tắc sau đây: - Tìm tất cả các đỉnh có cạnh (cung) tới b được ghi số m - 1, giả sử đó là xik (k = 1, 2,...). - Với mỗi đỉnh xik tìm tất cả các đỉnh có cạnh (cung) với xik (k = 1, 2, ...) được ghi số m -2. x1 x2 x3 x4 x7 x8 x9 x10 x6 x5 b a 0 1 2 3 3 3 2 1 1 2 Bằng cách lùi dần trở lại, đến một lúc nào đó gặp đỉnh ghi số 0, đó chính là đỉnh a. Tất cả các đường xác định theo các bước trên là đường đi từ a đến b có độ dài ngắn nhất là m cần tìm. Hình 1.1 Ví dụ đồ thị như hình 1.1 xây dựng đường đi ngắn nhất theo thuật toán trên: Bước 1: Đỉnh a được đánh số 0 và có A(0) = {a} A(1) = {x1, x6, x7} A(2) = {x2, x5, x8} A(3) = {x3, b, x9} Bước 2: Từ bước 1 ta có b Î A(3) nên từ a đến b là đường đi ngắn nhất có 3 cung. Tiếp theo ta xác định tất cả các đường đi ngắn nhất có độ dài 3: Đỉnh có cung về b được đánh số 2 là x5 Đỉnh có cung tới x5 được đánh số 1 là x6 Đỉnh có cung về x6 được đánh số 0 là a Vậy đường cần tìm là a - x6 - x5 - b. II. ĐƯỜNG ĐI NGẮN NHẤT TRONG ĐỒ THỊ CÓ TRỌNG SỐ 1. Các khái niệm Cho đồ thị hữu hạn G = với mỗi cạnh u Î U ta đặt tương ứng với số dương l(u) gọi là trọng số của u. Đồ thị có cạnh như trên được gọi là đồ thị có trọng số. Gọi a là một đường đi nào đó trong G = Giả sử a = xi1ui1xi2ui2 ... xin - 1uin-1xin, xij Î X , uij Î U (j = 1, 2, ...,n). Khi đó ký hiệu gọi là trọng số của đường a Ta ký hiệu D(a,b) là tập tất cả các đường đi nối đỉnh a với đỉnh b trong đồ thị G. Đường đi a giữa a và b là ngắn nhất nếu a thoả mãn l(a) = min {l(b) / b Î D(a,b)} Bài toán: Cho đơn đồ thị G = liên thông có trọng số, và a, b Î X. Tìm các đường đi ngắn nhất giữa 2 đỉnh a, b. 2. Thuật toán tìm đường đi ngắn nhất cho đồ thị có trọng số 2.1 Cơ sở thuật toán tìm đường đi ngắn nhất Cho G = tìm đường đi ngắn nhất từ đỉnh a tới đỉnh b Với x Î X nếu độ dài đường đi từ đỉnh xuất phát tới đỉnh x có trọng số là l(a) thì s(x) = l(a) gọi là trọng số của đỉnh x. Cơ sở của tất cả các thuật toán tìm đường đi ngắn nhất là xác định được các trọng số nhỏ nhất cho tất cả các đỉnh từ đó tìm đường đi ngắn nhất. Bước 1: Đánh trọng số các đỉnh, trọng số của đỉnh xuất phát là s(a) = 0. Tại các đỉnh còn lại ta ghi một số dương nào đó sao cho nó đủ lớn hơn trọng số của các đỉnh từ a tới. Bước 2: Thực hiện việc giảm trọng số các đỉnh. Giả sử tại đỉnh x được ghi trọng số s(x). Nếu tồn tại đỉnh y có trọng số s(y) từ y sang x mà s(x) > s(y) + l(y, x) thì ta thay trọng số của s(x) bởi trọng số s'(x) = s(y) + l(y, x). Trường hợp s(x) đạt cực tiểu, tức là x Î X không tồn tại y Î X kề với x mà s(y) + l(y, x) < s(x). Bước 3: Xác định đường từ a đến b có trọng số ít nhất. Từ bước 3 ta xác định được trọng số của đỉnh b. Xuất phát từ b đi về đỉnh kề với b, chẳng hạn đó là đỉnh xin có tính chất s(b) = s(x) + l(xin, b). Nếu không có đỉnh kề với xin như vậy thì ta đi về đỉnh kề với b có trọng số cạnh (cung) từ đỉnh đó về b là ít nhất. Từ đỉnh xin ta đi ngược về đỉnh xin-1 có tính chất s(xin) = s(in-1) + l(xin-1, xin) nếu không đi về đỉnh kề với xin mà trọng số cạnh (cung) giữa chúng là ít nhất. Bằng cách đó ta sẽ đi về đỉnh xi1 mà đỉnh kề là a sao cho s(xi1) = s(a) + l(a, xi1) = l(a, xi1) với s(a) = 0. Đường a = axi1xi2 ... xin - 1xinb là đường đi từ a đến b có trọng số ít nhất trong số tất cả các đường từ a đến b. Thật vậy l(a) = l(a,xi1) + l(xi1,xi2) + ... + l(xin-1,xin) + l(xin,b) = [s(xi1)- s(a)] + [s(xi2) - s(xi1)] + ... + [s(xin) - s(xin-1)] + [s(b) - s(xin)] = s(b) (1) Giả sử b Î D(a, b) là 1 đường bất kỳ từ a đến b và có dạng: b = aj1xj2 ... xjk-1xjkb. Theo bước 2 ta có bất đẳng thức sau: l(a, xj1) ³ s(xj1) - s(a) = s(xj1) l(xj1, xj2) ³ s(xj2) - s(xj1) ..................................... l(xjk-1,xjk) ³ s(xjk) - s(xjk-1) l(xjk, b) ³ s(b) - s(xjk) Cộng 2 vế ta có: l(b) = l(a, xj1) + l(xj1, xj2) + ... + l(xjn-1, xjk) + l(xjk, b) ³ s(b) (2) So sánh (1) và (2) ta có: l(a) = min{ l(b) / b Î D(a, b)} 2.2 Thuật toán Dijkstra Có thể khái quát thuật toán bằng thủ tục sau: Procedure Dijikstra(G: đồ thị liên thông có trọng số dương)} {G: có các đỉnh a = v0, v1, ..., vn = b và trọng số l(vi, vj) = ¥ nếu (vi, vj) Ï U của G} For i:=1 to n s(vi) := ¥; s(a) := 0; S := f {ban đầu các trọng số được khởi tạo sao cho trọng số của a = 0, còn các đỉnh khác bằng ¥, tập S rỗng} While b Ï S Begin u:= đỉnh không thuộc S có s(u) nhỏ nhất; S := S È {u}; For tất cả các đỉnh v không thuộc S if s(u) + l(u,v) < s(v) then s(v) := s(u) + l(u,v) {thêm vào S đỉnh có trọng số nhỏ nhất và sửa đổi trọng số của các đỉnh không thuộc S} End; {l(a) = l(a, b) = độ dài đường đi ngắn nhất từ a đến b} Độ phức tạp của thuật toán là O(n2), tức là phải dùng O(n2) phép cộng và so sánh đường đi ngắn nhất giữa 2 đỉnh trong đồ thị đơn vô hướng liên thông có trọng số. 2.3 Thuật toán Ford - Bellman Khác với thuật toán Dijkstra xác định các trọng số bé nhất của tất cả các đỉnh bằng cách "nổi bọt" dần các trọng số bé nhất, mỗi lần trọng số bé nhất được tìm thấy thì lấy nó làm hạt nhân để điều chỉnh và xác lập các trọng số cho các đỉnh khác, còn thuật toán Ford - Bellman xác định các trọng số nhỏ nhất cho tất cả các đỉnh bằng cách duyệt tất cả các đỉnh, trọng số nhỏ nhất của một đỉnh được xác lập là sau một số lần hữu hạn điều chỉnh nhờ các vòng lặp. Thuật toán được mô tả bằng thủ tục sau: Procedure Ford_Bellman; {Input: Đồ thị có hướng G = n đỉnh, a Î X là đỉnh xuất phát. t(i, j) với i, j Î X là ma trận trọng số Output: Với x Î X tìm các s(x) bé nhất và Truoc(x) để ghi nhận đỉnh đi trước x trong các đường đi ngắn nhất từ a đến x. } Begin {Khởi tạo} For x Î X do Begin s(x) := t[a, x]; Truoc[x] := a; End; s(a) := 0; For k:=1 to n - 2 do For x Î X \ {a} do For y Î X do if s(x) > s(y) + t[y, x] then begin s(x) := s(y) + t[y, x]; Truoc(x) := y; End; End; Độ phức tạp của thuật toán là O(n3) chúng ta có thể chấm dứt vòng lặp theo k khi phát hiện trong quá trình thực hiện 2 vòng lặp trong không có biến d[u] nào bị thay đổi giá trị. Đối với những đồ thị có số cạnh m thoả mãn m < 6.n thì tốt hơn là sử dụng danh sách kề để biểu diễn đồ thị, khi đó vòng lặp theo y cần viết dưới dạng For tất cả các đỉnh y kề với x do if s(x) > s(y) + t[y, x] then begin s(x) := s(y) + t[y, x]; Truoc(x) := y; End; Trong trường hợp này thuật toán có độ phức tạp là O(n.m). 2.4 Thuật toán Floyd. Trong nhiều trường hợp ta cần xác định đường đi ngắn nhất giữa tất cả các cặp đỉnh, với bài toán này có thể giải bằng cách sử dụng n lần thuật toán thuật toán Ford_bellman trong đó ta sẽ chọn s lần lượt là các đỉnh của đồ thị cách làm này không phải là cách làm tốt nhất ở đây, ta sẽ trình bày thuật toán để giải quyết bài toán này trên đó là thuật toán Floyd. Thuật toán được trình bày khái quát ở dạng thủ tục sau: Procedure Floyd; { Input: đồ thị cho bởi ma trận trọng số a[i,j], i,j = 1,2,...,n; Output: Ma trận đường đi ngắn nhất giữa tất cả các cặp đỉnh. d[i,j], i,j = 1,2,...n. Trong đó d[i,j] cho độ dài ngắn nhất từ i đến j Ma trận ghi nhận đường đi p[i,j] ghi nhận đường đi trước đỉnh j} Begin For i:=1 to n do For j:=1 to n do Begin d[i,j] := a[i,j] p[i,j] := i; End; For k:=1 to n do For i:=1 to n do For j:=1 to n do if d[i,j] > d[j,k] + d[k,j] then Begin d[i, j] := d[i, k] + d[k,j]; p[i,j] := p[k,j]; End; End; III. CÁC VÍ DỤ ỨNG DỤNG 1. Ứng dụng trong truyền tin Truyền tin trong mạng thường hay gặp sự cố dẫn đến các gói tin có thể bị sai lệch, để phát hiện và sửa chữa các bít sai khôi phục lại gói tin người ta đã tiến hành 1 số cách thức. Có cách thức đó là mã hoá dữ liệu trước khi truyền, nhờ cơ chế mã hoá mà những gói tin sai có thể sửa đúng lại được. Thực hiện điều này, người ta đã dùng máy hữu hạn trạng thái để mã hoá dữ liệu. A B C 00(0) 11(0) 00(1) 01(0) 11(1) Ta xét 1 ôtômát hữu hạn của máy mã hoá dữ liệu cho những gói tin 4 bít như hình 3.1: Hình 3.1 Giả sử cần mã hoá gói tin nhị phân x = 0100; Thì ta đi như sau: A, A, C, B, A với nhãn đặt trong trong dấu ngoặc ta thu được gói tin x = 0100 với nhãn đặt ngoài dấu ngoặc tướng ứng thì ta thu được bản mã của x là 00 11 01 11, bản mã này dài 8 bít. Để tiện minh hoạ, ôtômát thiết kế như trên là đơn giản dẫn đến chưa đầy đủ, vì giả sử có gói tin là x = 1111, ôtômát sẽ không mã hoá được. Để thực hiện được việc sửa sai gói tin, 1 giải thuật gọi là Viterbi được tiến hành như sau: - Thay vì bản mã là 8 bít ta xây dựng bản mã có độ dài là 12 bít bẳng cách xuất phát từ trạng thái ban đầu A đi một chu trình có độ dài 6. Khi đó lúc giải mã ta chỉ giải mã 8 bít đầu bỏ đi 4 bit cuối. - Từ ôtômát xây dựng đồ thị có hướng biểu diễn tất cả các khả năng mã hoá độ dài 12 của gói tin 4 bit như sau: A B C 1 2 3 4 5 6 0 00 11 01 11 00 00 00 00 00 00 11 11 11 11 11 00 01 01 01 01 Hình 3.2 Mỗi cạnh nét đứt biểu thị số 0, cạnh nét liền là số 1, ví dụ với gói tin x = 0100 để mã hoá 12 bit thì đi theo chu trình trong ôtômát là A, A, C, B, A, A, A thì tương ứng đi trong đồ thị là A0, A1, C2, B3, A4, A5, A6 thì bản mã là 001100110000. Gọi d(a, b) là số bit sai khác nhau giữa 2 chuỗi nhị phân a và b cùng độ dài, nếu x, y, z là những chuỗi bít nhị phân cùng độ dài n, thì thoả các tính chất sau: i) d(x, y) ³ 0 ii) d(x, y) = 0 Û x = y iii) d(x, y) + d(y, z) ³ d(x, z) i) và ii) hiển nhiên bây giờ ta chứng minh iii) Đặt x = x1, x2, ..., xn với xi (i = 1..n) là những bit, xi = 0 hoặc 1 tương tự đặt y = y1, y2, ..., yn và z = z1, z2, ..., zn a) Xét trường hợp n = 1, tức các chuỗi chỉ có 1 bit ta có - Nếu d(x1, y1) = 1 và d(y1, z1) = 1 thì d(x1, z1) = 0 hoặc 1 dẫn đến d(x1, y1) + d(y1, z1) = 2 luôn lớn d(x1, z1) - Nếu d(x1, y1) = 1 và d(y1, z1) = 0 thì y1 = z1 nên d(x1, z1) = 1 hoặc d(x1, y1) = 0 và d(y1, z1) = 1 thì x1 = y1 nên d(x1, z1) = 1 hoặc d(x1, y1) = 0 và d(y1, z1) = 0 thì x1 = y1 = z1 nên d(x1, z1) = 0 tất cả các trường hợp đều có d(x1, y1) + d(y1, z1) = d(x1, z1) Kết luận d(xi, yi) + d(yi, zi) ³ d(xi, zi) với i = 1..n b) Xét trường hợp n > 1 Ta thấy d(x, y) = d(x1, y1) + d(x2, y2) + ... + d(xn, yn) d(y, z) = d(y1, z1) + d(y2, z2) + ... + d(yn, zn) d(x, z) = d(x1, z1) + d(x2, z2) + ... + d(xn, zn) mà d(xi, yi) + d(yi, zi) ³ d(xi, zi) với i = 1.. n ta cắt lát theo chiều dọc suy điều phải chứng minh. Nhận xét rằng ôtômát như hình 3.1 được thiết kế với mục đích chỉ sửa sai với những bản mã có sai sót không quá 2 bit. Giả sử a, b là 2 bản mã 12 bit bất kỳ của ôtômát, ôtômát cũng được thiết kế sao cho d(a, b) ³ 5 (ta có thể kiểm chứng điều này). Giả sử x là bản mã 12 bít do ôtômát tạo ra nhưng khi truyền đi thì bị sai sót không quá 2 bit, cách sửa đúng lại x như sau: Gọi U là tập các chuỗi mã 12 bit ra ôtômát tạo ra khi đó a Î U là bản mã gốc của x nếu d(x, a) = min{d(x, b) /b Î U} khi đó a là duy nhất, không thể tồn tại mã b sao cho d(a, x) = d(x, b) vì theo trên d(a, b) ³ 5 và d(a, x) + d(x, b) ³ d(a, b) mà d(a, x) £ 2 suy ra d(x, b) > 2. Như vậy đường đi từ đỉnh A0 đến A6 tương ứng với đoạn mã a trong đồ thị hình 3.2 là đường đi có độ dài nhỏ nhất, mà trọng số của mỗi cung là số bit sai khác với từng cặp 2 bit trong x, để rõ hơn ta xét ví dụ: Giả sử nhận được bản tin bị sai không quá 2 bit x = 10 01 00 01 11 10 khi đó ta đánh trọng số cho mỗi cung cho đồ thị như hình 3.3 A B C 1 2 3 4 5 6 0 1 1 0 2 0 1 0 1 2 1 1 2 1 1 0 1 1 0 1 1 Hình 3.3 Cách đánh trọng số mỗi cung như sau, ở cặp 2 bit thứ nhất của x là 10 thì tương ứng với những cung thứ nhất của tất cả đường đi là A0A1 = 00; A0C1 = 11 và có số bit sai khác lần lượt là 1, 1, đây cũng là trọng số của cung tương ứng. Tương tự ở cặp 2 bit thứ hai của x là 01 thì tương ứng những cung thứ hai của tất cả đường đi là A1A2 = 00; A1C2 =11; C1B2 = 01 và có số bít sai khác lần lượt là 1, 1, 0. Tương tự ta tiếp tục đánh trọng số như thế... Nhận thấy đường đi ngắn nhất của đồ thị hình 3.3 là A0C1B2C3B4A5A6 Vậy đoạn mã tương ứng là 11 01 00 01 11 00, đây cũng là đoạn mã đúng của x và giải mã ta thu được gói tin được truyền là 1010. 2. Ứng dụng trong việc lập lịch thi công của một công trình Ta có thể mở rộng bài toán tìm đường đi ngắn nhất là bài toán tìm đường đi dài nhất. Với bài toán này chỉ có một điểm khác duy nhất là thay vì tìm trọng số nhỏ nhất là tìm trọng số lớn nhất cho các đỉnh. Đồ thị có nhiều ứng dụng trong vấn đề lập lịch, với bài toán toán tìm đường đi dài nhất ta sẽ đề cập tới một ứng dụng của nó về lập lịch đó sơ đồ mạng PERT. Sơ đồ mạng PERT (Project Evaluation and Review Technique) là sự sắp xếp lịch về một dự án công trình, nó được ứng dụng rộng rãi và đem lại nhiều hiệu quả trong việc thi công các công trình. Một công trình thi công được chia làm nhiều công việc, có một số công việc mà việc thực hiện nó chỉ được tiến hành sau khi một số công việc nào đó đã hoàn thành. Sơ đồ PERT được thể hiện bằng 1 đồ thị có hướng và mỗi cung trên đồ thị biểu diễn một công việc. Trên cung có đặt thời gian thực hiện công việc, mỗi đỉnh là bắt đầu hoặc kết thúc của một hay nhiều công việc. a) Xây dựng sơ đồ PERT Giả sử sơ đồ PERT là một đồ thị có hướng G = ta tiến hành xây dựng như sau: Với (i, j) Î U là 1 cung biểu diễn 1 công việc thì tij là thời gian thực hiện công việc đó, tij là trọng số cho cung (i, j). Mỗi một đỉnh là một hình tròn gồm 4 thành phần như hình vẽ sau tđ Di tmi tsi Trong đó: 1) tđ: là tên đỉnh, mỗi tên đỉnh là một con số và được xác định như sau: - Đánh số 0 cho đỉnh khởi công (Chỉ có cung đi ra) - Sau khi 1 đỉnh được đánh số thì xoá các cung đi ra từ đỉnh đó - Đánh số tiếp theo cho đỉnh chỉ có cung đi ra (nếu có nhiều đỉnh như vậy thì lấy tuỳ ý một đỉnh). - Tiếp tục như vậy cho đến khi hết các đỉnh, đỉnh cuối gọi là đỉnh kết thúc. 2) tsi: là thời gian sớm nhất có thể bắt đầu sự kiện thứ i (tại đỉnh thứ i) Tại đỉnh khởi công ts0 = 0 tại đỉnh thứ i: tsi = max{tsj + tji} 3) tmi : là thời gian muộn nhất để bắt đầu sự kiện i mà không ảnh hưởng thời gian rhực hiện cả công trình. Sau khi xác định tất cả các tsi thì các tmi được xác định từ đỉnh kết thúc quay về đỉnh khởi công như sau: tại đỉnh n là đỉnh kết thúc thì tmn = tsn tại đỉnh thứ i tmi = min{tmj - tij} 4) Di : là thời gian dự trữ sự kiện thứ i Di = tmi = tsi b) Tìm đường găng Đặt Dij = (tmj - tsi) - tij là thời gian dự trữ của công việc (i, j) Công việc có Dij = 0 là công việc găng, đường găng là một đường đi từ đỉnh khởi công đến đỉnh kết thúc sao cho nó chỉ đi qua các cung biểu thị công việc găng. Như vậy đường găng cũng là đường đi dài nhất từ đỉnh khởi công đến đỉnh kết thúc, việc tìm đường găng cũng là bài toán tìm đường đi dài nhất với đỉnh gốc là đỉnh khởi công, đỉnh đích là đỉnh kết thúc. Nhận xét: Với việc xây dựng sơ đồ PERT cho một dự án thi công ta thấy những việc có thời gian dự trữ là dương là việc có thể làm chậm mà không ảnh hưởng tới tiến độ, những việc găng là việc không thể kéo dài. Muốn rút ngắn thời gian thực hiện công trình thì phải tập trung cào các việc găng. Sơ đồ PERT thuận tiện cho việc quản lý vì nói chung không phải vẽ lại sơ đồ, nếu có phát sinh việc phụ thì thêm vào các cung mới hoặc điều chỉnh thời gian trên các cung. Trên sơ đồ nay có thể giải quyết 2 loại bài toán Bài toán 1: Với điều kiện nhân vật lực và trang thiết bị hiện có cần bố trí thời gian thực hiện công trình là ngắn nhất. Bài toán 2: Với điều kiện thời gian hoàn thành công trình cho trước cần tính toán việc thuê nhân công và sử dụng trang thiết bị sao cho chi phí xây dựng là nhỏ nhất. Ví dụ cho một bảng các công việc như sau: STT Công việc Làm sau việc Thời gian 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 a b c d e f g h k l m n p q r s t u Làm ngay Làm ngay Làm ngay c a b, a b, d, e b, d, e b, d, e c k, l h, m f, g, n h, m h, m k, l r, s p,q 12 8 7 9 6 14 15 15 11 18 9 4 8 16 23 14 12 14 Sơ đồ PERT cho lịch các công việc ở bảng trên được biểu diễn như hình 3.4 1 12 0 12 3 18 0 18 2 9 2 7 5 38 0 38 6 51 9 42 4 29 0 29 7 59 5 54 8 61 0 61 0 0 0 0 73 0 73 9 a, 12 b, 8 c, 7 e, 6 f, 14 p, 8 g, 15 h, 15 l, 18 k, 11 m, 9 s, 14 r, 23 q, 16 u, 14 t, 12 d, 9 n, 4 Hình 3.4 Đường găng là đường có các cung được tô đậm, như vậy những việc găng là a, e, k, m, r, t. * Sơ đồ PERT là 1 dạng đồ thị mà thường được gọi là đồ thị có ưu tiên trước sau ta có thể xét thêm một ví dụ ứng dụng của loại đồ thị này như sau: Giả sử máy tính thi hành một chương trình nào đó, các câu lệnh có thể được xử lý đồng thời. Nhưng điều quan trọng là không được thực hiện một câu lệnh mà đòi hỏi kết quả của câu lệnh khác khi mà các câu lệnh này chưa được thực hiện xong. Sự phụ thuộc các câu lệnh này vào các câu lệnh khác có thể mô tả bẳng đồ thị có hướng, khi đó mỗi cạnh là quá trình thực hiện một câu lệnh, mỗi đỉnh là một sự kiện, sự kiện này biểu hiện việc một số các câu lệnh đã thực hiện xong và đã có kết quả. Ví dụ giả sử máy tính cần thực hiện một số câu lệnh a, b, c, d, e, l... Trong đó các câu lệnh a, b, c được thực thi trước tiên và đồng thời, các lệnh d, l chỉ được thực hiện khi đã kết quả do lệnh c mang lại, lệnh e không thể thực hiện trước khi lệnh a được thực hiện xong v.v. Ta có thể lấy đồ thị ở hình 3.4 để minh hoạ cho ví dụ này. IV. CHƯƠNG TRÌNH MÔ TẢ THUẬT TOÁN DIJKSTRA TÌM ĐƯỜNG ĐI NGẮN NHẤT Const Max = 7; Var a: Array[1..Max, 1..Max] Of Integer; n,s,t: Integer; d, Truoc : Array[1..Max] Of Integer; MinOk : Array[1..Max] of Boolean; Procedure NhapSoLieu; Var f: Text; Fname: String; i,j: Integer; Begin Write('Vao ten file du lieu can doc: '); Readln(Fname); Assign(f,Fname); Reset(f); Readln(f,n); For i:=1 to n do For j:=1 to n do Read(f,a[i,j]); Close(f); End; Procedure InSoLieu; Var i,j: Integer; Begin Writeln('So dinh cua do thi: ',n); Writeln(' Ma tran khoang cach: '); For i:=1 to n do Begin For j:=1 to n do Write(a[i,j]:3,' '); Writeln; End; End; Procedure Dijkstra; Var u,v,Mind: Integer; Begin Writeln('Find the minimum way from "s" to "t"'); Write(' s = '); Readln(s); Write(' t = '); Readln(t); For v:=1 to n do Begin {Khoi tao cac gia tri} d[v] := MaxInt; { Khoi tao cac d(s,v)} MinOk[v]:= False; Truoc[v]:=n +1; End; d[s]:=0; MinOk[s]:=True; u:=s; {Buoc dau dinh goc la hat nhat cho dieu chinh} While not MinOk[t] do Begin {Tim duong di ngan nhat} {Xac lap va dieu chinh d(s,u)} For v:=1 to n do if not MinOk[v] then if (a[u,v]0) and (d[u] + a[u,v] < d[v]) Then Begin d[v] := d[u] + a[u,v]; Truoc[v]:= u; {Nho duong di ngan nhat} End; {Tim dinh u co d(s,u) la min} Mind:=MaxInt; For v:=1 to n do If (not MinOk[v]) And (Mind>d[v]) then Begin Mind := d[v]; u:= v; End; MinOk[u] := True; If Mind = MaxInt then Break; {Tac duong} End; End; Procedure Result; Var i: Integer; Begin Writeln('Duong di ngan nhat tu ',s,' Den ',t); i:=Truoc[t]; If i = n + 1 then Begin Writeln('Khong ton tai duong di tu ',s,' den ',t); Exit End; Write(t,'<='); While is do Begin Write(i,'<='); i:=Truoc[i]; End; Writeln(s); Writeln('Do dai cua duong di la: ',d[t]); Readln; End; BEGIN {Main program} ClrScr; NhapSoLieu; InSolieu; Dijkstra; Result; END. Chương 5 MỘT SỐ VẤN ĐỀ VỀ CÂY I. CÁC KHÁI NIỆM VÀ TÍNH CHẤT CƠ BẢN 1. Định nghĩa Cho đồ thị G = , G được gọi là một cây nếu G liên thông và không có chu trình, ở đây n = ÷ X÷ > 1. Khi đó sáu tính chất sau là tương đương 1) G là đồ thị liên thông và không có chu trình 2) G không có chu trình và có n - 1 cạnh 3) G liên thông và có n - 1 cạnh 4) G không có chu trình và nếu thêm vào một cạnh nối 2 đỉnh không kề nhau thì G xuất hiện duy nhất một chu trình. 5) G liên thông và nếu bỏ đi một cạnh tuỳ ý thì đồ thị nhận được sẽ không liên thông. 6) Mỗi cặp đỉnh trong G được nối với nhau bằng một đường duy nhất. Chứng minh: Ta chứng minh theo trình tự sau: 1) Þ 2) Þ 3) Þ 4) Þ 5) Þ 6) Þ 1). Ta sử dụng đẳng thức v(G) = m - n + p là số chu trình độc lập của đồ thị G = , ở đây ÷ X÷ = n, ÷ U÷ = m và p là số thành phần liên thông của G. 1) Þ 2): Vì G không có chu trình nên v(G) = m - n + p = 0. Do G liên thông nên p =1 khi đó m - n + 1 = 0 hay số cạnh m = n - 1. 2) Þ 3): Giả sử G không có chu trình và n - 1 cạnh ta chứng minh 3) Thật vậy, giả sử ngược lại G không liên thông, khi đó p ³ 2 . Từ 2) ta có v(G) = m - n + p = 0 và m = n -1, kết hợp ta có (n - 1) - n + p = 0 hay p = 1, trái với giả thiết p ³ 2. Vậy G liên thông và số cạnh là n -1. 3) Þ 4): Giả sử G là liên thông và có n - 1 cạnh, ta chứng minh 4). Thật vậy vì G liên thông nên p = 1, mặt khác m = n - 1 nên v(G) = m - n + 1 = 0 hay G không có chu trình . Nếu thêm vào G một cạnh thì ta được đồ thị G' với số cạnh là n, hay v(G') = n - n + 1 = 1 hay G' có một chu trình. 4) Þ 5): Giả sử ngược lại G không liên thông, tức là tồn tại cặp đỉnh x, y trong G mà không có đường nào nối x với y. Khi đó nối x và y bởi 1 cạnh, đồ thị nhận được vẫn không có chu trình điều này mâu thuẫn với 4). Hay G là liên thông. Nếu bỏ đi 1 cạnh trong G mà đồ thị vẫn liên thông thì nếu khôi phục lại cạnh này đồ thị sẽ có chu trình. Điều này mâu thuẫn với 4). Vậy ta có 5). 5) Þ 6): Giả sử ngược lại, nếu trong G có tồn tại cặp đỉnh x, y không nối với nhau bằng đường nào cả, chứng tỏ G không liên thông mâu thuẫn với 5). Vậy mỗi cặp đỉnh đều có đường đi nối với nhau, đường đó là duy nhất vì nếu có nhiều hơn thì sau khi bỏ đi 1 đường đồ thị vẫn liên thông, trái với 5). 6) Þ 1) Với mỗi cặp đỉnh nối với nhau bởi một đường thì G là liên thông. Giả sử G có chu trình thì xét cặp đỉnh x, y trên chu trình đó. Khi đó x, y có 2 cặp đường nối với nhau, mâu thuẫn với 6). 2. Một số khái niệm cơ bản - Gốc: Đối với một cây T bất kỳ có thể chọn 1 đỉnh nào đó làm gốc, một cây đã được chọn 1 đỉnh làm gốc thì được gọi là cây có gốc. Vậy một cây có thể tạo thành nhiều cây có gốc khác nhau. - Quan hệ cha con: Giả sử a là gốc nếu có b, c kề với a thì b, c được gọi là con của a (hoặc gọi a là cha của b, c) tương tự nếu có d, e kề với b thì b là cha của chúng còn d, e là con của b (Xem cây T' hình 1.1). - Trong một cây tất cả các đỉnh là cha được gọi là các đỉnh trong. Các đỉnh không phải là đỉnh trong được gọi là lá (hay lá là đỉnh con không có con), trong cây chỉ có gốc là đỉnh duy nhất không phải là con. - Bậc của đỉnh là số các con của nó, bậc của cây là bậc lớn nhất của đỉnh. - Mức của cây: Mỗi 1 đỉnh đều được gán bằng một mức, mức của gốc là 0, con của gốc có mức là 1. Nếu mức của cha là i thì mức của con là i + 1. Một đỉnh x nào đó có mức bằng độ dài đường đi từ gốc đến x, mức cao nhất trong số các đỉnh được gọi là chiều cao của cây. Khi cây chưa có gốc, chưa phân chia thành các các mỗi quan hệ cha con, bậc, mức... thì cây là cây tự do còn khi được phân chia gọi là cây phân cấp. h a d i j b e k g c f a b d i j e h k c g f T T' Hình 1.1 Ví dụ như hình 1.1 cây T là một cây tự do, nếu chọn a làm gốc thì nó trở thành cây phân cấp T' có gốc. Với cây T' gốc a có bậc 2 và mức 0, đỉnh c có bậc là 3 và mức 1 ... Mức cao nhất là 3 ở các đỉnh là lá như i, j, k nên chiều cao của cây h(T') = 3. 3. Cây m - phân - Định nghĩa: Xét cây phân cấp T nếu mỗi đỉnh trong của nó có không quá m con thì T được gọi là cây m phân. Đặc biệt nếu m = 2 thì cây được gọi là cây nhị phân, cây nhị phân rất quan trọng và có nhiều ứng dụng rộng rãi. - Cây đầy đủ: Cây m - phân T được gọi là cây m - phân đầy đủ nếu mỗi đỉnh trong đều có đúng m con. - Cây cân đối: Xét cây m - phân có chiều cao h. Nêu các lá của cây có mức h - 1 hoặc h thì cây được gọi là cây cân đối. 4. Các ứng dụng 4.1 Mã tiền tố Kỹ thuật nén và mã hoá là 1 trong những lĩnh vực thường hay được sử dụng trong Tin học, cây nhị phân có nhiều ứng dụng trong việc nghiên cứu áp dụng các giải thuật trong lĩnh vực vực này. Một trong những ứng dụng của cây nhị phân đó là mã tiền tố. Ví dụ mã tiền tố như là dùng các xâu nhị phân có độ dài khác nhau để mã các ký tự để không có xâu nhị phân nào ứng với hơn một chữ cái. Trên cây nhị phân mã hoá, các lá là các ký tự cần mã hoá và đường đi từ cha đến con trái là 1 (hoặc 0), còn đi tới con phải là 0 (hoặc 1). Quá trình mã hoá sẽ duyệt cây đó từ gốc tới lá, khi tới nút con sẽ tạo ra một bít 0 hoặc 1 và tới nút lá sẽ tạo ra một xâu bít. Do vậy, mã sinh ra cho một ký tự sẽ không là phần đầu của ký tự khác. 0 0 0 0 0 0 1 1 1 1 1 1 1 1 a e i k o p u Hình 1.2 Ví dụ như hình 1.2 cây nhị phân biểu diễn mã tiền tố của các ký tự a, e, i, k, o, p, u trong đó: a : 000 k : 1100 u : 11111 e : 001 o : 1101 i : 01 p : 11110 Thuật toán mã hoá Huffman: Một số thuật toán về mã tiền tố đã ra đời đã được sử dụng rộng rãi và đem lại hiệu quả cao trong vấn đề nén và mã hoá thông tin. Một trong những thuật toán đó là Huffman xuất hiện từ năm 1952, thuật toán này mã hoá theo phương pháp kiểu thống kê, tạo ra mã có độ dài thay đổi khác nhau khi đã có bảng tần số xuất hiện của các ký tự. Quá trình mã hoá và giải mã phụ thuộc vào việc xây dựng cây nhị phân mã hoá. Thuật toán Huffman tạo cây nhị phân từ nút lá đến nút gốc, ký tự nào có tần số càng cao thì nút lá tương ứng càng gần gốc hơn. Thuật toán: Vào: Bảng tần số xuất hiện các ký tự sắp xếp giảm dần Ra : Cây nhị phân biểu diễn mã, nhánh phải là 1, trái là 0. Bước 1: Lấy hai phần tử cuối bảng tần số xuất hiện ra khỏi bảng Bước 2: Nếu phần tử nào chưa nằm trong cây nhị phân thì tạo ra một nút lá chứa phần tử đó, phần tử này chính là ký tự. Nối hai nút tương ứng với hai phần tử này với nhau thông qua việc tạo nút cha của chúng. Phần tử có tần số xuất hiện lớn hơn là nút trái, nhỏ hơn là nút phải. Bước 3: Tính tổng tần số xuất hiện của 2 phần tử này chèn vào bảng sao cho phù hợp với nguyên tắc giảm dần của bảng. Phần tử mới của bảng sẽ tương ứng với nút vừa được tạo ra ở bước 2. Bước 4: Quay trở lại bước 1 đến khi bảng chỉ còn lại 1 phần tử. Phần tử cuối cùng tương ứng với nút gốc của cây nhị phân. Ví dụ: Ta có kết quả mã Huffman cho các ký tự ở bảng sau: Ký tự Tần suất Mã nhị phân Chiều dài mã a 0.3 00 2 b 0.2 10 2 c 0.2 11 2 d 0.1 011 3 e 0.1 0100 4 f 0.1 0101 4 Cây nhị phân biểu diễn như hình 1.3 a,e,f,d,b,c a,e,f,d b,c e,f,d a e,f d e f b c 0 0 0 0 0 1 1 1 1 1 0,3 0,6 0,2 0,1 0,1 0,1 0,3 0,4 0,2 0,2 Hình 1.3 Với thuật toán Huffman trường hợp xấu nhất là thời gian hình thành cây nhị phân là O(n) với n là số ký tự cần mã hoá. Chương trình viết bằng ngôn ngữ Pascal minh hoạ thuật toán tạo mã Huffman: Const n = 6; {Số ký tự cần mã hoá a, b, c, .....} Type Nod = record S:integer; {tần suất} Code:String; {mã nhị phân} Name:char; {tên ký tự} end; Var a:array[1..n] of Nod; i,m:integer; Procedure InputData; {Khởi tạo bảng tần suất các ký tự} Var i:integer; begin for i:=1 to n do with A[i] do begin S:=Round(exp(n/5)/exp(i/5))+1;Name:=Char(64+i);Code:=''; end; end; Procedure FindCode(m:integer); {Sinh mã huffman} Var y,z:nod; k:integer; Begin if m=1 then exit; y:=a[m-1]; a[m-1].s:=a[m-1].s+a[m].s; k:=m-1; While (k>1) and (a[k].s>a[k-1].s) do Begin z:=a[k]; a[k]:=a[k-1]; a[k-1]:=z; k:=k-1; End; FindCode(m-1); z:=a[k]; for i:=k to m-2 do a[i]:=a[i+1]; a[m-1]:=y; a[m-1].code:=z.code+'1'; a[m].code:=z.code+'0'; End; BEGIN InputData; FindCode(n); For i:=1 to n do writeln(a[i].code); END. 4.2 Cây biểu diễn biểu thức Một biểu thức toán học có thể biểu diễn bằng cây, đây cũng là vấn đề hữu ích trong việc xử lý và lưu trữ biểu thức toán học trong máy tính Xét biểu thức đại số sau: Có thể vẽ 1 cây nhị phân như hình 1.4 biểu diễn biểu thức A, trong đó mỗi đỉnh trong mang dấu của một phép tính, gốc của cây mang phép tính sau cùng của A, ở đây là dấu nhân ký hiệu: *, mỗi lá mang 1 số hoặc một chữ đại diện cho số. a * + - / b c d 2 Hình 1.4 Một phép duyệt cây là tiền thứ tự nếu thăm gốc trước rồi sau đó thăm con trái như là một cây con với phương pháp thăm gốc trước và cuối cùng thăm con phải như là một cây con với phương pháp thăm gốc trước. Duyệt cây như vậy mang tính đệ quy. Khi duyệt cây trên theo tiền thứ tự ta có: * + a b - c / d 2 Cách viết biểu thức theo tiền thứ tự là ký pháp Balan. Bằng duyệt cây ta có thể tính được giá trị biểu thức, ngoài phương pháp tiền thứ tự còn có thể duyệt cây theo phương pháp pháp khác để tính giá trị biểu thức tùy vào yêu cầu và đặc điểm của từng bài toán. 4.3 Cây quyết định Có những bài toán phụ thuộc vào các quyết định. Mỗi quyết định thì có thể có nhiều kết cục và những kết cục cuối cùng chính là lời giải của bài toán. Để giải những bài toán như vậy, người ta biểu diễn mỗi quyết định bằng một đỉnh của đồ thị và mỗi kết cục là 1 lá của quyết định. Một cây được xây dựng như trên gọi là cây quyết định. Trong nhiều bài toán Tin gặp phải, có thể dùng cây quyết định để mô hình hoá từ đó việc cài đặt sẽ dễ dàng thuận tiện hơn. Ví dụ: hình 1.5 là cây quyết định biểu diễn việc sắp xếp 3 số khác nhau a, b, c a ? b a ? c b ? c b ? c a ? c c<a<b c<b<a b<c<a b<a<c a<c<b a<b<c b<a a<b c<a a<c c<b b<c c<b b<c c<a a<c Hình 1.5 Đoạn chương trình sau thể hiện cho cây trên: Var a, b, c: Integer; Function Can(x,y: Integer): Boolean; Begin if x > y then Can:=True Else Can:=False; End; Begin Readln(a,b,c); If Can(a,b) then Begin If Can(a,c) then Begin if Can(b,c) then Writeln(c,' ',b,' ',a) Else Writeln(b,' ',c,' ',a); End Else Writeln(b,' ',a,' ',c); End Else Begin If Can(b,c) then Begin if Can(a,c) then Writeln(c,' ',a,' ',b) Else Writeln(a,' ',c,' ',b); End Else Writeln(a,' ',b,' ',c); End; End. 4.4 Cây sắp xếp và tìm kiếm Sắp xếp và tìm kiếm là một trong những vấn đề cơ bản trong kỹ thuật lập trình, cây nhị phân cũng có khá nhiều ứng dụng quan trọng trong vấn đề này. Ta có thể mô hình hoá việc sắp xếp và tìm kiếm bằng cây từ đó ta có thể đánh giá các kỹ thuật này từ góc độ về cây. 4.4.1 Sắp xếp chèn với tìm kiếm nhị phân Ý tưởng được bắt đầu như sau, cho 1 danh sách chưa sắp xếp hãy tìm 1 phần tử x bất kỳ nào đó trong danh sách, rõ ràng để tìm ta phải lần lượt xét từng phần tử cho tới khi nào bắt gặp phần tử cần tìm, nếu danh sách lớn thì thời gian tìm rất lâu. Bây giờ với một danh sách đã sắp xếp, chia đôi danh sách và lấy phần tử là t ở vị trí chia đôi để so sánh. Nếu t = x thì dừng, nếu t < x vì danh sách đã sắp xếp nên x chỉ có thể nằm bên nửa phải danh sách nên ta chỉ việc tìm kiếm trong 1 nửa danh sách bên phải và giảm đi khá nhiều công việc tìm kiếm. Nếu x < t thì tương tự, ta chỉ việc tìm bên nửa trái, đối với việc tìm kiếm cho lần sau với các danh sách con nửa trái hoặc nửa phải ta thực hiện tương tự như vậy một cách đệ quy. a) Từ những ý tưởng thuật toán ta xây dựng cây nhị phân tìm kiếm cho một danh sách như sau: - Chọn 1 phần tử bất kỳ làm gốc - Tất cả các phần tử có giá trị £ gốc thì thuộc cây con trái - Tất cả các phần tử có giá trị > gốc thì thuộc cây con phải - Đối với các cây con thì cũng có tính chất tương tự như vậy Ví dụ cây nhị phân tìm kiếm cho danh sách 12, 10, 6, 11, 15, 13, 16, 19, 18 như hình 1.6: 12 15 18 10 6 11 13 16 19 Hình 1.6 b) Sắp xếp chèn bằng việc tìm nhị phân vị trí đúng. Có thể tạm gọi là phương pháp sắp xếp chèn nhị phân. Ý tưởng như sau: cho trước một danh sách đã sắp xếp A, cần chèn 1 phần tử mới x vào A sao cho danh sách luôn được sắp xếp. Đầu tiên ta tìm vị trí đúng của x trong A sau đó chèn x vào đúng vị trí này trong A, ta có danh sách A = A È {x} luôn được sắp xếp. Để tìm được ví trí đúng cần chèn của x trong A ta sử dụng phương pháp tìm kiếm nhị phân, chèn theo cách này gọi là chèn nhị phân. Ví dụ để sắp xếp B = x1, x2, x3, ... xn ta thực hiện như sau: A := f; For i:=1 to n do Begin - Tìm vị trí đúng của xi trong A theo phương pháp tìm nhị phân - Chèn xi vào A theo đúng vị trí vừa tìm được (A := A È {xi}) End; Kết quả A là danh sách sắp xếp của B. Chương trình Pascal sau sắp xếp tăng dần theo phương pháp chèn nhị phân Const n = 9; Ds : Array[1..n] of Integer = (1,9,1,6,3,10,10,8,7); {Ham tra lai vi tri dung cua Pt trong danh sach} Function FindNp(l,r,Pt: Integer): Integer; Var t: Integer; Begin If Pt<=Ds[l] then FindNp:=l Else If Pt>=Ds[r] then FindNp:= r + 1 Else Begin Repeat t:= (l + r) div 2; If Pt = ds[t] then Begin FindNp:=t+1; Exit End Else If Pt<ds[t] then r:=t Else l:=t; Until r=l+1; FindNp:=l+1; End; End; Var i, j, vt, s: Integer; Begin For i:=2 to n do Begin vt:= FindNp(1,i-1,ds[i]); {Chen dung vi tri sao cho ds luon duoc sap xep} s:=ds[i]; For j:=i-1 Downto vt do ds[j+1]:=ds[j]; ds[vt]:=s; End; For i:=1 to n do Write(ds[i]:3); End. 4.4.2 Thuật toán sắp xếp hoà nhập Giả sử ta có danh sách chưa được sắp 8, 2, 4, 6, 9, 7, 10, 1, 5 ,3 có thể dùng cây nhị phân mô tả quá trình sắp xếp danh sách theo thứ tự tăng dần như sau: Cây nhị phân với gốc được gán là chính là danh sách đó. Các con của gốc được gán theo nguyên tắc: Con bên trái gán nửa danh sách đầu, con bên phải gán nửa danh sách còn lại (danh sách gán ở gốc cây con trái và cây con phải hoặc bằng nhau về số lượng hoặc chênh lệch nhau 1 phần tử). Cứ tiếp tục cho tới khi cây nhị phân có mỗi lá được gán 1 phần tử trong dãy. Đó là cây như hình 1.7 8, 2, 4, 6, 9, 7, 10, 1, 5, 3 8, 2, 4, 6, 9 7, 10, 1, 5, 3 8, 2, 4 6, 9 7, 10, 1 5, 3 8, 2 4 6 9 8 2 7, 10 1 7 10 5 3 Hình 1.7 Đây là cây nhị phân đầy đủ chưa phải cây sắp xếp của dãy đã cho ở trên 8 2 7 10 2, 8 4 6 9 7, 10 1 5 3 2, 4, 8 6, 9 1,7, 10 3, 5 2, 4, 6, 8,9 1, 3,5, 7, 10 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 Hình 1.8 Để có cây nhị phân sắp xếp của một dãy, trước hết cây được xây dựng tương tương tự như vậy, mỗi lá tương ứng với mỗi phần tử của dãy. Bước đầu tiên 2 phần tử được hoà nhập vào 1 danh sách theo thứ tự tăng dần, danh sách tương ứng này như một nút cha, 2 phần tử được hoà nhập là nút con. Sau đó ta tiếp tục hoà nhập các cặp nút tương tự như vậy cho tới toàn bộ danh sách được sắp xếp lại theo thứ tự tăng dần và cây biểu diễn cho dãy là cây nhị phân cân đối được mô tả như hình 1.8 Các bước thuật toán trên được mô tả trên là đã vận dụng thuật toán hoà nhập hai danh sách đã được sắp xếp thành một danh sách mới được sắp xếp, thuật toán này theo nguyên tắc sau: - So sánh phần tử bé nhất trong danh sách trong danh sách thứ nhất với phần tử bé nhất trong danh sách thứ 2. - Quá trình trên được lặp lại cho 2 danh sách nhận được ở bước trên - Sau một số bước sẽ gặp hai trường hợp sau: a) Cả 2 danh sách trở thành rỗng. Trong trường hợp này, các phần tử có mặt trong danh sách hoà nhập chính là danh sách cần xác định b) Một danh sách trở thành rỗng, còn danh sách kia khác rỗng. Trong trường hợp này đưa các phần tử còn lại (trong danh sách không rỗng) nối vào cuối của danh sách hoà nhập. Độ phức tạp thuật toán của thuật toán trên là O(nlogn) trong đó n là số phần tử hoà nhập Chương trình bằng ngôn ngữ Pascal thể hiện thuật toán hoà nhập như sau: Const n = 10; Type Vec = Array[1..n] of Integer; Const cm:Vec = (-3,3,-1,4,1,5,6,7,-8,-9); Var x,y:Vec; Procedure Viet; Var i:byte; Begin For i:=1 to n do Write(x[i]:3); Writeln; End; Procedure Hoa_nhap2p(x:Vec; p,m,n:Integer; Var z:Vec); Var i,j,k: Integer; Begin i:=p;j:=m+1;k:=p; While (i<=m) and (j<=n) do Begin If x[i]<x[j] Then Begin z[k]:=x[i];inc(i); End Else Begin z[k]:=x[j];inc(j);End; Inc(k); End; If i>m Then for K:=j to n Do z[k]:=x[k] Else for k:=i to m Do z[n+k-m]:=x[k]; End; Procedure Merge(l,r:integer); Var i,m:integer; Begin If l<r Then Begin m:=(l+r) div 2; Merge(l,m); Merge(m+1,r); For i:=l to r do y[i]:=x[i]; Hoa_nhap2p(y,l,m,r,x); End; End; BEGIN X := cm; Viet; Merge(1,n); Viet; END. 4.4.3 Thuật toán sắp xếp nhanh Sắp xếp 1 danh sách có nhiều thuật toán, mỗi thuật toán đều có những ưu nhược điểm. Trong các thuật toán sắp xếp thì thuật sắp xếp nhanh (Quick sort) tỏ ra có nhiều ưu điểm được sử dụng phổ biến và rất hiệu quả. Nguyên tắc của thuật toán này có tính đệ quy có thể sử dụng cây nhị phân để mô tả thuật toán này. Thuật toán có thể được mô tả tóm tắt như sau: Ví dụ để sắp xếp danh sách a1, a2, ..., an thuật toán bắt đầu bằng việc lấy ngẫu nhiên 1 phần tử làm chốt nhưng thường thì phần tử đầu tiên được chọn làm chốt. Như danh sách trên ta chọn a1 làm chốt khi đó danh sách được phân đoạn thành 2 danh sách con, một danh sách con gồm các phần tử nhỏ hơn a1 theo thứ tự xuất hiện, còn danh sách con khác gồm các phần tử lớn hơn a1 cũng theo thứ tự xuất hiện. Sau khi đã có hai danh sách con thì a1 được đặt vào sau cùng của danh sách con gồm các phần tử nhỏ hơn a1, như vậy sau a1 là danh sách con gồm các phần tử lớn hơn a1. Thủ tục này được lặp lại một cách đệ quy cho mỗi danh sách con cho tới khi nào mỗi danh sách con chỉ chứa một phần tử theo thứ tự xuất hiện của nó. Với kết quả này ta được một danh sách đã được sắp xếp. Ví dụ cho danh sách: 3, 5, 7, 8, 1, 9, 2, 6; Có thể dùng cây nhị phân biểu diễn thuật toán sắp xếp nhanh để sắp xếp danh sách này như hình 1.9 3, 5, 7, 8, 1, 9, 2, 4, 6 1, 2, 3 5, 7, 8, 9, 4, 6 1 2, 3 4, 5 7, 8, 9, 6 2 3 4 5 6, 7 8, 9 9 8 6 7 Hình 1.9 Danh sách lúc chưa sắp xếp là gốc, danh sách được sắp xếp là danh sách mà mỗi phần tử của nó là lá của cây. Chương trình thể hiện thuật toán sắp xếp nhanh như sau: Uses Crt; const Max = 10; type List = array[1..Max] of Integer; var Data: List; I: Integer; procedure QuickSort(var A: List; Lo, Hi: Integer); procedure Sort(l, r: Integer); var i, j, x, y: integer; begin i := l; j := r; x := a[(l+r) DIV 2]; repeat while a[i] < x do i := i + 1; while x < a[j] do j := j - 1; if i <= j then begin y := a[i]; a[i] := a[j]; a[j] := y; i := i + 1; j := j - 1; end; until i > j; if l < j then Sort(l, j); if i < r then Sort(i, r); end; Begin {QuickSort}; Sort(Lo,Hi); End; Begin {QSort} { Khởi tạo ngẫu nhiên 10 phần tử } Randomize; for i := 1 to Max do Data[i] := Random(3000); Writeln; {Sắp xếp các phần tử bằng Quick Sort} QuickSort(Data, 1, Max); Writeln; for i := 1 to 10 do Write(Data[i]:8); End. Người ta đã chỉ ra rằng độ phức tạp của thuật toán là O(nlog2n) II. CÂY BAO TRÙM 1. Định nghĩa và các tính chất Định nghĩa: Cho đồ thị G = với số đỉnh n lớn hơn 1. Giả sử G' là đồ thị bộ phận của G (G' nhận được từ G bằng cách bỏ đi một số cạnh nhưng vẫn giữ nguyên đỉnh). Nếu G' = là một cây thì G' gọi là cây bao trùm của G. Theo đúng tính chất về cây. G' là cây bao trùm phải có n - 1 cạnh và là một đồ thị liên thông không có chu trình. Trong một đồ thị có thể có nhiều cây bao trùm. e a b d c e a b d c a) b) hình 2.1 Ví dụ cây như hình 2.1.b là một cây bao trùm của đồ thị trong hình 2.1.a Định lý: Cho đồ thị G = , G có cây bao trùm khi và chỉ khi G là đồ thị liên thông. Chứng minh: Điều kiện cần: Giả sử G có cây bao trùm là G'. Ta chỉ ra G là liên thông. Thật vậy, nếu G không liên thông thì tồn tại cặp đỉnh x, y mà giữa chúng không được nối bởi đường nào, mà giữa x, y cũng là các đỉnh của G'. Chứng tỏ G' không liên thông, trái với giả thiết G' là một cây. Điều kiện đủ: Giả sử G là liên thông ta chứng minh G có cây bao trùm, thật vậy vì: - Nếu trong G không có chu trình thì theo định nghĩa G là một cây, đó là cây bao trùm. - Nếu trong G có chu trình thì bỏ đi 1 cạnh trong chu trình đó ta được G' liên thông và không có chu trình, G' là cây bao trùm. 2. Các thuật toán tìm cây bao trùm Xét đồ thị G = liên thông có n đỉnh, ta có các thuật toán tìm cây bao trùm như sau: 2.1 Thuật toán theo lý thuyết Giả sử G không có chu trình thì nó là một cây và cũng chính là cây bao trùm của nó. Nếu G có chu trình thì ở 1 chu trình đơn nào đó bỏ đi 1 cạnh đồ thị vẫn liên thông. Nếu G còn chu trình đơn thì bỏ tiếp 1 cạnh nữa ... cho đến khi không còn chu trình thì ta được đồ thị mới G' nhận được từ G và G' chính là 1 cây bao trùm của G. Thuật toán trên chỉ có ý nghĩa lý thuyết vì khi số đỉnh lớn, chu trình lớn thì việc kiểm tra chu trình đối với máy tính đòi hỏi nhiều tính toán 2.2 Thuật toán tìm kiếm ưu tiên chiều sâu và chiều rộng Rất nhiều thuật toán trên đồ thị được xây dựng dựa trên cơ sở duyệt tất cả các đỉnh của đồ thị sao cho mỗi đỉnh của nó được thăm đúng 1 lần, trong mục này ta sẽ đề cập tới 2 thuật toán rất cơ bản của đồ thị về thăm đỉnh theo nguyên tắc trên. Đó là thuật toán tìm kiếm theo chiều sâu và chiều rộng, chúng được sử dụng để tìm cây bao trùm của đồ thị, ngoài ra chúng còn được sử dụng trong các thuật toán tìm đường đi, tìm các thành phần liên thông, kiểm tra tính liên thông... Trước khi đi vào 2 thuật toán, ta sẽ đề cập tới 1 yếu tố cơ bản cấu thành nên ý tưởng của nhiều thuật toán trong đồ thị đó là kỹ thuật quay lui. Đây là một kỹ thuật chính trong kỹ thuật lập trình có nhiều áp dụng, đặc biệt là áp dụng trong giải thuật tìm kiếm theo chiều sâu. 2.2.1 Kỹ thuật quay lui Nội dung của kỹ thuật quay lui có thể tóm tắt như sau: Dùng cây quyết định, còn lá thì biểu thị 1 lời giải có thể. Để tìm nghiệm bằng kỹ thuật quay lui, trước tiên tạo ra dãy quyết định (càng dài càng tốt) để tiến tới lời giải. Dãy quyết định có thể biểu thị một đường đi trong cây quyết định. Mỗi khi biết được không thể có lời giải từ bất kỳ dãy quyết định nào thì ta quay lui lại đỉnh cha của đỉnh hiện tại để hướng tới lời giải bằng dãy quyết định khác (nếu có thể). Thủ tục tiếp tục cho tới khi tìm được lời giải hoặc là kết luận không có lời giải. Ví dụ cho 1 tập A = {1, 2, 3, 4} hãy tìm tập con của A gồm 3 phần tử sao cho tổng các phần tử của tập con này là 8. Trước hết ta xây dựng cây