Giáo án môn lý thuyết đồ thị

Chia sẻ: Tran Ngoc Minh | Ngày: | Loại File: PDF | Số trang:63

3
1.871
lượt xem
562
download

Giáo án môn lý thuyết đồ thị

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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?. Đồ...

Chủ đề:
Lưu

Nội dung Text: Giáo án môn lý thuyết đồ thị

  1. 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
  2. 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
  3. 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. R3 R2 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
  4. 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 v5 v4 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) v∈V v∈V Ví dụ 10: v3 v2 v1 v6 v4 v5 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
  5. 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 ∑ deg(v ) + ∑ deg(v Theo định lý 1 ta có: deg(G) = ) = 2|V| = 2n i j i =1 j = k +1 k k k ∑ deg(vi ) = ∑ (2m i +1) = 2∑ mi + k Do i =1 i =1 i =1 n n n ∑ deg(v ∑ 2m = 2 ∑mj )= và j j j = k +1 j = k +1 j = k +1 k  k n k n n ∑ deg(vi ) + ∑ deg(v j ) = 2∑ mi + k + 2 ∑ m j = 2 ∑ mi + ∑m  + k =2n Suy ra deg(G) =   j  i =1  i =1 j = k +1 i =1 j = k +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 e d c Trong đồ thị trên ta co: 5 NguyÔn Minh §øc - §HQG Hµ Néi
  6. 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à: vi1 vi2 vi3 vij vij+1 ei1 ei2 eij 6 NguyÔn Minh §øc - §HQG Hµ Néi
  7. Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ vi0 Theo giả thiết deg(vij) ≥ 2 nên phải tồn tại ít nhấ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
  8. 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: I H 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
  9. 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: an+1 R bn+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 R bn+1 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
  10. 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
  11. 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 G2 G1 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 d b 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
  12. Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ v5 v3 e5 e6 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 e4 v4 v3 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 c a b) a, d, b, e, a c) a, d, a, d, a d) a, b, e, c, b, d, a e d 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
  13. 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
  14. 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 ijp , i, j = 1,2,.., n là các phần tử của ma trận tích A p = 123 A. A... A p Khi đó a , i, j = 1,2,.., n cho ta số đường đi khác nhau từ đỉnh i đến đỉnh j qua p-1 đỉnh trung p ij 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
  15. Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ 4 Ma trận kề của G là 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 2 1 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
  16. 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 8 10 v2 v5 5 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
  17. 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 c 7 4 3 a d 4 9 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 v3 v2 v1 e6 e2 e4 e5 e1 e3 v5 v4 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
  18. 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 v3 e4 e2 e1 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 còn rất hay được sử dụng trong v5 0 0 0 0 1 1 0 0 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
  19. Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Ví dụ 11: Cho ma trận G như sau 2 4 6 1 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 6 1 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
  20. 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 v3 v1 v2 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 v2 v4 v5 v1 v1 v3 v4 v2 v2 v4 v5 v3 v1 v2 v3 v5 v4 v1 v3 v4 v5 Danh sách kề lưu trữ dưới dạng danh sách liên kết như sau: v2 v4 v5 nill v1 v1 v3 v4 nill v2 v2 v4 v5 nill v3 v1 v2 v3 v5 nill v4 v1 v3 v4 nill v5 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
Đồng bộ tài khoản