Chuyên đề Tin học 12 Bài 11 (Kết nối tri thức): Khái niệm đồ thị

Giải Chuyên đề Tin học 12 Bài 11: Khái niệm đồ thị

Khởi động trang 49 Chuyên đề Tin học 12: Năm 1736, nhà bác học Euler đưa ra bài toán, được gọi là bài toán 7 cây cầu ở Königsberg. Tại thành phố cổ Königsberg của nước Phổ cũ (nay thuộc nước Nga) có dòng sông Pregel vắt ngang qua, chia thành phố thành các vùng riêng biệt. Bài toán Euler đặt ra là làm sao đi qua tất cả 7 cây cầu này, mỗi cầu chỉ được phép đi qua đúng một lần.

Em hãy giải bài toán trên.

Có thể dùng mô hình dữ liệu nào để mô phỏng bài toán này?

Lời giải:

Bài toán 7 cây cầu ở Königsberg có thể được giải bằng một số phương pháp, trong đó một phương pháp hiệu quả là sử dụng đồ thị. Mô hình đồ thị có thể được sử dụng để mô phỏng bài toán này.

Một cách tiếp cận đơn giản là sử dụng đồ thị vô hướng, trong đó mỗi cầu được biểu diễn bởi một cạnh của đồ thị, và mỗi khu vực của thành phố được biểu diễn bởi một đỉnh. Bài toán trở thành việc tìm một đường đi qua tất cả các cầu (cạnh) một lần và quay lại nút xuất phát (đỉnh xuất phát).

Một cách khác để mô hình hóa bài toán này là sử dụng cây tìm kiếm nhị phân. Mỗi nút trong cây có thể biểu diễn một câu chuyện từ điểm xuất phát đến các cây cầu, trong đó mỗi cầu được đi qua một lần. Bằng cách này, ta có thể tìm kiếm một đường đi hợp lệ (nếu tồn tại) từ điểm xuất phát đến các cây cầu và quay lại điểm xuất phát.

Tùy thuộc vào cách tiếp cận, mô hình dữ liệu sẽ thay đổi. Đối với mô hình đồ thị, ta có thể sử dụng ma trận kề hoặc danh sách kề để biểu diễn đồ thị. Đối với mô hình cây tìm kiếm nhị phân, mỗi nút có thể lưu trữ thông tin về cầu đã đi qua và các khu vực đã được ghé thăm.

1. Khái niệm đồ thị

Hoạt động 1 trang 49 Chuyên đề Tin học 12:

1. Trao đổi, thảo luận về mô hình đồ thị, các khái niệm cơ bản của đồ thị và trả lời câu hỏi: Bài toán trong phần khởi động có thể biểu diễn được bằng mô hình đồ thị không?

2. Em hãy tìm một số bài toán thực tế khác có thể biểu diễn được bằng đồ thị.

Lời giải:

1. Mô hình đồ thị là một cách mạnh mẽ để mô tả một tập hợp các đối tượng (đỉnh) và các mối quan hệ giữa chúng (cạnh). Đồ thị có thể có các biến thể khác nhau như đồ thị vô hướng, đồ thị có hướng, đồ thị có trọng số, và đồ thị có hướng và trọng số.
Bài toán trong phần khởi động, cụ thể là bài toán 7 cây cầu ở Königsberg, có thể biểu diễn được bằng mô hình đồ thị. Trong mô hình này, mỗi khu vực của thành phố sẽ được biểu diễn bởi một đỉnh, và mỗi cây cầu sẽ được biểu diễn bởi một cạnh. Với mỗi cầu, ta có thể có một cạnh vô hướng nối hai đỉnh biểu diễn hai khu vực mà cầu đó nối.
Bằng cách này, ta có thể sử dụng các thuật toán trên đồ thị để giải quyết bài toán, chẳng hạn như thuật toán DFS (Depth-First Search) hoặc BFS (Breadth-First Search) để kiểm tra xem có đường đi qua tất cả các cầu một lần hay không.

2. Có nhiều bài toán thực tế khác mà có thể biểu diễn bằng mô hình đồ thị. Dưới đây là một số ví dụ:

- Mạng lưới điện: Trong một mạng lưới điện, các trạm biến áp và đường dây truyền điện có thể được biểu diễn bằng các đỉnh và cạnh trong đồ thị. Việc phân tích mạng lưới điện có thể giúp tối ưu hóa việc phân phối điện năng.

- Mạng xã hội: Trong mạng xã hội, mỗi cá nhân có thể được biểu diễn bằng một đỉnh và mối quan hệ giữa các cá nhân có thể được biểu diễn bằng các cạnh. Đồ thị của mạng xã hội có thể được sử dụng để phân tích mối quan hệ, tìm kiếm những cá nhân quan trọng, hoặc dự đoán sự lan truyền của thông tin.

- Mạng giao thông: Trong mạng giao thông, các nút giao thông và các tuyến đường có thể được biểu diễn bằng các đỉnh và cạnh trong đồ thị. Việc phân tích mạng giao thông có thể giúp tối ưu hóa lộ trình đi lại, dự đoán tình trạng giao thông, hoặc thiết kế hệ thống giao thông hiệu quả hơn.

Câu hỏi 1 trang 51 Chuyên đề Tin học 12: Cây, cây nhị phân và cây tìm kiếm nhị phân có là mô hình đồ thị không?

Lời giải:

Cây, cây nhị phân và cây tìm kiếm nhị phân không phải là mô hình đồ thị trong định nghĩa cơ bản của đồ thị. Tuy nhiên, chúng có mối liên quan với đồ thị thông qua một số khái niệm và biến thể.

1. Cây: Trong lý thuyết đồ thị, một cây là một loại đồ thị vô hướng không chứa chu trình. Cây có thể được biểu diễn dưới dạng một đồ thị đặc biệt, trong đó mỗi nút có đúng một nút cha trừ nút gốc, và không có chu trình.

2. Cây nhị phân: Cây nhị phân là một loại cây trong đó mỗi nút có tối đa hai con, được gọi là con trái và con phải. Mỗi nút trong cây nhị phân đều có mối quan hệ với nút cha của nó, tạo thành một cấu trúc phân cấp. Mặc dù cây nhị phân không phải là đồ thị theo định nghĩa chính thức, nhưng nó có thể được biểu diễn bằng đồ thị với một số ràng buộc, chẳng hạn như mỗi nút chỉ có thể có tối đa hai con.

3. Cây tìm kiếm nhị phân: Cây tìm kiếm nhị phân là một loại cây nhị phân đặc biệt, trong đó mỗi nút chứa một giá trị (phần tử) và được sắp xếp theo thứ tự sao cho mọi giá trị ở cây con trái nhỏ hơn giá trị của nút cha và mọi giá trị ở cây con phải lớn hơn giá trị của nút cha. Cây tìm kiếm nhị phân cũng có thể được coi là một biến thể của đồ thị, với mỗi nút là một đỉnh và mối quan hệ giữa các nút được xác định bởi thứ tự giá trị của chúng.

Như vậy, mặc dù cây, cây nhị phân và cây tìm kiếm nhị phân không phải là đồ thị trong định nghĩa chính thức, nhưng chúng có mối quan hệ mật thiết với đồ thị thông qua một số khái niệm và biến thể, và có thể được mô phỏng hoặc biểu diễn dưới dạng đồ thị.

Câu hỏi 2 trang 51 Chuyên đề Tin học 12: Vẽ đồ thị vô hướng G = (V, E) sau:

V = [0, 1, 2, 3, 4]

E = [{0,1}, {0,4}, {1,2}, {1,3}, {2,4}]

Lời giải:

Để vẽ đồ thị vô hướng G = (V, E) có các đỉnh V = [0, 1, 2, 3, 4] và các cạnh E = [{0,1}, {0,4}, {1,2}, {1,3}, {2,4}], chúng ta sẽ vẽ các đỉnh và các cạnh tương ứng.

Đầu tiên, vẽ các đỉnh:

Sau đó, vẽ các cạnh:

Đồ thị vô hướng này có 5 đỉnh và 5 cạnh, và mỗi cạnh nối hai đỉnh.

Câu hỏi 3 trang 51 Chuyên đề Tin học 12: Mô tả tập hợp đỉnh V và tập hợp cạnh E của đồ thị vô hướng trong Hình 11.7. Quan sát đồ thị ở Hình 11.8 và thực hiện các yêu cầu sau:

Lời giải:

Dựa trên hình ảnh bạn đã cung cấp, đây là mô tả của tập hợp đỉnh ( V ) và tập hợp cạnh ( E ) cho đồ thị vô hướng trong Hình 11.7:

Tập hợp đỉnh (V): ( V = {0, 1, 2, 3, 4} )

Tập hợp cạnh (E): ( E = {(0,1), (1,2), (2,3), (3,4), (4,0), (0,2)} )

Mỗi cạnh được biểu diễn bằng một cặp đỉnh mà nó kết nối, và vì đồ thị là vô hướng, không có mũi tên chỉ hướng trên các cạnh.

2. Một số khái niệm liên quan đến đồ thị

Hoạt động 2 trang 52 Chuyên đề Tin học 12: Đọc, trao đổi và thảo luận các khái niệm, định nghĩa liên quan đến đồ thị. Quan sát đồ thị ở Hình 11.8 và thực hiện các yêu cầu sau:

1. Kể tên các đỉnh kề với D.

2. Hãy cho biết bậc của đỉnh A.

3. Liệt kê một vài đường đi từ đỉnh A đến đỉnh E.

Lời giải:

1. Các đỉnh kề với D: Đỉnh D kề với các đỉnh A, C và E.

2. Bậc của đỉnh A: Đỉnh A có bậc là 3, vì nó được kết nối với ba đỉnh khác là B, D và E.

3. Đường đi từ A đến E:

Đường đi 1: A -> D -> E

Đường đi 2: A -> B -> C -> D -> E

Đường đi 3: A -> E (trực tiếp vì có cạnh nối giữa chúng)

Câu hỏi 1 trang 53 Chuyên đề Tin học 12: Khi nào một đỉnh của đồ thị có bậc bằng 0? trang 52 Chuyên đề Tin học 12.

Lời giải:

Trong lý thuyết đồ thị, bậc của một đỉnh là số lượng cạnh kề với đỉnh đó. Một đỉnh của đồ thị có bậc bằng 0 khi không có cạnh nào kề với đỉnh đó.

Một đỉnh có thể có bậc bằng 0 trong một số trường hợp sau:

1. Đỉnh không có cạnh kề với nó.

2. Trong đồ thị có hướng, đỉnh không có cạnh đi vào đỉnh đó (không có cạnh nào có đỉnh này là đỉnh đích).

3. Trong đồ thị vô hướng, đỉnh không có cạnh nào kết thúc tại đỉnh đó.

Đỉnh có bậc bằng 0 có thể là các "đỉnh cô lập" trong đồ thị, tức là chúng không có liên kết với các đỉnh khác trong đồ thị.

Câu hỏi 2 trang 53 Chuyên đề Tin học 12: Xác định ma trận kề và danh sách kề của các đồ thị ở Hình 11.11.

Lời giải:

Ma trận kề và danh sách kề cho hai đồ thị trong Hình 11.11:

Đồ thị (a):

- Ma trận kề:

- Danh sách kề:

+ Đỉnh 0: 2, 3

+ Đỉnh 1: 2, 3, 4

+ Đỉnh 2: 0, 1, 3

+ Đỉnh 3: 0, 1, 2

+ Đỉnh 4: 1

Đồ thị (b):

- Đồ thị đầy đủ:

Ma trận kề:

Danh sách kề:

Đỉnh 1: 2, 3, 4

Đỉnh 2: 1, 3, 4

Đỉnh 3: 1, 2, 4

Đỉnh 4: 1, 2, 3

3. Biểu diễn đồ thị

Hoạt động 3 trang 53 Chuyên đề Tin học 12: Tìm hiểu một số cách biểu diễn dữ liệu đồ thị trên máy tính. Thảo luận xem cách nào là hợp lí nhất. Hãy biểu diễn dữ liệu của các đồ thị ở Hình 11.12.

Lời giải:

Có hai cách biểu diễn dữ liệu đồ thị trên máy tính mà bạn có thể xem xét:

- Ma trận kề: Mỗi hàng và cột tương ứng với một đỉnh, và giá trị tại hàng i, cột j là 1 nếu có cạnh nối giữa đỉnh i và j, ngược lại là 0.

- Danh sách kề: Mỗi đỉnh liệt kê các đỉnh mà nó kết nối trực tiếp.

Đồ thị (a) - Cấu trúc hình sao:

- Ma trận kề:

- Danh sách kề:

Đỉnh 0: 1, 2, 3, 4

Đỉnh 1: 0

Đỉnh 2: 0

Đỉnh 3: 0

Đỉnh 4: 0

Đồ thị (b) - Cấu trúc liên kết nhiều hơn:

- Ma trận kề:

- Danh sách kề:

Đỉnh 0: 1, 3

Đỉnh 1: 0, 2, 4

Đỉnh 2: 1, 3

Đỉnh 3: 0, 2, 4

Đỉnh 4: 1, 3

Câu hỏi trang 55 Chuyên đề Tin học 12: Thiết lập bộ dữ liệu biểu diễn gồm (n, V, E, A, Adj) cho các đồ thị sau:

Lời giải:

Bộ dữ liệu biểu diễn cho hai đồ thị:

Đồ thị (a):

n (số đỉnh): 4

V (tập hợp đỉnh): {a, b, c, d}

E (tập hợp cạnh): {(a,b), (a,c), (a,d), (b,c), (c,d)}

A (ma trận kề): Chưa được xác định trong hình ảnh

Adj (danh sách kề):

Đỉnh a: {b, c, d}

Đỉnh b: {a, c}

Đỉnh c: {a, b, d}

Đỉnh d: {a, c}

Đồ thị (b):

n: 6

V: {0, 1, 2, 3, 4, 5}

E: {(0,1), (0,5), (1,2), (1,4), (2,3), (3,4), (4,5)}

A: Chưa được xác định trong hình ảnh

Adj:

Đỉnh 0: {1, 5}

Đỉnh 1: {0, 2, 4}

Đỉnh 2: {1, 3}

Đỉnh 3: {2, 4}

Đỉnh 4: {1, 3, 5}

Đỉnh 5: {0, 4}

Luyện tập 1 trang 55 Chuyên đề Tin học 12: Đồ thị ứng với mô hình bài toán 7 cây cầu ở Königsberg có phải là đơn đồ thị không? Tính bậc của các đỉnh của đồ thị đó.

Lời giải:

Đồ thị ứng với mô hình bài toán 7 cây cầu ở Königsberg không phải là đơn đồ thị vì có các cạnh được đi qua nhiều lần. Trong mô hình này, mỗi đỉnh biểu diễn một khu vực của thành phố và mỗi cầu biểu diễn một cạnh nối hai khu vực.

Để tính bậc của các đỉnh của đồ thị, chúng ta cần xem xét số lượng cạnh kề với mỗi đỉnh. Đối với bài toán 7 cây cầu ở Königsberg, ta có thể xác định số lượng cạnh kề với mỗi đỉnh từ danh sách các cầu:

- Đỉnh A: Khu vực 1 và 2 nối với đỉnh A.

- Đỉnh B: Khu vực 1, 2 và 3 nối với đỉnh B.

- Đỉnh C: Khu vực 2 và 4 nối với đỉnh C.

- Đỉnh D: Khu vực 2 và 3 nối với đỉnh D.

Tùy thuộc vào cách biểu diễn và phân loại các khu vực, có thể có sự khác biệt trong việc xác định các đỉnh và cạnh tương ứng. Tuy nhiên, trong trường hợp tổng quát, ta có thể tính bậc của mỗi đỉnh bằng cách đếm số lượng cạnh kề với nó.

Luyện tập 2 trang 55 Chuyên đề Tin học 12: Cho đồ thị G vô hướng với ma trận kề như hình bên. Hãy vẽ đồ thị trên.

Lời giải:

Xét từng hàng của ma trận kề:

- Hàng 1: Đỉnh 0 kề với đỉnh 1 và 2.

- Hàng 2: Đỉnh 1 kề với đỉnh 0 và 3.

- Hàng 3: Đỉnh 2 kề với đỉnh 0 và 3.

- Hàng 4: Đỉnh 3 kề với đỉnh 1 và 2.

Dựa trên thông tin này, ta có thể vẽ đồ thị như sau:

Xét từng hàng của ma trận kề:

- Hàng 1: Đỉnh 0 kề với đỉnh 1 và 2.

- Hàng 2: Đỉnh 1 kề với đỉnh 0 và 3.

- Hàng 3: Đỉnh 2 kề với đỉnh 0 và 3.

- Hàng 4: Đỉnh 3 kề với đỉnh 1 và 2.

Dựa trên thông tin này, ta có thể vẽ đồ thị như sau:

Trong đồ thị này, mỗi đỉnh được biểu diễn bởi một số, và mỗi cạnh giữa các đỉnh được biểu diễn bằng các đoạn thẳng nối hai đỉnh tương ứng.

Vận dụng 1 trang 55 Chuyên đề Tin học 12: Đồ thị vô hướng G được gọi là đầy đủ nếu giữa hai đỉnh bất kì (khác nhau) đều có cạnh nối. Hãy vẽ và thiết lập ma trận kề của đồ thị đầy đủ với số đỉnh n = 2, 3, 4.

Lời giải:

Để vẽ và thiết lập ma trận kề của đồ thị đầy đủ với số đỉnh n=2,3,4 ta sẽ xác định tất cả các cạnh có thể nối giữa các đỉnh.

1. Khi n=2:

- Đồ thị chỉ có hai đỉnh V={0,1}

- Vì đồ thị đầy đủ, nên có một cạnh nối giữa mọi cặp đỉnh.

- Ma trận kề sẽ có dạng:

2. Khi n=3:

- Đồ thị có ba đỉnh V={0,1,2}.

- Tương tự như trường hợp trên, có một cạnh nối giữa mọi cặp đỉnh.

- Ma trận kề:

3. Khi n=4:

- Đồ thị có bốn đỉnh V={0,1,2,3}.

- Đồ thị đầy đủ có một cạnh nối giữa mọi cặp đỉnh.

- Ma trận kề:

Trong ma trận kề, giá trị 1 ở hàng i và cột j thể hiện rằng có một cạnh nối giữa đỉnh i và đỉnh j.

Vận dụng 2 trang 55 Chuyên đề Tin học 12: Đồ thị trong Hình 11.17 có bao nhiêu thành phần liên thông?

Lời giải:

Theo đồ thị trong Hình 11.17 có 3 thành phần liên thông:

- Thành phần 1: Hình vuông với 4 nút và 4 cạnh.

- Thành phần 2: Hình tam giác với 3 nút và 3 cạnh.

- Thành phần 3: 2 nút được nối với nhau bởi 1 cạnh.