MỞ ĐẦU

Trong lí thuyết đồ thị, bài toán Bảy cây cầu ở Konigsberg (nay là thành phố Kaliningrad, nước Nga) được phát biểu như sau: Thành phố có 7 cây cầu bắc qua sông như Hình 2.15a dưới đây; có thể nào đi qua khắp các cây cầu nhưng mỗi cầu chỉ đi qua một lần không?

Nếu ta coi mỗi khu vực A, B, C, D của thành phố là một đỉnh, mỗi cầu qua lại hai khu vực như một cạnh nối hai đỉnh, thì bản đồ thành phố Konigsberg là một đa đồ thị như Hình 2.15b. Vấn đề đặt ra chính là: Có thể vẽ được Hình 2.15b bằng một nét liền hay không?

Giải chi tiết:

Không thể nào đi qua khắp các cây cầu nhưng mỗi cầu chỉ đi qua một lần và cũng không thể vẽ được bằng một nét liền ở Hình 2.15b.

1. ĐƯỜNG ĐI EULER

a) Khái niệm đường đi Euler

Hoạt động 1: Nhận biết đường đi Euler

Hãy thử vẽ mỗi hình trên Hình 2.16 bằng một nét liền.

Giải chi tiết:

a) Xuất phát từ điểm đỏ, đi theo mũi tên xanh và quay lại điểm đỏ.

b) Xuất phát từ A, đi theo mũi tên xanh và kết thúc tại B.

Luyện tập 1: Đồ thị nào dưới đây có một đường đi Euler? Hãy chỉ ra một đường đi Euler của nó.

Giải chi tiết:

Đồ thị 2.19a liên thông, chỉ có hai đỉnh A và B có bậc lẻ (bậc bằng 3), các đỉnh còn lại đều bậc chẵn. Do đó đồ thị có đường đi Euler. Đường đi Euler trong đồ thị: ACBEADB.

Đồ thị 2.19b liên thông nhưng tất cả các đỉnh đều có bậc lẻ nên đồ thị không có đường đi Euler.

2. ĐƯỜNG ĐI HAMILTON

Hoạt động 2: Nhận biết đường đi Hamilton

Có 5 thành phố du lịch A, B, C, D, E và các con đường nối các thành phố này như Hình 2.20. Hãy chỉ ra một cách để đi tham quan cả 5 thành phố đó, mà không cần đến địa điểm nào quá một lần.

Giải chi tiết:

Một cách để đi tham quan cả 5 thành phố đó, mà không cần đến địa điểm nào quá một lần: EABCD.

Luyện tập 2: Đồ thị nào trong Hình 2.23 có đường đi Hamilton? Hãy chỉ ra một đường đi Hamilton của nó.

Giải chi tiết:

Đồ thị 2.23a có 5 đỉnh. Đỉnh A và B có bậc 3 (lớn hơn (5−1)/2), đỉnh C, D, E có bậc 2 (bằng (5−1)/2). Do đó, theo định lí Dirac, đồ thị có đường đi Hamilton. Một đường đi Hamilton: DAEBC.

Đồ thị 2.23b có 4 đỉnh. Tất cả các đỉnh đều có bậc 3 (lớn hơn (4−1)/2). Do đó, theo định lí Dirac, đồ thị có đường đi Hamilton. Một đường đi Hamilton: DABC.

BÀI TẬP

2.7. Mỗi đồ thị sau có một chu trình Euler hoặc một chu trình Hamilton hay không? Hãy vẽ một chu trình Euler hoặc một chu trình Hamilton khi có thể.

Giải chi tiết:

Hình 2.24a không có chu trình Euler, cũng không có chu trình Hamilton.

Hình 2.24b có chu trình Euler và có chu trình Hamilton. Chu trình Euler: ABCDEADBECA; chu trình Hamilton: ABCDEA.

Hình 2.24c không có chu trình Euler nhưng có chu trình Hamilton: EFGHDCBAE.

Hình 2.24d không có chu trình Euler, cũng không có chu trình Hamilton.

2.8. Có thể nào đi dạo chơi qua các cây cầu trong Hình 2.25, mỗi cây cầu vừa đúng một lần?

Giải chi tiết:

Nếu ta coi mỗi khu vực A, B, C, D, E, F là một đỉnh, mỗi cầu qua lại hai khu vực như một cạnh nối hai đỉnh, thì đây là một đa đồ thị. Ta có hình vẽ:

Ta thấy: Đỉnh A có bậc lẻ, đỉnh B có bậc lẻ, đỉnh C, D, E, F đều có bậc chẵn nên theo định lí 2 , đồ thị có đường đi Euler.

Vậy có thể dạo chơi qua các cây cầu sao cho mỗi cây cầu vừa đúng một lần.

2.9. Cho đồ thị G như Hình 2.26. Tìm một chu trình Hamilton xuất phát từ đỉnh S của G.

Giải chi tiết:

Một chu trình Hamilton xuất phát từ đỉnh S là: SUKTRNHOMS.

2.10. Cho đồ thị G như Hình 2.27. Tìm một đường đi Hamilton từ S đến R.

Giải chi tiết:

Một đường đi Hamilton từ S đến R là: SABEFDCR.

2.11. Hãy chỉ ra một ví dụ chứng tỏ rằng điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn n2 trong Định lí Dirac, không thể thay bằng điều kiện "bậc của mỗi đỉnh không nhỏ hơn (n−1)/2".

Giải chi tiết:

Điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn n/2 thì đồ thị G có một chu trình Hamilton.

Điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn (n−1)/2 thì đồ thị G có một đường đi Hamilton.

Nếu thay điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn n/2 bằng điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn (n−1)/2 thì đồ thị sẽ chỉ có đường đi Hamilton.

Tuy nhiên ta có ví dụ:

Ta thấy bậc của mỗi đỉnh thỏa mãn điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn (n−1)/2.

Nhưng đồ thị trên có một chu trình Hamilton, ví dụ ABCFDEA. Do đó, đồ thị thỏa mãn điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn n/2.

Vậy điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn n/2 trong Định lí Dirac, không thể thay bằng điều kiện "bậc của mỗi đỉnh không nhỏ hơn (n−1)/2".

2.12. a) Giả sử G là một đồ thị với n đỉnh và cạnh. Sử dụng Định lí Ore, hãy chứng minh rằng G có một chu trình Hamilton.

b) Tìm một đồ thị với n đỉnh và cạnh mà không có chu trình Hamilton.

Giải chi tiết:

a) Định lí 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.

Ta có lí thuyết: Giả sử G là đồ thị đơn gồm n đỉnh và m cạnh. Nếu thì G là đồ thị có chu trình Hamilton.

Áp dụng vào bài toán ta được điều phải chứng minh.

b) Ta có đồ thị sau có 5 đỉnh, 7 cạnh và đồ thị không có chu trình Hamilton.

2.13. Với giá trị nào của n thì đồ thị đầy đủ Kn có một chu trình Euler? Có một đường đi Euler?

Giải chi tiết:

Ta có đồ thị đầy đủ Kn có n đỉnh và bậc của mọi đỉnh là n - 1

- Theo Định lí 1, đồ thị G có chu trình Euler khi và chỉ khi đồ thị liên thông và mọi đỉnh của đồ thị đều có bậc chẵn.

Do đó để đồ thị đầy đủ Kn có một chu trình Euler khi và chỉ khi n - 1 phải là số chẵn. Suy ra n là số lẻ.

- Theo Định lí 2, đồ thị G có đườ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ẻ.

Tuy nhiên, với đồ thị đầy đủ Kn, bậc của mọi đỉnh đều là n - 1 nên nếu có hai đỉnh có bậc lẻ thì các đỉnh còn lại đều có bậc lẻ.

Do đó, đồ thị đầy đủ Kn không có đường đi Euler với mọi n.

2.14. Với giá trị nào của n thì đồ thị đầy đủ Kn có một chu trình Hamilton? Có một đường đi Hamilton?

Giải chi tiết:

Đồ thị đầy đủ luôn là đồ thị có chu trình Hamilton với mọi n. Đồ thị có chu trình Hamilton thì chắc chắn sẽ có đường đi Hamilton.