CHÀO MỪNG CÁC EM
ĐẾN VỚI TIẾT HỌC!

KHỞI ĐỘNG

Trong lí thuyết đồ thị, bài toán Bảy cây cầu ở Konigsberg (nay là thành phố Kaliningrad, ngướ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 dạo qua khắp các cây cầu mà 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 1 nét liền hay không?

CHUYÊN ĐỀ 2: LÀM QUEN VỚI MỘT VÀI KHÁI NIỆM CỦA

LÍ THUYẾT ĐỒ THỊ

BÀI 9: ĐƯỜNG ĐI EULER VÀ ĐƯỜNG ĐI HAMILTON

NỘI DUNG BÀI HỌC

1. ĐƯỜNG ĐI EULER

HĐ1

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

Giải:

Ta có thể vẽ mỗi hình trên Hình 2.16 bằng một nét liền.

+ Đối với Hình 2.16 a), ta có thể vẽ một nét liền theo thứ tự .

+ Đối với Hình 2.16 b), ta có thể vẽ một nét liền theo thứ tự ABCDAEFB.

Khái niệm

Cho một đa đồ thị .

Một đường đi đơn giản từ đỉnh đến đỉnh và chứa mọi cạnh của được gọi là một đường đi Euler từ đến .

Một chu trình đơn giản chứa mọi cạnh của được gọi là mọt chu trình Euler của .

Ví dụ 1:Tìm một chu trình Euler của đồ thị trên Hình 2.17

Giải:

Một chu trình Euler của đồ thị là

Định lí 1 (Euler)

Một đa đồ thị có một chu trình Euler khi và chỉ khi liên thông và mọi đỉnh của đều có bậc chẵn.

Định lí 2

Một đa đồ thị có một đường đi Euler từ đến khi và chỉ khi liên thông và mọi đỉnh của đều có bậc chẵn, chỉ trừ và có bậc lẻ.

Chú ý: Hai định lí trên cũng đúng cho trường hợp là đơn đồ thị.

Ví dụ 2:Giải thích vì sao trong Hình 2.18:

a) Các hình a) và b) có thể vẽ được bằng một nét liền;

b) Các hình c) và d) không thể vẽ được bằng một nét liền.

Giải:

a) Đồ thị ở hình a) là liên thông và các đỉnh đều có bậc chẵn (ở đây là bậc bằng 2) nên nó có chu trình Euler. Đồ thị ở hình b) là liên thông và chỉ có đúng hai đỉnh bậc lẻ (ở đây là bậc bằng 3) nên nó có đường đi Euler. Vì vậy ta có thể vẽ các hình a) và b) bằng một nét liền.

b) Các đồ thị ở hình c) và d) có bốn đỉnh bậc lẻ (ở đây là bậc bằng 3) nên chúng không có chu trình Euler và cũng không có đường đi Euler. Vì vậy ta không thể vẽ các hình c) và d) bằng một nét liền.

Hãy giải bài toán trong tình huống mở đầu.

Giải:

Xét đa đồ thị G ở Hình 2.15b. Vì các đỉnh A, B, C, D đều có bậc lẻ nên theo Định lí 2, G không có đường đi Euler (và không có cả chu trình Euler).

Vậy không thể nào đi dạo qua khắp các cây cầu của thành phố Königsberg mà mỗi cầu chỉ đi qua một lần.

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:

a) Đồ thị a) liên thông, có đúng 2 đỉnh bậc lẻ là và nên có đường đi Euler nối và , chẳng hạn .

b) Đồ thị b) có 4 đỉnh bậc lẻ nên không có đường đi Euler.

2. ĐƯỜNG ĐI HAMILTON

HĐ2

Có 5 thành phố du lịch 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ểmnào quá một lần.

Giải:

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 là ta có thể đi theo thứ tự (hoặc có thể chọn , hoặc ,...).

Khái niệm

Một đường đi sơ cấp từ đỉnh đến đỉnh và qua mọi đỉnh của đồ thị được gọi là một đường đi Hamilton từ đến .

Một chu trình sơ cấp chứa mọi đỉnh của được gọi là một chu trình Hamilton của .

Ví dụ 4:Tìm một chu trình Hamilton của đồ thị trên Hình 2.21.

Giải:

Một chu trình Hamilton của đồ thị là ABECDA.

Định lí 3 (Ore)

Nếu là đơn đồ thị có đỉnh và mỗi cặp đỉnh không kề nhau đều có tổng bậc không nhỏ hơn thì có một chu trình Hamilton.

Hệ quả (Định lí Dirac)

Định lí 4

Nếu đơn đồ thị có đỉnh và mỗi đỉnh có bậc không

Ví dụ 5:Đồ thị Hình 2.22 có chu trình Hamilton không? Nếu có, hãy chỉ ra một chu trình Hamilton xuất phát từ đỉnh A.

Giải:

Đồ thị có 8 đỉnh, mỗi đỉnh đều có bậc là 4. Do đó, theo Định líDirac, đồ thị có một chu trình Hamilton.

Có thể thấy một chu trình Hamilton xuất phát từ đỉnh A là:

AGCKDHBEA.

--------------- Còn tiếp ---------------