Giáo trình Các bài toán về đường đi

Nội dung text: Giáo trình Các bài toán về đường đi

1. CÁC BÀI TỐN VỀ ĐƯỜNG ĐI
2. CHƯƠNG II CÁC BÀI TỐN VỀ ĐƯỜNG ĐI I. Chu trình và đường đi Euler 1. Bài tốn mở đầu 2. Định nghĩa 3. Chu trình và đường đi Euler trong đồ thị vơ hướng 4. Chu trình và đường đi Euler trong đồ thị cĩ hướng II. Chu trình và đường đi Hamilton 1. Chu trình Hamilton 2. Phương pháp tìm chu trình Hamilton 3. Đường đi Hamilton III. Bài tốn đường đi ngắn nhất 1. Mở đầu 2. Thuật tốn tìm đường đi ngắn nhất IV. Thuật tốn Hedetniemi 1. Phép cộng ma trận Hedetniemi 2. Thuật tốn Hedetniemi I. Chu trình và đường đi Euler 1. Bài tốn mở đầu : Bài tốn 7 cây cầu ở Kưnigsberg: Thành phố Kưnigsberg thuộc Phổ (bây giờ gọi là Kaliningrad thuộc Cộng hịa Liên bang Nga) được chia thành bốn vùng bằng các nhánh sơng Pregel. Các vùng này gồm 2 vùng bên bờ sơng, đảo Kneiphof và một miền nằm giữa 2 nhánh của sơng Pregel. Vào thế kỷ thứ XVIII, người ta đã xây 7 cây cầu nối các vùng lại với nhau như sơ đồ sau:
3. Vào chủ nhật, người dân ở đây thường đi bộ dọc theo các vùng trong thành phố. Họ tự hỏi “Cĩ thể xuất phát tại một điểm nào đĩ trong thành phố, đi qua tất cả 7 cây cầu, mỗi cây một lần, rồi trở về điểm xuất phát được khơng?” Nhà tốn học Thụy Sĩ Leonard Euler đã nghiên cứu giải bài tốn này. Lời giải của ơng được cơng bố năm 1736. Bài tốn này cĩ thể được coi là một trong những ứng dụng đầu tiên của lý thuyết đồ thị. Ta cĩ thể xây dựng đồ thị G = (V, E) mơ tả bài tốn như sau: + Đỉnh: Lấy các điểm trên mặt phẳng hay trong khơng gian tương ứng với các vùng đất trong sơ đồ. Đối tượng của bài tốn ở đây là một vùng đất trong sơ đồ. Vậy, mỗi đỉnh biểu diễn cho một vùng đất. Đồ thị G sẽ cĩ 4 đỉnh A, B, C, D tương ứng với 4 vùng đất. + Cạnh: Trong đồ thị G các đỉnh và được nối với nhau bằng một cạnh e đại diện cho một chiếc cầu nối giữa hai vùng đất. Đồ thị G sẽ cĩ 7 cạnh tương ứng với 7 chiếc cầu nối giữa các vùng đất trong sơ đồ. Euler đã nghiên cứu bài tốn này, mơ hình nĩ bằng một đa đồ thị, bốn vùng được biểu diễn bằng 4 đỉnh, các cầu là các cạnh như đồ thị sau: Bài tốn tìm đường đi qua tất cả các cầu mỗi cầu khơng quá một lần cĩ thể được phát biểu lại bằng mơ hình này như sau: “Tồn tại hay khơng một chu trình đơn trong đa đồ thị G= (V, E) cĩ chứa tất cả các cạnh?” 2. Định nghĩa 2.1. Chu trình Euler (Đồ thị Euler) Cho G = (V,E) là một đa đồ thị liên thơng. Chu trình đơn chứa tất cả các cạnh của đồ thị G được gọi là chu trình Euler. Đồ thị cĩ chứa một chu trình Euler được gọi là đồ thị Euler.
4. 2.2. Đường đi Euler Cho G = (V,E) là một đa đồ thị liên thơng. Đường đi Euler trong G là đường đi đơn chứa tất cả các cạnh của đồ thị G. Ví dụ 1: Đồ thị cĩ chu trình Euler: a, b, e, d, c, e, a. Ví dụ 2: Đồ thị khơng cĩ chu trình Euler nhưng cĩ đường đi Euler: a, c, d, a, b, e, d, b. Ví dụ 3: Đồ thị khơng cĩ chu trình Euler và đường đi Euler. 3. Chu trình và đường đi Euler trong đồ thị vơ hướng Khi giải bài tốn cầu Kưnigsberg, Euler đã phát hiện ra các tiêu chuẩn để khẳng định một đa đồ thị cĩ chu trình và đường đi Euler hay khơng? 3.1. Định lý về chu trình Euler Một đa đồ thị liên thơng G =(V, E) cĩ chu trình Euler khi và chỉ khi mỗi đỉnh của nĩ đều cĩ bậc chẵn. Chứng minh (⇒) Ta sẽ chứng minh nếu đồ thị G cĩ chu trình Euler thì mọi đỉnh của G đều cĩ bậc chẵn. Thật vậy, trước tiên giả sử G cĩ chu trình Euler bắt đầu từ đỉnh a và tiếp tục bằng cạnh liên thuộc với a, chẳng hạn ab, khi đĩ cạnh ab gĩp một vào deg (a). Mỗi lần khi chu trình đi qua một đỉnh, nĩ tăng thêm 2 đơn vị cho bậc của đỉnh đĩ. Vì chu trình đi vào một đỉnh bằng một cạnh liên thuộc và rời khỏi đỉnh này bằng một cạnh liên thuộc khác. Cuối cùng chu trình kết thúc ở đỉnh mà nĩ xuất phát, do đĩ nĩ tăng thêm một đơn vị vào deg (a). Nghĩa là deg (a) phải là một số chẵn. Đỉnh khác a cũng cĩ bậc chẵn vì chu trình gĩp 2 đơn vị vào bậc của nĩ mỗi lần đi qua đỉnh này. Vậy, mỗi đỉnh của G đều cĩ bậc chẵn. (⇐) Giả sử mọi đỉnh của đa đồ thị liên thơng G đều cĩ bậc chẵn. Ta sẽ chứng minh tồn tại một chu trình Euler trong G.
5. Thật vậy, ta sẽ xây dựng một chu trình đơn bắt đầu từ đỉnh a tùy ý của G. Gọi xo = a; Trước tiên, ta chọn tùy ý cạnh xox1, x1x2, , xn−1xn càng dài càng tốt. Ví dụ, trong đồ thị G sau: Ta bắt đầu tại a và chọn các cạnh liên tiếp ab, bc, cf, fa. Đường đi mà ta chọn sẽ kết thúc vì đồ thị cĩ hữu hạn đỉnh. Đường đi này bắt đầu tại a với cạnh cĩ dạng ax và kết thúc tại a với cạnh cĩ dạng ya. Điều này luơn xảy ra vì mỗi lần đường đi qua một đỉnh bậc chẵn, nĩ chỉ dùng một cạnh để vào đỉnh này và cịn ít nhất một đỉnh để ra khỏi đỉnh này. Đường đi vừa nĩi trên cĩ thể đi qua tất cả các cạnh hoặc cĩ thể khơng. Nếu tất cả các cạnh được sử dụng thì ta nhận được chu trình Euler. Nếu khơng, ta gọi H là đồ thị con nhận được từ G bằng cách xĩa các cạnh đã dùng và các đỉnh khơng liên thuộc với các cạnh cịn lại. Chẳng hạn với đồ thị trên, khi xĩa đi chu trình a, b, c, f, a khỏi đồ thị trên, ta nhận được đồ thị con H. Vì G là liên thơng ⇒ H cĩ ít nhất cĩ một đỉnh chung với chu trình vừa bị xĩa. Gọi w là đỉnh đĩ (trong ví dụ trên là đỉnh c). Mỗi đỉnh của H cĩ bậc chẵn vì tất cả các đỉnh của G cĩ bậc chẵn và với mỗi đỉnh ta đã xĩa đi từng cặp liên thuộc để tạo ra H. Lưu ý rằng H cĩ thể khơng liên thơng. Bắt đầu từ đỉnh w ta xây dựng một đường đi đơn bằng cách chọn càng nhiều càng tốt như ta đã làm trong G. Đường này phải kết thúc tại w. Ví dụ trong đồ thị H nêu trên ta cĩ chu trình con: c, d, e, c. Sau đĩ, ta tạo một chu trình trong G bằng cách ghép chu trình trong H và chu trình ban đầu trong G (điều này thực hiện được vì 2 chu trình cĩ chung đỉnh w). Tiếp tục quá trình này cho đến khi tất cả các đỉnh được sử dụng. Quá trình này phải kết thúc vì đồ thị cĩ hữu hạn đỉnh. Do đĩ, ta đã xây dựng được một chu trình Euler. Bây giờ, trở lại bài tốn 7 cây cầu ở Kưnigsberg: cĩ thể xuất phát từ một địa điểm nào đĩ trong thành phố, đi qua tất cả các cầu (mỗi cầu đi qua đúng một lần) và trở về điểm xuất phát? Ta đã thấy đồ thị biểu diễn các cầu ở Kưnigsberg cĩ 4 đỉnh bậc lẻ. Do đĩ, theo định lý trên sẽ khơng cĩ chu trình Euler trong đồ thị này. Điều này cũng cĩ nghĩa là bài tốn 7 cây cầu ở Kưnigsberg khơng cĩ lời giải. Hay nĩi cách khác, khơng cĩ chu trình nào thỏa yêu cầu đặt ra. 3.2. Thuật tốn Fleury tìm chu trình Euler Để tìm một chu trình Euler trong một đa đồ thị cĩ tất cả các đỉnh đều bậc chẵn, ta cĩ thể sử dụng thuật tốn Fleury như sau: Xuất phát từ một đỉnh bất kỳ của đồ thị G và tuân theo hai qui tắc sau: ¾ Qui tắc 1: Mỗi khi đi qua một cạnh nào thì xĩa cạnh đĩ đi, sau đĩ xĩa đỉnh cơ lập (nếu cĩ).
6. ¾ Qui tắc 2: Khơng bao giờ đi qua một cầu, trừ khi khơng cịn cách đi nào khác để di chuyển. Ví dụ 4: Tìm một chu trình Euler trong đồ thị sau: Xuất phát từ đỉnh A, giả sử ta chọn cạnh AB, BC, CF. Sau đĩ xĩa 3 cạnh này, ta được đồ thị: Đến đây, ta khơng thể chọn FG vì GF là một cầu, cho nên ta chọn FD, DC, CE, EF. Đến đây, ta được đồ thị sau: Ta khơng cịn cách chọn nào khác, nên phải chọn FG, GH, HB, BG, GA. Như vậy, ta cĩ chu trình Euler sau: A, B, C, F, D, C, E, F, G, H, B, G, A. Ví dụ 5: Tìm một chu trình Euler của đồ thị sau: Dễ thấy một chu trình Euler: A, B, C, D, E, C, F, B, E, F, A. 3.3. Định lý về đường đi Euler Đa đồ thị liên thơng G =(V, E) cĩ đường đi Euler nhưng khơng cĩ chu trình Euler khi và chỉ khi nĩ cĩ đúng hai đỉnh bậc lẻ. Chứng minh:
7. (⇒) Giả sử đa đồ thị G cĩ đường đi Euler nhưng khơng cĩ chu trình Euler. Ta sẽ chứng minh G cĩ đúng 2 đỉnh bậc lẻ. Thật vậy, giả sử G cĩ đường đi Euler từ a đến b, nhưng khơng cĩ chu trình Euler. Cạnh đầu tiên của đường đi gĩp một đơn vị vào deg (a). Sau đĩ mỗi lần đường đi qua a lại gĩp thêm 2 đơn vị vào deg (a). Chắc chắn đường đi khơng thể kết thúc tại a, cho nên deg(a) là số lẻ. Cạnh cuối cùng của đường đi gĩp một đơn vị vào deg(a) và mỗi lần đi qua b, nĩ cũng gĩp 2 đơn vị vào deg(b). Do đĩ, deg(b) là số lẻ. Các đỉnh trung gian đều cĩ bậc chẵn vì mỗi lần đường đi tới rồi lại đi nên tăng hai đơn vị cho bậc của đỉnh đĩ. Vậy, đồ thị đã cho cĩ đúng 2 đỉnh bậc lẻ. (⇐) Giả sử đa đồ thị liên thơng G cĩ đúng 2 đỉnh bậc lẻ. Ta sẽ chứng minh G cĩ đường đi Euler. Thật vậy, giả sử G cĩ đúng 2 đỉnh bậc lẻ là a và b. Khi đĩ trong đồ thị mới G' = G ∪ ab, tất cả các đỉnh đều cĩ bậc chẵn. Do đĩ, theo định lý Euler, tồn tại một chu trình Euler trong G'. Trong chu trình này bỏ cạnh ab, ta được đường đi Euler trong G. Như vậy, trong một đa đồ thị liên thơng cĩ 2 đỉnh bậc lẻ thì đường đi Euler trong đồ thị đĩ sẽ nhận 2 đỉnh bậc lẻ làm các điểm đầu mút. Ví dụ 6: Xét đồ thị sau: Trong G cĩ 2 đỉnh bậc lẻ là g và e. Do đĩ, một đường đi Euler trong G sẽ nhận g và e làm 2 đỉnh đầu mút. Chẳng hạn: g, a, b, g, f, b, c, f, e, c, d, e. Ví dụ 7: Chứng minh rằng ta cĩ thể xếp tất cả các con cờ của bộ cờ Đơminơ thành một vịng khép kín. (Xem như bài tập - Sinh viên tự chứng minh). 4. Chu trình và đường đi Euler đối với đồ thị cĩ hướng 4.1. Định lý về chu trình Euler: Đồ thị cĩ hướng G = (V, E) cĩ chứa một chu trình Euler khi và chỉ khi G là liên thơng yếu, đồng thời bậc vào và bậc ra của mỗi đỉnh là bằng nhau. Chứng minh: Tương tự định lý Euler đối với đồ thị vơ hướng (Xem như bài tập - Sinh viên tự chứng minh).
8. Ví dụ 7: Đồ thị cĩ chu trình Euler: a, b, c, a, d, c, a. Ví dụ 8: Đồ thị khơng cĩ chu trình Euler. 4.2. Định lý về đường đi Euler: Cho G =(V,E) là một đa đồ thị cĩ hướng. G cĩ đường đi Euler nhưng khơng cĩ chu trình Euler ⇔ G là liên thơng yếu, đồng thời bậc vào và bậc ra của các đỉnh là bằng nhau, trừ 2 đỉnh, một đỉnh cĩ bậc vào lớn hơn bậc ra một đơn vị, cịn đỉnh kia cĩ bậc vào nhỏ hơn bậc ra một đơn vị. Chứng minh: Tương tự định lý Euler đối với đồ thị vơ hướng (Xem như bài tập - Sinh viên tự chứng minh). Ví dụ 9: Đồ thị cĩ đường đi Euler: a, b, c, a, d, c. II. Chu trình và đường đi Hamilton 1. Chu trình Hamilton 1.1. Định nghĩa Một chu trình sơ cấp đi qua tất cả các đỉnh của đồ thị G =(V,E) (đi qua mỗi đỉnh đúng một lần) được gọi là chu trình Hamilton. Đồ thị G=(V,E) cĩ chứa chu trình Hamilton được gọi là đồ thị Hamilton. Ví dụ 11: Đồ thị cĩ chu trình Hamilton là: a, b, c, d, e, a. Ví dụ 12: Đồ thị khơng cĩ chu trình Hamilton vì mọi chu trình chứa mọi đỉnh của đồ thị đều phải đi qua cạnh ab 2 lần. 1.2. Điều kiện đủ để tồn tại chu trình Hamilton
9. Định lý Ore (1960): Cho G = (V,E) là một đơn đồ thị liên thơng với n đỉnh (n ≥ 3) và nếu: deg(v) + deg(w) ≥ n với mọi cặp đỉnh khơng liền kề v, w trong G. Khi đĩ G cĩ chu trình Hamilton. Chứng minh: Sử dụng phương pháp chứng minh phản chứng. Giả sử G thỏa deg(v) + deg(w) ≥ n; ∀v,w khơng liền kề trong G nhưng G khơng cĩ chu trình Hamilton. Khi đĩ ta cĩ thể ghép thêm vào G những cạnh cho đến khi nhận được một đồ thị con H của Kn sao cho H khơng cĩ chu trình Hamilton, nhưng với mọi cạnh e ∈ Kn nhưng e ∉ H, ta cĩ (H + e) cĩ chu trình Hamilton. Việc ghép thêm cạnh vào G là hồn tồn thực hiện được và khơng ảnh hưởng gì đến điều kiện của giả thiết. Do H ≠ Kn nên tồn tại a, b ∈ V sao cho ab ∉ H nhưng H + ab cĩ chu trình Hamilton C. Bản thân H khơng cĩ chu trình Hamilton mà H + ab cĩ chu trình Hamilton ⇒ ab ∈ C. Giả sử ta liệt kê các đỉnh của H trong chu trình C như sau: a(=v1) → b(=v2) → v3 → v4 → → vn-1 → vn; 3 ≤ i ≤ n. Khi đĩ, nếu cạnh bvi ∈ H, ta cĩ thể kết luận avi-1 ∉ H vì nếu cả hai bvi và avi-1 cùng nằm trong H, ta cĩ chu trình: b → vi → vi+1 → → vn-1 → vn → a → vi-1 → vi-2 → → v3 Chu trình này nằm trong H, điều này mâu thuẫn vì H khơng cĩ chu trình Hamilton. Vì vậy, vi (3 ≤ i ≤ n) chỉ cĩ một trong 2 cạnh: bvi hoặc avi-1 nằm trong H. Do đĩ: degH(a) + degH(b) < n. Với degH(a): bậc của a trong H. Ta cĩ ∀ v ∈ V: degH(v) ≥ degG(v) = deg(v) (vì G là đồ thị con của H) ⇒ với cặp đỉnh khơng liền kề trong G: a, b ta cĩ: deg(a) + deg(b) < n. Điều này mâu thuẫn với giả thiết: deg(v) + deg(w) ≥ n; ∀ v, w khơng liền kề. Vậy, G cĩ chứa chu trình Hamilton. ¾ Hệ quả: (Định lý Dirac, 1952)
10. Nếu đơn đồ thị G = (V,E) cĩ n đỉnh (n ≥ 3) và deg(v) > ; ∀ v ∈ V thì G cĩ chu trình Hamilton. 1.3. Định lý Pĩsa về chu trình Hamilton G = (V, E) là một đơn đồ thị cĩ . Giả sử rằng với mỗi số ta cĩ khơng quá k - 1 đỉnh cĩ bậc khơng lớn hơn k, và trong trường hợp n là số lẻ ta cĩ khơng quá đỉnh cĩ bậc khơng vượt quá . Khi đĩ đồ thị G cĩ một chu trình Hamilton. Chứng minh Chúng ta sẽ chứng minh định lý này bằng phương pháp phản chứng. Giả sử G khơng cĩ chu trình Hamilton, ta cĩ thể giả sử rằng nếu thêm một cạnh bất kỳ nối 2 đỉnh khơng kề nhau của G thì đồ thị thu được sẽ cĩ một chu trình Hamilton. Đồ thị G như vậy được gọi là cĩ tính chất cực đại. Nếu G khơng thỏa tính chất cực đại, ta cĩ thêm vào G các cạnh mới bằng cách nối các cặp đỉnh khơng kề nhau, lúc đĩ ta sẽ thu được một đồ thị khơng cĩ chu trình Hamilton cĩ tính chất cực đại như đã mơ tả ở trên và vẫn khơng ảnh hưởng gì đến giả thuyết của bài tốn ban đầu. Do tính chất cực đại của đồ thị nên giữa hai đỉnh tuỳ ý khơng kề nhau của đồ thị luơn tồn tại một đường Hamilton nối hai đỉnh này. Cĩ thể đĩ là đường Hamilton thu được từ chu trình Hamilton xuất hiện khi thêm vào một cạnh nối hai đỉnh khơng kề nhau này. Ký hiệu là một đường Hamilton (khơng khép kín) trong G. Cho . Ta cĩ nếu vk được nối với v1 bởi một cạnh thì vk-1 khơng được nối với vn bởi cạnh nào cả, nếu khơng thì: là một chu trình Hamilton. Từ đĩ ta cĩ:
11. Trong đồ thị G mỗi đỉnh bậc khơng nhỏ hơn kề với tất cả các đỉnh bậc khơng nhỏ hơn . Thật vậy, giả sử cĩ đỉnh bậc khơng nhỏ hơn , khơng mất tính tổng quát giả sử đỉnh v1 với khơng kề với đỉnh vn cĩ bậc . Giả sử là một đường Hamilton nối v1 với vn. Ký hiệu các đỉnh lân cận của v1 là với . Khi đĩ vn khơng kề với , và ta cĩ Suy ra: Trong G tồn tại những đỉnh cĩ bậc , nếu khơng G cĩ chu trình Hamilton theo định lý Dirac. Ký hiệu là bậc cao nhất trong các đỉnh của G cĩ bậc nhỏ hơn . và p là số các đỉnh cĩ bậc nhỏ hơn . Khi đĩ theo giả thuyết của định lý ta cĩ . Ta sẽ chứng minh rằng . Ký hiệu q là số các đỉnh cĩ bậc lớn hơn , ta cĩ: Giả sử u1 là một đỉnh cĩ bậc là , trong số đỉnh cĩ bậc lớn hơn tồn tại ít nhất một đỉnh gọi là un khơng kề với u1. Khi đĩ bậc của u1 khơng thể là được, nếu khơng thì u1 phải kề với un như trên đã chứng minh. Do đĩ, ta cĩ: . Theo giả thuyết của định lý, số đỉnh cĩ bậc khơng vượt quá sẽ nhỏ hơn , do đĩ . Ta cĩ .
12. Xét đường Hamilton nối u1 với un. Ký hiệu các đỉnh lân cận của u1 là với . Khi đĩ cĩ một trong các đỉnh gọi là cĩ bậc là . Ở phần trên ta đã chứng minh được khi đĩ phải kề với un. Ta được chu trình Hamilton: là điều vơ lý. Mâu thuẫn này đã kết thúc phần chứng minh của ta. 2. Phương pháp tìm chu trình Hamilton TOP Cho một đồ thị G =(V,E). Để tìm một chu trình Hamilton trong đồ thị G, ta thực hiện theo 4 qui tắc sau: ¾ Qui tắc 1: Nếu tồn tại một đỉnh v của G cĩ thì đồ thị G khơng cĩ chu trình Hamilton. ¾ Qui tắc 2: Nếu đỉnh v cĩ bậc là 2 thì cả 2 cạnh tới v đều phải thuộc chu trình Hamilton. ¾ Qui tắc 3: Chu trình Hamilton khơng chứa bất kỳ chu trình con thực sự nào. ¾ Qui tắc 4: Trong quá trình xây dựng chu trình Hamilton, sau khi đã lấy 2 cạnh tới một đỉnh v đặt vào chu trình Hamilton rồi thì khơng thể lấy thêm cạnh nào tới v nữa, do đĩ cĩ thể xĩa mọi cạnh cịn lại tới v. Ví dụ 13: Tìm một chu trình Hamilton của đồ thị: Xuất phát từ đỉnh a. Ta cĩ deg(a) = 3, cho nên ta chỉ giữ lại 2 cạnh liên thuộc với a: ta chọn ab và ad, do đĩ ta bỏ cạnh ae (theo quy tắc 4). Tương tự tại b, ta bỏ cạnh be tại c ta bỏ cạnh ce (theo quy tắc 4). Khi đĩ ta cĩ đồ thị: Tại đỉnh f, ta bỏ cạnh fe. Tại đỉnh i ta bỏ cạnh ie, tại đỉnh h ta bỏ cạnh hg (theo quy tắc 4) tại đỉnh e, ta bắt buộc đi theo eg, gd (theo quy tắc 2). Tại đỉnh a ta phải chọn cạnh da (theo quy tắc 2). Vậy, ta cĩ chu trình Hamilton: a, b, c, f, i, h, e, g, d, a.
13. Ví dụ 14: Đồ thị khơng cĩ chu trình Hamilton vì: deg(f) = 1. + Giả sử đồ thị cĩ một chu trình Hamilton H. + Vì nên H phải chứa các cạnh AB, AC, GE và GI (theo qui tắc 2). + Xét đỉnh I: Do tính chất đối xứng của hình vẽ ta cĩ thể giả sử cạnh , xĩa cạnh IJ (theo qui tắc 4). D A B C F E H G I J K
14. Ví dụ 15: Chứng minh rằng đồ thị sau khơng cĩ chu trình Hamilton: + Xét đỉnh J: Bây giờ nên hai cạnh JF và JK phải thuộc vào H. + Xét đỉnh K: ta đã chọn 2 cạnh KI và KJ nên xĩa KH (theo qui tắc 4) và xĩa cạnh EF (do quy tắc 3). D A B C F E H G I J K D
15. A B C F E H G I J K Đồ thị bây giờ trở thành: Dễ dàng thấy các cạnh FB, HE, HC phải Thuộc chu trình Hamilton H. Ta nhận được
16. Một chu trình con thật sự trong H (Vơ lý). Theo qui tắc 2 ta cĩ các cạnh FB, HE, HC phải thuộc chu trình Hamilton H. Khi đĩ, ta cĩ một chu trình con thật sự trong H. Vậy đồ thị khơng cĩ chu trình Hamilton. 3. Đường đi Hamilton TOP 3.1. Định nghĩa: Đường đi sơ cấp đi qua tất cả các đỉnh của đồ thị G = (V,E) (đi qua mỗi đỉnh đúng một lần) được gọi là đường đi Hamilton. Ví dụ 16: Đồ thị cĩ đường đi Hamilton: a, b, c, f, d, e. Cịn đồ thị: khơng cĩ đường đi Hamilton. Vì đường đi Hamilton phải bắt đầu và kết thúc tại 2 trong 3 đỉnh treo: c, d, g. 3.2. Định lý Kưnig: Mọi đồ thị G =(V, E) cĩ hướng đầy đủ (đồ thị vơ hướng tương ứng của G là đầy đủ) đều cĩ đường Hamilton. Chứng minh: Xét đồ thị cĩ hướng G =(V, E). Gọi là một đường đi sơ cấp trong G.
17. Nếu mọi đỉnh của G đều thuộc thì chính là đường Hamilton cần tìm. Ngược lại, nếu cĩ một đỉnh thì trong G phải tồn tại một đường sơ cấp thuộc một trong 3 dạng sau: + (1) + (2) + (3) Ta sẽ chứng minh rằng nếu khơng cĩ dạng (1) và (2) thì phải cĩ dạng (3). Thật vậy: + Nếu khơng cĩ dạng (1) + Nếu khơng cĩ dạng (2) với nghĩa là cĩ dạng (3). III. Bài tốn đường đi ngắn nhất TOP 1. Mở đầu TOP Trong thực tế, nhiều bài tốn cĩ thể mơ hình bằng đồ thị cĩ trọng số. Đĩ là đồ thị mà mỗi cạnh của nĩ được gán một con số (nguyên hoặc thực) gọi là trọng số ứng với cạnh đĩ. Ví dụ ta cần mơ hình một hệ thống đường hàng khơng. Mỗi thành phố được biểu diễn bằng một đỉnh, mỗi chuyến bay là một cạnh nối 2 đỉnh tương ứng. Nếu trong bài tốn đang xét ta cần tính đến khoảng cách giữa các thành phố thì ta cần gán cho mỗi cạnh của đồ thị cơ sở trên khoảng cách giữa các thành phố tương ứng. Nếu ta quan tâm đến thời gian của mỗi chuyến bay thì ta sẽ gán các thời lượng này cho mỗi cạnh của đồ thị cơ sở Đồ thị biểu diễn khoảng cách giữa một số thành phố của nước Mỹ.
18. Bài tốn đặt ra là tìm đường đi ngắn nhất từ thành phố này đến thành phố khác. Hay nĩi theo ngơn ngữ của lý thuyết đồ thị: ta cần tìm đường đi cĩ tổng trọng số (ngắn) nhỏ nhất từ đỉnh này đến một đỉnh khác của đồ thị. 2. Thuật tốn tìm đường đi ngắn nhất TOP 2.1. Thuật tốn Dijkstra tìm đường đi ngắn nhất Cĩ một số thuật tốn tìm đường đi ngắn nhất giữa 2 đỉnh trên một đồ thị cĩ trọng số. Ở đây ta sẽ sử dụng thuật tốn Dijkstra, do nhà tốn học người Hà Lan: E.Dijkstra đề xuất năm 1959. Chúng ta sẽ áp dụng thuật tốn Dijkstra đối với đồ thị vơ hướng. Đối với đồ thị cĩ hướng, ta chỉ cần thay đổi một chút. Trước khi giới thiệu thuật tốn, ta xét ví dụ sau: Tính độ dài của đường đi ngắn nhất giữa 2 đỉnh a và z trong đồ thị cĩ trọng số sau: Đối với đồ thị này, ta dễ dàng tìm được đường đi ngắn nhất từ a đến z bằng cách thử trực tiếp. Tuy nhiên, ta sẽ phát triển một số ý tưởng giúp ta hiểu thuật tốn Dijkstra dễ dàng hơn. Ta sẽ tìm độ dài của đường đi ngắn nhất từ a đến các đỉnh kế tiếp cho đến khi đạt tới đỉnh z. Xuất phát từ đỉnh a, ta thấy chỉ cĩ 2 đỉnh b và d liên thuộc với a. Nên chỉ cĩ hai đường đi xuất phát từ a đến b và d là ab và ad với độ dài tương ứng là 3 và 2. Do đĩ, d là đỉnh gần a nhất. Bây giờ, ta tìm đỉnh tiếp theo gần a nhất trong tất cả các đường đi qua a và d. Đường đi ngắn nhất từ a tới b là ab với độ dài 3. Đường đi ngắn nhất từ a đến e là a, b, e với độ dài 5. Đường đi ngắn nhất từ a đến c là a, b, c với độ dài 6. Khi đĩ ta cĩ 2 đường đi từ a đến z qua c và e là a, b, c, z với độ dài 8; a, b, e, z với độ dài 6. Vậy, đường đi ngắn nhất từ a đến z là: a, b, e, z với độ dài 6.
19. Ví dụ trên đã minh họa những nguyên tắc chung dùng trong thuật tốn Dijkstra. Đường đi ngắn nhất từ đỉnh a đến z cĩ thể tìm được bằng cách thử trực tiếp. Nhưng phương pháp này khơng áp dụng được đối với đồ thị cĩ nhiều cạnh. Bây giờ, ta nghiên cứu bài tốn tìm độ dài của đường đi ngắn nhất giữa a và z trong đơn đồ thị liên thơng, vơ hướng và cĩ trọng số. Thuật tốn Dijkstra được thực hiện bằng cách tìm độ dài của đường đi ngắn nhất từ a đến đỉnh đầu tiên, từ a đến đỉnh thứ hai, cho đến khi tìm được độ dài ngắn nhất từ a đến z. Thuật tốn này dựa trên một dãy các bước lặp. Một tập đặc biệt các đỉnh được xây dựng bằng cách cộng thêm một đỉnh trong mỗi bước lặp. Thủ tục gán nhãn được thực hiện trong mỗi lần lặp đĩ. Trong thủ tục gán nhãn này, đỉnh w được gán nhãn bằng độ dài đường đi ngắn nhất từ a đến w và chỉ đi qua các đỉnh thuộc tập đặc biệt. Một đỉnh được thêm vào tập này là đỉnh cĩ nhãn nhỏ nhất so với các đỉnh chưa cĩ trong tập đĩ. Cụ thể của thuật tốn Dijkstra như sau: - Gán cho đỉnh a nhãn bằng 0; cịn các đỉnh khác bằng ∞. Ta ký hiệu: Lo(a) = 0; Lo(v) = ∞; ∀ v ≠ a (đây là bước lặp thứ 0). - Gọi Sk là tập đặc biệt các đỉnh sau bước lặp thứ k của thủ tục gán nhãn. Chúng ta bắt đầu bằng So = φ. Tập Sk được tạo thành từ Sk-1 bằng cách thêm vào đỉnh u ∉ Sk−1 mà cĩ nhãn nhỏ nhất. - Sau khi đỉnh u được ghép vào Sk, ta sửa đổi nhãn của các đỉnh khơng thuộc Sk sao cho Lk(v) (nhãn của đỉnh v tại bước k) là độ dài của đường đi ngắn nhất từ a đến v mà đường đi này chỉ chứa các đỉnh thuộc Sk (tức là các đỉnh đã thuộc tập đặc biệt cùng với đỉnh u). Giả sử v là một đỉnh khơng thuộc Sk. Để sửa nhãn của v, ta chọn Lk(v) là độ dài của đường đi ngắn nhất từ a đến v và chỉ chứa các đỉnh thuộc Sk. Để ý rằng đường đi ngắn nhất từ a đến v chỉ chứa các phần tử của Sk hoặc là đường đi ngắn nhất từ a đến v chỉ chứa các phần tử của Sk−1 hoặc là đường đi ngắn nhất từ a đến u trong bước (k−1) cộng với độ dài cạnh uv. Tức là: Lk(a,v) = min{Lk−1(a,v); Lk−1(a,u) + w(uv)} Thủ tục này được lặp bằng cách liên tiếp thêm các đỉnh vào tập đặc biệt các đỉnh cho tới khi đạt tới đỉnh z. Khi thêm z vào tập đặc biệt các đỉnh thì nhãn của nĩ bằng độ dài của đường đi ngắn nhất từ a đến z.
20. Thuật tốn Dijkstra cĩ thể được trình bày dưới dạng giải mã (pseudo - code) như sau: THUẬT TỐN DIJKSTRA Procedure Dijkstra (G: đơn đồ thị liên thơng cĩ trọng số dương); {G cĩ các đỉnh a = vo; v1, v2, , vn = z và trọng số w(vi,vj) với w(vivj) = ∞ nếu vivj khơng là một cạnh của G}. for i = 1 to n L(vi): = ∞ L(a): = 0 S: = φ {Ban đầu các nhãn được khởi tạo sao cho nhãn của a bằng khơng, các đỉnh khác bằng ∞; S = φ} While z ∉ S begin u: đỉnh khơng thuộc S cĩ L(u) nhỏ nhất S: = S ∪ {u} for tất cả các đỉnh v khơng thuộc S if L(u) + w(uv) < L(v) then L(v): = L(u) + w(uv) {thêm vào S đỉnh cĩ nhãn nhỏ nhất, và sửa đổi nhãn của các đỉnh khơng thuộc S} end {L(z) = Độ dài đường đi ngắn nhất từ a tới z}. Ví dụ 17: Dùng thuật tốn Dijkstra, tìm đường đi ngắn nhất từ a đến z trong đồ thị sau: + Ta cĩ: V = {a,b,c,d,e,z}; S = φ.
21. + Tại bước lặp thứ 1: ta gán 0 cho đỉnh a và gán ∞ cho các đỉnh cịn lại. L(a) = 0. + Trong các đỉnh khơng thuộc S = {a} và kề với a cĩ 2 đỉnh b và c. Ta cĩ: L(b) = min {∞, L(a) + w(ab)} = min {∞, 0 + 4} = 4. L(c) = min {∞, L(a) + w(ac)} = min {∞, 0 + 2} = 2. Ta cĩ: L(c) nhỏ nhất nên c ∈ S. ⇒ S = {a,c}. + Trong các đỉnh khơng thuộc S mà kề với c cĩ 3 đỉnh là b, d, e. L(b) = min {4, L(c) + w(cb)} = min{4,2+1} = 3. L(e) = min {∞, L(c) + w(ce)} = min{∞,12} = 12. L(d) = min{∞,L(c) + w(cd)} = min{∞,2 + 8} = 10. Ta cĩ: L(b) nhỏ nhất nên b ∈ S ⇒ S = {a,b,c}. + Trong các đỉnh khơng thuộc S mà kề với b là d. L(d) = min{10,L(b) + w(bd)} = min{10,3 + 5} = 8 ⇒ d ∈ S: S = {a,b,c,d}
22. + Trong các đỉnh kề với d mà khơng thuộc S, cĩ: e,z. L(e) = min{12, L(d) + w(de)} = min{12, 8+2} = 10 L(z) = min{∞, d(d) + w(dz)} = min{∞, 8+6} = 14 ⇒ e ∈ S: S = {a,b,c,d,e}. + Các đỉnh kề với e mà khơng thuộc S: z. L(z) = min{14, L(e) + w(ez)} = min{14, 10+3} = 13. Vậy, đường đi ngắn nhất từ a đến z là: a, c, b, d, e với độ dài 13. 2.2. Định lý: Thuật tốn Dijkstra tìm được đường đi ngắn nhất giữa 2 đỉnh trong đơn đồ thị liên thơng, cĩ trọng số. IV. Thuật tốn Hedetniemi TOP Một trong những thuật tốn tìm đường đi ngắn nhất ngồi thuật tốn Dijkstra như đã trình bày, là thuật tốn Hedetniemi. Thuật tốn này đầu tiên do Hedetniemi đề xuất và Arlignhaus, Nysteren là những người đã phát triển thuật tốn này. Thuật tốn Hedetniemi đầu tiên được cơng bố vào năm 1990. Trước khi giới thiệu thuật tốn Hedetniemi, ta cĩ khái niệm ma trận "liền kề" A = (aij) của một đồ thị G liên thơng cĩ trọng số với các đỉnh v1, v2, , vn như sau:
23. Với aij 0 nếu i = j = x nếu i ≠ j và x = w(vivj) ∞ nếu vivj ∉ G Ví dụ 18: Ta cĩ đồ thị G sau: Theo thứ tự các đỉnh a, b, c, d, e, z. Ta cĩ ma trận "liền kề" của G như sau: A = 1. Phép cộng ma trận Hedetniemi TOP Cho A = (aij)m x n và B = (bij)n x p. Khi đĩ tổng ma trận Hedetniemi là ma trận C = (Cij)m x p với Cij = min{ai1 + b1j, ai2 + b2j, , ain + bnj}. Ký hiệu: C = A B. Ví dụ 19: A = ; B = ⇒ A B = = Ví dụ 20: A = ; B =
24. ⇒ A B = 2. Thuật tốn Hedetniemi TOP Để tìm đường đi ngắn nhất giữa hai đỉnh bất kỳ của một đơn đồ thị liên thơng cĩ trọng số G, gọi A là ma trận "liền kề" của G được xác định theo trên. Ký hiệu: A2 = A A; A3 = A2 A Khi đĩ ta lần lượt tính A2, A3, cho đến AK sao cho: AK ≠ AK−1 và AK = AK+1. Ta cĩ định lý sau: đối với đơn đồ thị liên thơng cĩ trọng số gồm n đỉnh, nếu ma trận Hedetniemi AK ≠ AK−1 và AK = AK+1 thì A biểu diễn tập hợp các độ dài đường đi ngắn nhất giữa hai đỉnh của G khi đĩ phần tử aij của AK là độ dài đường đi ngắn nhất giữa hai đỉnh vi và vj. 3. Ví dụ Tìm độ dài đường đi ngắn nhất giữa hai đỉnh a và z của đơn đồ thị G sau: Ta cĩ ma trận "liền kề" của G là: A = ⇒ A2 =
25. ⇒ A3 = ⇒ Độ dài khoảng cách ngắn nhất từ a đến z là 7. Để tìm đường ngắn nhất từ a đến z ta thấy trong A4: + a46 ⇒ đường đi trước khi đến z phải qua d. Ta lại cĩ: + a54 ⇒ trước khi đến d, phải qua e. Ta cũng cĩ: = a12 + a25 ⇒ đi qua b. Vậy, đường đi ngắn nhất từ a đến z: a, b, e, d, z. BÀI TẬP Bài 01. Các đồ thị sau cĩ chu trình Euler, đường đi Euler hay khơng? Nếu cĩ hãy xây dựng chu trình, đường đi đĩ. a. b. a
26. a b d c e a b c d e f c. d. a d h i j
27. k g c b e f d b a c e f i g h e. f.
28. a b e f h g d c a d b f c e g. h. Bài 02. Một người nào đĩ cĩ thể đi qua những chiếc cầu như trên hình vẽ sau, mỗi chiếc cầu đi qua đúng 1 lần và lại trở về nơi xuất phát được khơng?
29. Bài 03. Xem xét các đồ thị cĩ hướng sau, cĩ chu trình hay đường đi Euler hay khơng? Nếu cĩ, hãy xây dựng chu trình và đường đi đĩ. a b d c d e a b c a b c d e f e f g h a b c d
30. Bài 04. Với giá trị nào của n, các đồ thị sau cĩ chu trình Euler: a. Kn b. Cn c. Wn d. Kn,n Bài 05. Một ơng vua đã xây dựng một lâu đài để cất báu vật. Người ta tìm thấy sơ đồ của lâu đài như sau với lời căn dặn: muốn tìm báu vật, chỉ cần từ một trong các căn phịng bên ngồi cùng (số 1, 2, 6, 10 ) đi qua tất cả các cửa phịng, mỗi cửa chỉ một lần. Báu vật được giấu sau cánh cửa cuối cùng. Hãy tìm nơi giấu báu vật. 20 21 16 17 18 11 12 13 14 3 4 5 6 7 8 9 10 1 2 19 15
31. Bài 06. Tìm các chu trình Hamilton hoặc đường đi Hamilton của cạc đồ thị sau: a b c d e f g a b c d e f g h i j a. b. b c d e f e g
32. a e g f j h i c d a Đồ thị Petersen b. d. b Bài 07. Cho ví dụ về: a. Đồ thị cĩ một chu trình vừa là chu trình Euler vừa là chu trình Hamilton. b. Đồ thị cĩ một chu trình Euler và một chu trình Hamilton nhưng hai chu trình này khơng trùng nhau. c. Đồ thị cĩ chu trình Euler nhưng khơng cĩ chu trình Hamilton. d. Đồ thị cĩ chu trình Hamilton nhưng khơng cĩ chu trình Euler.
33. Bài 08. Với giá trị nào của n, các đồ thị sau cĩ chu trình Hamilton: a. Kn b. Cn c. Wn d. Kn,n Bài 09. Tìm độ dài đường đi ngắn nhất giữa a và z trong các đồ thị cĩ trọng số sau: b 5 d 5 f 3 c 6 e 5 g 2 1 2 a z 4 3 4 7 a. 19 d 11 b 40 g c 10 f a z 30
34. 50 6 35 12 23 20 8 c. b 2 d 3 g 5 j c 9 f 2 i 2 k 6 1 6 a z 9 e 3 h 1 5 9 5
35. 3 2 b. 3
36. h 8 o b 1 e d 4 g k 2 r a 2 4 3 2 6 j 3 4 3 2 2 3 i 3 1 l 6 2 p
37. 4 3 2 6 3 4 5 m 5 2 5 n 1 8 q 1 2 1 3 8 5 t 6
38. s 2 z 3 d. 2 Bài 10. Tìm đường đi ngắn nhất giữa a và z của đồ thị sau, với điều kiện: 8 8 5 12 A Z 7 6 5 E 7
39. 8 4 3 6 L 5 5 6 N J G F C 4 4 3 8 I K M D B 3
40. 5 4 8 5 7 5 4 H a. Đi qua đỉnh H. b. Chứa cạnh IJ. Bài 11. Dùng thuật tốn Hedetniemi, tìm đường đi ngắn nhất giữa a và z trong các đồ thị của bài 9a và 9c.