HĐ CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

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

Nhiệm vụ 1: Tìm hiểu khái niệm đồ thị

- GV cho HS thực hiện HĐ 1.

+ GV lưu ý, đầu mút A và B có hai cạnh nối hai đầu mút.

- GV cho HS khái quát:

+ Thế nào đồ thị G?

- GV chú ý cho HS về bản chất của đồ thị là có bao nhiêu đỉnh, bao nhiêu cạnh, đỉnh nào được nối với đỉnh nào.

- HS đọc Ví dụ 1. GV gợi mở: có thể sử dụng đồ thị để biểu diễn thành phố và đường đi để dễ hình dung, giống như Euler đã làm với các cây cầu và vùng đất.

- HS thực hiện Luyện tập 1.

- HS thực hiện HĐ 2. Từ đó HS nhận xét đặc điểm của đồ thị Hình 4 về: mỗi cặp đỉnh của đồ thị có bao nhiêu cạnh nối nó, có đỉnh được nối với chính nó không?

- GV giới thiệu với đặc điểm như của Hình 4, đồ thị được gọi là đồ thị đơn.

- HS đọc Ví dụ 2, tìm đồ thị đơn và giải thích.

- GV có thể giới thiệu thêm cho HS.

+ Nếu hai đầu mút của cạnh trùng nhau tại đỉnh C thì ta gọi cạnh ấy là một khuyên, kí hiệu CC.

Ví dụ:

- HS thực hiện Luyện tập 2: Cho ví dụ về đồ thị đơn.

- GV đưa ra quy ước: Nếu không nói gì thêm, các đồ thị sẽ được giả thiết là đồ thị đơn.

Nhiệm vụ 2: Tìm hiểu về bậc của đỉnh

- HS thực hiện HĐ 3.

Từ đó GV giới thiệu về bậc của đỉnh P.

- HS khái quát thế nào là bậc của đỉnh A.

+ Nhận xét: Bậc của đỉnh và số cạnh nhận đỉnh đó là đầu mút có mối quan hệ gì?

(Bằng nhau).

- HS đọc hiểu Ví dụ 3, tìm bậc các đỉnh trong đồ thị hình 6, từ đó xác định bậc lẻ, bậc chẵn.

- HS thực hiện Luyện tập 3. Xác định các đỉnh bậc lẻ.

- HS thực hiện HĐ 4.

Kết quả của HĐ 4 cho thấy mối liên hệ của tổng các bậc của đỉnh và số cạnh của đồ thị đó.

- HS phát biểu định lí.

- Sử dụng định lí vừa học, chứng minh Ví dụ 4.

- HS thảo luận, làm Luyện tập 4, có thể đưa ra nhiều đáp án.

Nhiệm vụ 3: Tìm hiểu về đường đi trên đồ thị

- HS thực hiện HĐ 5.

- GV giới thiệu

+ Hai đỉnh kề nhau hay láng giềng của nhau.

+ Đường đi từ đỉnh A đến đỉnh E của đồ thị.

- Từ đó có khái quát về đường đi, chu trình.

- HS chỉ ra đường đi và chu trình trong Ví dụ 5.

- HS thực hiện Luyện tập 5.

- HS thực hiện HĐ 6.

GV giới thiệu về đồ thị liên thông.

- HS đọc Ví dụ 6, áp dụng làm Luyện tập 6.

+ Nhận biết và thể hiện đồ thị liên thông và đồ thị không liên thông.

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, hoàn thành các yêu cầu, thảo luận nhóm.

- GV quan sát hỗ trợ.

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 và yêu cầu HS ghi chép đầy đủ vào vở.

I. Bài toán bảy cây cầu của Euler

II. Một số khái niệm cơ bản

1. Khái niệm đồ thị

HĐ 1:

Các đỉnh: A, B, C, D.

Các cạnh: AB (a), AB (b), AC (a), AC (b), AD, BD, CD.

Kết luận:

Đồ thị G là hình bao gồm:

• Tập hợp hữu hạn các điểm, mỗi điểm gọi là một đỉnh của đồ thị,

• Tập hợp các đoạn (cong hoặc thẳng), mỗi đoạn nối hai đỉnh nào đó của đồ thị, được gọi là cạnh của đồ thị.

Ví dụ 1 (SGK – tr.36)

Luyện tập 1:

HĐ 2:

a) Không có đỉnh nào được nối với chính nó bởi một cạnh của đồ thị.

b) Mỗi cặp đỉnh có nhiều nhất 1 cạnh nối chúng.

Kết luận

Đồ thị G được gọi là đồ thị đơn nếu mỗi cặp đỉnh của đồ thị chỉ có không quá một cạnh nối chúng và không có đỉnh nào được nối với chính nó bởi một cạnh của đồ thị.

Ví dụ 2 (SGK – tr.37)

Đồ thị đơn: hình a.

Luyện tập 2:

Ví dụ về đồ thị đơn

Quy ước: Nếu không nói gì thêm, từ nay về sau các đồ thị đều được giả thiết là đồ thị đơn.

2. Bậc của đỉnh

HĐ 3:

Số cạnh nhận P làm đầu mút là: 3.

Kết luận

Bậc của một đỉnh A trong đồ thị G là số cạnh của đô thị nhận đỉnh A làm đầu mút, kí hiệu là d(A).

Nhận xét:

Một đỉnh của đồ thị có bậc n nếu đỉnh đó là đầu mút của n cạnh.

Ví dụ 3 (SGK – tr.37)

Luyên tập 3:

Các đỉnh bậc lẻ của đồ thị là: B, E (đều có bậc 3).

HĐ 4:

a) Tổng các bậc của năm đỉnh là: 3 + 2 + 2 + 4 + 1 = 12.

b) Số cạnh của đồ thị: 6.

c) Tổng các bậc của năm đỉnh gấp đôi tổng số cạnh của đồ thị.

Kết luận:

Trong một đồ thị, tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh của đồ thị đó.

Ví dụ 4: Chứng minh rằng trong một đồ thị, số đỉnh có bậc lẻ là một số chẵn.

Giải:

Theo định lí trên, tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh của đồ thị đó, suy ra tổng tất cả các bậc của các đỉnh là số chẵn. Vậy số đỉnh bậc lẻ là số chẵn.

Luyện tập 4:

Các đỉnh bậc chẵn là: A, C, D.

3. Đường đi trên đồ thị

HĐ 5:

a) Hai đỉnh A, B có được nối với nhau bằng một cạnh.

b) Dãy các cạnh kế tiếp nhau AB, BC, CD, DE có đặc điểm: không có cạnh nòa xuất hiện hai lần, đỉnh cuối của cạnh bất kì là đỉnh đầu của cạnh tiếp theo, không có đỉnh nào được đi qua hai lần.

Nhận xét:

Hai đỉnh A, B được nối với nhau bằng một cạnh của đồ thị. Ta nói hai đỉnh A, B là kề nhau hay là láng giềng của nhau.

Kết luận:

Trong một đồ thị, dãy các cạnh kế tiếp nhau AB, BC, ...,MN, NP được gọi là một đường đi từ đỉnh A đến đỉnh P, kí hiệu ABC...MNP, nếu dãy các cạnh kế tiếp nhau đó có những tính chất sau: không có cạnh nào xuất hiện hai lần, đỉnh cuối của cạnh bất kì là đỉnh đầu của cạnh tiếp theo và không có đỉnh nào được đi qua hai lần.

Một đường đi khép kín (đỉnh ban đầu của đường đi trùng với đỉnh cuối của đường đi đó) được gọi là một chu trình.

Ví dụ 5 (SGK – tr.39)

Luyện tập 5:

a) Một đường đi từ đỉnh A đến đỉnh F: ADF.

b) Một chu trình có đỉnh E là đỉnh đầu và đỉnh cuối: ECBADFE.

HĐ 6:

Hai đỉnh bất kì của đồ thị có được nối với nhau bằng một đường đi.

Kết luận

Một đồ thị được gọi là liên thông nếu hai đỉnh bất kì của đồ thị đều được nối với nhau bằng một đường đi.

Ví dụ 6 (SGK – tr.39)

Luyện tập 6:

Đồ thị liên thông

Đồ thị không liên thông:

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

SẢN PHẨM DỰ KIẾN

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

Nhiệm vụ 1: Tìm hiểu về đường đi Euler trên đồ thị

- HS thực hiện HĐ 7.

GV giới thiệu đường đi CABDCB được gọi là đường đi Euler.

- HS tổng quát thế nào là đường đi Euler,

+ HS hãy nêu thế nào là chu trình? Từ đó dự đoán thế nào là chu trình Euler?

(Chu trình: một đường đi khép kín).

- HS thực hiện Ví dụ 7 và Luyện tập 7.

+ Chỉ ra đường đi Euler trong hình.

- GV đặt câu hỏi: Có dấu hiệu nhận biết nào để xác định đồ thị có đường đi Euler hay chu trình Euler hay không?

+ Từ đó GV giới thiệu về định lí Euler.

- Sử dụng định lí Euler có thể chứng minh nhiều bài toán.

- HS đọc và thảo luận cách chứng minh trong Ví dụ 8, yêu cầu giải thích, trình bày cách chứng minh.

- Tương tự HS hãy chứng minh theo yêu cầu Luyện tập 8.

- GV chú ý: việc chỉ ra cụ thể cách xây dựng chu trình hay đường đi là không đơn giản.

Nhiệm vụ 2: Đường đi Hamilton trên đồ thị

- HS trả lời câu hỏi của HĐ 8.

- Từ đó GV giới thiệu về đường đi Hamilton.

- Gv đặt câu hỏi: Phân biệt giữa đường đi Euler và đường đi Hamilton?

(Đường đi Hamilton không nhất thiết qua tất cả các cạnh.

Đường Euler thì phải đi qua tất cả các cạnh. Đường Hamilton thì phải đi qua tất cả các đỉnh).

- HS đọc Ví dụ 9, trình bày lại và giải thích.

- HS thực hiện Luyện tập 9 theo nhóm đôi, chỉ ra đường đi Hamilton.

- GV đưa ra vấn đề:

+ Khác với xét xem có tồn tại đường đi Euler hay không, vấn đề tồn tại đường đi Hamilton trong tổng quát khó giải quyết.

- GV giới thiệu Định lí Dirac và định lí Ore.

- HS đọc hiểu Ví dụ 10 + 11.

+ HS nghe giảng, đọc đề bài thực hiện theo nhóm đôi Luyện tập 10 và 11 vào phiếu học tập.

- GV lưu ý: Các đồ thị có thể thỏa mãn điều của định lí này nhưng không thỏa mãn điều kiện của định lí kia.

Ví dụ Hình 18.

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 và yêu cầu HS ghi chép đầy đủ vào vở.

III. Đường đi Euler. Đường đi Hamilton trên đồ thị

1. Đường đi Euler trên đồ thị

HĐ 7:

a) Đường đi CABDCB cói đi qua tất cả các cạnh của đồ thị.

b) Đường đi trên đi qua mỗi cạnh 1 lần.

Khái niệm:

Trong đồ thị, một đường đi được gọi là đường đi Euler nếu đường đi đó đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần.  Nếu chu trình là đường đi Euler thì chu trình đó được gọi là chu trình Euler.

Ví dụ 7 (SGK – tr.40)

Luyện tập 7:

Đường đi Euler: ACDBEDAB; BDCADEBA.

Kết luận (Định lí Euler)

• Một đồ thị G có chu trình Euler khi và chỉ khi G liên thông và không có đỉnh bậc lẻ.

• Một đồ thị G có đường đi Euler không khép kín khi và chỉ khi G liên thông và có đúng hai đình bậc lẻ.

Ví dụ 8: Sử dụng định lí Euler, giải bài toán cây cầu ở Königsberg.

Giải:

Bài toán chính là bài toán chỉ ra một đường đi Euler không khép kín trong đồ thị G ở Hình 12.

Đồ thị G có bốn đỉnh bậc lẻ là A, B, C, D. Vì thế theo định lí Euler không có đường đi Euler không khép kín trong đồ thị G.

Luyện tập 8:

Có đỉnh A là đỉnh bậc lẻ (d(A)=3), nên theo định lí Euler thì đồ thị không có chu trình Euler.

2. Đường đi Hamilton trên đồ thị

Đường đi có đi qua tất cả các đỉnh của đồ thị và mỗi đỉnh đi qua một lần.

Khái niệm:

Trong đồ thị, một đường đi được gọi là đường đi Hamilton nếu đường đi đó đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần.

Nếu chu trình là đường đi Hamilton thì chu trình đó được gọi là chu trình Hamilton.

Chú ý:

Trong đồ thị, đường đi Hamilton hoặc chu trình Hamilton không nhất thiết phải đi qua mỗi cạnh của đồ thị đó.

Ví dụ 9 (SGK – tr.41)

Luyện tập 9:

Hai đường đi Hamilton bắt đầu từ đỉnh E: EABD, ECADB.

Định lí Dirac:

Cho đồ thị G gồm n đỉnh. Nếu bậc của mỗi đỉnh của G không nhỏ hơn  thì G có một chu trình Hamilton.

Định lí Ore:

Cho đồ thị G gồm n đỉnh. Nếu tổng bậc của hai đỉnh không kề nhau bất kì P và Q của G thỏa mãn bất đẳng thức:  thì G có một chu trình Hamilton.

Ví dụ 10 (SGK – tr.42)

Ví dụ 11 (SGK – tr.43)

Luyện tập 10:

Đồ thị G của hình 17 có 5 đỉnh, mỗi đỉnh có bậc lớn hơn hoặc bằng 3. Do đó theo định lí Dirac, đồ thị G có ít nhất một chu trình Hamilton.

Luyện tập 11:

Đồ thị G gồm 6 đỉnh.

Ta có: d(A) = 4, d(B) = 5, d(C) = 5, d(D) = 4, d(E) = 4, d(F) = 2.

Các cặp đỉnh không kề nhau là: A và F; F và D; F và E.

Nhận thấy tổng của hai đỉnh không kề nhau bất kì đều không nhỏ hơn 6.

Do đó, theo định lí Ore, đồ thị G có ít nhất một chu trình Hamilton.

Chú ý: Đồ thị ở Hình 18, thỏa mãn điều kiện của định lí Ore nhưng không thỏa mãn điều kiện của định lí Dirac.

PHIẾU HỌC TẬP

Luyện tập 10 (SGK – tr.42)

Chứng minh rằng đồ thị G ở Hình 17 có ít nhất một chu trình Hamilton.

Luyện tập 11 (SGK – tr.43)

Chứng minh rằng đồ thị G ở Hình 19 có ít nhất một chu trình Hamilton.