Giáo án Lý thuyết đồ thị

63 trang hapham 2890

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo án Lý thuyết đồ thị", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

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

giao_an_ly_thuyet_do_thi.pdf

Nội dung text: Giáo án Lý thuyết đồ thị

Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ €GIÁO ÁN MÔN LÝ THUYẾT ĐỒ THN Số tiết học: 60 tiết ( 45 tiết lý thuyết + 15 tiết thực hành) Tài liệu tham khảo: 1) Toán rời rạc, PGS. TS Đỗ Đức Giáo, Nhà xuất bản Đại học Quốc gia Hà Nội 2002 2) Toán rời rạc, Nguyễn Đức Nghĩa, Nguyễn Tô Thành, Nhà xuất bản Đại học Quốc gia Hà Nội 2003 3) Giáo trình Lý thuyết đồ thị, Nguyễn Thanh Hùng, Nguyễn Đức Nghĩa 4) Toán học rời rạc ứng dụng trong tin học, Dịch từ Discrete Mathematics and Its Applications, Nhà xuất bản khoa học kỹ thuật Chương 1 CÁC KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THN (9 tiết) 1.1 Giới thiệu Lý thuyết đồ thị là nghành khoa học đã có từ lâu nhưng lại có rất nhiều ứng dụng hiện đại. Những ý tưởng cơ sở ban đầu của nó được đưa ra từ những năm đầu thế kỷ 18 bởi nhà toán học người Thuỵ Sỹ là Leonhard Euler. Lý thuyết đồ thị được dùng để giải quyết các bài toán thuộc nhiều lĩnh vực khác nhau. Chẳng hạn: Dùng mô hình đồ thị để xác định xem hai máy tính trong một mạng máy tính có trao đổi thông tin được với nhau hay không?. Đồ thị với các trọng số được gắn cho các cạnh có thể dùng để giải quyết bài toán tìm đường đi ngắn nhất giữa hai thành phố trong một mạng lưới giao thông. Chúng ta cũng có thể phân biệt các hợp chất hoá học có cùng công thức phân tử nhưng có cấu trúc khác nhau nhờ vào đồ thị 1.2 Các định nghĩa và tính chất cơ bản Định nghĩa 1: Giả sử V là một tập khác rỗng các phần tử nào đó và E ⊆ VxV (E là tập con của tích đề các VxV). Bộ G = (V, E) được gọi là một đồ thị. Mỗi phần tử v ∈V được gọi là một đỉnh của đồ thị, V được gọi là tập các đỉnh của đồ thị. Mỗi phần tử e = (u,v) ∈ E được gọi là một cạnh của đồ thị, E được gọi là tập các cạnh của đồ thị. Ví dụ 1: G = (V = {v1, v2, v3, v4, }, E = {e1 = (v1,v2), e2 = (v1,v3), e3 = (v2,v3), e4 = (v3,v4), }) v2 e1 e3 v1 v3 e2 e4 v4 Như vậy ta có thể hình dung đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh này với nhau. 1 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Chú ý: Nếu tập V là tập hữu hạn các phần tử thì G = (V,E) được gọi là đồ thị hữu hạn. Từ đây về sau chủ yếu ta nghiên cứu các đồ thị hữu hạn. (có thể coi đây là một định nghĩa về đồ thị) Ví dụ 2: G = (V={Thanh hoá, Nghệ an, Hà nội, TP.HCM},E={(Thanh hoá,Nghệ an),(Thanh hoá, Hà nội), (Nghệ an, Hà nội), (Hà nội, TP.HCM) }) Thanh hoá Nghệ an Hà nội TP.HCM Định nghĩa 2: a) Hai đỉnh được gọi là kề nhau nếu có cạnh nối hai đỉnh đó với nhau. Cạnh nối hai đỉnh được gọi là cạnh liên thuộc. b) Hai cạnh được gọi là kề nhau nếu giữa chúng có đỉnh chung. c) Nếu e = (v,v) là một cạnh của đồ thị thì e được gọi là một khuyên. Trong trường hợp này đồ thị được gọi là giả đồ thị. Ví dụ 3: v1 v2 v3 e3 e1 e2 v1 và v2 được gọi là hai đỉnh kề nhau, e1 được gọi là cạnh liên thuộc hai đỉnh v1 và v2. e1 và e2 được gọi là hai cạnh kề nhau, e3 được gọi là một khuyên. Định nghĩa 3: a) Nếu mỗi cạnh e = (u,v) ∈ E là không phân biệt thứ tự của các đỉnh u và v, (tức là từ u tới v không kể hướng) thì ta nói đồ thị G = (V,E) là đồ thị vô hướng. b) Nếu mỗi cạnh e = (u,v) ∈ E có phân biệt thứ tự của các đỉnh u và v, (tức là từ u tới v khác với từ v tới u) thì ta nói đồ thị G = (V,E) là đồ thị có hướng. Cạnh của đồ thị có hướng còn được gọi là cung. Tây hồ Ví dụ 4: v1 CVThủ lệ Hồ gươm v2 v3 TTCPQG Đồ thị vô hướng Đồ thị có hướng 2 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Định nghĩa 4: Đồ thị G =(V,E) được gọi là đơn đồ thị nếu giữa hai đỉnh bất kỳ của đồ thị được nối với nhau bởi không quá một cạnh (cung). Ví dụ 5: Định nghĩa 5: Đồ thị G = (V,E) được gọi là đa đồ thị nếu 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. Ví dụ 6: Định nghĩa 6: Đồ thị G = (V,E) được gọi là đồ thị phẳng nếu nó có dạng biểu diễn hình học trên mặt phẳng mà các cạnh (cung) chỉ cắt nhau ở đỉnh. Cách vẽ như vậy được gọi là biểu diễn phẳng của đồ thị. Trong trường hợp ngược lại đồ thị là không phẳng. Ví dụ 7: Đồ thị phẳng Đồ thị không phẳng Biểu diễn phẳng của một đồ thị chia mặt phẳng thành các miền. Ví dụ biểu diễn phẳng của đồ thị dưới đây chia mặt phẳng thành 5 miền. R2 R3 R5 R1 R1 Định nghĩa 7: Đồ thị G = (V,E) được gọi là đồ thị đầy đủ nếu mỗi cặp đỉnh đều có cạnh (cung) nối giữa chúng. Ví dụ 8: 3 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Định nghĩa 8: Cho đồ thị vô hướng G = (V,E). Với v ∈V là một đỉnh của đồ thị, ta kí hiệu deg(v) là số các cạnh thuộc đỉnh v, riêng với khuyên thì đựơc tính là 2. deg(v) được gọi là bậc của đỉnh v. Nếu deg(v) = 0 thì v được gọi là đỉnh cô lập, nếu deg(v) = 1 thì v được gọi là đỉnh treo. Bậc của đồ thị vô hướng G = (V,E) được kí hiệu là deg(G) và được tính deg(G) = ∑deg(v) v∈V Ví dụ 9: v1 v2 v3 v4 v5 Với đồ thị trên ta có: deg(v5) = 0, v5 được gọi là đỉnh cô lập deg(v4) = 1, v4 được gọi là đỉnh treo deg(v3) = 4, deg(v2) = 3, deg(v1) = 2 Định nghĩa 9: Cho đồ thị có hướng G = (V,E). Với v∈V là một đỉnh của đồ thị, ta ký hiệu deg-(v) là số các cung vào của đỉnh v, deg+(v) là số các cung ra của đỉnh v. Khi đó deg-(v) được gọi là bậc vào của đỉnh v, deg+(v) được gọi là bậc ra của đỉnh v và bậc của đỉnh v là deg(v) = deg-(v) + deg+(v). Nếu deg+(v) = deg-(v) = 0 thì v được gọi là đỉnh cô lập, nếu deg+(v) = 0, deg-(v) = 1 hoặc deg+(v) = 1, deg-(v) = 0 thì v được gọi là đỉnh treo. Bậc của đồ thị có hướng G = (V,E) được kí hiệu là deg(G) và được tính deg(G) = ∑∑deg− (v) + deg + (v) vV∈∈V v Ví dụ 10: v1 v2 v3 v6 v5 v4 Với đồ thị trên ta có: deg-(v1) = 2, deg+(v1) = 5 deg-(v2) = 2, deg+(v2) = 1 deg-(v3) = 1, deg+(v3) = 0, đỉnh v3 được gọi là đỉnh treo deg-(v4) = deg+(v4) = 0, đỉnh v4 được gọi là đỉnh cô lập deg-(v5) = 3, deg+(v5) = 0 deg-(v6) = 1, deg+(v6) = 3 Định lý 1: Giả sử G = (V,E) là đồ thị hữu hạn. Khi đó bậc của đồ thị G bằng hai lần số cạnh của đồ thị, tức là deg(G) = 2|E| Chứng minh: 4 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Giả sử u,v∈V và e = (u,v)∈E Nhận xét: Giả sử u ≠ v. Khi đó nếu xoá cạnh (cung) e thì bậc của đồ thị sẽ giảm đi 2. Nếu ta xoá tất cả các cạnh có dạng như trên thì đồ thị còn lại chỉ gồm các đỉnh cô lập hoặc các đỉnh có khuyên. Tại mỗi đỉn u có khuyên, nếu ta xoá khuyên thì bậc của đồ thị cũng sẽ giảm đi 2. Như vậy nếu ta xoá một cạnh hoặc một khuyên thì bậc của đồ thị giảm đi 2 và sau khi xoá hết tất cả các cạnh và các khuyên của đồ thị thì bậc của đồ thị còn lại là bằng 0. Từ nhận xét trên, hiên nhiên ta có đẳng thức deg(G) = 2|E| (đpcm) Định lý 2: Giả sử G = (V,E) là đồ thị hữu hạn. Khi đó số các đỉnh bậc lẽ của đồ thị là một số chẵn. Chứng minh: Giả sử V = {v1,v2, vn } và trong n đỉnh có k đỉnh bậc lẻ là v1,v2, ,vk. Các đỉnh còn lại có bậc chẵn là vk+1, vk+2, vn I Ở đây ta có deg(vi) = 2mi+1 với i=1,2 ,k và deg(vj) = 2mj với j=k+1, ,n. mi,mj là các số nguyên dương. k n + Theo định lý 1 ta có: deg(G) = ∑deg(vi ) ∑deg(v j ) = 2|V| = 2n i=1 j=k+1 k k k = + = + Do ∑deg(vi ) ∑∑(2mi 1) 2 mi k i=1 i==11i n n n = = và ∑∑∑deg(v j ) 2m j 2 m j j=+k+111j=+k j=k k n k n  k n  Suy ra deg(G) = deg(v ) + deg(v ) = 2 m + k + 2 m = 2 m + m  + k =2n ∑ i ∑ j ∑∑i j ∑ i ∑ j  i=1 j=k+1 i=+11j=k  i=1 j=k +1  Từ đó suy ra k là một số chẵn. (đpcm). Ví dụ 11: Có bao nhiêu cạnh trong một đồ thị có 10 đỉnh, mỗi đỉnh có bậc bằng 5? Giải: Vì bậc của đồ thị bằng 10.5 = 50, mà 2.e = 50 Suy ra e = 25 1.3 Đường và chu trình trong đồ thị Định nghĩa 10: Cho đồ thị G = (V,E). Một đường đi trong đồ thị là một dãy vi1ei1vi2ei2 vijeij vikeikvik+1, Trong đó vij∈V là các đỉnh, eij∈E là các cạnh sao cho với ∀j ∈{1,2, , k}thì đỉnh vij và đỉnh vij+1 là hai đỉnh kề nhau. Đường đi đó xuất phát từ đỉnh vij và kết thúc tại đỉnh vik+1(hoặc ngược lại). Độ dài của đường bằng số các cạnh (hoặc cung) trong đường đi đó. Chu trình trong đồ thị là một đường đi có đỉnh xuất phát và đỉnh kết thúc trùng nhau. Ví dụ 12: a b d e c Trong đồ thị trên ta co: 5 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ a,b,e,d là một đường đi có độ dài 3 c,e,b,a,d là một đường đi có độ dài 4 a,d,c,a là một chu trình có độ dài 3 d,a,b,c,d là một chu trình có độ dài 4 a,b,d không phải là một đường đi a,d,e,a không phải là một chu trình Ví dụ 13: a b d c Trong đồ thị trên ta có: a,c,d là một đường đi có độ dài 2 c,d,a,b là một đường đi có độ dài 3 a,b,d,a là một chu trình có độ dài 3 a,c,d,b,d,a là một chu trình có độ dài 5 a,c,b không phải là một đường đi a,b,c,a không phải là một chu trình Định nghĩa 11: Đường hay chu trình trong đồ thị được gọi là đơn nếu nó đi qua mỗi cạnh (cạnh của đường hay chu trình) không quá một lần. Đường hay chu trình trong đồ thị được gọi là sơ cấp nếu nó đi qua mỗi đỉnh đúng một lần. Ví dụ 14: a b d c Với đồ thị trên ta có: a,b,c,d là một đường đi đơn trong đồ thị d,a,b,c,d là một chu trình đơn trong đồ thị a,b,c,d,a là một chu trình sơ cấp của đồ thị a,b,c là một đường sơ cấp Định lý 3: Giả sử G = (V,E) là đồ thị vô hướng. Nếu trong đồ thị mà mỗi đỉnh v ∈V đều có bậc deg(v)≥ 2 thì đồ thị có chu trình sơ cấp Chứng minh: Xét tất cả các đường sơ cấp có thể có trong đồ thị. Rõ ràng số các đường này là hữu hạn, vì vậy trong số các đường sơ cấp đó sẽ tồn tại một đường có độ dài lớn nhất. Giả sử đó là đường w: vi1ei1vi2ei2 vijeijvij+1dạng hình học của nó là: v v v v v i1 i2 i3 ij ij+1 ei1 ei2 eij 6 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Theo giả thiết deg(vij) ≥ 2 nên phải tồn tại ít nhvi0ấ t một đỉnh vi0 và một cạnh nối đỉnh vi1 và vi0. Đỉnh vi0 phải trùng với một đỉnh, chẳng hạn là đỉnh vij trong đường w, vì nếu không trùng thì đường w không phải là đường sơ cấp dài nhất, điều này trái với giả thiết w là đường có độ dài lớn nhất. Điều này chứng tỏ phải tồn tại một chu trình trong đồ thị đang xét. Vì các đường đang xét là các đường sơ cấp, cho nên chu trình này là chu trình sơ cấp. Định lý đã được chứng minh. 1.4 Đồ thị con, đồ thị bộ phận và đồ thị liên thông Định nghĩa 12: Cho đồ thị G = (V,E) a) Nếu trong đồ thị G ta bỏ đi một số đỉnh nào đó và các cạnh chứa các đỉnh đó thì phần còn lại của đồ thị được gọi là đồ thị con của đồ thị G. b) Nếu trong đồ thị G ta bỏ đi một số cạnh nào đó và 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. Ví dụ 15: Đồ thị G Một số đồ thị con của đồ thị G Mộ số đồ thị bộ phận của đồ thị G Định nghĩa 13: Cho đồ thị G = (V,E) a) Hai đỉnh u,v ∈ V được gọi là liên thông nếu tồn tại một đường đi nối hai đỉnh u,v với nhau. b) Đồ 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ụ 16: Các đồ thị liên thông 7 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Các đồ thị không liên thông Định nghĩa 14: Cho đồ thị có hướng G = (V,E) a) Đồ thị G được gọi là liên thông mạnh nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó. b) Đồ thị G được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng với nó là đồ thị liên thônng. Ví dụ 17: Đồ thị liên thông mạnh Đồ thị liên thông yếu Định nghĩa 15: Cho đồ thị G = (V,E), H = (W,F) là đồ thị con của G. Nếu H là đồ thị liên thông thì H được gọi là thành phần liên thông của G. Ví dụ 18: H I G Trong ví dụ này H, I là các thành phần liên thông của G Định lý 4: Đồ thị G = (V,E) là liên thông khi và chỉ khi nó có một thành phần liên thông. Chứng minh: Điều khẳng định được trực tiếp suy ra từ các định nghĩa. Định lý 5: (Công thức Euler) Cho G = (V,E) là một đơn đồ thị phẳng liên thông với e cạnh và v đỉnh. Gọi r là số miền trong biểu diễn phẳng của G. Khi đó r = e – v +2. 8 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Chứng minh: Trước tiên ta xác định biểu diễn phẳng của G. Ta sẽ chứng minh định lý bằng cách xây dựng một dãy các đồ thị con G1, G2, ,Ge = G, ở mỗi bước ghép thêm một cạnh vào đồ thị ở bước trước. Để làm điều này ta sử dụng định nghĩa đệ quy say: Lấy tuỳ ý một cạnh của G để nhận được G1. Để nhận được Gn từ Gn-1 ta thêm tuỳ ý một cạnh liên thuộc với một cạnh của Gn-1 và thêm một đỉnh khác liên thuộc với cạnh mới đó nếu đỉnh đó chưa có trong Gn-1, điều này làm được vì G là liên thông. G sẽ nhận được sau khi e cạnh được ghép thêm vào các đồ thị tạo ra trước. Gọi rn, en, và vn tương ứng là số miền, số cạnh, số đỉnh của biểu diễn phẳng của Gn sinh ra. Ta sẽ chứng minh bằng quy nạp biểu thức r = e – v +2 Với G1 thì biểu thức r1 = e1 – v1 + 2 là đúng, vì r1 = 1, e1 = 1, v1 = 2, điều này được thể hiện như hình sau: R1 G1 Giả sử ta có rn = en – vn + 2. Gọi (an+1, bn+1) là cạnh gộp vào Gn để được Gn+1. Khi đó có hai khả năng xảy ra. Trường hợp thứ nhất hai đỉnh an+1, bn+1 đã thuộc Gn. Khi đó nó phải ở trên biên của miền chung R nếu không thì không thể gộp cạnh (an+1,bn+1) vào Gn mà không có các cạnh cắt nhau (Gn+1 là phẳng). Cạnh mới này sẽ chia miền R thành hai miền con. Do đó rn+1 =rn+1, en+1 = en+1, vn+1 = vn. Do vậy ta có công thức rn+1 = en+1 – vn+1 +2. Trường hợp này được minh hoạ như sau: a n+1 R b n+1 Trường hợp thứ hai, một trong hai đỉnh của cạnh chưa thuộc Gn. Ta giả sử an+1 thuộc Gn còn bn+1 không thuộc. Trong trường hợp này cạnh thêm (an+1, bn+1) không sinh ra miền mới nào vì bn+1 phải nằm trong miền có an+1 và ở trên biên của nó (Gn+1 phẳng). Do đó rn+1 = rn. Nhưng en+1 = en+1 và vn+1 = vn+1. Mỗi vế của công thức không đổi nên công thức vẫn đúng, hay rn+1=en+1 – vn+1 +2. Trường hợp này được minh hoạ như sau: an+1 bn+1 R Vậy với mọi n ta đều có rn = en – vn +2. Vì đồ thị gốc là Ge nhận được sau khi thêm e cạnh, định lý được chứng minh. Ví dụ 19: Cho đơn đồ thị G phẳng liên thông có 20 đỉnh, mỗi đỉnh đều có bậc là 3. Hỏi biểu diễn phẳng của đồ thị này chia mặt phẳng thành bao nhiêu miền? Giải: Ta có v = 20, deg(G) = v.3 = 20.3 = 60 = 2.e Suy ra e = 30. Áp dụng công thức Euler : r = e – v +2 = 12. Vậy mặt phẳng bị chia thành 12 miền. 9 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Bài tập chương 1 Bài 1: Hãy gọi tên (Đồ thị đơn, đa, đầy đủ, ) các đồ thị cho dưới đấy G1 G2 G3 G4 G5 G6 G7 G8 Bài 2: Vẽ đồ thị vô hướng và đồ thị có hướng cho bởi G = (V,E) V = {A, B, C, D, E, G, H} G = {(A,B), (B,C), (A,C), (G,H), (H,E), (E,A), (D,A)} Bài 3: Hãy tìm số đỉnh, số cạnh, bậc của mỗi đỉnh trong các đồ thị vô hướng cho dưới đây. Xác định các đỉnh cô lập và đỉnh treo. Xác định bậc của đồ thị và kiểm tra xem nó có bằng hai lần số cạnh không? v1 v2 a b c d e f v4 v3 v5 G1 G2 Bài 4: 10 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Hãy tìm số đỉnh, số cạnh, bậc ra, bậc vào và bậc của mỗi đỉnh trong các đồ thị vô hướng cho dưới đây. Xác định các đỉnh cô lập và đỉnh treo. Xác định bậc của đồ thị và kiểm tra xem nó có bằng hai lần số cạnh không? v2 a b c v1 d e f v3 G1 G2 Bài 5: Có tồn tại đồ thị đơn có 10 đỉnh, mỗi đỉnh có bậc bằng 5 không? Bài 6: Trong một cuộc liện hoan mọi người bắt tay nhau. Hãy chỉ ra rằng tổng số lượt người được bắt tay được bắt tay là một số chẵn.(Giả sử rằng không ai tự bắt tay mình) Bài 7: Liệt kê tất cả các đồ thị con của đồ thị sau a e c b d G Bài 8: Cho đơn đồ thị phẳng liên thông G với 5 đỉnh và 9 cạnh. Hỏi đồ thị này chia mặt phẳng thành bao nhiêu miền?. Bài 9: Có bao nhiêu cạnh trong một đồ thị có 6 đỉnh mà hai đỉnh có bậc 4, hai đỉnh có bậc 6, hai đỉnh có bậc 8 ?. Bài 10: Chỉ ra môt vài đường đơn và chu trình đơn có thể có trong đồ thị sau: v1 v2 e1 e2 e3 e4 11 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ v3 e5 e6 v5 v4 Bài 11: Chỉ ra tất cả các đường sơ cấp và chu trình sơ cấp có thể có của đồ thị sau v1 e6 e5 e2 e1 v2 e3 v3 e4 v4 Bài 12: Mỗi danh sách các đỉnh sau đây có tạo nên đường đi trong đồ thị đã cho hay không? Đường đi nào là đơn? Đường đi nào là chu trình? Độ dài của các đường đi này là bao nhiêu? a) a, b, e, c, b b) a, d, b, e, a a b c c) a, d, a, d, a d) a, b, e, c, b, d, a d e Bài 13: Trong các đồ thị cho dưới đây, đồ thị nào liên thông, đồ thị nào không liên thông? G1 G2 G3 G4 G5 12 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Chương 2 CÁC PH ƯƠNG PHÁP BIỂU DIỄN ĐỒ THN (6 tiết) 2.1 Biểu diễn bằng hình học Cho đồ thị G = (V, E), khi đó ta có thể biểu diễn G bằng phương pháp hình học như sau: Mỗi v∈V ta đặt tương ứng với một điểm trong mặt phẳng, điểm đó gọi là đỉnh của đồ thị. a) Trường hợp G là đồ thị vô hướng, nếu e = (u,v) ∈V thì trong mặt phẳng, các đỉnh u, v được nối với nhau bởi một cạnh không có hướng. Nếu e = (u,u) ∈V thì tại đỉnh u sẽ có một khuyên. b) Trường hợp G là đồ thị có hướng, Nếu e = (u,v) ∈V thì trong mặt phẳng sẽ có một cung có hướng đi từ u đến v. Nếu u = v thì tại đỉnh u sẽ có một khuyên có hướng vào chính nó. Ví dụ 1: Đồ thị vô hướng G = ({v1, v2, v3, v4}, {(v1,v2), (v2,v3), (v2,v4), (v3,v4), (v4,v4)}) được biểu diễn hình học như sau: v1 v3 v4 v2 Đồ thị có hướng G = ({v1, v2, v3}, {(v1,v1), (v1,v2), (v2,v3), (v3,v1), (v3, v2)}) được biểu diễn hình học như sau: v2 v1 v3 Biểu diễn đồ thị bằng hình học là một cách biểu diễn đơn giản, trực quan nhưng không có nhiều ý nghĩa trong việc xử lý bằng máy tính. 2.2 Biểu diễn bằng ma trận kề (liền kề), ma trận trọng số Xét đơn đồ thị vô hướng G = (V,E), với tập đỉnh V = {v1, v2, ,vn}, tập cạnh E = {e1, e2, , em}. Ta gọi ma trận kề của đồ thị G là ma trận: A = {aij: i,j = 1,2, ,n} với các phần tử aij được xác định theo quy tắc sau: aij = 1 nếu (vi,vj)∈E aij = 0 nếu (vi,vj)∉E , i,j = 1, 2, , n Ví dụ 2: Cho đồ thị vô hướng G = ({v1, v2, v3},{(v1,v1), (v1,v2), (v1,v3), (v2,v3)}) Ma trận kề của G là 13 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ V1 v2 v3 v1 1 1 1 v2 1 0 1 v3 1 1 0 Ví dụ 3: Cho đồ thị vô hướng G như sau: 1 2 3 4 5 Ma trận kề của G là 1 2 3 4 5 1 0 1 0 1 0 2 1 0 1 0 1 3 0 1 0 1 0 4 1 0 1 0 1 5 0 1 0 1 0 Chú ý: Ma trận kề của một đồ thị tuỳ thuộc vào thứ tự liệt kê các đỉnh. Do vậy có tới n! ma trận kề khác nhau của một đồ thị n đỉnh vì có n! cách sắp xếp n đỉnh. Các tính chất của ma trận kề của đồ thị đơn vô hướng: a) Ma trận kề của đơn đồ thị vô hướng n đỉnh là một ma trân vuông đối xứng cấp nxn. b) Tổng các phần tử trên hàng i (cột j) của ma trận kề chính bằng bậc của đỉnh i (đỉnh j). c) Nếu kí hiệu a p ,i, j = 1,2, , n là các phần tử của ma trận tích A p = A.A A ij 123 p p = Khi đó aij ,i, j 1,2, , n cho ta số đường đi khác nhau từ đỉnh i đến đỉnh j qua p-1 đỉnh trung gian. Ma trận kề của đồ thị đơn có hướng cũng được định nghĩa tương tự, nhưng lưu ý ma trận này là không đối xứng. Ví dụ 4: Cho đơn đồ thị có hướng G 2 3 1 14 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Ma trận kề của G là 4 1 2 3 4 1 0 1 1 0 2 0 0 0 1 3 0 1 0 0 4 1 0 0 0 Trên đây ta chỉ mới xét các đơn đồ thị, đối với đa đồ thị thì ma trận kề cũng được xây dựng hoàn toàn tương tự, chỉ khác là thay vì ghi 1 vào vị trí aij nếu (vi,vj) là cạnh (cung) của đồ thị, ta sẽ ghi k là số cạnh (cung) nối hai đỉnh vi và vj. Ví dụ 5: Cho đa đồ thị vô hướng G như sau: 3 1 2 4 5 Ma trận kề của G là 1 2 3 4 5 1 0 1 1 3 1 2 1 0 1 1 1 3 1 1 1 0 2 4 3 1 0 0 0 5 1 1 2 0 0 Ví dụ 6: Cho đa đồ thi có hướng G như sau: v4 v3 v2 v1 15 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Ma trận kề của G là V1 v2 v3 v4 v1 0 0 0 0 v2 1 0 2 1 v3 1 1 0 0 v4 1 1 0 0 Trong rất nhiều ứng dụng của lý thuyết đồ thị, mỗi cạnh e = (u,v) của đồ thị được gắn một con số c nào đó (c(e), c(u,v)) gọi là trọng số của cạnh e. Đồ thị có các cạnh được gán trọng số gọi là đồ thị có trọng số. Trong trường hợp đồ thị có trọng số, để biểu diễn đồ thị thay vì dùng ma trận kề ta dùng ma trận trọng số như sau: C = cij, i,j=1, 2, , n Với cij = c(eij)) nếu eij ∈E cij = θ nếu eij ∉E , i = 1,2, ,n; j = 1,2, ,n Trong đó số θ tuỳ từng trường hợp cụ thể, có thể được đặt bằng một trong các giá trị sau: 0, - ∞ , + ∞ . Ví dụ 7: Cho đồ thị vô hướng có trọng số G như sau v1 10 8 v5 5 v2 v4 6 3 7 v3 Ma trận trọng số của G là v1 v2 v3 v4 v5 v1 0 0 0 10 8 v2 0 0 7 0 5 v3 0 7 0 3 0 v4 10 0 3 0 6 v5 8 5 0 6 0 16 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Ví dụ 8: Cho đồ thị có hướng có trọng số G như sau: b 7 c 4 3 a 4 9 d 5 7 e Ma trận trọng số của G là a B c d e a 0 0 0 0 5 b 4 0 7 0 4 c 0 0 0 3 0 d 0 0 0 0 7 e 0 0 9 0 0 Ưu điểm lớn nhất của phương pháp biểu diễn đồ thị bằng ma trận kề (hoặc ma trận trọng số) là để trả lời câu hỏi: Hai đỉnh u, v có kề nhau trên đồ thị hay không, chúng ta chỉ phải thực hiện một phép so sánh. Nhược điểm lớn nhất của phương pháp này là: Không phụ thuộc vào số cạnh của đồ thị, ta luôn phải sử dụng n2 đơn vị bộ nhớ để lưu trữ ma trận kề của nó. 2.3 Biểu diễn bằng ma trận liên thuộc đỉnh - cạnh Giả sử G = (V,E) là một đồ thị vô hướng với tập đỉnh V = {v1,v2, , vn}, và tập các cạnh E = {e1,e2, ,em}. Khi đó ma trận liên thuộc đỉnh - cạnh A = aij, i = 1,2, n, j = 1,2, m của nó được xác định như sau: Aij = 1 nếu cạnh ej nối với đỉnh vi Aij = 0 nếu cạnh ej không nối với đinh vi, i = 1,2, ,n, j = 1,2, ,m Ví dụ 9: Cho đồ thị G như sau v1 v2 e6 v3 e2 e4 e5 e1 e3 v4 v5 Khi đó ma trận liên thuộc đỉnh - cạnh của G như sau 17 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ e1 e2 e3 e4 e5 e6 v1 1 1 0 0 0 0 v2 0 0 1 1 0 1 v3 0 0 0 0 1 1 v4 1 0 1 0 0 0 v5 0 1 0 1 1 0 Ma trận liên thuộc cũng có thể được dùng để biểu diễn đồ thị có cạnh bội và khuyên Ví dụ 10: Cho đồ thị G như sau v1 v2 e4 v3 e1 e2 e3 e7 e6 e5 v4 v5 e8 Khi đó ma trận liên thuộc đỉnh cạnh của G là e1 e2 e3 e4 e5 e6 e7 e8 v1 1 1 1 0 0 0 0 0 v2 0 1 1 1 0 1 1 0 v3 0 0 0 1 1 0 0 0 v4 0 0 0 0 0 0 1 1 Ma trận liên thuôc đỉnh - cạnh v5 0 0 0 0 1 1 0 0 còn rất hay được sử dụng trong các bài toán liên quan đến đồ thị có hướng mà trong đó phải xử lý các cung của đồ thị. Cho G = (V,E) , V = {v1,v2, ,vn}, E = {e1,e2, ,em}, là đồ thị có hướng. Khi đó ma trận liên thuộc đỉnh - cạnh A = aij , i = 1,2, ,n; j = 1,2, , m của G được xác định như sau: aij = 1 nếu đỉnh vi là đỉnh đầu của cung ej aij =-1 nếu đỉnh vi là đỉnh cuối của cung ej aij = 0 nếu đỉnh vi không là đầu mút của cung ej 18 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Ví dụ 11: Cho ma trận G như sau 2 4 1 6 3 5 Ma trận liên thuộc cạnh - đỉnh của G như sau (1,2) (1,3) (2,3) (2,4) (3,5) (4,5) (5,2) (5,6) (6,4) 1 1 1 0 0 0 0 0 0 0 2 -1 0 1 1 0 0 -1 0 0 3 0 -1 -1 0 1 0 0 0 0 4 0 0 0 -1 0 1 0 0 -1 5 0 0 0 0 -1 -1 1 1 0 6 0 0 0 0 0 0 0 -1 1 2.4 Biểu diễn bằng danh sách cạnh (cung) Xét đồ thị G = (V,E), với |V| = n, |E| = m. Để biểu diễn đồ thị theo phương pháp danh sách cạnh (cung) chúng ta sẽ lưu trữ danh sách tất cả các cạnh (cung) của đồ thị vô hướng (có hướng). Mỗi cạnh (cung) e = (u,v) của đồ thị sẽ tương ứng với hai biến Dau[e] và Cuoi[e]. Như vậy để lưu trữ đồ thị ta cần sử dụng 2m đơn vị ô nhớ. Trong trường hợp đồ thị có trọng số ta phải cần thêm m đơn vị ô nhớ nữa để lưu trữ trọng số của các cạnh. Ví dụ 12: Cho đồ thị vô hướng G như sau 3 4 1 6 2 5 Danh sách cạnh của G như sau Dau Cuoi 1 2 1 3 2 3 2 5 3 4 4 5 4 6 5 6 19 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Ví dụ 13: Cho đồ thị có hướng G như sau v2 v1 Khi đó danh sách cạnh của G là Dau Cuoi v1 v2 v3 v1 v3 v2 v3 v3 v2 2.5 Biểu diễn bằng danh sách kề Trong rất nhiều vấn đề ứng dụng của lý thuyết đồ thị, cách biểu diễn đồ thị dưới dạng danh sách kề là cách biểu diễn thích hợp được sử dụng. Trong cách biểu diễn này, với mỗi đỉnh v của đồ thị chúng ta lưu trữ danh sách các đỉnh kề với nó. Để làm được điều này chúng ta có thể sử dụng cấu trúc mảng các mảng (mảng hai chiều) hoặc mảng các danh sách liên kết. Ví dụ 1: Cho đồ thị vô hướng G như sau v1 v2 v5 v4 v3 Khi đó, danh sách kề lưu trữ dưới dạng mảng như sau v1 v2 v4 v5 v2 v1 v3 v4 v3 v2 v4 v5 v4 v1 v2 v3 v5 v5 v1 v3 v4 Danh sách kề lưu trữ dưới dạng danh sách liên kết như sau: v1 v2 v4 v5 nill v2 v1 v3 v4 nill v3 v2 v4 v5 nill v4 v1 v2 v3 v5 nill v5 v1 v3 v4 nill Chúng ta có rất nhiều phương pháp khác nhau để biểu diễn đồ thị, mỗi phương pháp đều có những ưu và nhược điểm riêng của nó. Vì vậy việc lựa chọn phương pháp biểu diễn đồ thị sao cho việc xử lý nó có hiệu quả nhất phải tuỳ thuộc vào từng bài toán và giải thuật cụ thể. Cài đặt thuật toán: (nhập và hiển thị DS kề của một đồ thị biểu diễn bằng danh sách lien kết: // // Chuong trinh nhap va in ra danh sach ke. 20 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ // #include #include #include #define VMAX 100 //So dinh toi da cho mot do thi typedef struct pp //Cau truc tu tro { int v; struct pp *next; }Link; Link *Ke[VMAX]; //Danh sach ke cua do thi int n; char ch; //So dinh cua do thi // // Ham nhap danh sach ke cua do thi co n dinh // void nhap_dsk(Link *Ke[], int n) { int i,v; Link *pd,*p; //Khoi tao mang cac danh sach cac dinh ke cua cac dinh for(i=1;i v=i; Ke[i]->next = NULL; } //Nhap danh sach cac dinh ke cua cac dinh for(i=1;i next = (Link*)malloc(sizeof(Link)); p=p->next; 21 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ } p->v=v; p->next = NULL; } Ke[i]->next = pd; } } // // Ham hien thi danh sach ke cua do thi co n dinh // void in_dsk(Link *Ke[], int n) { int i; Link *pd; printf("\nDanh sach ke cua cac dinh cua do thi:\n"); printf("\n \n"); for(i=1;i v); pd = Ke[i]->next; while(pd!=NULL) { printf("%5d",pd->v); pd=pd->next; } } } // Ham in tieu de cua chuong trinh // void tieu_de() { printf("\n CHUONG TRINH CAI DAT CAC THUAT TOAN TIM KIEM TREN DO THI"); printf("\n \n\n"); } // // Ham hien thi Menu chon chuc nang cua chuong trinh // char menu() { printf("\n Menu chon chu nang"); printf("\n \n"); printf("\n\n 1. Nhap do thi cho boi danh sach ke"); printf("\n\n 2. Hien thi danh sach ke cua do thi"); printf("\n\n 5. Ket thuc chuong trinh"); printf("\n\n "); printf("\n\n Ban chon:"); ch=getche(); return ch; } // 22 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ // Chuong trinh chinh // void main() { int kt=0,i; char ch; do { clrscr(); tieu_de(); ch = menu(); switch(ch) { case '1': //Nhap danh sach ke cua do thi clrscr(); tieu_de(); kt=1; printf("\n\n1.Nhap danh sach ke cua do thi"); printf("\n \n\n"); printf("\n\nSo dinh cua do thi n ="); scanf("%d",&n); nhap_dsk(Ke,n); printf("\n\n\n\n "); printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!"); getch(); break; case '2': //Hien thi danh sach ke cua do thi clrscr(); tieu_de(); printf("\n\n2.In danh sach ke cua do thi"); printf("\n \n\n"); if(kt) in_dsk(Ke,n); else printf("\nDo thi chua duoc nhap vao!"); printf("\n\n\n\n "); printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!"); getch(); break; case '5': //Ket thuc chuong trinh printf("\n\nXin cam on ban da su dung chuong trinh!"); getch(); break; } }while(ch!='5'); } 23 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Chương 3 CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THN VÀ ỨNG DỤNG Trong lý thuyết đồ thị, có rất nhiều thuật toán được xây dựng dựa trên cơ sở duyệt qua tất cả các đỉnh của đồ thị sao cho mỗi đỉnh chỉ được duyệt đúng một lần. Do vậy, việc xây dựng các thuật toán cho phép duyệt qua tất cả các đỉnh của đồ thị một cách có hệ thống là một vấn đề quan trọng thu hút sự quan tâm nghiên cứu của nhiều nhà khoa học. Các thuật toán như vậy được gọi chung là thuật toán tìm kiếm trên đồ thị. Trong chương này chúng ta sẽ nghiên cứu hai thuật toán tìm kiếm cơ bản trên đồ thị là Thuật toán tìm kiếm theo chiều sâu (Depth First Search) và Thuật toán tìm kiếm theo chiều rộng (Breadth First Search) và một vài ứng dụng của hai thuật toán này. Để đơn giản cho việc trình bày, chúng ta sẽ xét đồ thị vô hướng G = (V,E), |V| = n, |E| = m; Đồ thị có hướng sẽ được suy ra một cách tương tự với một vài điểm đặc biệt cần chú ý. Để đánh giá hiệu quả của các thuật toán này, chúng ta chỉ chú trọng đến việc đánh giá độ phức tạp tính toán của thuật toán, tức số phép toán mà thuật toán cần thực hiện trên mọi bộ dữ liệu vào trong trường hợp xấu nhất. Độ phức tạp tính toán này được biểu diễn bằng một hàm số của kích thước dữ liệu đầu vào. Cụ thể ở đây kích thước của dữ liệu vào sẽ là số đỉnh n và số cạnh m của đồ thị. Khi đó độ phức tạp tính toán của thuật toán sẽ được biểu diễn bằng hàm hai biến f(n,m) là số phép toán nhiều nhất mà thuật toán cần phải thực hiện đối với mọi đồ thị n đỉnh, m cạnh. Để so sánh tốc độ tăng của hai hàm nhận giá trị không âm f(n) và g(n) chúng ta sử dụng ký hiệu f(n) = O(g(n)). Điều này có nghĩa tương đương với việc tìm được các hằng số dương C và N sao cho: f (n) ≤ Cg(n);∀n ≥ N Trường hợp mở rộng, nếu f(n1,n2, ,nk) và g(n1,n2, ,nk) là các hàm biểu diễn, ta viết: f(n1,n2, ,nk)=O(g(n1,n2, ,nk)) ⇔ Tìm được các hằng số dương C và N sao cho: f(n1,n2, ,nk) ≤ Cg(n1,n2, ,nk) với ∀n ≥ N Nếu độ phức tạp tính toán của thuật toán là O(g(n)) thì ta nói là thuật toán có thời gian tính toán cỡ O(g(n)). 3.1 Thuật toán tìm kiếm theo chiều sâu trên đồ thị (Depth First Search) Ý tưởng chính của thuật toán tìm kiếm theo chiều sâu có thể được hiểu như sau: Ban đầu tất cả các đỉnh của đồ thị đều chưa được duyệt đến, ta sẽ bắt đầu việc tìm kiếm từ một đỉnh nào đó, giả sử đỉnh đó là v1. Sau đó chọn u là một đỉnh (có thể chọn tuỳ ý) trong danh sách các đỉnh kề với đỉnh v1 mà chưa được xét đến và lặp lại quá trình tìm kiếm đối với đỉnh u này. Ở bước tổng quát, giả sử đang xét đỉnh vk, nếu trong các đỉnh kề với đỉnh vk ta tìm được đỉnh w là đỉnh chưa được duyệt đến thì ta sẽ lại bắt đầu quá trình tìm kiếm từ đó và w sẽ trở thành đỉnh đã được duyệt qua. Nếu không còn đỉnh nào kề với đỉnh vk là chưa được duyệt đến thì ta nói rằng đỉnh này đã được duyệt xong và quay lại tiếp tục tìm kiếm từ đỉnh mà trước đó ta đến được đỉnh vk. Quá trình cứ tiếp tục như vậy cho đến khi tất cả các đỉnh của đồ thị đã được duyệt hết. Như vậy ta có thể hiểu một cách đơn giản là việc tìm kiếm theo chiều sâu trên đồ thị bắt đầu từ đỉnh v được thực hiện trên cơ sở tìm kiếm theo chiều sâu từ các đỉnh chưa được duyệt kề với v. Quá trình này được mô tả bằng thủ tục đệ quy sau: Procedure DFS(v) 24 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ (* Tìm kiếm theo chiều sâu trên đồ thị bắt đầu từ đỉnh v *) (* Các biến Chuaxet và Ke là biến toàn cuc *) Begin Xet_dinh(v); Chuaxet[v]:=False; For u∈Ke(v) do If Chuaxet[u] Then DFS(u); End; (* Chương trình chính thực hiện thủ tục *) BEGIN (* Khởi tạo biến toàn cục Chuaxet *) For v ∈ V do Chuaxet[v]:=True; (* Duyệt đồ thị *) For v ∈ V do If Chuaxet[v] Then DFS(v); END. Như vậy, với thuật toán trên đây rõ ràng mỗi lệnh gọi DFS(v) sẽ thực hiện duyệt qua tất cả các đỉnh cùng thành phần liên thông với đỉnh v, bởi vì sau mỗi khi xét đỉnh v là lệnh gọi đến thủ tục DFS đối với các đỉnh kề với v. Mặt khác, do mỗi khi thăm đỉnh v xong, biến Chuaxet[v] được gán giá trị False nên mỗi đỉnh sẽ được thăm đúng một lần. Thuật toán lần lượt sẽ tiến hành tìm kiếm từ các đỉnh chưa được xét đến, vì vậy nó sẽ duyệt được qua tất cả các đỉnh của đồ thị. (Kể cả đồ thị không liên thông). Dộ phức tạp tính toán của thuật toán được đánh giá như sau: Trước hết ta thây rằng số phép toán cần thực hiện trong hai chu trình của thuật toán (Hai vòng For ở chương trình chinh) có cỡ là n. Còn thủ tục DFS phải thực hiện không quá m lần. Do đó tổng số phép toán cần thực hiện trong các thủ tục này có cỡ là n+m. Vậy độ phức tạp tính toán của thuật toán là O(n+m). Ví dụ 1: Xét đồ thị vô hướng cho bởi hình dưới đây (Hình 3.1) 2 7 6 3 1 8 4 5 9 10 Hình 3.1 Giả sử danh sách kề của đồ thị được lưu như sau: 1: 2 3 4 2: 1 3 3: 1 2 5 8 4: 1 9 10 25 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ 5: 3 8 6: 7 8 7: 6 8 8: 3 5 6 7 9: 4 10 10: 4 9 Khi đó thứ tự các đỉnh được duyệt theo thuật toán trên bắt đầu từ đỉnh 1 là: 1 2 3 5 8 6 7 4 9 10 Thuật toán tìm kiếm theo chiều sâu trên đồ thị có hướng cũng được thực hiện tương tự, trong trường hợp này thủ tục DFS(v) sẽ cho phép duyệt tất cả các đỉnh u của đồ thị mà từ v có đường đi tói u. Độ phức tạp tính toán của thuật toán trong trường hợp này vẫn là O(n+m). Ví dụ 2: Xét đồ thị có hướng cho bởi hình dưới đây (Hình 3.2) 2 1 5 7 9 3 4 8 6 Hình 3.2 Giả sử danh sách các đỉnh kề của đồ thị được lưu như sau: 1: 3 2: 1 4 3: 4: 5 5: 7 8 6: 5 7: 2 9 8: 6 9: Khi đó thứ tự các đỉnh được duyệt theo thuật toán tìm kiếm theo chiều sâu bắt đầu từ đỉnh 1 là: 1 3 2 4 5 7 9 8 6 3.2 Thuật toán tìm kiếm theo chiều rộng trên đồ thị (Breadth First Search) Tư tưởng chính của phương pháp tìm kiếm theo chiều rộng trên đồ thị có thể được hiểu như sau: Ban đầu tất cả các đỉnh của đồ thị là chưa được xét đến, ta sẽ bắt đầu việc tìm kiếm từ một đỉnh nào đó của đồ thị, giả sử đỉnh đó là v1. Khi duyệt đỉnh v1 ta sẽ để ý tới tất cả các đỉnh v11, v12, , v1k 26 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ kề với đỉnh v1 mà chưa được xét đến để ngay sau đó lần lượt xét tới các đỉnh này, khi duyệt đỉnh v1i (i=1,2, k) ta lại để ý tới tất cả các đỉnh kề với nó mà chưa được xét đến để rồi lần lượt xét đến các đỉnh đó. Qua trình sẽ cứ như vậy cho đến khi nào tất cả các đỉnh của đồ thị đều được xét hết. Ta có thể hình dung phương pháp này như hình ảnh của vết dầu loang, từ một điểm trên mặt phẳng dầu sẽ loang sang ngay các điểm lân cận với điểm đó. Với phương pháp này ta thấy rằng các đỉnh kề với một đỉnh của đồ thị sẽ được xếp hàng theo thứ tự để được lần lượt xét tới, do đó chúng ta có thể dùng cơ chế hàng đợi để thực hiện công việc này. Thủ tục mô tả phương pháp này như sau Procedure BFS(v) (* tìm kiếm theo chiều rộng bắt đầu từ đỉnh v *) (* Các biến Chuaxet, Ke là toàn cục *) Begin Queue : = φ Queue ⇐ v; (* Nạp v vào Queue *) Chuaxet[v]:=False; While Queue ≠ φ do Begin p ⇐ Queue; (* Lấy p ra khỏi Queue *) Xet_dinh(p); For u ∈Ke(p) do If Chuaxet[u] then Begin Queue ⇐ u; Chuaxet[u]:=False; End; End; End; (* Chương trình chính thực hiện thủ tục *) BEGIN (* Khởi tạo biến toàn cục Chuaxet *) For v ∈ V do Chuaxet[v]:=True; (* Duyệt các đỉnh *) For v ∈ V do If Chuaxet[v] then BFS(v); END. Với thuật toán này ta cũng thấy rằng mỗi lệnh gọi BFS(v) sẽ thực hiện duyệt qua các đỉnh cùng thành phần liên thông với đỉnh v. Thủ tục BFS sẽ được thực hiện lần lượt với các đỉnh chưa được duyệt của đồ thị, do đó nó sẽ duyệt hết tất cả các đỉnh của đồ thị. Mặt khác, mỗi khi duyệt xong đỉnh v, biến Chuaxet[v] cũng được gán giá trị False nên mỗi đỉnh sẽ được thăm đúng một lần. Lập luận tương tự thuật toán tìm kiếm theo chiều sâu ta cũng có được độ phức tạp tính toán của thuật toán này là O(n+m). Ví dụ 3 Xét đồ thị vô hướng cho ở ví dụ 1 (hình 3.1) Khi đó thứ tự các đỉnh được duyệt theo thuật toán tìm kiếm theo chiều rộng sẽ là: 1 2 3 4 5 8 9 10 6 7 27 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Ví dụ 4 Xét đồ thị có hướng cho ở ví dụ 2 (Hình 2) Khi đó thứ tự các đỉnh được duyệt theo thuật toán tìm kiếm theo chiều rộng sẽ là: 1 3 2 4 5 7 8 9 6 Dưới đây là chương trình cài đặt hai thuật toán tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng bằng ngôn ngữ lập trình C. Chương trình xử lý trên đồ thị được cho bởi danh sách kề. // // huong trinh cai dat cac thuat toan tim kiem tren do thi // Depth First Search - Breadth First Search // #include #include #include #define VMAX 100 //So dinh toi da cho mot do thi typedef struct pp //Cau truc tu tro { int v; struct pp *next; }Link; Link *Ke[VMAX]; //Danh sach ke cua do thi int chuaxet[VMAX]; //Bien mang dung de danh dau cac dinh da xet Link *Queue; //Hang doi luu thu tu cac dinh se xet int n; //So dinh cua do thi // // Ham nhap danh sach ke cua do thi co n dinh // void nhap_dsk(Link *Ke[], int n) { int i,v; Link *pd,*p; //Khoi tao mang cac danh sach cac dinh ke cua cac dinh for(i=1;i v=i; Ke[i]->next = NULL; } //Nhap danh sach cac dinh ke cua cac dinh for(i=1;i<=n;i++) { pd = NULL; printf("\nNhap cac dinh ke voi dinh %d (nhap 0 de ket thuc!):",i); while(1) { 28 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ scanf("%d",&v); if(v==0) break; if(pd == NULL) { pd = (Link*)malloc(sizeof(Link)); p=pd; } else { p->next = (Link*)malloc(sizeof(Link)); p=p->next; } p->v=v; p->next = NULL; } Ke[i]->next = pd; } } // // Ham hien thi danh sach ke cua do thi co n dinh // void in_dsk(Link *Ke[], int n) { int i; Link *pd; printf("\nDanh sach ke cua cac dinh cua do thi:\n"); printf("\n \n"); for(i=1;i v); pd = Ke[i]->next; while(pd!=NULL) { printf("%5d",pd->v); pd=pd->next; } } } // // Ham nap mot phan tu (mot dinh ) vao hang doi // void Push(Link *u) { Link *q,*p; q=(Link*)malloc(sizeof(Link)); q->v=u->v; q->next=NULL; if(Queue==NULL) 29 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Queue = q; else { p=Queue; while(p->next!=NULL) p=p->next; p->next = q; } } // // Ham lay mot phan tu trong hang doi ra // int Pop() { if(Queue==NULL) return 0; //Quee rong! Link *p; p=Queue; Queue=p->next; int t=p->v; free(p); //Giai phong p return t; } // // Ham de quy tim kiem theo chieu sau bat dau tu mot dinh // void dfs(Link *u) { printf("%3d",u->v); chuaxet[u->v]=0; Link *p = Ke[u->v]->next; while(p!=NULL) { if(chuaxet[p->v]) dfs(p); p=p->next; } } // // Ham tim kiem theo chieu rong bat dau tu mot dinh // void bfs(Link *u) { Queue=NULL; //Khoi tao hang doi Push(u); chuaxet[u->v]=0; while(Queue!=NULL) { int u; 30 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ u=Pop(); printf("%5d",u); Link *p=Ke[u]->next; while(p!=NULL) { if(chuaxet[p->v]) { Push(p); chuaxet[p->v]=0; } p=p->next; } } } // // Ham in tieu de cua chuong trinh // void tieu_de() { printf("\n CHUONG TRINH CAI DAT CAC THUAT TOAN TIM KIEM TREN DO THI"); printf("\n \n\n"); } // // Ham hien thi Menu chon chuc nang cua chuong trinh // char menu() { printf("\n Menu chon chu nang"); printf("\n \n"); printf("\n\n 1. Nhap do thi cho boi danh sach ke"); printf("\n\n 2. Hien thi danh sach ke cua do thi"); printf("\n\n 3. Tim kiem theo chieu sau tren do thi"); printf("\n\n 4. Tim kiem theo chieu rong tren do thi"); printf("\n\n 5. Ket thuc chuong trinh"); printf("\n\n "); printf("\n\n Ban chon:"); char ch=getche(); return ch; } // // Chuong trinh chinh // void main() { int kt=0,i; char ch; do { clrscr(); tieu_de(); 31 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ ch = menu(); switch(ch) { case '1': //Nhap danh sach ke cua do thi clrscr(); tieu_de(); kt=1; printf("\n\n1.Nhap danh sach ke cua do thi"); printf("\n \n\n"); printf("\n\nSo dinh cua do thi n ="); scanf("%d",&n); nhap_dsk(Ke,n); printf("\n\n\n\n "); printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!"); getch(); break; case '2': //Hien thi danh sach ke cua do thi clrscr(); tieu_de(); printf("\n\n2.In danh sach ke cua do thi"); printf("\n \n\n"); if(kt) in_dsk(Ke,n); else printf("\nDo thi chua duoc nhap vao!"); printf("\n\n\n\n "); printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!"); getch(); break; case '3': //Tim kiem theo chieu sau tren do thi clrscr(); tieu_de(); printf("\n\n3.Tim kiem theo chieu sau tren do thi"); printf("\n \n\n"); if(kt) { //Khoi toa bien chuaxet; for(i=1;i<=n;i++) chuaxet[i]=1; //Ket qua tim kiem theo chieu sau printf("\n\nThu tu cac dinh duoc xet theo chieu xau:\n\n"); for(i=1;i<=n;i++) if(chuaxet[i]) dfs(Ke[i]); } else printf("\nDo thi chua duoc nhap vao!"); printf("\n\n\n\n "); printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!"); getch(); break; 32 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ case '4': //Tim kiem theo chieu rong tren do thi clrscr(); tieu_de(); printf("\n\n4.Tim kiem theo chieu rong tren do thi"); printf("\n "); if(kt) { //Khoi toa bien chuaxet; for(i=1;i<=n;i++) chuaxet[i]=1; //Ket qua tim kiem theo chieu rong printf("\n\nThu tu cac dinh duoc xet theo chieu rong:\n\n"); for(i=1;i<=n;i++) if(chuaxet[i]) bfs(Ke[i]); } else printf("\nDo thi chua duoc nhap vao!"); printf("\n\n\n\n "); printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!"); getch(); break; case '5': //Ket thuc chuong trinh printf("\n\nXin cam on ban da su dung chuong trinh!"); getch(); break; } }while(ch!='5'); } 3.3 Ứng dụng của thuật toán tìm kiếm trên đồ thị Trong mục này chúng ta sẽ thực hiện ứng dụng hai thuật toán tìm kiếm trên đồ thị đã trình bầy ở trên vào việc giải hai bài toán cơ bản trên đồ thị là bài toán tìm một đường đi nối hai đỉnh bất kỳ của đồ thị và bài toán kiểm tra tính liên thông của đồ thị (xác định số thành phần liên thông của đồ thị). 3.3.1 Bài toán tìm đường đi giữa hai đính bất kỳ của đồ thị Bài toán Giả sử u và v là hai đỉnh nào đó của đồ thị G = (V,E), Hãy tìm đường đi từ đỉnh u tới đỉnh v. Như chúng ta đã biết hai thủ tục DFS(u) và BFS(u) sẽ cho phép duyệt qua tất cả các đỉnh thuộc cùng một thành phần liên thông với đỉnh u. Vì vậy sau khi thực hiện xong thủ tục mà biến Chuaxet[v] vẫn bằng True (đỉnh v chưa được duyệt) thì có nghĩa là không có đường đi từ u tới v, ngược lại nếu Chuaxet[v] = False thì v thuộc cùng một thành phần liên thông với u, hay tồn tại một đường đi từ u tới v. Trong trường hợp này, để ghi lại đường đi từ u tưới v ta có thể dùng một biến mảng Truoc[v] để lưu lại các đỉnh đi qua trước đỉnh v trong đường đi từ u tới v. Khi đó hai thủ tục DFS(u) và BFS(u) được sửa lại như sau: Thủ tục đệ quy tìm kiếm theo chiều sâu áp dụng cho việc tìm đường đi: 33 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Procedure DFS(u) Begin Chuaxet[u]:=False; For v ∈Ke(u) do If Chuaxet[v] then Begin Truoc[v]:= u; DFS(v); End; End; Thủ tục tìm kiếm theo chiều rộng áp dụng cho việc tìm đường đi: Procedure BFS(u) Begin Queue : = φ Queue ⇐ v; Chuaxet[u]:=False; While Queue ≠ φ do Begin p ⇐ Queue; For v ∈Ke(p) do If Chuaxet[v] then Begin Queue ⇐ v; Chuaxet[v]:=False; Truoc[v]:=p; End; End; End; Theo cách trên, đường đi cần tìm sẽ là: ← = ← = ← ← v t1 : Truoc[v] t2 : Truoc[t1 ] u Ví dụ 5 Xét đồ thị cho bởi hình dưới đây (Hình 3.3) 2 6 5 1 8 3 7 4 Hình 3.3 Nếu áp dụng tìm đường đi theo thuật toán tìm kiếm theo chiều sâu bắt đầu từ đỉnh 1 ta sẽ có: 34 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Truoc[2]=1, Truoc[3]=5, Truoc[4]=5, Truoc[5]=2, Truoc[6]=5, Truoc[7]=8, Truoc[8]=6 Vậy đường đi tìm theo thuật toán tìm kiếm theo chiều sâu từ đỉnh 1 đến đỉnh 8 sẽ là: 1 ← 2 ← 5 ← 6 ← 8 Nếu áp dụng tìm đường đi theo thuật toán tìm kiếm theo chiều rộng bắt đầu từ đỉnh 1 ta sẽ có: Truoc[2]=1, Truoc[3]=1, Truoc[4]=1, Truoc[5]=2, Truoc[6]=5, Truoc[7]=5, Truoc[8]=5 Vậy đường đi tìm theo thuật toán tìm kiếm theo chiều sâu từ đỉnh 1 đến đỉnh 8 sẽ là: 1 ← 2 ← 5 ← 8 Chú ý Xét theo cách duyệt các đỉnh của đồ thị thì ta có thể suy ra được đường đi tìm được theo thuật toán tìm kiếm theo chiều rộng là đường đi có số cạnh ít nhất. 3.3.2 Bài toán kiểm tra tính liên thông của đồ thị Bài toán Hãy cho biết đồ thị gồm bao nhiêu thành phần liên thông và các đỉnh trong từng thành phần liên thông của đồ thị Do hai thủ tục DFS(u) và BFS(u) đều cho phép ta duyệt qua tất cả các đỉnh thuộc cùng một thành phần liên thông với đỉnh u. Do đó số thành phần liên thông của đồ thị chính bằng số lần ta gọi tới thủ tục DFS (hoặc BFS) khi thực hiện việc duyệt qua tất cả các đỉnh của đồ thị. Vậy để giải quyết bài toán trên ta có thể áp dụng một trong hai thủ tục DFS hoặc BFS, trong đó ta cần phải có một biến Sotplt dùng để đếm số thành phần liên thông (số lần gọi thủ tục) và một biến mảng Thanhplt[] đánh dấu các đỉnh thuộc cùng một thành phần liên thông với nhau (có thể dùng ngay mảng Chuaxet[]). Các thủ tục DFS và BFS có thể được sửa lại như sau: Thủ tục DFS: Procedure DFS(u) (* Biến Sotplt và Thanhplt[] là toàn cục *) Begin Chuaxet[u]:=False; Thanhplt[u]:=Sotplt; For v ∈Ke(u) do If Chuaxet[v] then DFS(v); End; Thủ tục BFS: Procedure BFS(u) (* Bien Sotplt và Thanhplt[] là toàn cục *) Begin Queue : = φ Queue ⇐ v; Chuaxet[u]:=False; Thanhplt[u]:=Sotplt; While Queue ≠ φ do 35 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Begin p ⇐ Queue; For v ∈Ke(p) do If Chuaxet[v] then Begin Queue ⇐ v; Chuaxet[v]:=False; Thanhplt[v]:=Sotplt; End; End; End; Khi đó chương trình chính sẽ là: BEGIN Sotplt=0; For v ∈ V do Chuaxet[v]:=True; For v ∈ V do If Chuaxet[v] Then Begin Sotplt:=Sotplt+1; DFS(v); (* BFS(v) *) End; END. Dưới đây là chương trình được viết bằng ngôn ngữ C để giải quyết hai bài toán nói trên // // Chuong trinh cai dat ung dung cua thuat toan tim kiem tren do thi // ( Tim duong di va kiem tra tinh lien thong ) // #include #include #include #define VMAX 100 //So dinh toi da cho mot do thi typedef struct pp //Cau truc tu tro { int v; struct pp *next; }Link; Link *Ke[VMAX]; //Danh sach ke cua do thi int chuaxet[VMAX]; //Bien mang dung de danh dau cac dinh da xet Link *Queue; //Hang doi dung cho thuat toan tim kiem theo chieu rong int sTruoc[VMAX]; //Duong di tim theo thuat tim kiem theo chieu sau int rTruoc[VMAX]; //Duong di tim theo thuat tim kiem theo chieu rong int sotplt; //So thanh phan lien thong int n; //So dinh cua do thi // // Ham nhap danh sach ke cua do thi co n dinh // 36 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ void nhap_dsk(Link *Ke[], int n) { int i,v; Link *pd,*p; //Khoi tao mang cac danh sach cac dinh ke cua cac dinh for(i=1;i v=i; Ke[i]->next = NULL; } //Nhap danh sach cac dinh ke cua cac dinh for(i=1;i next = (Link*)malloc(sizeof(Link)); p=p->next; } p->v=v; p->next = NULL; } Ke[i]->next = pd; } } // // Ham hien thi danh sach ke cua do thi co n dinh // void in_dsk(Link *Ke[], int n) { int i; Link *pd; printf("\nDanh sach ke cua cac dinh cua do thi:\n"); printf("\n "); for(i=1;i v); 37 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ pd = Ke[i]->next; while(pd!=NULL) { printf("%5d",pd->v); pd=pd->next; } } } // // Ham nap mot phan tu (mot dinh ) vao hang doi // void Push(int t) { Link *q,*p; q=(Link*)malloc(sizeof(Link)); q->v=t; q->next=NULL; if(Queue==NULL) Queue = q; else { p=Queue; while(p->next!=NULL) p=p->next; p->next = q; } } // // Ham lay mot phan tu trong hang doi ra // int Pop() { if(Queue==NULL) return 0; //Quee rong! Link *p; p=Queue; Queue=p->next; int t=p->v; free(p); //Giai phong p return t; } // // Ham de quy tim kiem theo chieu sau bat dau tu mot dinh // ( Ap dung de tim duong di giua hai dinh va kiem tra lien thong) // void dfs(int u) { chuaxet[u]=sotplt; Link *p = Ke[u]->next; 38 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ while(p!=NULL) { if(chuaxet[p->v]==1) { sTruoc[p->v]=u; dfs(p->v); } p=p->next; } } // // Ham tim kiem theo chieu rong bat dau tu mot dinh // ( Ap dung de tim duong di giua hai dinh va kiem tra lien thong) // void bfs(int t) { Queue=NULL; //Khoi tao hang doi Push(t); chuaxet[t]=sotplt; while(Queue!=NULL) { int u; u=Pop(); Link *p=Ke[u]->next; while(p!=NULL) { if(chuaxet[p->v]==1) { Push(p->v); chuaxet[p->v]=sotplt; rTruoc[p->v]=u; } p=p->next; } } } // // Ham tim duong di giua hai dinh bat ky tren do thi // Ap dung thuat toan tim kiem theo chieu sau // void dd_dfs() { int dau, cuoi; printf("\n\nTim duong di tu dinh:"); scanf("%d",&dau); printf("den dinh:"); scanf("%d",&cuoi); dfs(dau); if(chuaxet[cuoi]==1) printf("\n\nKhong co duong di tu dinh %d den dinh %d tren do thi!",dau,cuoi); else 39 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ { printf("\n\nDuong di tu dinh %d den dinh %d tren do thi la:\n",dau,cuoi); printf("%d< ",cuoi); int j=cuoi; while(sTruoc[j]!=dau) { printf("%d< ",sTruoc[j]); j=sTruoc[j]; } printf("%d",dau); } } // // Ham tim duong di giua hai dinh bat ky tren do thi // Ap dung thuat toan tim kiem theo chieu rong // void dd_bfs() { int dau, cuoi; printf("\n\nTim duong di tu dinh:"); scanf("%d",&dau); printf("den dinh:"); scanf("%d",&cuoi); bfs(dau); if(chuaxet[cuoi]==1) printf("\n\nKhong co duong di tu dinh %d den dinh %d tren do thi!",dau,cuoi); else { printf("\n\nDuong di tu dinh %d den dinh %d tren do thi la:\n",dau,cuoi); printf("%d< ",cuoi); int j=cuoi; while(rTruoc[j]!=dau) { printf("%d< ",rTruoc[j]); j=rTruoc[j]; } printf("%d",dau); } } // // Ham kiem tra tinh lien thong cua do thi // void kiemtra_lt() { sotplt=1; for(int i=1;i<=n;i++) chuaxet[i]=1; for(i=1;i<=n;i++) if(chuaxet[i]==1) { 40 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ sotplt++; dfs(Ke[i]->v); //co the dung bfs(Ke[i]->v) thay cho dfs(Ke[i]->v) } if(sotplt==2) printf("\n\nDo thi la lien thong!"); else { printf("\n\nDo thi la khong lien thong!"); printf("\n\nSo thanh phan lien thong cua do thi la %d",sotplt-1); for(int j=2;j<=sotplt;j++) { printf("\n\nThanh phan lien thong thu %d gom cac dinh:",j); for(int k=1;k<=n;k++) if(chuaxet[k]==j) printf("%5d",k); } } } // // Ham in tieu de cua chuong trinh // void tieu_de() { printf("\n CHUONG TRINH TIM DUONG DI VA KIEM TRA TINH LIEN THONG"); printf("\n \n\n"); } // // Ham hien thi Menu chon chuc nang cua chuong trinh // char menu() { printf("\n Menu chon chu nang"); printf("\n \n"); printf("\n\n 1. Nhap do thi cho boi danh sach ke"); printf("\n\n 2. Hien thi danh sach ke cua do thi"); printf("\n\n 3. Tim duong di - theo thuat tk chieu sau"); printf("\n\n 4. Tim duong di - theo thuat tk chieu rong"); printf("\n\n 5. Kiem tra tinh lien thong cua do thi"); printf("\n\n 6. Ket thuc chuong trinh"); printf("\n\n "); printf("\n\n Ban chon:"); char ch=getche(); return ch; } // // Chuong trinh chinh // void main() { int i,kt=0; 41 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ char ch; do { clrscr(); tieu_de(); ch = menu(); switch(ch) { case '1': //Nhap danh sach ke cua do thi clrscr(); tieu_de(); kt=1; printf("\n\n1.Nhap danh sach ke cua do thi"); printf("\n \n\n"); printf("\n\nSo dinh cua do thi n ="); scanf("%d",&n); nhap_dsk(Ke,n); printf("\n\n\n\n "); printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!"); getch(); break; case '2': //Hien thi danh sach ke cua do thi clrscr(); tieu_de(); printf("\n\n2.In danh sach ke cua do thi"); printf("\n \n\n"); if(kt) in_dsk(Ke,n); else printf("\n\nDo thi chu duoc nhap vao!"); printf("\n\n\n\n "); printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!"); getch(); break; case '3': //Tim duong di - theo thuat tk chieu sau clrscr(); tieu_de(); printf("\n\n3.Tim duong di - theo thuat tk chieu sau"); printf("\n \n\n"); if(kt) { //Khoi toa bien chuaxet; for(i=1;i<=n;i++) chuaxet[i]=1; dd_dfs(); } else printf("\n\nDo thi chua duoc nhap vao!"); printf("\n\n\n\n "); printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!"); getch(); 42 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ break; case '4': //Tim duong di - theo thuat tk chieu rong clrscr(); tieu_de(); printf("\n\n4.Tim duong di - theo thuat tk chieu rong"); printf("\n \n\n"); if(kt) { //Khoi toa bien chuaxet; for(i=1;i<=n;i++) chuaxet[i]=1; dd_bfs(); } else printf("\n\nDo thi chua duoc nha vao!"); printf("\n\n\n\n "); printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!"); getch(); break; case '5': //Kiem tra tinh lien thong cu do thi clrscr(); tieu_de(); printf("\n\n5.Kiem tra tinh lien thong cua do thi"); printf("\n "); if(kt) kiemtra_lt(); else printf("\n\nDo thi chua duoc nhap vao!"); printf("\n\n\n\n "); printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!"); getch(); break; case '6': //Ket thuc chuong trinh printf("\n\nXin cam on ban da su dung chuong trinh!"); getch(); break; } }while(ch!='6'); } 43 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Chương 4 ĐỒ THN EULER VÀ ĐỒ THN HAMILTON Trong chương này chúng ta sẽ tập trung nghiên cứu hai dạng đồ thị đặc biệt là đồ thị Euler và đồ thị Hamilton. Trong quá trình trình bày nếu không có chú thích bổ xung gì thì ta hiểu thuật ngữ đồ thị dùng để chỉ đồ thị tổng quát (Đa đồ thị vô hướng hoặc có hướng), thuật ngữ cạnh dùng để chỉ cả cạnh lẫn cung cua đồ thị. 4.1 Đồ thị Euler Định nghĩa 1 Cho đồ thị G=(V,E) Đường đi đơn trong đồ thị G đi qua mỗi cạnh của nó một lần được gọi là đường đi Euler. Chu trình đơn trong đồ thị G đi qua mỗi cạnh của nó một lần được gọi là chu trình Euler. Ví dụ 1 Xét dồ thị vô hướng cho bởi hình sau (Hình 4.1) f a b e d c Hình 4.1 Đường đi a, b, f, a, e, b, a, d, e, c, b là đường đi Euler Đường đi a, f, b, c, e, d, a, e, b, a là đường Euler và cũng là chu trình Euler. Đường đi a, b, c, e, d, a, e, b, a, f, b, a không phai là chu trình Euler và cũng không phải là đường Euler Ví dụ 2 Xét đồ thị có hướng cho bởi hình sau (Hình 4.2) v1 v2 v3 v5 v4 Hình 4.2 44 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Đường v4, v3, v2, v4, v1, v5, v2 là đường đi Euler Chu trình v1, v5, v2, v4, v3, v2, v4, v1 không phải là chu trình Euler và cũng không là đường đi Euler. Chú ý: Đường đi Euler và chu trình Euler cũng có thể được định nghĩa như sau: Đường đi(chu trình) trong đồ thị G là đường đi (chu trình) Euler nếu nó đi qua tất cả các cạnh của đồ thị và mỗi cạnh đi qua đúng một lần. Định nghĩa 2 Đồ thị G=(V,E) được gọi là đồ thị Euler nếu như nó có chu trình Euler và gọi là đồ thị nửa Euler nếu nó có đường đi Euler. Ví dụ 3: Đồ thị cho trong ví dụ 1 là đồ thị Euler còn đồ thị cho trong ví dụ 2 là đồ thị nữa Euler. Định lý 1(định lý Euler) Một đồ thị vô hướng liên thông có chu trình Euler khi và chỉ khi mỗi đỉnh của nó đều có bậc chẵn. (Điều kiện cần và đủ để một đồ thị liên thông có chu trình Euler là tất cả các đỉnh của nó đều có bậc chẵn). Chứng minh Điều kiện cần: Một đồ thị liên thông có chu trình Euler thì mỗi bậc của nó đều có bậc chẵn. Thật vậy, giả sử chu trình Euler của đồ thị bắt đầu từ đỉnh v1 và tiếp theo là cạnh liên luộc với v1, tức là cạnh (v1,v2). Cạnh (v1,v2) góp 1 vào deg(v1). Mỗi lần chu trình đi qua một đỉnh vk của đồ thị, nó tăng thêm 2 đơn vị cho deg(vk) vì chu trình đi vào một đỉnh bằng một cạnh liên thuộc với đỉnh đó và đi ra bằng một cạnh liên thuộc khác, điều đó có nghĩa các đỉnh vk (k ≠ 1) đều có bậc là một số chẵn. Cuối cùng chu trình kết thúc ở đỉnh mà nó xuất phát v1, vì vậy nó tăng thêm 1 vào deg(v1). Do đó deg(v1) cũng phải là một số chẵn. Vậy ta kết luận nếu đồ thị liên thông có chu trình Euler thì mỗi đỉnh của nó đều có bậc chẵn. Điều kiện đủ: Một đồ thị liên thông mà các đỉnh đều có bậc chẵn thì tồn tại chu trình Euler trong đồ thị đó. Thật vậy, giả sử G là một đồ thị liên thông với các đỉnh đều có bậc là một số chẵn. Ta đi xây dựng một chu trình đơn bắt đầu từ đỉnh v1 tuỳ ý của đồ thị G. Trước tiên ta chọn cạnh (v1, v2), sau đó là (v2, v3), càng chọn được nhiều càng tốt. Đến một lúc nào đó đi mà ta đang chọn phải kết thúc tại v1 với cạnh (vk,v1) vì đồ thị là hữu hạn và các đỉnh đều có bậc là một số chẵn. Điều này là chắc chắn xãy ra vì mỗi lần đường đi qua một đỉnh bậc chẵn nó chỉ đi vào bằng một cạnh nên ít nhất vẫn còn một cạnh để đi ra. Ví dụ trong đồ thị G cho bởi hình 4.3 ta bắt đầu ở đỉnh a và chọn tiếp các cạnh (a, b), (b, c), (c, h) và (h, a). b g g c a e e e G H h d d Hình 4.3 45 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Chu trình mà ta xây dựng như trên có thể dùng hết tất cả các cạnh hoặc không. Nếu tất cả các cạnh đã được dùng hết thì chu trình của ta là chu trình Euler. Trường hợp ngược lại, ta gọi H là đồ thị con nhân được từ đồ thị G bằng cách xoá các cạnh đã dùng và các đỉnh không liên thuộc với các đỉnh còn lại. Chẳng hạn trên hình 4.3 ta xoá đi chu trình đơn a, b, c, h, a khỏi đồ thị ta nhận được đồ thị con H. Vì G là liên thông nên H phải có ít nhất một đỉnh chung với chu trình mà ta đã xoá, ta gọi w là đỉnh chung đó (Trong hình 4.3 đỉnh chung là c). Mỗi đỉnh của H cũng có bậc chẵn bởi vì mỗi đỉnh nếu có xoá cạnh thì đều xoá từng cặp cạnh liên thuộc với nó. Lưu ý là H có thể không liên thông. Bắt đầu từ đỉnh w ta lại đi xây dựng đường đi đơn trong H như đã làm đối với G bằng cách chọn được càng nhiều cạnh càng tốt. Đường đi phải kết thúc tại w. chẳng hạn trong ví dụ của ta là c, d, e, g, c là một chu trình mới trong H. Tiếp theo ta tạo một chu trình mới trong G bằng cách ghép chu trình trong H với chu trình ban đầu trong G, điều này làm được vì hai chu trình này có đỉnh chung là w. Qúa trình cứ tiếp tục như vậy cho tới khi tất cả các cạnh của đồ thị đã được sử dụng (quá trình này đến một lúc nào đó phải kết thúc vì đồ thị là hữu hạn) Như vậy ta đã xây dựng được một chu trình Euler trong đồ thị. Trong ví dụ của ta chu trình Euler tìm được là a, b, c, d, e, g, c, h, a. Điều này chứng tỏ nếu đồ thị liên thông mà các đỉnh đều có bậc chẵn thì đồ thị có chu trình Euler. (định lý được chứng minh). Từ cách chứng minh thuật toán, giả sử G là đồ thị Euler ta có thuật toán xây dựng chu trình Euler như sau Procedure Euler(G: Đồ thị liên thông với tất cả các đỉnh có bậc chẵn); Begin Chu trình:=chu trình trong G bắt đầu tại một đỉnh tuỳ ý và các cạnh được thêm vào để xây dựng đường đi qua một số đỉnh và cuối cùng quay về đỉnh này; H:=G với các cạnh của G sau khi bỏ đi Chu trình; While H còn cạnh Begin Chu trình con:=chu trình trong H bắt đầu tại đỉnh trong H cũng là đỉnh đầu mút của một cạnh thuôc Chu trình; H:=H với các cạnh của Chu trình con và tất cả các đỉnh cô lập bị loại bỏ; Chu trình:=Chu trình với Chu trình con được chèn vào tại một đỉnh thích hợp; End; End; Ví dụ 4 Xét đồ thị vô hướng G cho bởi hình dưới đây (Hình 4.4) v3 v2 v4 v1 v5 Hình 4.4 đồ thị G v7 v6 Đây là đồ thị liên thông và có các đỉnh đều có bậc chẵn, ta sẽ đi xây dựng chu trình Euler như sau: Xuất phát từ đỉnh v1 ta có chu trình đơn P1: v1, v2, v7, v1. Bỏ đi chu trình này ta nhận được đồ thị G1 như sau: 46 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ v3 v4 v5 v2 Đồ thị G1 v6 Xuất phát từ đỉnh v2 của đồ thị G1 ta xây dựng chu trình đơn P2: v2, v4, v3, v2, sau khi bỏ đi chu trình P2 ta nhân được đồ thị G2 như sau: v4 v5 Đồ thị G2 v6 Xuất phát từ đỉnh v4 của đồ thị G2 ta xây dựng chu trình đơn P3: v4, v6, v5, v4. Cuối cùng ghép các chu trình P1, P2, P3 ta được chu trình Euler cần tìm là: v1, v2, v4, v6, v5, v4, v3, v2, v7, v1 Từ thuật toán xây dựng chu trình Euler cho đồ thị Euler ở trên ta có thủ tục sau để tìm chu trình Euler trong đồ thị Procedure Euler_Circle(u); (* ST và EC là hai cấu trúc Stack *) Begin ST:= Φ ; EC:= Φ ; ST ⇐u; (* Nạp u vào Stack ST *) While ST ≠ Φ do Begin x:=top(ST); (* x là phần tử ở đỉnh Stack ST *) If Ke(x) ≠ Φ then Begin y:= đỉnh đầu tiên trong danh sách Ke(x); ST⇐ y; Ke(x):=Ke(x)\ {y}; Ke(y):=Ke(y)\ {x}; (* Loại cạnh (x,y) ra khỏi đồ thị *) End Else Begin x⇐ST; (* Lấy x ra khỏi Stack ST *) EC ⇐ x; (* Nạp x vào Stack CE *) End; End; End; Từ thuật toán xây dựng chu trình Euler cho đồ thị Euler ta xây dựng thuật toán tìm chu trình Euler cho một đồ thị G bất kỳ như sau: Thuật toán tìm chu trình Euler 47 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Bước 1: Kiểm tra xem đồ thị G có 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 đồ thị không có chu trình Euler. Bước 2: Kiểm tra xem tất cả các đỉnh của đồ thị G đều có bậc chẵn hay không, nếu co thì chuyển sang bước 3, ngược lại thì thuật toán dừng và kết luận đồ thị không có chu trình Euler. Bước 3: Xây dựng chu trình Euler theo thuật toán trên. (thuật toán xây dựng chu trình Euler của đồ thị Euler) Định lý 2 Đồ thị vô hướng liên thông G là đồ thị nữa Euler khi và chỉ khi nó có không quá hai đỉnh bậc lẻ. Chứng minh: Thật vậy, nếu đồ thị G có không quá hai đỉnh bậc lẻ thì số đỉnh bậc lẻ của nó chỉ có thể là 0 hoặc 2 (Số đỉnh bậc lẻ trong một đồ thị là một số chẵn). Nếu G không có đỉnh bậc lẻ thì theo Định lý 1 nó là đồ thị Euler do đó nó cũng là Đồ thị nữa Euler. Nếu G có hai đỉnh bậc lẻ, giả sử hai đỉnh đó là u và v. Ta gọi H là đồ thị nhận được từ đồ thị G bằng cách thêm vào G một đỉnh w và hai cạnh (u, w), (v, w). Khi đó H là đồ thị liên thông có các đỉnh đều có bậc chẵn do đó theo định lý 1 đồ thị H có chu trình Euler. Nếu xoá khỏi chu trình này đỉnh w và hai cạnh kề (w,u), (w,v) ta nhận được đường đi Euler trong đồ thị G. (Định lý được chứng minh). Ví dụ 5: Cho đồ thị G=(V,E) liên thông có hai đỉnh bậclẻ là v1 và v2 như hình sau (Hình 4.5) v5 v4 v3 v1 v2 Hình 4.5 Ta bổ sung thêm đỉnh mới v và hai cạnh (v,v1), (v,v2) vào đồ thị G ta thu được G’=(V’,E’) như hình 4.6 v5 v4 v3 . v1 v2 v Hình 4.5 Đồ thị G’ là đồ thị liên thông có các đỉnh đều bậc chẵn, do đó theo định lý 1 (Định lý Euler) tồn tại chu trình Euler: (v,v1),(v1,v5),(v5,v4),(v4,v3),(v3,v2),(v2,v4),(v4,v1),(v1,v2),(v2,v). Ta bỏ đi đỉnh v và hai cạnh (v,v1), (v2,v) Ta được đường đi Euler trong đồ thị G là: 48 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ (v1,v5),(v5,v4),(v4,v3),(v3,v2),(v2,v4),(v4,v1),(v1,v2) Định lý 3: Đồ thị có hướng liên thông mạnh là đồ thị Euler khi và chỉ khi deg+(v)=deg-(v), ∀v ∈V (Chứng minh tương tự như định lý 1) 4.2 Đồ thị Hamilton Định nghĩa 3 Cho đồ thị G=(V,E) Đường đi sơ cấp trong đồ thị G đi qua mỗi đỉnh của đồ thị một lần được gọi là đường đi Hamilton. Chu trình sơ cấp trong đồ thị G đi qua mỗi đỉnh của đồ thị một lần gọi là chu trình Hamilton. Ví dụ 6 Xét đồ thị vô hướng cho bởi hình sau (Hình 4.6) a b Hình 4.6 d c Đường đi d, c, a, b là đường đi Hamilton Chu trình a, b, c, d, a là chu trình Hamilton Chu trình d, a, c, b, a, d không phải là chu trình Hamilton Ví dụ 7 Xét đồ thị có hướng cho bởi hình sau (Hình 4.7) 2 1 3 Hình 4.7 4 Đường đi 3, 1, 4, 2 là đường đi Hamilton Đường đi 2, 1, 4 không phải là đường đi Hamilton Chu trình 2, 1, 4, 2 không phải chu trình Hamilton Chú ý Đường đi Hamilton và chu trình Hamilton cũng có thể được định nghĩa như sau: Đường đi(chu trình) trong đồ thị G là đường đi(chu trình) Hamilton nếu nó đi qua tất cả các đỉnh của đồ thị và mỗi đỉnh đi qua đúng một lần. Định nghĩa 4 Đồ thị G=(V,E) được gọi là đồ thị Hamilton nếu như nó có chu trình Hamilton và gọi là đồ thị nữa Hamilton nếu nó có đường đi Hamilton. Ví dụ 7 Đồ thị cho ở hình 4.6 là đồ thị Hamilton, còn đồ thị ho ở hình 4.7 là đồ thị nữa Hamilton. Định lý 4 Đơn đồ thị vô hướng liên thông G=(V,E) có bậc ở mỗi đỉnh không nhỏ hơn nữa số đỉnh của đồ thị (deg(v) ≥ |V|/2 với ∀v ∈V ) thì đồ thị luôn tồn tại chu trình Hamilton. (là đồ thị Hamilton). Ở đây ta giả thiết |V|>2. 49 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Chứng minh Ta đi chứng minh định lý bằng phương pháp phản chứng như sau: Giả sử trong đồ thị G=(V,E) không tồn tại chu trình Hamilton. Ta tiến hành bổ sung thêm các đỉnh mới vào đồ thị G và các cạnh nối các đỉnh mới này với tất cả các đỉnh của đồ thị G cho tới khi ta nhận được đồ thị mới G’=(V’,E’) là đồ thị có chu trình Hamilton. Giả sử số đỉnh tối thiểu mà ta cần bổ xung vào đồ thị G để nhận được đồ thị G’ là k đỉnh. Khi đó |X’| = |X| + k. Trước tiên ta nhận thấy rằng các đỉnh mới phải đứng xen kẽ hai đỉnh cũ trong chu trình Hamilton. Thật vậy, nếu hai đỉnh mới u1, u2 là kề nhau trong chu trình Hamilton, chẳng hạn: vi u1 u2 vj Do u1, u2 đều có cạnh nối với các đỉnh cũ nên ta có thể bỏ đi một trong hai đỉnh u1, u2 mà vẫn được chu trình Hamilton. Điều này trái với giả thiết số đỉnh bổ sung vào là tối thiểu. Vậy đỉnh mới phải đứng xen kẽ hai đỉnh cũ (*). Từ khẳng định (*) ta thấy chu trình Hamilton co dạng: vi u vj (trong đó vi, vj là đỉnh cũ thuộc V, còn u là đỉnh mới thuộc V’-V) Trong trường hợp này ta cần chỉ ra số đỉnh kề của vi là không lớn hơn số đỉnh không kề của vj. Thật vậy, giả sử v1 là đỉnh kề của vi và v2 là đỉnh kề của v1. Nếu v2 là đỉnh kề của đỉnh vj, thì khi đó chu trình Hamilton có dạng vi u vj v1 v2 Tức là ta có thể bỏ đỉnh u bằng cách thay vi, u, vj bởi vi, v1, v2, vj. Điều này trái với giả thiết số đỉnh mà ta bổ sung là tối thiểu. Vậy v2 không thể kề với vj. Như vậy có nghĩa là với đỉnh v1 kề với vi thì sẽ có tương ứng một đỉnh v2 không kề với vj, tức số đỉnh kề với vi không lớn hơn số đỉnh không kề với vj ( ). Từ khẳng định ( ) ta có bất đẳng thức: S2 ≤ S1 ≤ |V|+p=|V’| (1) (deg(v) ≥ |V|/2) Trong đó S2 là tổng số đỉnh kề của vi và đỉnh kề của vj, S1 là tổng số đỉnh không kề của vi và đỉnh không kề của vj Ta có, số đỉnh kề của dỉnh vi = deg(vi) ≥ |V|/2 + p và số đỉnh kề của đỉnh vj = deg(vj) ≥ |V|/2 + p (2) Từ (1) và (2) ta có bất đẳng thức |V| + 2p ≤ |V| + p Sy ra p=0. điều này chứng tỏ không cần bổ sung đỉnh mới nào thì đồ thị G=(V,E) vẫn có chu trình Hamilton. (Đpcm) Ví dụ 8 Xét đồ thị vô hướng cho bởi hình sau (Hình 4.8) 50 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ 2 1 3 Hình 4.8 4 6 5 Các đỉnh của đồ thị này đều có bậc lớn hơn hoặc bằng nữa số đỉnh do đó trong đồ thị có tồn tại chu trình Hamilton, chu trình đó là 1, 2, 3, 4, 5, 6, 1 Định lý 5 Giả sử G=(V,E) là đồ thị có hướng và đầy đủ. Khi đó trong đồ thị luôn tồn tại đường Hamilton. Chứng minh Giả sử w = vi1 vi2 vik vik+1 vim-1 vim là một đường sơ cấp bất kỳ trong đồ thị. Nếu trong đường sơ cấp w mà tất cả các đỉnh của đồ thị đều đã có mặt thì w chính là đường Hamilton. Ngựơc lại nếu còn có những đỉnh của đồ thị chưa có mặt trong w thì ta có thể bổ xung hết những đỉnh vào đường sơ cấp w để w trở thành đường Hamilton theo nguyên tắc sau: Giả sử v thuộc V mà v chưa có mặt trong đường sơ cấp w. Khi đó do tính đầy đủ của đồ thị, chỉ có thể sãy ra các trường hợp sau: 1) Nếu v có cung tới vi1 thì ta bổ sung v vào đầu w, và khi đó nó có dạng v vi1 vi2 vik vik+1 vim-1 vim 2) Nếu vik có cung tới v tà từ x có cung tới vik+1 thì ta bổ sung v vào giữa hai đỉnh vik và vik+1. Khi đó w có dạng vi1 vi2 vik v vik+1 vim-1 vim 3) Nếu từ vik và vik+1 có cung đi tới v và từ v lại có cong đi tới vk+2 thì ta bổ sung v vào giữa hai đỉnh vik+1 và vik+2, w khi đó có dạng vi1 vi2 vik vik+1 v vik+2 vim-1vim 4) Nếu với mọi k thuộc [1, m-1] và từ vik và vik+1 có cung sang v thì ta bổ sung v vào cuối w, khi đó nó có dạng vi1 vi2 vik vik+1 vim-1 vim v Bằng cách đó ta có thể bổ sung hết các đỉnh của đồ thị vào w nếu như nó chưa có mặt trong w để w trở thành đường Hamilton (Đpcm). Ví dụ 9 Xét đồ thị có hướng đầy đủ cho bởi hình sau (Hình 4.9) 2 1 3 6 4 5 51 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Hình 4.9 Với đồ thị này ta luôn xây dựng được đường Hamilton, thật vậy giả sử ta chọn một đường sơ cấp như sau: 2, 5, 4, bây giời ta sẽ lần lượt thêm các dỉnh 1, 3, 6 vào đường này để có đường Hamilton như sau: đỉnh 1 có cung nối với đỉnh 2 nên ta thêm 1 vào đầu đường đi sơ cấp trên và ta nhận được đường sơ cấp mới là 1, 2, 5, 4. với đỉnh 3 ta thấy từ đỉnh 1 có cung tới đỉnh 3, từ đỉnh 3 có cung đi tới đỉnh 2 nên ta sẽ bổ sung đỉnh 3 vào giữa đỉnh 1 và đỉnh 2 và ta được đường sơ cấp mới là: 1, 3, 2, 5, 4 Tiếp đến ta bổ sung đỉnh 6 vào sau đỉnh 4 và ta nhận được đường Hamilton 1, 3, 2, 5, 4, 6 Hệ quả (Không chứng minh) Đồ thị vô hướng đầy đủ G = (V,E) với |V|>2 luôn tồn tại chu trình Hamilton. điều ngược lại nói chung là không đúng. Ví dụ 10 Đồ thị vô hướng cho bởi hình sau (Hình 4.10) có chu trình Hamilton nhưng không đầy đủ v1 v2 v3 v4 Thuật toán liệt kê các chu trình Hamilton của đồ thị Bài tập chương 4 52 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Chương 5 CÂY VÀ CÂY KHUNG CỦA ĐỒ THN 5.1 Cây và các tính chất cơ bản của cây Định nghĩa 1 Cây là đồ thị vô hướng, liên thông và không có chu trình đơn. Đồ thị không liên thông được gọi là rừng (các thành phần liên thông của đồ thị là các cây của rừng). Ví dụ 1 Trong hình 5.1 dưới đây là một rừng gồm ba cây T1, T2 và T3 T1 T2 T3 Định lý 1 (Các tính chất của cây) Giả sử T = (V,E) là đồ thị vô hướng liên thông n đỉnh. Khi đó các mệnh đề sau đây là tương đương. 1) T là cây 2) T không chứa chu trình và có n-1 cạnh 3) T liên thông và có n-1 cạnh 4) T liên thông và nếu bỏ đi một cạnh tuỳ ý thì đồ thị nhận được sẽ không liên thông 5) Hai đỉnh bất kỳ của T được nối với nhau bởi đúng một đường đi đơn 6) T không chứa chu trình nhưng nếu thêm vào một cạnh nối hai đỉnh không kề nhau thì xuất hiện duy nhất một chu trình. Chứng minh Ta sẽ chứng minh định lý theo sơ đồ vòng tròn như sau: 1) ⇒ 2) ⇒ 3) ⇒ 4) ⇒ 5) ⇒ 6) ⇒ 1) 1)⇒ 2): Theo định nghĩa, vì T là cây nên nó không chứa chu trình. Ta đi chứng minh bằng quy nạp nếu T có n đỉnh thì nó có n-1 cạnh. Thật vậy, với n=1 là hoàn toàn đúng. Giả sử điều khẳng định dúng với n=k, tức là cây T có k đỉnh thì có k-1 cạnh, ta đi chứng minh khẳng định đúng với n=k+1. Trước hết ta thấy rằng mọi cây T có k+1 đỉnh ta luôn tìm được ít nhất một đỉnh là đỉnh cheo (đỉnh có bậc bằng 1). Gọi v1, v2, vj là đường đi dài nhất theo số cạnh trong T, khi đó rõ ràng v1 và vj là các đỉnh treo, vì từ v1 (và vk) không có cạnh nối tới bất kì đỉnh nào khác do T không chứa chu trình và đường đang xét là đường dài nhất. Loại dỉnh v1 và cạnh (v1, v2) khỏi T ta thu được cây T1 với k đỉnh, theo giả thiết thì T1 có k-1 cạnh do đó T phải có k cạnh. Vậy khẳng định là đúng với mọi n. 53 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ 2) ⇒ 3): Ta chứng minh bằng phản chứng: Giả sử T không liên thông, khi đó T có k>1 thành phần liên thông T1, T2, ,Tk. Do T không chứa chu trình nên Ti cũng không chúa chu trình, vì thế mỗi Ti là một cây. Nếu ta gọi v(Ti) và e(Ti) lần lượt là số đỉnh và cạnh của cây Ti ta sẽ có: e(Ti) = v(Ti)-1 Suy ra n-1 = e(T) = e(T1)+e(T2)+ +e(Tk) = v(T1)+v(T2)+ +v(Tk)-k=n-k Suy ra k=1, nghĩa là T phải liên thông. 3) ⇒ 4): Việc loại bỏ bất kì một cạnh nào của T đều cho ta một đồ thị n đỉnh n-2 cạnh, rõ ràng là đồ thị khi đó sẽ không liên thông. 4) ⇒ 5): Ta chứng minh bằng phản chứng: Giả sử tồn tại hai đỉnh trong T được nối với nhau bởi hai đường đi đươn khác nhau, khi đó ta hoàn toàn có thể bỏ đi một cạnh ở một trong hai đường đi đó mà đồ thị nhận được vẫn liên thông, điều này là trái với giả thiết. 5) ⇒ 6): Rõ ràng T không chứa chu trình, vì nếu có thì ta sẽ tìm được một cặp đỉnh được nối với nhau bởi hai đường đi đơn, trái với giả thiết. Bây giờ nếu ta thêm vào T một cạnh e nối hai đỉnh u và v của T. Khi đó cạnh này cùng với đường đi đơn nối u và v sẽ tạo thành một chu trình. Chu trình thu được này là duy nhất vì nếu không thì trước đó phải có chu trình, điều này lại trái với giả thiết. 6) ⇒ 1): Giả sử T không liên thông, khi đó T có ít nhất là hai thành phần liên thông, khi đo nếu thêm một cạnh nối hai đỉnh ở hai thành phần liên thông khác nhau ta không thu được thêm một chu trình nào cả, điều này trái với giả thiết. Định lý được chứng minh. Định lý 2 Trong một cây số đỉnh treo là lơn hơn hoặc bằng 2. Chứng minh Ta chứng minh bằng phản chứng: Giả sử số đỉnh treo trong cây là nhỏ hơn 2, khi đó có hai trường hợp xãy ra: a) Số đỉnh treo băng 0 Nếu không có đỉnh treo thì xuất phát từ một đỉnh ta luôn tìm đường quay về đỉnh đó, nghĩa là luôn tìm được một chu trình, mâu thuẫn với giả thiết b) Số đỉnh treo là 1, Ta xuất phát từ đỉnh treo này, vì mỗi đỉnh khác đỉnh treo đường đi se đi vào từ một cạnh rồi đi ra bằng một cạnh khác quá trình này sẽ vô hạnh vì nếu hữu hạn sẽ xuất hiện đỉnh treo. điều này mâu thuNn với tính hữu hạn của đồ thị. (Định lý được chứng minh) 5.2 Cây khung của đồ thị (Cây bao trùm) Định nghĩa 2 Giả sử G = (V,E) là đồ thị vô hướng liên thông. Cây T = (V,F) với F⊂ E được gọi là cây khung của đồ thị G. Ví dụ2 Cho đồ thị vô hướng G = (V,E) như hình vẽ sau (Hình 5.2) Định lý 3 Đồ thị G = (V,E) có cây khung (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: Đồ thị G có cây bao trùm thì G là đồ thị liên thông. 54 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Giả sử G có cây bao trùm là G’, ta chi 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 u, v mà giữa chúng không có đường nối nào, mà u, v cũng là đỉnh của G’, chứng tỏ G’ không liên thông. điều này trái với giả thiết G’ là cây. Điều kiện đủ: Đồ thị G là liên thông thì G có cây bao trùm. Giả sử G là liên thông a) N ếu trong G không có chu trình thì G là một cây, do đó cây bao trùm G’ của G chính là G. b) N ếu trong G có chu trình thì ta bỏ đi một cạnh trong chu trình đó thì ta được G’ liên thông và không có chu trình, G’ là cây của G. (Đpcm). Để tìm khung của đồ thị ta có thể áp dụng một trong hai thuật toán tìm kiếm theo chiều sâu và thuật toán tìm kiếm theo chiều rộng trên đồ thị. Trong cả hai trường hợp mỗi khi ta đến được đỉnh u (tức là biến Chuaxet[u]=true) từ đỉnh v thì cạnh (u,v) sẽ được nạp vào cây khung. Hai thuật toán được áp dụng như sau: Tìm kiếm theo chiều sâu: Procedure DFS_TREE(r) (* Tìm cây khung T của đồ thị vô hướng liên thông G cho bởi danh sách kề *) Begin Chuaxet[r]:=false; For v∈Ke(r) do If Chuaxet[v] Then Begin T:=T ∪ (r,v); DFS_TREE(v); End; End; Tìm kiếm theo chiều rộng Procedure BFS_TREE(r) Begin Q:= Φ ; Q ⇐ r; Chuaxet[r]:=False; While Q ≠ Φ do Begin v ⇐Q; For u∈Ke(v) do If Chuaxet[u] Then Begin Q ⇐u; Chuaxet[u]:=False; T:= T ∪ (v,u); End; End; End; Chương trình chính 55 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ BEGIN For v ∈ V do Chuaxet[v]:=True; T:= Φ ; DFS_TREE(root); (* Hoặc BFS_TREE(root); *) END. Ví dụ 3 5.3 Bài toán tìm cây khung nhỏ nhất (lớn nhất của đồ thị) Bài toán: Cho G=(V,E) là đồ thị vô hướng liên thông với |V|=n và |E|=m. Mỗi cạnh e của đồ thị được gán một số c(e) gọi là độ dài của cạnh. Giả sử H = (V,T) là cây khung của đồ thị G. Ta goi độ c(H) của cây khung H là tổng độ dài các cạnh của cây: c(H)= ∑c(e) e∈T Bài toán đặt ra là trong số tất cả các cây khung H của đồ thị G hãy tìm cây khung có c(H) nhỏ nhất. Cây khung như vậy được gọi là cây khung nhỏ nhất của đồ thị. Để giải quyêt bài toán này ta hoàn toàn có thể liệt kê tất cả các cay khung của đồ thị sau đó chọn lấy cây khung có độ dài nhỏ nhất, xong cách này không được tốt trong trường hợp đồ thị có nhiều cây khung. Do vậy ta phải có một các nào đó để xây dựng được một cây khung của đồ thị sao cho độ dài của cây là nhỏ nhất. Dưới đây ta sẽ nghiên cứu hai thuật toán đáp ứng được yêu cầu trên. 5.3.1 Thuật toán Kruskal Thuật toán Kruskal sẽ xây dựng tập cạnh T của cây khung T=(V,K) theo từng bước như sau: Trước hết sắp xếp các cạnh của đồ thị G theo thứ tự không giảm của độ dài cạnh. Ban đầu tâp K:= Φ , ở mỗi bước ta sẽ lần lượt duyệt trong danh sách các cạnh đã sắp xếp để tìm ra một cạnh có độ dài nhỏ nhất sao cho việc bổ xung cạnh đó vào tập K mà không tạo thành chu trình. Thuật toán sẽ kết thúc khi ta thu được tập K có n-1 cạnh, thủ tục trình bày thuật toán như sau: Procedure Kruskal; Begin K:= Φ ; While |K|<(n-1) and E ≠ Φ do Begin Chon e là cạnh có độ dài nhỏ nhất trong E; E:=E\{e}; If K ∪ {e} không chứa chu trình Then K:=K ∪ {e}; End; If |K|<n-1 Then Đồ thị không có cây khung; Else T:=(V,K) là cây khung nhỏ nhất; End; Ví dụ 4 Xét đồ thị cho bởi hình dưới đây (Hình 5. 56 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ 1 2 17 2 6 4 5 9 15 8 7 6 1 7 3 5 3 12 18 21 8 9 23 4 16 Thứ tự từ trái qua phải, từ trên xuống dưới của các hình dưới đây minh hoạ việc tìm cây khung nhỏ nhất theo thuật toán Kruskal, trong đó các cạnh có nét đậm là cạnh được chọn vào cây khung, các cạnh có nét đứt là các cạnh bị bỏ qua trong quá trình tìm cây khung của thuật toán. 57 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ 5.3.2 Thuật toán Prim Thuật toán Prim sẽ xây dựng cây khung T=(V,P) theo cách sau: Bắt đầu từ từ một đỉnh s tuỳ ý của đồ thị, đầu tiên ta nối s với đỉnh lân cậnh gần nhất của nó, chẳng hạn là đỉnh u (đỉnh u là lân cận gần nhất của s nếu như (u,s) là cạnh kề có độ dài nhỏ nhất của đỉnh s). Tiếp theo, trong số các trong số các cạnh kề với hai đỉnh s, u ta tìm cạnh có độ dài nhỏ nhất, cạnh này dẫn đến đỉnh thư ba, chẳng hạn là đỉnh v, và ta thu được cây bộ phận gồm 3 đỉnh 2 cạnh. Quá trình này sẽ tiếp tục cho đến khi thu được cây gồm n đỉnh và n-1 cạnh, cây này sẽ là cây khung nhỏ nhất cần tìm. Giả sử đồ thị cho bởi ma trận trọng số C={c[i,j];i,j=1,2, ,n}. Trong quá trình thực hiện thuật toán, ở mỗi bước để nhanh chóng chọn được các đỉnh và cạnh cần bổ xung vào cây khung, mỗ đỉnh v của đồ thị sẽ được gán một nhãn có dạng [min(v), near(v)], trong đó min(v) là độ dài của cạnh có độ dài nhỏ nhất trong số các cạnh nối đỉnh v với các đỉnh của cây khung đang xây dựng, còn near(v) là đỉnh của cây khung gần v nhất. Thuật toán Prim được mô tả bằng thủ tục sau Procedure Prim; Begin (* Bước khởi tạo *) Chọn s là một đỉnh nào đó của đồ thị; VT:= {s}; P:=φ ; (* VT là tập đỉnh, P là tập cạnh của cây khung *) min(s):=0; near(s):=s; For v ∈V\VT do Begin min(v):=c[s,v]; near(v):=s; End; (* Bước lặp *) Stop:=false; While not Stop do Begin Tìm u∈V\VT có min(u) nhỏ nhất; VT:=VT ∪ {u}; P:=P ∪ { (u,near(u))}; If |VT| = n then Begin T = (VT,P) là cây khung nhỏ nhất; Stop:=true; End Else For v ∈V\VT do If min(v)>c[u,v] then Begin min(v):=c[u,v]; near(v):=u; End; End; End; Ví dụ 5: Xét đồ thị cho ở ví dụ 4 Ma trận trọng số của đồ thị có dạng 58 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ 1 2 3 4 5 6 7 8 9 1 0 17 ∞ ∞ ∞ 2 4 ∞ ∞ 2 17 0 15 ∞ ∞ ∞ 9 ∞ ∞ 3 ∞ 15 0 18 ∞ ∞ 7 ∞ 21 4 ∞ ∞ 18 0 12 ∞ 1 23 5 ∞ ∞ ∞ 12 0 8 6 3 ∞ 6 2 ∞ ∞ ∞ 8 0 5 ∞ ∞ 7 4 9 7 1 6 5 0 ∞ ∞ 8 ∞ ∞ ∞ 23 3 ∞ ∞ 0 ∞ 9 ∞ ∞ 21 16 ∞ ∞ ∞ ∞ 0 Bảng dưới đây cho ta hình ảnh về các bước lặp của thuật toán Prim, đỉnh có dấu * là đỉnh được chọn để bổ xung vào cây khung và khi đó nhãn của nó không còn bị biến đổi ở các bước tiếp theo nên ta dùng dấu x để ghi nhận điều đó. Đỉnh 1 2 3 4 5 6 7 8 9 VT P B.lặp K.tạo [0,1] [17,1] [ ∞ ,1] [ ∞ ,1] [ ∞ ,1] [2,1]* [4,1] [ ∞ ,1] [ ∞ ,1] 1 φ 1 x [17,1] [ ∞ ,1] [ ∞ ,1] [8,6] x [4,1]* [ ∞ ,1] [ ∞ ,1] 1,6 (6,1) 2 x [9,7] [7,7] [1,7]* [6,7] x x [ ∞ ,1] [ ∞ ,1] 1,6,7 (6,1)(7,1) 3 x [9,7] [7,7] x [6,7]* x x [23,4] [16,4] 1,6,7,4 (6,1)(7,1)(4,7) 4 x [9,7] [7,7] x x x x [3,5]* [16,4] 1,6,7,4,5 (6,1)(7,1)(4,7)(5,7) 5 x [9,7] [7,7] x x x x x [16,4] 1,6,7,4,5,8 (6,1)(7,1)(4,7)(5,7)(8,5) 6 x [9,7]* x x x x x x [16,4] 1,6,7,4,5,8,3 (6,1)(7,1)(4,7)(5,7)(8,5)(3,7) 7 x x x x x x x x [16,4]* 1,6,7,4,5,8,3,2 (6,1)(7,1)(4,7)(5,7)(8,5)(3,7)(2,7) 8 x x x x x x x x X 1,6,7,4,5,8,3,1,9 (6,1)(7,1)(4,7)(5,7)(8,5)(3,7)(2,7)(9,4) 59 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Chương 6 MỘT SỐ BÀI TOÁN ỨNG DỤNG (Bài toán tìm đường đi ngắn nhất và bài toán luồng cực đại) 6.1 Bài toán tìm đường đi ngắn nhất 6.1.1 Tìm đường đi ngắn nhất trong đồ thị không có trọng số Bài toán: Cho đồ thị không có trọng số G = (V,E) và hai đỉnh u, v ∈V. Tìm đường đi ngắn nhất từ đỉnh u đến đỉnh v, tức là đường đi từ u đến v có số cạnh (cung) là ít nhất Để giải quyết bài toán này ta có thể thực hiện theo thuật toán sau đây: Thuật toán: Bước 1: Tại đỉnh u ta ghi số 0 Các đỉnh kề với u (có cạnh đi từ u đến) ta ghi số 1 Các đỉnh kề với các đỉnh đã được ghi số 1 ta ghi số 2 Giả sử ta đã ghi tới i, tức là ta đã đánh số được các tập đỉnh là V(0) = {u}, V(1), V(2), ,V(i). Trong đó V(i) là tập tất cả các đỉnh được ghi bởi số i. Ta xác định tập các đỉnh được đánh số bởi số i+1 như sau: V(i+1) = {x| x ∈V, x∉V(k) với k=0,1, ,i và ∃ y∈V(i) sao cho từ y có cạnh (cung) đi tưới x} Do tính hữu hạn của đồ thị, sau một số hữu hạn bước, thuật toán dừng lại và cho ta tập các đỉnh có chứa đỉnh v được đánh số bởi m là V(m). Bước 2: Do ở bước 1 đỉnh v được đánh số là m, điều này chứng tỏ đường đi từ u đến v có m cạnh (cung) và là đường đi ngắn nhất từ u tới v. Để tìm tất cả các đường đi có độ dài m ngắn nhất từ u tới v, ta xuất phát từ v đi ngược về u theo 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) tới xik được ghi số m-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 u. Tất cả các đường đi xác đinh theo các bước trên là đường đi từ u tới v với độ dài m ngắn nhất cần tìm Ví dụ Xét đồ thị có hướng cho bởi hình dưới đây (Hình 6.1) v2 v3 v4 v1 v10 v8 v9 v5 v6 v7 Tìm đường đi ngắn nhất từ đỉnh v1 đế 60 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Chu ý: Thuật toán tìm đường đi giữa hai đỉnh u và v trong đồ thị bằng cách áp dụng thuật toán tìm kiếm theo chiều rộng chính là đường đi ngắn nhất từ u tới v (theo số cạnh). 6.1.2 Tìm đường đi ngắn nhất trong đồ thị có trọng số Bài toán: Cho đồ thị có trọng số G = (V,E) và hai đỉnh s, t ∈V. Tìm đường đi ngắn nhất từ đỉnh s đến đỉnh t, tức là đường đi từ s đến t có tổng trọng số của các cạnh (cung) là nhỏ nhất. Phần lớn các thuật toán tìm đường đi ngắn nhất từ s đến t được xây dựn trên ý tưởng như sau: Từ ma trận trọng số c[u,v]; u,v∈V, ta tính cận trên d[v] của khoảng cách từ đỉnh s đến tất cả các đỉnh v ∈V, mỗi khi phát hiện d[u]+c[u,v] d[u] +c[u,v] thì ta thay trọng số d[v] bởi d’[v]=d[u]+c[u,v]. Trường hợp ngược lại ta giữ nguyên là d[v]. Quá trình thực hiện cho tới khi trọng số của tất cả các đỉnh đã đạt cực tiểu, tức là ∀v ∈V không tồn tại u∈V kề với v mà d[u]+c[u,v]<d[v] . Bước 3: Xác định đường đi từ s tới t có trọng số nhỏ nhất Từ bước 2 ta xác định được trọng số của đỉnh t, xuất phát từ t ta đi về đỉnh kề với t, chẳng hạn đó là đỉnh x có tính chất d[t] = d[x] + c[x,t], nếu không có đỉnh x như vậy thì ta đi về đỉnh kề với t có trọng số nhỏ nhất, cứ tiếp tục như vậy ta sẽ đi về đến đỉnh y mà đỉnh kề là s sao cho d[y]=d[s]+c[ s,y], với d[s]=0. Ví dụ Tuy nhiên, trên thực tế việc tìm đường đi ngắn nhất giữa hai đỉnh lại có rất nhiều trường hợp riêng biệt mà chưa có một thuật toán nào thực sự tối ưu được tất cả, chẳng hạn đồ thị có trọng số của cạnh là một số âm, hay đồ thị có chứa chu trình có trọng số âm Sau đây ta sẽ xét qua môt số trường hợp riêng. 6.1.2.1 Đường đi ngắn nhất xuất phát từ một đỉnh (Thuật toán Ford – Bellman) Thuật toán tìm đường đi ngắn nhất từ một đỉnh s đến tất cả các đỉnh còn lại của đồ thị được đưa ra bởi hai nhà bác học Ford và Bellman, thuật toán này làm việc trong trường hợp trọng số của các cạnh (cung) là tuỳ ý, nhưng giả thiết rằng trong đồ thị không có chu trình âm. 61 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Procedure Ford_Bellman; (* Đầu vào: Đồ thị G = (V,E) với n đỉnh, s∈V là đỉnh xuất phát, c[u,v] là ma trận trọng số; Đầu ra: Khoảng cách ngắn nhất từ s đến tất cả các đỉnh còn lại d[v], Truoc[v] ghi nhận đỉnh đi trước v trong đường đi ngắn nhất từ s đến v; Giả thiết: Đồ thị không có chu trình âm; *) Begin (* Khởi tạo *) For v∈V do Begin d[v]:=c[s,v]; Truoc[v]:=s; End; d[s]:=0; For k:=1 to n-2 do For v ∈V\{s} do For u∈V do If d[v]>d[u]+c[u,v] then Begin d[v]:=d[u]+c[u,v]; Truoc[v]:=u; End; End; 6.1.2.2Tìm đường đi ngắn nhất trong đồ thị có trọng số không âm (thuật toán Dijkstra) Dijkstra đề nghị một thuật toán tìm đường đi ngắn nhất từ một đỉnh tới tất cả các đỉnh còn lại của đồ thị. Thuật toán Dijkstra được xây dựng dựa trên cơ sở gán cho các đỉnh các nhãn tạm thời. N hãn của mỗi đỉnh cho biết cận trên của độ dài đường đi ngắn nhất từ đỉnh xuất phát đến nó. Các nhãn này sẽ được biến đổi theo các bước lặp, trong mỗi bước lặp có một nhãn tạm thời trở thành nhãn cố định. N ếu nhãn của một đỉnh nào đó trở thành cố định thì nó sẽ cho ta độ dài của đường đi ngắn nhất từ đỉnh xuất phát đến nó. Thuật toán được mô tả cụ thể như sau: Procedure Dijkstra; (* Đầu vào: Đồ thị G=(V,E) với n đỉnh cho bởi ma trận trọng số c[i,j] s∈V là đỉnh xuất phát Đầu ra: Khoảng cách từ đỉnh s đến tất cả các đỉnh v còn lại là d[v] Truoc[v] ghi nhận đỉnh đi trước v trong đường đi ngắn nhất từ s đến v Giả thiết: Trọng số các cạnh (cung) của đồ thị là không âm *) Begin (* Khởi tao *) For v∈V do Begin d[v]:=c[s,v]; Truoc[v]:=s; End; 62 NguyÔn Minh §øc - §HQG Hµ Néi
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ d[s]:=0; T:=V\{s}; (* T là tập các đỉnh có nhãn tạm thời *) (* Bước lặp *) While T ≠ φ do Begin Tìm đỉnh u thuộc T thoả mãn: d[u] = min{d[z]; z thuộc T}; T:=T\{u}; (* Cố định nhãn của đỉnh u *) for v thuộc T do (*Gán lại nhãn cho các đỉnh *) if d[v]>d[u] + c[u,v] then Begin d[v]:=d[u]+c[u,v]; Truoc[v]:=u; End; End; End; Ví dụ: 63 NguyÔn Minh §øc - §HQG Hµ Néi