Tiêu đề Chuyên đề 37_ _Lời giải_TLN.pdf ✅

CHUYÊN ĐỀ 37_ĐƯỜNG EULER VÀ ĐƯỜNG ĐI HAMILTON. BÀI TOÁN TỐI ƯU VỀ ĐƯỜNG ĐI NGẮN NHẤT A. KIẾN THỨC CƠ BẢN CẦN NẮM 1. ĐƯỜNG ĐI EULER a) Khái niệm đường đi Euler  Cho một đa đồ thị G.  Một đường đi đơn giản từ đỉnh A đến đỉnh B và chứa mọi cạnh của G được gọi là một đường đi Euler từ A đến B.  Một chu trình đơn giản chứa mọi cạnh của G được gọi là một chu trinh Euler của G. Định lí 1 (Euler) Một đa đồ thị G có một chu trình Euler khi và chỉ khi G liên thông và mọi đỉnh của G đều có bậc chã̃n. Định lí 2 Một đa đồ thị G có một đường đi Euler từ A đến B khi và chỉ khi G liên thông và mọi đỉnh của G đều có bậc chẵn, chỉ trừ A và B có bậc lẻ. Chú ý. Hai định lí trên cũng đúng cho trường hợp G là đơn đồ thị. 2. ĐƯỜNG ĐI HAMILTON  Một đường đi sơ cấp từ đỉnh A đến đỉnh B và qua mọi đỉnh của đồ thị G được gọi là một đường đi Hamilton từ A đến B.  Một chu trình sơ cấp chứa mọi đỉnh của G được gọi là một chu trình Hamilton của G. Định lí 3 (Ore)
Nếu G là đơn đồ thị có n đỉnh (n ≥ 3) và mổi cặp đỉnh không kề nhau đều có tổng bậc không nhỏ hơn n thì G có một chu trình Hamilton. Hệ quả (Định lí Dirac). Nếu G là đơn đồ thị có n đỉnh (n ≥ 3) và mổi đỉnh có bậc không Định lí 4 Nếu đơn đồ thị G có n đỉnh (n ≥ 3) và mỗi đỉnh có bậc không nhỏ hơn n―1 2 thì G có một đường đi Hamilton. Chú ý. Trong một số trường hợp đơn giản, ta có thề tìm đường đi (chu trình Hamilton) của G hoặc chứng minh G không có đường đi (chu trình Hamilton) dựa vào nhận xét sau: Đường đi (chu trình) Hamilton phải đi qua các cạnh có đầu mút tại những đỉnh có bậc 2. 3. BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT HĐ. Cho sơ đồ như trên Hình 2.28, ở đó A B C D E F , , , , , là các địa điểm nối với nhau bởi các con đường với độ dài của mỗi con đường được cho như trên hình. a) Hãy chỉ ra 2 đường đi từ A đến F và so sánh độ dài của hai đường đi đó. b) Với mỗi đỉnh V của sơ đồ trên Hình 2.28, ta gắn số I V( ) là khoảng cách ngắn nhất để đi từ A đến V và gọi là nhãn vĩnh viễn của đỉnh V . Như vậy, ta có ngay I A( ) 0 = . Dựa vào Hình 2.28, hãy tìm các nhãn vĩnh viễn I B I C ( ), ( ) của hai đỉnh kề với A là B C, . Lời giải a) Hai đường đi từ A đến F là: ABDF và ACEF . Độ dài đường đi ABDF là 3 7 9 19 + + = ; độ dài đường đi ACEF là 1 5 8 14 + + = . Suy ra: độ dài ABDF lớn hơn độ dài ACEF . b) I B I C ( ) 3; ( ) 1 = = . Để giải quyết bài toán tìm đường đi ngắn nhất nối A với F , chúng ta sẽ xem sơ đồ đã cho như một đồ thị liên thông và mỗi cạnh được gắn với một số không âm, số đó chính là độ dài của con đường. Những đồ thị như vậy gọi là đồ thị có trọng số và con số được gắn với một cạnh gọi là trọng số của cạnh đó. Bài toán đã cho trở thành tìm một đường đi từ A đến F với tổng các trọng số nhỏ nhất, tức là cần xác định nhãn vĩnh viễn I F( ) . - Đồ thị có trọng số là một đồ thị liên thông và mỗi cạnh được gắn với một số không âm, gọi là trọng số của cạnh đó.
- Để tìm đường đi ngắn nhất từ đỉnh A đến đỉnh F của một đồ thị có trọng số, ta xuất phát từ đỉnh A và di chuyển theo các cạnh của đồ thị. Với mỗi đỉnh V , ta gắn một số I V( ) là khoảng cách ngắn nhất để đi từ A đến V , gọi là nhãn vĩnh viễn của đỉnh V . Như vậy, để tìm độ dài của đường đi ngắn nhất nối A với F , ta cần tìm I F( ) . Ví dụ 1. Tìm độ dài của đường đi ngắn nhất nối A với F trong đồ thị có trọng số trên Hình 2.28. Giải Ta áp dụng thuật toán đã mô tả ở trên. Đầu tiên ta gắn nhãn đỉnh A là I A( ) 0 = và gắn cho 2 đỉnh kề với A là B C, các nhãn tạm thời I A I A ( ) 3 3, ( ) 1 1 + = + = . Chọn số nhỏ nhất trong chúng và viết I C( ) 1 = . Đỉnh C bây giờ được gắn nhãn vĩnh viễn là 1. Tiếp theo ta gắn cho các đỉnh kề với C là B D E , , các nhãn tạm thời I C I C ( ) 6 7, ( ) 4 5 + = + = , I C( ) 5 6 + = (B hiện nay có hai nhãn tạm thời là 3 và 7 ) . Nhãn tạm thời nhỏ nhất trong các nhãn đã gán (ở B D E , , ) hiện nay là 3 (tại B ), nên ta viết l B( ) 3 = . Đỉnh B được gắn nhãn vĩnh viễn là 3. Bây giờ ta xét các đỉnh kề với B (mà chưa được gắn nhãn vĩnh viễn) là D và E . Ta gắn cho đỉnh D nhãn tạm thời I B( ) 7 10 + = ( D hiện nay có hai nhãn tạm thời là 5 và 10), gắn cho đỉnh E nhãn tạm thời I B( ) 2 5 + = (E có hai nhãn tạm thời là 6 và 5). Nhãn tạm thời nhỏ nhất bây giờ là 5 (tại D và E ), do đó ta viết I D( ) 5 = và I E( ) 5 = . Hai đỉnh D và E đều được gắn nhãn vĩnh viễn là 5. Xét đỉnh kề với D là F , ta gắn cho F nhãn tạm thời I D( ) 9 14 + = . Xét đỉnh kề với E là F , ta gắn cho F nhãn tạm thời I E( ) 8 13 + = . Vậy đỉnh F sẽ được gắn nhãn vĩnh viễn là 13. Vì I F( ) 13 = nên đường đi ngắn nhất từ A đến F có độ dài là 13. Để tìm một đường đi ngắn nhất từ A đến F như vậy, ta sẽ lần ngược từ điểm cuối F . Ta chỉ cần giới hạn ở việc xét những cạnh mà độ dài là hiệu của các nhãn gắn tại các đầu mút của nó, đó là: EF BE , và AB (do I F I E I E I B ( ) ( ) 13 5 8, ( ) ( ) 5 3 2 - = - = - = - = và I B I A ( ) ( ) 3 0 3) - = - = . Khi đó ta có thể kết luận, đường đi ngắn nhất từ A đến F phải đi qua các cạnh EF BE , và AB . Vậy, đường đi ngắn nhất (trong trường hợp này là duy nhất) từ A đến F là A B E F ® ® ® . Chú ý a) Nếu đồ thị có trọng số mà mỗi cạnh đều có trọng số là 1 thì bài toán trở thành tìm số các cạnh của đường đi ngắn nhất từ A đến F .
b) Các con số trong sơ đồ ở Hình 2.28 có thể là thời gian để đi dọc con đường đó, hoặc là chi phí khi đi hết con đường đó,. Bởi vậy, ta có thể sử dụng thuật toán giải quyết bài toán gốc về bài toán tìm đường đi ngắn nhất để giải quyết bài toán tìm đường đi nhanh nhất hoặc đường đi có chi phí rẻ nhất,. 4. BÀI TOÁN NGƯỜI ĐƯA THƯ Bài toán người đưa thư phát biểu như sau: Một người đưa thư xuất phát từ bưu điện phải đi qua một số con đường để phát thư rồi quay lại điểm xuất phát, hỏi người đó phải đi như thế nào để đường đi là ngắn nhất. Ở đây các điểm cần phát thư nằm dọc theo các con đường cần phải đi qua. Trong bài toán này, người đưa thư sẽ phải đi trên mỗi con đường ít nhất một lần (để phát được thư cho các điểm cần phát nằm dọc theo con đường đó) và cuối cùng quay lại vị trí xuất phát. Ngoài ra, cần đảm bảo quãng đường phải đi là nhỏ nhất có thể. Trong ngôn ngữ của lí thuyết đồ thị, bài toán người đưa thư tương đương với bài toán tìm chu trình ngắn nhất đi qua tất cả các cạnh của một đồ thị cho trước. Bài toán này có thể phát biểu dưới dạng một đồ thị có trọng số, ở đó đồ thị ứng với hệ thống các con đường, và trọng số của mỗi cạnh là độ dài của con đường tương ứng. Các cạnh của đồ thị này mô tả các con đường cần phải đi qua, các đỉnh của đồ thị là điểm đầu và điểm cuối của các con đường đó (và có thể không phải là điểm cần phát thư). Khi đó ta cần tìm một chu trình có tổng trọng số nhỏ nhất và chứa mỗi cạnh ít nhất một lần. Trong trường hợp tổng quát, nói chung đây là một bài toán khá phức tạp. Trong mục này, ta chỉ xét hai tình huống đơn giản (liên quan đến đồ thị có trọng số, liên thông): 1) Tất cả các đỉnh của đồ thị đều có bậc chẵn. Khi đó đồ thị có chu trình Euler và chu trình Euler đó chính là một đường đi yêu cầu. 2) Chỉ có đúng hai đỉnh của đồ thị có bậc lẻ. Khi đó ta có thể tìm một đường đi Euler từ đỉnh bậc lẻ này đến đỉnh bậc lẻ kia, sau đó dùng thuật toán ở Mục 1 tìm đường đi ngắn nhất để quay trở lại đỉnh xuất phát. Kết hợp hai đường đi đó, ta được lời giải của bài toán đã cho. Dưới đây ta xét hai ví dụ minh hoạ cho hai trường hợp này. Ví dụ 2. Cho đồ thị có trọng số như Hình 2.30. Chứng tỏ rằng đồ thị có chu trình Euler và hãy tìm một chu trình Euler xuất phát từ đỉnh A . Giải Vì đồ thị là liên thông và các đỉnh đều có bậc chẵn (ở đây đều là bậc 4) nên đồ thị có chu trình Euler. Một chu trình Euler xuất phát từ đỉnh A là ABCBECDEADA. Chú ý. Nếu đồ thị có chu trình Euler thì độ dài quãng đường phải đi trong lời giải của bài toán người đưa thư chính là tổng các trọng số gắn trên các cạnh của đồ thị.