HĐ CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

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

- GV cho HS thảo luận hoàn thành HĐKP 1.

+ ý c có thể có nhiều cách đi. HS có thể nêu nhiều phương án.

- Từ đó GV giới thiệu về đồ thị là tập hợp các điểm và các cạnh của đồ thị.

- GV nhấn mạnh: 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.

- GV giới thiệu về cách kí hiệu các đỉnh, các cạnh của đồ thị.

+ Lưu ý: hai đầu mút có thể tạo ra nhiều cạnh khác nhau.

- GV giới thiệu về hai đỉnh kề nhau và đỉnh cô lập.

- HS nêu ví dụ hai đỉnh kề nhau, đỉnh cô lập của hình 2.

(Ví dụ: hai đỉnh kề nhau là A và B, B và D, C và F,…

Đỉnh cô lập: E)

- GV giới thiệu về hình có khuyên

- GV đặt câu hỏi:

+ Quan sát hình sau, nhận xét có khuyên nào không? Trong hình 2 có hai đỉnh nào được nối với nhau bằng nhiều hơn một cạnh không?

(Hình 1 không có khuyên, không có hai đỉnh nào được nối với nhau nhiều hơn một cạnh).

- Từ đó GV giới thiệu về đơn đồ thị và đa đồ thị.

Ví dụ về đa đồ thị: Hình 2

- HS đọc Ví dụ 1, trình bày về:

+ chỉ ra các cạnh, các đỉnh, số cạnh, số đỉnh.

+ Chỉ ra đỉnh kề đỉnh A.

+ GV có thể yêu cầu kể thêm đỉnh kề đỉnh B, C,…

+ Chỉ ra đỉnh cô lập.

- HS đọc Ví dụ 2. GV yêu cầu HS biểu diễn bài toán bằng đồ thị.

+ b) Số lần bắt tay có mối quan hệ gì với đỉnh hoặc số cạnh của đồ thị không?

(Số lần bắt tay bằng số cạnh của đồ thị vì hai người đã quen thì nối với nhau bởi 1 cạnh và hai người quen thì bắt tay).

- HS thực hiện Thực hành 1, lên bảng trình bày.

- HS làm Vận dụng 1 theo nhóm đôi, vẽ đồ thị biểu diễn sự kết nối giữa các máy tính theo bảng đã cho.

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ở.

1. Đồ thị

HĐKP 1:

a)

Hãng X có 4 đường thẳng bay đến 5 thành phố còn lại.

b) Giữa 6 thành phố có tất cả 11 đường bay của hãng X.

c) Có thể bay từ A đến 5 thành phố còn sao cho mỗi thành phố chỉ qua đúng một lần rồi quay trở về A.

(Ví dụ đường đi: A – D – C – B – F – E).

Kết luận:

Một đồ thị G là một tập hợp gồm hữu hạn các điểm, gọi là đỉnh của đồ thị, cùng với tập hợp các đoạn đường cong hoặc thẳng có các đầu mút là các đỉnh của đồ thị, gọi là cạnh của đồ thị.

Ví dụ:

Các đỉnh: A, B, C,…

Các cạnh: AB (hoặc BA), a, b.

Hai cạnh a và b có chung đầu mút B và D.

Kết luận

Hai đỉnh của đồ thị gọi là kề nhau (còn gọi đỉnh này kề với đỉnh kia) nếu chúng là hai đầu mút của một cạnh. Một đỉnh không kề với đỉnh nào (kể cả chính nó) gọi là đỉnh cô lập.

Nhận xét:

a) Hai đầu mút của 1 cạnh có thể trùng nhau, cạnh đó gọi là khuyên.

Ví dụ: hai khuyên a và b.

b) Một đồ thị không có khuyên, trong đó hai đỉnh bất kì là đầu mút của nhiều nhất một cạnh gọi là một đơn đồ thị.

Ví dụ:

c) Một đồ thị không có khuyên, trong đó hai đỉnh có thể nối với nhau bằng nhiều cạnh gọi là một đa đồ thị.

Ví dụ:

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

Ví dụ 2 (SGK – tr45)

Thực hành 1

a) Các đỉnh: A, B, C, D, E, F.

Các cạnh: AE, AD, AC, ED, DB, DC, CF, a, b, c.

Số đỉnh: 6. Số cạnh: 10.

b) Các đỉnh kề đỉnh D: A, E, B, C.

Các đỉnh kề đỉnh B: D, C.

c) G không có đỉnh cô lập.

Vận dụng 1:

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 yêu cầu HS đọc và hoàn thành HĐKP 2.

+ Xác định số cổng chào của các làng?

(Làng A: 3 cổng, B - 5, C – 2, D – 3, E – 3).

+ Từ đó trả lời câu hỏi a.

+ Tính tổng số cổng chào.

- GV giới thiệu: trong đồ thị mỗi đỉnh sẽ có số cạnh tương ứng, đó gọi là bậc của đỉnh.

+ GV giới thiệu về đỉnh bậc chẵn, đỉnh bậc lẻ, đỉnh cô lập có bậc 0.

- HS đọc Ví dụ 3, xác định bậc của các đỉnh ở đồ thị.

+ Tìm số cạnh và tổng các bậc.

- GV cho HS quan sát tìm điểm đặc biệt giữa số cạnh và tổng các bậc của đỉnh trong đồ thị.

(Tổng các bậc gấp đôi số cạnh).

- GV có thể yêu cầu HS giải thích hoặc đặt câu hỏi gợi mở thêm:

+ Nếu đồ thị có cạnh AB thì để tính số bậc của đỉnh A và B ta đã tính mấy lần cạnh AB?

- Từ đó rút ra nhận xét về tổng số bậc của đỉnh và tổng số cạnh.

+ Như vậy tổng số bậc của đỉnh là số chẵn hay số lẻ?

Ta có định lí về tổng số bậc của một đồ thị.

- GV cho HS thảo luận, suy nghĩ chứng minh nhận xét: số đỉnh bậc lẻ của mọi đồ thị là số chẵn.

(Gợi ý: tổng các bậc là số chẵn, mà tổng các bậc của các đỉnh bậc chẵn là số chẵn. Nên tổng các bậc của các đỉnh bậc lẻ cũng phải là số chẵn.

Để tổng bậc các đỉnh bậc lẻ là số chẵn thì số đỉnh phải là số chẵn).

- HS đọc, trình bày lại Ví dụ 4, ví dụ 5, áp dụng định lí về tổng số bậc của các đỉnh để xét xem số liệu đã cho có thể xác định được đồ thị không.

- HS thực hiện Thực hành 2.

+ chỉ ra bậc của đỉnh, tổng số bậc.

- HS làm Vận dụng 2 theo nhóm đôi, vận dụng định lí đã học để xét xem tổng số bậc của bài toán có thỏa mãn yêu cầu khô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, 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ở.

2. Bậc của đỉnh

HĐKP 2:

Làng C có ít cổng chào nhất. Làng B có nhiều cổng chào nhất.

b) Năm ngôi làng có 16 cổng chào.

Kết luận:

Giả sử A là đỉnh của một đồ thị. Số cạnh của đồ thị có A là đầu mút gọi là bậc của A, kí hiệu

Chú ý:

1) Đỉnh có bậc là một số chẵn còn được gọi là đỉnh bậc chẵn, đỉnh có bậc là một số lẻ còn được gọi là đỉnh bậc lẻ.

2) Đỉnh cô lập có bậc bằng 0.

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

Trong đồ thị G: d(A) = 2, d(B) = 3, …

Trong đồ thị H: d(A) = 4, d(B) = 5,…

Đồ thị G có 5 đỉnh.

Tổng các bậc của các đỉnh của G là: 10.

Đồ thị H có 9 cạnh.

Tổng các bậc của các đỉnh của H là: 18.

Nhận xét:

Trong mọi đồ thị, mỗi cạnh đều có hai đỉnh đầu mút. Như vậy, mỗi cạnh đóng góp 2 đơn vị vào tổng các bậc của tất cả các đỉnh của đồ thị.

Định lí:

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

Nhận xét:

Số đỉnh bậc lẻ của mọi đồ thị là một số chẵn.

Ví dụ 4 (SGK – tr.48)

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

Đồ thị trên có 6 đỉnh, 7 cạnh, các đỉnh đều bậc lẻ.

Thực hành 2:

a)

Tổng của các bậc của các đỉnh: 20.

b) Các đỉnh kề đỉnh B: A, D, C.

Số đỉnh này không bằng bậc của đỉnh B.

Vận dụng 2:

Giả sử tồn tại một đồ thị có ba đỉnh, trong đó hai đỉnh có bậc bằng 2 và một đỉnh có bậc bằng 3.

Tổng tất cả các bậc của các đỉnh là: 2 + 2 + 3 = 7.

Vô lí vì tổng tất cả các bậc của đỉnh là một số chẵn.

Vậy không tồn tại đồ thị theo yêu cầu đề bài.