Giáo án chuyên đề Khoa học máy tính 12 cánh diều Bài 2: Biểu diễn đồ thị trên máy tính

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 mô tả cách biểu diễn đơn đồ thị có hướng bằng ma trận kề.

- GV yêu cầu HS thực hiện Hoạt động 1 SGK tr.57:

Nếu coi các địa điểm A, B, C, D trong Bảng 1 tương ứng là các đỉnh 0, 1, 2, 3 của đồ thị thì mảng hai chiều g trong Hình 1 biểu diễn đồ thị mô tả tuyến xe buýt giữa các địa điểm. Nếu Nam bổ sung thêm thông tin có một tuyến xe buýt từ B đến D, thì mảng g biểu diễn đồ thị thay đổi như thế nào? Em có nhận xét gì về tính đối xứng của mảng g?

Hình 1. Mảng g kích thước 4 × 4 biểu diễn đồ thị mô tả các tuyến xe buýt

- GV tiếp tục đặt câu hỏi:

+ Em hãy biểu diễn đơn đồ thị vô hướng sau bằng mảng hai chiều và rút ra nhận xét về tính đối xứng của mả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 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. 

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. Biểu diễn đồ thị bằng ma trận kề

- Để giải quyết bài toán bằng máy tính sử dụng mô hình đồ thị, trước tiên cần phải biểu diễn được đồ thị trên máy tính. 

- Một cách biểu diễn đơn giản, trực quan là biểu diễn bằng ma trận kề. 

• Đối với đơn đồ thị có hướng: Có thể sử dụng một mảng hai chiều g kích thước n × n (với n là số đỉnh của đồ thị), trong đó phần tử g[i][j] nhận giá trị bằng 1 (hoặc 0) tương ứng có (hoặc không có) cạnh nối từ i tới j.

• Đối với đơn đồ thị vô hướng: Vẫn sử dụng một mảng hai chiều g như đối với đơn đồ thị có hướng.

Ví dụ:

Mảng g biểu diễn đơn đồ thị vô hướng trên là:

Nhận xét: Mảng g biểu diễn đơn đồ thị vô hướng sẽ là một mảng đối xứng qua đường chéo chính, nghĩa là phần tử g[i][j] có giá trị bằng g[j][i].

Hướng dẫn thực hiện Hoạt động 1 SGK tr.57:

Nếu bổ sung tuyến xe buýt từ B đến D thì phần tử ở hàng 1 cột 3 đang là 0 thành 1.

Nhận xét: 

- Trước khi bổ sung, mảng g không đối xứng qua đường chéo chính.

- Sau khi bổ sung, mảng g đối xứng qua đường chéo chính (nếu đỉnh i tới được đỉnh j thì đỉnh j cũng tới được đỉnh i).

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 yêu cầu HS thực hiện Hoạt động 2 SGK tr.58:

Quan sát Hình 2, em hãy xây dựng mảng g biểu diễn đồ thị cho mối quan hệ giáp ranh giữa 8 tỉnh (các tỉnh được đánh số từ 0 đến 7): Sơn La (0), Điện Biên (1), Lai Châu (2), Lào Cai (3), Hà Giang (4), Cao Bằng (5), Lạng Sơn (6), Quảng Ninh (7). Mảng g có kích thước như thế nào? Em có nhận xét gì về số lượng số 0 và số 1 trong mảng g?

- Từ kết quả thực hiện Hoạt động 2, GV giúp HS thấy được việc biểu diễn đồ thị bằng ma trận kề trong trường hợp đồ thị thưa là chưa hiệu quả, từ đó giới thiệu cách biểu diễn đồ thị bằng danh sách kề.

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

- HS thực hiện Hoạt động 2.

- 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

- GV mời 1 – 2 HS trình bày kết quả thực hiện Hoạt động 2.

- 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 tóm tắt bài học:

……………………

2. Biểu diễn đồ thị bằng danh sách kề

- Trong trường hợp đồ thị có nhiều đỉnh nhưng ít cạnh (đồ thị thưa) thì việc biểu diễn đồ thị bằng ma trận kề sẽ rất lãng phí bộ nhớ vì phần lớn các phần tử của mảng đều nhận giá trị bằng 0. 

Khi đó, nên sử dụng biểu diễn đồ thị bằng danh sách kề, cụ thể, với mỗi đỉnh ta có một danh sách các đỉnh kề với đỉnh đó.

Ví dụ: Trong Bảng 2, với mỗi tỉnh ta liệt kê danh sách các tỉnh kề với tỉnh đó.

Bảng 2. Danh sách các tỉnh kề 
trong Hoạt động 2

Khi đó, ta sử dụng mảng g kích thước n (với n là số đỉnh của đồ thị), trong đó g[i] là một mảng một chiều chứa các đỉnh kề của đỉnh i. Mảng g tương ứng với Bảng 2 có giá trị như Bảng 3.

Bảng 3. Giá trị của mảng g

Cách biểu diễn này dùng được cho cả đơn đồ thị có hướng và đơn đồ thị vô hướng. Trong trường hợp đơn đồ thị vô hướng, nếu j nằm trong danh sách g[i] thì i cũng sẽ nằm trong danh sách g[j].

…………………..