Giáo án điện tử 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

CHÀO MỪNG CÁC EM

ĐẾN BUỔI HỌC MỚI!

KHỞI ĐỘNG

Nam thu thập thông tin về tuyến xe buýt giữa các địa điểm và kí hiệu như trong Bảng 1. Ví dụ, trên hàng bắt đầu bằng kí tự A cho biết từ địa điểm A có hai tuyến xe buýt, tuyến thứ nhất từ A tới B và tuyến thứ hai từ A tới D. Với thông tin Nam thu thập được, em hãy cho biết: Từ địa điểm B có tuyến xe buýt nào tới địa điểm D không? Từ địa điểm D có những tuyến xe buýt tới các địa điểm nào?

Bảng 1. Thông tin về các tuyến xe buýt

KHỞI ĐỘNG

Bảng 1. Thông tin về các tuyến xe buýt

Không có tuyến xe buýt nào từ địa điểm B tới địa điểm D.

Từ địa điểm D có các tuyến xe buýt tới địa điểm A, B, C.

BÀI 2:

BIỂU DIỄN ĐỒ THỊ

TRÊN MÁY TÍNH

NỘI DUNG BÀI HỌC

Biểu diễn đồ thị bằng ma trận kề

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

PHẦN 1.

BIỂU DIỄN ĐỒ THỊ

BẰNG MA TRẬN KỀ

1. Biểu diễn đồ thị bằng ma trận kề

• Giúp giải quyết bài toán bằng máy tính sử dụng mô hình đồ thị.
• Cách biểu diễn đơn giản, trực quan.
• 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.
• 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.

1. Biểu diễn đồ thị bằng ma trận kề

Ví dụ

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

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, phần tử g[i][j] = g[j][i].

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?

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?

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

Trả lời:

• 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).

PHẦN 2.

BIỂU DIỄN ĐỒ THỊ

BẰNG DANH SÁCH KỀ

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

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

Hình 2. Lược đồ một số tỉnh Bắc Bộ

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?

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

• Mảng g có kích thước 8 × 8.
• Số lượng số 0 trong mảng g gấp 3 lần số lượng số 1 (mảng g có 48 số 0 và 16 số 1).

Trả lời:

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

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.

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 đó.

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

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

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

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

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à vô hướng. 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].

• Biểu diễn đồ thị trên máy tính bằng ma trận kề là cách sử dụng một mảng hai chiều, mỗi phần tử là 0 hoặc 1, trong đó phần tử ở hàng i cột j bằng 1 nếu có cạnh nối từ đỉnh i tới đỉnh j.

• Khi biểu diễn đồ thị có nhiều đỉnh nhưng ít cạnh trên máy tính, chúng ta nên sử dụng danh sách kề, với mỗi đỉnh lưu trữ một danh sách các đỉnh kề với đỉnh đó.

GHI NHỚ

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

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