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: