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

CHÀO MỪNG CẢ LỚP

ĐẾN BUỔI HỌC NÀY!

KHỞI ĐỘNG

Em hãy nhắc lại định nghĩa mảng hai chiều và cách khai báo mảng hai chiều trong ngôn ngữ Python. Theo em, có thể sử dụng mảng hai chiều để biểu diễn một đồ thị được không?

KHỞI ĐỘNG

Mảng hai chiều: một cấu trúc dữ liệu cho phép lưu trữ các phần tử trong một bảng có hàng và cột. Mỗi phần tử trong mảng hai chiều có thể được truy cập bằng cách sử dụng hai chỉ số: chỉ số hàng và chỉ số cột.

KHỞI ĐỘNG

Cách khai báo mảng hai chiều trong Python:

• Sử dụng danh sách lồng nhau.

• Sử dụng vòng lặp để tạo mảng hai chiều.

Có thể sử dụng mảng hai chiều để biểu diễn một đồ thị.

BÀI 3.2:

BIỂU DIỄN ĐỒ THỊ

NỘI DUNG BÀI HỌC

1. Biểu diễn đồ thị bằng ma trận kề (mảng hai chiều)

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

1. BIỂU DIỄN ĐỒ THỊ

BẰNG MA TRẬN KỀ

(MẢNG HAI CHIỀU)

1. Biểu diễn đồ thị bằng

ma trận kề (mảng hai chiều)

• Đồ thị G có thể được biểu diễn bằng một ma trận kề A (mảng hai chiều) có n hàng và n cột, với n là số đỉnh của đồ thị.
• Phần tử ở hàng i cột j của ma trận kề A, kí hiệu là A[i, j], được xác định như sau:

1. Biểu diễn đồ thị bằng

ma trận kề (mảng hai chiều)

Biểu diễn đồ thị vô hướng ở Hình 1 và đồ thị có hướng ở Hình 2 bằng ma trận kề.

1. Biểu diễn đồ thị bằng

ma trận kề (mảng hai chiều)

1. Biểu diễn đồ thị bằng

ma trận kề (mảng hai chiều)

1. Biểu diễn đồ thị bằng

ma trận kề (mảng hai chiều)

Theo em, ma trận kề có thể được biểu diễn bằng kiểu dữ liệu nào trong Python?

Ma trận kề được cài đặt bằng danh sách (kiểu list của Python).

Chương trình biểu diễn đồ thị bằng ma trận kề:

• Hàm cho phép thêm các đỉnh, các cạnh vào đồ thị và hàm tạo đồ thị (vô hướng hoặc có hướng) từ tệp:

Chương trình biểu diễn đồ thị bằng ma trận kề:

• Hàm kiểm tra tệp đồ thị:
• Để tạo đồ thị vô hướng/có hướng từ tệp dữ liệu vô hướng/có hướng, có thể viết chương trình có tham số điều khiển (control parameter) là một cờ (flag) với quy ước:
• Hàm createAdjMatrixGraph(filename, flag):
• flag = 0 là tệp dữ liệu của đồ thị vô hướng.
• flag = 1 là tệp dữ liệu của đồ thị có hướng.

Lưu ý

Tệp dữ liệu của đồ thị vô hướng chỉ chứa các cạnh (không phải chứa các cung, số lượng cung gấp đôi số lượng cạnh).

• Hàm tạo đồ thị biểu diễn bằng ma trận kề từ tệp:

LƯU Ý

Tệp dothi.txt có dạng

Hàng đầu tiên là danh sách các đỉnh của đồ thị, mỗi đỉnh cách nhau bởi khoảng trắng.

Các hàng kế tiếp: mỗi hàng chứa một cung gồm đỉnh gốc và đỉnh ngọn.

Kết quả của chương trình trên là:

Hoạt động Làm SGK tr.56

Bảng 3. Ma trận kề biểu diễn đồ thị

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

2. Đồ thị vô hướng tương ứng (Đồ thị dưới đây chỉ là một trong các phương án vì các điểm có thể nằm ở nhiều vị trí khác nhau):

GHI NHỚ

2. BIỂU DIỄN ĐỒ THỊ

BẰNG DANH SÁCH KỀ

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

Đồ thị G có thể được biểu diễn bằng n danh sách kề của đỉnh với n là số đỉnh của đồ thị.

Ví dụ 4:

Danh sách kề có thể được cài đặt bằng kiểu từ điển (dictionary) của Python. Phần tử thứ i trong từ điển sẽ chứa danh sách các đỉnh kề của đỉnh i.

• Các hàm cho phép thêm các đỉnh, các cạnh vào đồ thị và hàm tạo danh sách kề của đồ thị với dữ liệu được lấy từ tệp:

Hoạt động Làm SGK tr.57

1. Em hãy dùng danh sách kề biểu diễn các đồ thị ở Hình 4 và Hình 5.

2. Từ danh sách kề ở Bảng 6. Hãy vẽ đồ thị có hướng tương ứng.

Bảng 6. Danh sách kề biểu diễn đồ thị

1. Danh sách kề biểu diễn các đồ thị ở Hình 4 và Hình 5:

2. Đồ thị có hướng tương ứng (Đồ thị dưới đây chỉ là một trong các phương án vì các điểm có thể nằm ở nhiều vị trí khác nhau):

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