Giáo án chuyên đề Khoa học máy tính 12 cánh diều Bài 1: Đồ thị, phân loại đồ thị

Ngày soạn:…/…/…

Ngày dạy:…/…/…

CHUYÊN ĐỀ 3: TÌM HIỂU KĨ THUẬT DUYỆT ĐỒ THỊ VÀ ỨNG DỤNG

BÀI 1: ĐỒ THỊ, PHÂN LOẠI ĐỒ THỊ

(2 tiết)

I. MỤC TIÊU

1. Kiến thức

Sau bài học này, HS sẽ:

• Trình bày được khái niệm đồ thị.

• Nhận biết được đơn đồ thị vô hướng và có hướng.

• Biết được một số thuật ngữ và tính chất của đồ thị.

• Tìm hiểu được một số ứng dụng.

2. Năng lực

Năng lực chung:

• Tự chủ và tự học: Chủ động, tích cực thực hiện công việc của cá nhân.

• Giao tiếp và hợp tác: Phân tích được các công việc cần thực hiện để hoàn thành nhiệm vụ của nhóm trong các hoạt động nhóm.

• Giải quyết vấn đề và sáng tạo: Nêu được nhiều ý tưởng mới trong học tập, suy nghĩ không theo lối mòn, tạo ra yếu tố mới dựa trên những ý tưởng khác nhau.

Năng lực Tin học:

• Trình bày được khái niệm và các loại đồ thị.

• Hiểu được một số thuật ngữ và tính chất trên đồ thị.

3. Phẩm chất

• Chăm chỉ: Tích cực tìm tòi và sáng tạo trong học tập.

• Trung thực: Thực hiện đúng phần việc của bản thân và hợp tác làm việc nhóm khi được giao nhiệm vụ. Có ý thức báo cáo kết quả một cách chính xác.

• Trách nhiệm: Hoàn thành các bài tập theo yêu cầu của GV thông qua hệ thống câu hỏi, phiếu học tập, thông qua sản phẩm.

II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU:

1. Đối với giáo viên:

• Máy chiếu, máy tính, màn hình hiển thị, hoặc ti vi.

• SGK, SGV Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Cánh diều.

2. Đối với học sinh:

• Các dụng cụ học tập theo yêu cầu của GV; SGK Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Cánh diều.

III. TIẾN TRÌNH DẠY HỌC

A. HOẠT ĐỘNG KHỞI ĐỘNG

a. Mục tiêu: Tạo hứng thú cho HS, giúp HS bước đầu hình dung về đồ thị.

b. Nội dung: GV yêu cầu HS làm việc cá nhân, suy nghĩ trả lời câu hỏi ở hoạt động Khởi động SGK tr.53. 

c. Sản phẩm học tập: HS hoàn thành hoạt động Khởi động SGK tr.53.

d. Tổ chức thực hiện:

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV dẫn dắt vào bài học, yêu cầu HS suy nghĩ trả lời câu hỏi Khởi động SGK trang 53:

Để mô tả các cặp tỉnh có địa giới giáp ranh nhau, ta có thể nêu bằng lời, ví dụ, quan sát lược đồ bốn tỉnh Bạc Liêu, Cà Mau, Sóc Trăng và Kiên Giang trong Hình 1, ta nói “Các cặp tỉnh: (Bạc Liêu, Cà Mau), (Bạc Liêu, Sóc Trăng), (Bạc Liêu, Kiên Giang), (Kiên Giang, Cà Mau) giáp ranh nhau; còn (Kiên Giang, Sóc Trăng) và (Sóc Trăng, Cà Mau) không giáp ranh nhau”. Em có cách mô tả nào khác về mối quan hệ giáp ranh giữa các tỉnh đó không?

Hình 1. Lược đồ phần đất liền một số tỉnh miền Tây Nam Bộ

Bước 2: HS thực hiện nhiệm vụ học tập

- HS tiếp nhận, thực hiện nhiệm vụ.

- GV hướng dẫn, hỗ trợ HS (nếu cần thiết).

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời một số HS xung phong trả lời câu hỏi Khởi động tr.53 SGK.

Gợi ý trả lời:

Việc mô tả mối quan hệ giáp ranh giữa các tỉnh có thể biểu diễn bằng đồ thị như sau:

- HS khác lắng nghe, nhận xét và bổ sung.

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

GV đánh giá kết quả của HS, dẫn dắt HS vào bài học mới: Để mô tả (biểu diễn) các đối tượng và mối quan hệ giữa các đối tượng có thể dùng mô hình đồ thị. Vậy đồ thị có cấu trúc và được phân loại như thế nào? Đồ thị có những tính chất gì? Để giúp các em trả lời được những câu hỏi này, chúng ta sẽ cùng nhau đến với Bài 1: Đồ thị, phân loại đồ thị.

B. HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1. Khái niệm đồ thị

a. Mục tiêu: Cung cấp cho HS khái niệm và một số ứng dụng của đồ thị.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 1. Khái niệm đồ thị và thực hiện nhiệm vụ học tập.

c. Sản phẩm: Khái niệm một số ứng dụng của đồ thị.

d. Tổ chức thực hiện:

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập - GV trình chiếu lại hình ảnh đồ thị trong hoạt động Khởi động và đặt câu hỏi: + Đồ thị là gì? - GV yêu cầu HS làm việc độc lập và thực hiện Hoạt động 1 SGK tr.54: Việc mô tả mối quan hệ giáp ranh của bốn tỉnh Kiên Giang, Cà Mau, Bạc Liêu, Sóc Trăng trong phần khởi động có thể biểu diễn bằng bốn đỉnh (tương ứng với bốn vòng tròn nét liền) và bốn cạnh (tương ứng với bốn đường nối giữa hai vòng tròn cho biết cặp tỉnh giáp ranh) như trong Hình 2. Em hãy vẽ Hình 2 vào vở và vẽ thêm hai vòng tròn mô tả hai tỉnh Cần Thơ, Hậu Giang cùng với các cạnh để mô tả mối quan hệ giáp ranh của sáu tỉnh. Hình 2. Đồ thị mô tả mối quan hệ giáp ranh của bốn tỉnh Kiên Giang, Cà Mau, Bạc Liêu, Sóc Trăng - GV tiếp tục đặt câu hỏi: + Theo em, đồ thị được ứng dụng trong thực tế như thế nào? Bước 2: HS thực hiện nhiệm vụ học tập - HS tìm hiểu nội dung mục 1 SGK tr.54 và trả lời các câu hỏi mà GV đưa ra. - GV quan sát và trợ giúp HS (nếu cần thiết). Bước 3: Báo cáo kết quả hoạt động và thảo luận - HS lần lượt trả lời các câu hỏi. - HS khác nhận xét, bổ sung.  Hướng dẫn thực hiện Hoạt động 1 SGK tr.54: Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập - Từ câu trả lời của HS, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ. - GV chính xác hoá lại các nội dung kiến thức. - GV chuyển sang nội dung tiếp theo.

1. Khái niệm đồ thị - Khái niệm: Đồ thị G là một cấu trúc gồm hai tập:  Tập đỉnh V (mỗi đỉnh tương ứng với một đối tượng). Tập cạnh E (mỗi cạnh cho biết mối quan hệ giữa hai đối tượng). - Ứng dụng: Đồ thị được dùng để biểu diễn, giải nhiều bài toán trong nhiều lĩnh vực, như mô tả các hệ thống:  Mạng điện. Mạng lưới giao thông. Mạng máy tính. Mối quan hệ dinh dưỡng giữa các loài. …

Hoạt động 2. Phân loại đồ thị

a. Mục tiêu: Cung cấp cho HS khái niệm đơn đồ thị vô hướng và đơn đồ thị có hướng.

b. Nội dung: GV giao nhiệm vụ; HS làm việc độc lập, tìm hiểu nội dung mục 2. Phân loại đồ thị và thực hiện nhiệm vụ học tập.

c. Sản phẩm: Khái niệm đơn đồ thị vô hướng và đơn đồ thị có hướng

d. Tổ chức thực hiện:

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập - GV trình bày cách phân loại đồ thị, sau đó hướng dẫn HS tìm hiểu kiến thức bằng cách trả lời các câu hỏi: + Thế nào là đơn đồ thị vô hướng? + Thế nào là đơn đồ thị có hướng? - GV phân tích ví dụ minh họa để HS hiểu rõ khái niệm đơn đồ thị vô hướng và đơn đồ thị có hướng. Bước 2: HS thực hiện nhiệm vụ học tập - HS tìm hiểu nội dung mục 2 SGK tr.54 – 55 và trả lời các câu hỏi mà GV đưa ra. - GV quan sát và trợ giúp HS (nếu cần thiết). Bước 3: Báo cáo kết quả hoạt động và thảo luận - HS lần lượt trả lời các câu hỏi. - HS khác nhận xét, bổ sung. Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập - Từ câu trả lời của HS, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ. - GV chính xác hoá lại các nội dung kiến thức.  - GV chuyển sang nội dung tiếp theo.

2. Phân loại đồ thị - Để phân loại đồ thị, người ta dựa vào các tính chất của cạnh. - Một cạnh của đồ thị có thể có các tính chất:  Có hướng hay vô hướng. Có trọng số hay không có trọng số. … Trong bài học này, chúng ta sẽ tìm hiểu hai loại đồ thị: đơn đồ thị vô hướng và đơn đồ thị có hướng. a) Đơn đồ thị vô hướng Khái niệm: Đơn đồ thị vô hướng là đồ thị  G = (V, E) gồm một tập không rỗng V mà các phần tử là các đỉnh và một tập E mà các phần tử là các cạnh, mỗi cạnh tương ứng với một cặp đỉnh phân biệt không có thứ tự. Một cạnh nối giữa hai đỉnh phân biệt u, v kí hiệu là {u, v} hoặc {v, u}. Ví dụ: Đồ thị trong Hình 2 là đơn đồ thị vô hướng. Nói tỉnh Cà Mau giáp ranh với tỉnh Kiên Giang là đồng nghĩa với nói tỉnh Kiên Giang cũng giáp ranh với tỉnh Cà Mau và cặp đỉnh này không phân biệt thứ tự. Hình 2. Đồ thị mô tả mối quan hệ giáp ranh của bốn tỉnh Kiên Giang, Cà Mau, Bạc Liêu, Sóc Trăng b) Đơn đồ thị có hướng Khái niệm: Đơn đồ thị có hướng là đồ thị  G = (V, E) gồm một tập đỉnh không rỗng V và một tập cạnh E, mỗi cạnh tương ứng với một cặp đỉnh phân biệt có thứ tự. Một cạnh nối từ đỉnh u tới đỉnh v kí hiệu là (u, v). Ví dụ: Hình 3 mô tả mối quan hệ dinh dưỡng giữa sáu loài, mối quan hệ giữa các đỉnh là có thứ tự, chẳng hạn Chuột là thức ăn của Rắn nhưng Rắn không phải là thức ăn của Chuột mà Rắn là thức ăn của Diều hâu. Hình 3. Mô tả mối quan hệ dinh dưỡng  giữa các loài

Hoạt động 3. Một số thuật ngữ và tính chất trên đồ thị

a. Mục tiêu: Cung cấp cho HS một số thuật ngữ và tính chất trên đồ thị.

b. Nội dung: GV giao nhiệm vụ; HS làm việc độc lập, tìm hiểu nội dung mục 3. Một số thuật ngữ và tính chất trên đồ thị và thực hiện nhiệm vụ học tập.

c. Sản phẩm: Một số thuật ngữ và tính chất trên đồ thị.

d. Tổ chức thực hiện:

--------------------------------------

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