Chuyên đề Tin học 12 Bài 3.2 (Chân trời sáng tạo): Biểu diễn đồ thị

Giải Chuyên đề Tin học 12 Bài 3.2: Biểu diễn đồ thị

Khởi động trang 53 Chuyên đề Tin học 12: 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?

Lời giải:

Định nghĩa mảng hai chiều và cách khai báo mảng hai chiều trong Python

Định nghĩa mảng hai chiều

Mảng hai chiều là 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.

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

Trong Python, có nhiều cách để khai báo và sử dụng mảng hai chiều, nhưng phổ biến nhất là sử dụng danh sách lồng nhau (nested lists). Dưới đây là một số cách để khai báo mảng hai chiều trong Python:

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

# Khai báo mảng hai chiều 3x3

array = [

[1, 2, 3],

[4, 5, 6],

[7, 8, 9]

]

# Truy cập phần tử tại hàng 1, cột 2

element = array[1][2] # Giá trị là 6

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

# Tạo mảng hai chiều 3x3 với các giá trị ban đầu là 0

rows, cols = 3, 3

array = [[0 for _ in range(cols)] for _ in range(rows)]

Sử dụng mảng hai chiều để biểu diễn đồ thị

Có thể sử dụng mảng hai chiều để biểu diễn một đồ thị. Một trong những cách phổ biến để làm điều này là sử dụng ma trận kề (adjacency matrix).

Ma trận kề

Ma trận kề là một mảng hai chiều dùng để biểu diễn các cạnh của đồ thị. Nếu đồ thị có n đỉnh, thì ma trận kề là một ma trận vuông n x n trong đó phần tử ở hàng i và cột j có giá trị 1 nếu có cạnh nối từ đỉnh i đến đỉnh j, và 0 nếu không có cạnh nối.

Dưới đây là cách khai báo và sử dụng ma trận kề trong Python để biểu diễn đồ thị:

1. Khai báo ma trận kề cho đồ thị vô hướng:

# Số lượng đỉnh

n = 5

# Khai báo ma trận kề n x n với các giá trị ban đầu là 0

graph = [[0 for _ in range(n)] for _ in range(n)]

# Thêm cạnh (1, 2) vào đồ thị

graph[1][2] = 1

graph[2][1] = 1

# Thêm cạnh (0, 3) vào đồ thị

graph[0][3] = 1

graph[3][0] = 1

2. Khai báo ma trận kề cho đồ thị có hướng:

# Số lượng đỉnh

n = 5

# Khai báo ma trận kề n x n với các giá trị ban đầu là 0

graph = [[0 for _ in range(n)] for _ in range(n)]

# Thêm cạnh có hướng từ 1 đến 2 vào đồ thị

graph[1][2] = 1

# Thêm cạnh có hướng từ 0 đến 3 vào đồ thị

graph[0][3] = 1

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

Câu hỏi 1 trang 56 Chuyên đề Tin học 12: Cho đồ thị G3, như Hình 3. Hãy biểu diễn đồ thị bằng ma trận kề.

Lời giải:

Nội dung đang được cập nhật

Câu hỏi 2 trang 56 Chuyên đề Tin học 12: Dựa trên mô tả của hình ảnh, đồ thị G3 có thể được biểu diễn bằng ma trận kề như sau:

Trong ma trận này, các hàng và cột tương ứng với các đỉnh của đồ thị, và một giá trị ‘1’ trong ma trận biểu thị sự kết nối trực tiếp giữa hai đỉnh, trong khi giá trị ‘0’ biểu thị không có kết nối trực tiếp.

Lời giải:

Dựa vào ma trận kề trong Hình 3, bạn có thể vẽ đồ thị vô hướng với 5 đỉnh được đánh số từ 0 đến 4. Các cạnh của đồ thị sẽ được nối dựa trên các giá trị ‘1’ trong ma trận:

Đỉnh 0 nối với đỉnh 3

Đỉnh 1 nối với đỉnh 2

Đỉnh 1 nối với đỉnh 3

Đỉnh 2 nối với đỉnh 3

Đỉnh 2 nối với đỉnh 4

Đây là cách biểu diễn trực quan giúp bạn dễ dàng nhận biết mối liên kết giữa các đỉnh trong đồ thị mà không cần đến hình ảnh cụ thể.

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

Câu hỏi 1 trang 57 Chuyên đề Tin học 12: Em hãy dùng danh sách kề biểu diễn các đồ thị ở Hình 4 và Hình 5.

Lời giải:

Danh sách kề là một cách biểu diễn đồ thị thông qua việc liệt kê các đỉnh kề với mỗi đỉnh. Dưới đây là danh sách kề cho các đồ thị trong Hình 4 và Hình 5:

Hình 4 - Đồ thị G4:

Đỉnh 0: [1, 3]

Đỉnh 1: [0, 2, 3]

Đỉnh 2: [1, 3, 4]

Đỉnh 3: [0, 1, 2]

Đỉnh 4: 2

Hình 5 - Đồ thị G5:

Đỉnh 0: [1, 2, 3]

Đỉnh 1: [0, 5]

Đỉnh 2: [0, 6]

Đỉnh 3: [0, 4]

Đỉnh 4: 3

Đỉnh 5: 1

Đỉnh 6: 2

Danh sách này giúp ta dễ dàng nhận biết các đỉnh nào kề nhau trong đồ thị mà không cần nhìn vào hình ảnh cụ thể của đồ thị.

Câu hỏi 2 trang 57 Chuyên đề Tin học 12: Từ danh sách kề ở Bảng 6. Hãy vẽ đồ thị có hướng tương ứng.

Lời giải:

Dựa vào danh sách kề từ Bảng 6, bạn có thể vẽ đồ thị có hướng với các đỉnh A, B, C, D, và E. Các mũi tên sẽ được vẽ theo hướng từ đỉnh này sang đỉnh kề của nó:

Từ đỉnh A đến đỉnh B và D

Từ đỉnh B đến đỉnh A và C

Từ đỉnh C đến đỉnh B và E

Từ đỉnh D đến đỉnh A và E

Từ đỉnh E đến đỉnh C và D

Đồ thị này thể hiện mối quan hệ hướng từ giữa các đỉnh, phổ biến trong việc biểu diễn các mô hình dữ liệu và phân tích mạng trong khoa học máy tính.

Luyện tập trang 58 Chuyên đề Tin học 12: Cho hai đồ thị G6 (Hình 6) và G7 (Hình 7

Em hãy thực hiện biểu điễn bằng hai cách:

- Ma trận kê.

- Danh sách kề.

Lời giải:

Dựa vào mô tả của đồ thị G7 (Hình 7), dưới đây là cách biểu diễn bằng ma trận kề và danh sách kề:

Ma trận kề cho G7:

Danh sách kề cho G7:

Đỉnh 0: [1, 2, 4]

Đỉnh 1: [2, 5]

Đỉnh 2: [1, 3, 5]

Đỉnh 3: [0, 4]

Đỉnh 4: [0, 5]

Đỉnh 5: [3, 4]

Rất tiếc, mô tả cho đồ thị G6 (Hình 6) không được cung cấp, vì vậy em không thể thực hiện biểu diễn cho đồ thị đó. Nếu bạn có thông tin về đồ thị G6, hãy cung cấp và em sẽ giúp bạn biểu diễn nó.

Thực hành 1 trang 58 Chuyên đề Tin học 12: Sử dụng chương trình trong bài học, hãy viết chương trình xuất ra màn hình ma trận kể biểu diễn đồ thị G2 (Hình 2) và G3 (Hình 3).

Lời giải:

Ví dụ về cách viết chương trình để xuất ra màn hình ma trận kề biểu diễn cho từng đồ thị:

Chương trình cho Đồ thị G2 (Hình 2):

# Số lượng đỉnh của đồ thị G2

n = 6

# Khởi tạo ma trận kề với tất cả giá trị là 0

adj_matrix_G2 = [[0]*n for _ in range(n)]

# Cập nhật ma trận kề dựa trên các cạnh và trọng số của đồ thị G2

# Ví dụ: adj_matrix_G2[1][4] = 4 nếu có cạnh từ đỉnh 1 đến đỉnh 4 với trọng số là 4

# Lặp qua và cập nhật tất cả các cạnh tương tự

# In ma trận kề

for row in adj_matrix_G2:

print(' '.join(map(str, row)))

Chương trình cho Đồ thị G3 (Hình 3):

# Số lượng đỉnh của đồ thị G3

n = 7

# Khởi tạo ma trận kề với tất cả giá trị là 0

adj_matrix_G3 = [[0]*n for _ in range(n)]

# Cập nhật ma trận kề dựa trên các cạnh của đồ thị G3

# Ví dụ: adj_matrix_G3[1][2] = 1 và adj_matrix_G3[2][1] = 1 nếu có cạnh giữa đỉnh 1 và đỉnh 2

# Lặp qua và cập nhật tất cả các cạnh không hướng tương tự

# In ma trận kề

for row in adj_matrix_G3:

print(' '.join(map(str, row)))

Thực hành 2 trang 58 Chuyên đề Tin học 12: Sử dụng chương trình trong bài học, hãy viết chương trình xuất ra màn hình danh sách kể biểu diễn đồ thị G4 (Hình 4) và G5 (Hình 5).

Lời giải:

Ví dụ về cách viết chương trình để xuất ra màn hình danh sách kề biểu diễn cho từng đồ thị:

Chương trình cho Đồ thị G4 (Hình 4):

# Danh sách kề của đồ thị G4

adj_list_G4 = {

'0': ['1', '3', '2'],

'1': ['2'],

'2': ['3'],

'3': ['0'],

'4': []

}

# In danh sách kề

for vertex, edges in adj_list_G4.items():

print(f"Đỉnh {vertex}: {', '.join(edges)}")

AI-generated code. Review and use carefully. More info on FAQ.

Chương trình cho Đồ thị G5 (Hình 5):

# Danh sách kề của đồ thị G5

adj_list_G5 = {

'0': ['1', '2', '3'],

'1': ['0', '2', '6'],

'2': ['0', '1', '5'],

'3': ['0', '4'],

'4': ['3', '5', '6'],

'5': ['2', '4', '6'],

'6': ['1', '4', '5']

}

# In danh sách kề

for vertex, edges in adj_list_G5.items():

print(f"Đỉnh {vertex}: {', '.join(edges)}")

Vận dụng trang 58 Chuyên đề Tin học 12: Một hãng hàng không đưa ra lịch bay trong ngày như sau:

- Từ TP.HCM: có một chuyến đến Hà Nội, Đà Nẵng, Phú Quốc, Nghệ An và Hải Phòng;

- Từ Hà Nội: có hai chuyến đến TP.HCM và một chuyến đến Đà Nẵng, Nghệ An, Hải Phòng;

- Từ Đà Nẵng: có một chuyến đến Hải Phòng, hai chuyến bay đến TP.HCM, một chuyến đến Hà Nội;

- Từ Nghệ An: có một chuyến đến Hà Nội, một chuyến đến TP.HCM;

- Từ Hải Phòng: có một chuyển đến Hà Nội, một chuyến đến TP.HCM, và một chuyến đến Đà Nẵng;

- Từ Phú Quốc: có một chuyến đến TP.HCM.

a) Vẽ đồ thị biểu diễn các thành phố có chuyến bay giữa chúng (không quan tâm đến số lượng các chuyến bay).

b) Từ đồ thị đã vẽ được trong câu a). Hãy biểu diễn đồ thị bằng hai cách:

- Ma trận kê.

- Danh sách kể.

Lời giải:

Một hãng hàng không đưa ra lịch bay trong ngày như sau:

- Từ TP.HCM: có một chuyến đến Hà Nội, Đà Nẵng, Phú Quốc, Nghệ An và Hải Phòng;

- Từ Hà Nội: có hai chuyến đến TP.HCM và một chuyến đến Đà Nẵng, Nghệ An, Hải Phòng;

- Từ Đà Nẵng: có một chuyến đến Hải Phòng, hai chuyến bay đến TP.HCM, một chuyến đến Hà Nội;

- Từ Nghệ An: có một chuyến đến Hà Nội, một chuyến đến TP.HCM;

- Từ Hải Phòng: có một chuyển đến Hà Nội, một chuyến đến TP.HCM, và một chuyến đến Đà Nẵng;

- Từ Phú Quốc: có một chuyến đến TP.HCM.

a) Vẽ đồ thị biểu diễn các thành phố có chuyến bay giữa chúng (không quan tâm đến số lượng các chuyến bay).

b) Từ đồ thị đã vẽ được trong câu a). Hãy biểu diễn đồ thị bằng hai cách:

- Ma trận kê.

- Danh sách kể.

a) Vẽ đồ thị biểu diễn các thành phố có chuyến bay giữa chúng

Để biểu diễn các thành phố và các chuyến bay giữa chúng, chúng ta có các đỉnh (vertices) là các thành phố và các cạnh (edges) là các chuyến bay giữa các thành phố đó.

Các thành phố:

TP.HCM (HCM)

Hà Nội (HN)

Đà Nẵng (DN)

Phú Quốc (PQ)

Nghệ An (NA)

Hải Phòng (HP)

Các chuyến bay (cạnh):

Từ TP.HCM: HCM -> HN, HCM -> DN, HCM -> PQ, HCM -> NA, HCM -> HP

Từ Hà Nội: HN -> HCM, HN -> DN, HN -> NA, HN -> HP

Từ Đà Nẵng: DN -> HP, DN -> HCM, DN -> HN

Từ Nghệ An: NA -> HN, NA -> HCM

Từ Hải Phòng: HP -> HN, HP -> HCM, HP -> DN

Từ Phú Quốc: PQ -> HCM

Đồ thị:

b) Biểu diễn đồ thị bằng hai cách:

1. Ma trận kề (Adjacency Matrix)

Ma trận kề là một ma trận vuông trong đó mỗi hàng và cột đại diện cho một đỉnh (thành phố) và các phần tử ma trận biểu thị sự tồn tại của một cạnh (chuyến bay) giữa các đỉnh.

2. Danh sách kề (Adjacency List)

Danh sách kề biểu thị đồ thị bằng cách liệt kê các đỉnh kề nhau cho mỗi đỉnh trong đồ thị.

adj_list = {

"HCM": ["HN", "DN", "PQ", "NA", "HP"],

"HN": ["HCM", "DN", "NA", "HP"],

"DN": ["HP", "HCM", "HN"],

"PQ": ["HCM"],

"NA": ["HN", "HCM"],

"HP": ["HN", "HCM", "DN"]

}

Tóm tắt

Ma trận kề: Sử dụng một ma trận vuông để biểu diễn các kết nối giữa các thành phố. Mỗi hàng và cột tương ứng với một thành phố và phần tử tại hàng i cột j là 1 nếu có chuyến bay giữa thành phố i và j, ngược lại là 0.

Danh sách kề: Sử dụng một từ điển (dictionary) để liệt kê các thành phố kề nhau cho mỗi thành phố. Mỗi khóa của từ điển là một thành phố và giá trị tương ứng là một danh sách các thành phố có chuyến bay trực tiếp từ thành phố đó.

Xem thêm các bài giải Chuyên đề Tin học 12 sách Chân trời sáng tạo hay, chi tiết khác:

Bài 2.4: Thực hành cây tìm kiếm nhị phân

Bài 3.1: Các khái niệm cơ bản của đồ thị

Bài 3.3: Duyệt đồ thị theo chiều rộng

Bài 3.4: Duyệt đồ thị theo chiều sâu

Bài 3.5: Thực hành kĩ thuật duyệt đồ thị