Giáo án chuyên đề Toán 11 chân trời CĐ 2 bài 2: Đường đi Euler và đường đi Hamilton (P2)

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: Chuyển giao nhiệm vụ:

- GV triển khai HĐKP4 và vẽ Hình 15b), cho HS quan sát.

+ GV mời 2 – 3 HS nêu cách đi theo đề bài yêu cầu.

+ GV nhận xét: Những đường đi mà các bạn vừa trình bày được gọi là đường đi Hamilton trong một đồ thị.

 GV trình chiếu, giới thiệu, giảng giải cho HS hiểu về Khái niệm đường đi Hamilton

- GV lưu ý cho HS về chu trình Hamilton và cách để có một đường đi Hamilton.

- GV cho HS thỏa luận nhóm 3 và thực hiện Ví dụ 6

+ Các nhóm vận dụng Khái niệm chu trình Hamilton và thực hiện các ý của Ví dụ.

+ GV chỉ định 3 HS đứng tại chỗ phát biểu đáp án cho 3 đồ thị hình 16.

- GV dẫn dắt: Người ta tìm ra được các điều kiện đủ để một đồ thị có chu trình Hamilton nhưng chưa tìm được điều kiện cần và đủ nào.

 GV giới thiệu hai điều kiện đủ để một đồ thị có chu trình Hamilton.

- GV giới thiệu tiếp Định lí 4 cho HS hiểu rõ hơn về điều kiện đủ của một chu trình Hamilton.

- GV gợi ý cho HS thực hiện Ví dụ 7

+ Đồ thị  có bao nhiêu đỉnh và có liên thông không? Mỗi đỉnh của  có thỏa mãn Định lí Dirac hay không?

 Nếu có, hãy xác định 1  chu trình Hamilton?

+ Đồ thị  có bao nhiêu đỉnh? Và  có thỏa mãn Định lí Ore hay không?

 Nếu có hãy chỉ ra một chu trình Hamilton?

- GV giảng giải cho HS về vấn đề: Có nhiều đồ thị tuy không thỏa mãn của định lí Dirac hay Ore nhưng vẫn có chu trình Hamilton và giới thiệu cách tìm chu trình (đường đi) Hamilton của chúng.

- GV hướng dẫn cho HS thực hiện Ví dụ 8

+ Xác định số đỉnh và bậc của các định đó trong đồ thị .

+ Chu trình Hamilton của  phải đi qua các cạnh nào và không thể đi qua cạnh nào?

+ Nếu xóa cạnh  và  thì chu trình Hamilton còn đi qua được những cạnh nào nữa?

+ Từ đó tìm một chu trình Hamilton của đồ thị .

+ HS thực hiện tương tự với đồ thị .

- HS thảo luận nhóm đôi thực hiện và trình bày HĐTH3

+ GV mời 2 HS lên bảng thực hiện tìm chu trình Hamilton cho đồ thị Hình a) và b)

+ HS dưới lớp quan sát, nhận xét và cho ý kiến bổ sung.

+ GV chốt đáp án.

- GV gợi ý cho HS thực hiện HĐVD2

+ Đồ thị Hình 22 có những cạnh nào bậc 2? Và đồ thị Hamilton phải đi qua cạnh nào và không đi qua cạnh nào?

+ Xóa những cạnh chu trình không đi qua thì xuất hiện mấy đỉnh có bậc 2?

+ Từ đó đồ thị đi qua những cạnh nào tiếp và không đi qua cạnh nào?

+ Xóa tiếp những cạnh chu trình không đi qua, thì chu trình sẽ đi qua những ccanhj còn lại nào?

=> HS tìm chu trình Hamilton từ những cạnh mà chu trình đi qua.

Bước 2: Thực hiện nhiệm vụ:

- HS theo dõi SGK, chú ý nghe, tiếp nhận kiến thức, suy nghĩ trả lời câu hỏi, hoàn thành các yêu cầu.

- GV: quan sát và trợ giúp HS.

Bước 3: Báo cáo, thảo luận:

- HS giơ tay phát biểu, lên bảng trình bày

- Một số HS khác nhận xét, bổ sung cho bạn.

Bước 4: Kết luận, nhận định: GV tổng quát lưu ý lại kiến thức trọng tâm:

+ Khái niệm đường đi và chu trình Hamilton.

+ Tính chất (Định lí) Dirac, Ore.

2. Đường đi Hamilton

HĐKP4

Có nhiều cách đi như vậy, ví dụ:

Khái niệm

Cho đồ thị . Đường đi đi qua mọi đỉnh của , mỗi đỉnh đúng một lần gọi là đường đi Hamilton trong .

Đường đi bắt đầu và kết thúc tại đỉnh , đi qua mọi đỉnh của , mỗi đỉnh đúng một lần, trừ đỉnh , được gọi là chu trình Hamilton trong .

Chú ý

1) Đường đi và chu trình Hamilton đi qua mỗi cạnh của đồ thị nhiều nhất một lần (không đi qua lần nào hoặc đi qua một lần).

2) Từ chu trình Hamilton, bỏ đi cạnh cuối cùng ta được đường đi Hamilton. Do đó, một đồ thị có chu trình Hamilton thì cũng có đường đi Hamilton (như vậy, một đồ thị không có đường đi Hamilton thì cũng không có chu trình Hamilton).

Ví dụ 6: (SGK – tr.55)

Hướng dẫn giải (SGK – tr.55)

Định lí 3 (Định lí Dirac)

Cho đồ thị  một đơn đồ thị liên thông có  đỉnh với . Khi đó, nếu mọi đỉnh của đồ thị  đều có bậc lớn hơn hoặc bằng  thì đồ thị  có chu trình Hamilton.

Định lí 4 (Định lí Ore)

Cho  là một đơn đồ thị liên thông có  đỉnh với . Nếu với mọi cặp đỉnh  không kề nhau của  đều có:

Thì đồ thị  có chu trình Hamilton.

Ví dụ 7: (SGK – tr.56)

Hướng dẫn giải (SGK – tr.56)

Nhận xét:

Tìm chu trình (đường đi) Hamilton dựa trên quy tắc:

1) Chu trình Hamilton đi qua ít nhất 2 đỉnh bậc 2, ngoại trừ đỉnh bắt đầu hoặc kết thúc.

2) Một đỉnh có bậc lớn hơn 2 chỉ có thể được đi qua tối đa 2 lần trong một chu trình Hamilton.

3) Đường đi Hamilton đi qua ít nhất 1 cạnh nối với đỉnh bậc 1. Đồ thị có đỉnh bậc 1 thì không có chu trình Hamilton.

Ví dụ 8: (SGK – tr.57)

Hướng dẫn giải: SGK – tr.7

HĐTH3

=> Chu trình Hamilton:

=> Chu trình Hamilton:

HĐVD2

- Đỉnh  và  có bậc bằng 2 nên chu trình Hamilton (nếu có) phải đi qua cạnh

+ Những cạnh mà chu trình không đi qua: . Xóa các cạnh này đi.

+ Khi đó đỉnh  có bậc 2, chu trình đi qua cạnh .

+ Đồ thị sẽ không đi qua . Xóa 2 cạnh này

+ Khi đó chu trình đi qua cạnh .

=> Ta có chu trình:

Ta có :

Suy ra đồ thị  có tất cả các đỉnh đều có bậc chẵn.

Vậy đồ thị  có chu trình Euler

Chẳng hạn :

Ta có :  ;

Suy ra đồ thị  có hai đỉnh  có bậc lẻ

Vậy đồ thị  không có chu trình Euler

Ta có :

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

Một số chu trình Hamilton của đồ thị  là :

Một đường đi Hamilton của đồ thị :

Biểu thị mỗi khu phố  bằng một đỉnh, mỗi cây cầu nối hai đỉnh, ta được đồ thị như hình bên.

Ta thấy tất cả các đỉnh đều có bậc chẵn (bằng 4) nên đồ thị có chu trình Euler.

Tức là có cách đi qua tất cả các cây cầu, mỗi cây cầu chỉ qua một lần, rồi quay lại nơi xuất phát.

Chẳng hạn, có chu trình : .

Biểu thị mỗi vùng đất  và  bằng mỗi đỉnh, mỗi cây cầu bằng một cạnh nối hai đỉnh tương ứng, ta được đồ thị như hình bên.

a) Đồ thị không có chu trình Euler, vì nó có hai đỉnh bậc lẻ là  và . Do đó, không có cách đi qua tất cả các cây cầu, mỗi cây cầu chỉ qua một lần, rồi quay trở lại nơi xuất phát.

b) Có cách đi như vậy, chẳng hạn, đi theo đường đi Euler : .