Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 11: Khái niệm đồ thị

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?

Hình 11.1. Sơ đồ các cây cầu trong thành phố cổ Königsberg

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 tiếp tục tổ chức cho HS làm việc theo nhóm 2 – 3 HS.

- GV yêu cầu các nhóm thảo luận và thực hiện Hoạt động 1 – Tìm hiểu khái niệm đồ thị SGK tr.49:

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

- GV đặt câu hỏi định hướng cho các nhóm thảo luận:

a) Khái niệm đồ thị

+ Đồ thị là gì?

+ Em hãy nêu một số ví dụ về mô hình đồ thị trong thực tế.

+ Đồ thị được mô tả như thế nào?

+ Dựa vào khái niệm và cách mô tả đồ thị, em hãy phát biểu lại bài toán ở phần Khởi động.

b) Đồ thị vô hướng và đồ thị có hướng

+ Thế nào là đồ thị vô hướng?

+ Thế nào là đồ thị có hướng?

c) Đơn đồ thị

+ Em hãy quan sát Hình 11.6 và cho biết khuyên và cạnh song song trong đồ thị là gì?

+ Thế nào là đơn đồ thị?

+ Giữa hai đỉnh bất kì của đơn đồ thị có thể có bao nhiêu cạnh nối?

+ Để biểu diễn tập hợp các đỉnh và các cạnh của đồ thị trong Python, em sử dụng kiểu dữ liệu nào?

- GV đưa ra một số ví dụ biểu diễn đồ thị trong Python.

- GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, thực hiện hoạt động Củng cố kiến thức tr.51 SGK:

1. 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?

2. 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}]

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

Hình 11.7. Đồ thị vô hướ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.49 – 51, thảo luận nhóm và thực hiện các nhiệm vụ học tập.

- 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 đại diện các nhóm báo cáo kết quả thảo luận.

- Các nhóm còn lại lắng nghe và nhận xét, bổ sung cho nhau. 

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

1. Bài toán trong phần khởi động có thể biểu diễn được bằng mô hình đồ thị.

2. Một số bài toán thực tế có thể biểu diễn được bằng đồ thị:

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

Hướng dẫn thực hiện hoạt động Củng cố kiến thức SGK tr.51:

1. Cây nhị phân và cây tìm kiếm nhị phân là mô hình đồ thị.

2. Đồ thị vô hướng:

3. Tập hợp đỉnh V và tập hợp cạnh E của đồ thị vô hướng:

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

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

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- Từ kết quả thảo luận của các nhóm, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

- GV chốt kiến thức theo Hộp kiến thức.

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

a) Khái niệm đồ thị

- Đồ thị G = (V, E) là tập hợp hữu hạn các đỉnh V và tập hợp các cạnh E nối các đỉnh V với nhau. 

- Giả sử đồ thị G = (V, E) có n đỉnh và m cạnh, ta có các kí hiệu sau:

+ Tập hợp các đỉnh V = {, , ,…, };

+ Tập hợp các cạnh E = {, , ,…, }.

Trong đó, các cạnh có dạng e = (, ) nối hai đỉnh  và .

Ví dụ: Một số mô hình đồ thị trong thực tế:

a) Cấu trúc tinh thể liên kết ion của muối ăn

b) Sơ đồ các tuyến xe buýt 
trong một thành phố

c) Mạng Internet kết nối máy tính toàn cầu

d) Mô hình liên kết siêu văn bản 
của các trang web trên Internet

Hình 11.2. Một số mô hình đồ thị trong thực tế

- Đồ thị được mô tả bằng cách vẽ các nút để mô tả các đỉnh và các đường nối giữa các đỉnh để mô tả các cạnh của đồ thị. 

a) Đồ thị với 4 đỉnh có tên A, B, C, D

b) Các đỉnh của đồ thị có tên a, b, c, d, e, f

c) Hai sơ đồ trên là tương đương, 
biểu diễn cùng một đồ thị

Hình 11.3. Một số đồ thị

- Mô hình thành phố và các cây cầu của bài toán 7 cây cầu ở Königsberg (Hình 11.4a) được mô phỏng lại để dễ quan sát hơn với các vùng đất được kí hiệu là A, B, C, D và các cây cầu đóng vai trò các cạnh nối những vùng đất này. Mô hình đồ thị được biểu diễn như Hình 11.4b.

Hình 11.4. Mô hình đồ thị bài toán 
7 cây cầu ở Königsberg

Bài toán 7 cây cầu có thể phát biểu lại như sau:

Cho mô hình đồ thị như Hình 11.4b, hãy tìm đường đi qua tất cả các cạnh, mỗi cạnh đi qua đúng một lần.

b) Đồ thị vô hướng và đồ thị có hướng

- Đồ thị vô hướng có các cạnh nối không phân biệt hướng, có thể đi được hai chiều, các cạnh được biểu diễn bằng các đoạn thẳng. 

Hình 11.5a. Đồ thị vô hướng

- Đồ thị có hướng có mũi tên chỉ hướng trên các cạnh, chỉ đi theo hướng có mũi tên.

Hình 11.5b. Đồ thị có hướng

c) Đơn đồ thị

- Nếu đồ thị có cạnh e = (v, v), tức là xuất phát và kết thúc tại một đỉnh, thì được gọi là có khuyên. 

Hình 11.6a. Khuyên trong đồ thị

- Nếu giữa hai đỉnh u, v có nhiều hơn một cạnh nối thì được gọi là có cạnh song song.

b) Cạnh song song

c) Cạnh song song có hướng

Hình 11.6b. Cạnh song song trong đồ thị

- Đồ thị G = (V, E) được gọi là đơn đồ thị nếu đồ thị không có khuyên và không có cạnh song song. - Với đơn đồ thị, giữa hai đỉnh bất kì của đồ thị có nhiều nhất một cạnh nối. 

(Trong phạm vi cuốn sách này, chúng ta chỉ xét các đơn đồ thị)

- Trong Python, chúng ta sẽ sử dụng kiểu dữ liệu list để mô tả V và E:

+ Mỗi cạnh là một cặp hai chỉ số mô tả cặp đỉnh tương ứng. 

+ Nếu đồ thị vô hướng thì sử dụng tập hợp để mô tả cạnh. 

+ Nếu đồ thị có hướng thì dùng list hoặc tuple để mô tả cạnh có hướng giữa hai đỉnh.

Ví dụ: 

• Đồ thị vô hướng (Hình 11.5a) được biểu diễn trong Python như sau: 

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

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

• Với đồ thị có hướng (Hình 11.5b) thì danh sách các cạnh E được mô tả như sau: 

E = [(0,1), (0,4), (1,3), (3,2)].

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 các nhóm thảo luận và thực hiện Hoạt động 2 – Tìm hiểu một số khái niệm, định nghĩa liên quan đến đồ thị SGK tr.52:

Đọ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. 

Hình 11.8. Đồ thị vô hướng

- GV yêu cầu các nhóm thảo luận và tìm hiểu các khái niệm, định nghĩa:

+ Đỉnh kề.

+ Bậc của đỉnh.

+ Đường đi và chu trình trong đồ thị.

+ Đồ thị liên thông. Thành phần liên thông của đồ thị.

+ Ma trận kề.

+ Danh sách kề.

- GV đưa ra và phân tích ví dụ để HS hiểu rõ cách biểu diễn đồ thị bằng ma trận kề và danh sách kề. 

- GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, thực hiện hoạt động Củng cố kiến thức tr.53 SGK:

1. Khi nào một đỉnh của đồ thị có bậc bằng 0?

2. Xác định ma trận kề và danh sách kề của các đồ thị ở Hình 11.11. 

Hình 11.11. Các đồ thị

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 2 SGK tr.52 – 53, thảo luận nhóm và thực hiện các nhiệm vụ học tập.

- 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 đại diện các nhóm báo cáo kết quả thảo luận.

- Các nhóm còn lại lắng nghe và nhận xét, bổ sung cho nhau. 

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- Từ kết quả thảo luận của các nhóm, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

- GV chốt kiến thức theo Hộp kiến thức.

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

Cho đơn đồ thị G = (V, E) có thể vô hướng hoặc có hướng.

- Nếu từ đỉnh u có cạnh nối đến đỉnh v thì v được gọi là đỉnh kề của u. Nếu G là vô hướng thì nếu v là đỉnh kề của u thì u cũng là đỉnh kề của v. 

- Nếu cạnh e từ u đến v thì kí hiệu:

e: u  v hay u  v.

- Bậc (degree) của đỉnh u, kí hiệu deg(u), là số lượng các đỉnh kề với u.

- Nếu G là đồ thị có hướng thì sẽ có các định nghĩa sau:

• Bậc ra (out degree) của đỉnh u, kí hiệu deg+(u) là số lượng các đỉnh kề với u.

• Bậc vào (in degree) của đỉnh u, kí hiệu 
  deg-(u), là số các đỉnh có cạnh nối đến u.

• Đường đi (path) từ đỉnh s đến đỉnh t là dãy các cạnh kề nhau , ,…,  nối từ đỉnh s đến đỉnh t và thoả mãn điều kiện: tồn tại dãy các đỉnh kề nhau và khác nhau từng đôi một , , ,…, , sao cho  là cạnh nối đỉnh   đến  (i = 1, 2,…, k),   = s và  = t.

- Vì các đỉnh , ,…,  khác nhau từng đôi một, do đó các cạnh , ,…,  cũng khác nhau từng đôi một. Trong trường hợp đỉnh  trùng với đỉnh  thì dãy các cạnh kề nhau , ,…, ở trên là chu trình (cycle).

- Đồ thị liên thông: 

• Đồ thị G = (V, E) được gọi là liên thông nếu với mọi đỉnh u, v  V thì tồn tại đường đi từ u đến v. 

• Nếu G không là liên thông thì tập hợp V có thể được chia thành các tập hợp con rời nhau mà mỗi đồ thị con xác định bởi các tập hợp này là liên thông. Các tập hợp con đó được gọi là các thành phần liên thông của G.

Hình 11.9. Đồ thị có hai thành phần liên thông là [A, D, E] và [B, C]

• Theo quy ước, nếu đồ thị G chỉ có một đỉnh thì đồ thị này là liên thông.

- Cho đồ thị G = (V, E), V có n đỉnh. Các đỉnh V được kí hiệu 0, 1, 2,…, n – 1. Khi đó ma trận kề (Adjacency Matrix) của đồ thị G là ma trận có kích thước n  n, được định nghĩa như sau:

Lưu ý: Ma trận kề được định nghĩa cho cả đồ thị vô hướng và có hướng. Nếu G là đồ thị vô hướng thì ma trận kề là đối xứng, tức là  =  với mọi i, j.

- Với mỗi u ∈ V, danh sách các đỉnh kề của u là Adj(u) = {v | (u,v) ∈ E}. Danh sách kề (Adjacency List) của đồ thị G, kí hiệu là Adj, là tập hợp danh sách đỉnh kề của các đỉnh của G.

Ví dụ: Với đồ thị vô hướng trong Hình 11.10a, ta có ma trận kề và danh sách kề như Hình 11.10b và Hình 11.10c.

a) Đồ thị G = (V,E)

Hình 11.10. Đồ thị và ma trận kề, 
danh sách kề tương ứng

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

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

2. Đỉnh A có bậc bằng 2.

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

+ {(A, D), (D, E)}

+ {(A, D), (D, C), (C, E)}

+ {(A, B), (B, C), (C, E)}

+ {(A, B), (B, C), (C, D), (D, E)}

Hướng dẫn thực hiện hoạt động Củng cố kiến thức SGK tr.53:

1. Một đỉnh của đồ thị có bậc bằng 0 nếu không có cạnh đi vào hoặc đi ra từ đỉnh này.

2. Ma trận kề và danh sách kề của các đồ thị:

a)

………………………………