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

CHÀO MỪNG CÁC EM ĐẾN VỚI BUỔI HỌC HÔM NAY!

KHỞI ĐỘNG

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

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

Cách 1

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

Cách 2

CHUYÊN ĐỀ 3: TÌM HIỂU KĨ THUẬT DUYỆT ĐỒ THỊ VÀ ỨNG DỤNG

BÀI 11: KHÁI NIỆM ĐỒ THỊ

1

KHÁI NIỆM ĐỒ THỊ

Tìm hiểu khái niệm đồ thị SGK tr.49:

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?

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

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

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ị

b)

Hình 11.4. Mô hình đồ thị bài toán

7 cây cầu ở Königsberg

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 đượ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.

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.

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

b) Cạnh song song

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

c) Đơn đồ thị

• Gọi là đơn đồ thị nếu đồ thị không có khuyên và không có cạnh song song.
• Giữa hai đỉnh bất kì có nhiều nhất một cạnh nối.
• Trong Python, sử dụng kiểu dữ liệu list để mô tả V và E:

Ví dụ

Đồ thị vô hướng được biểu diễn như sau:

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

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

Đồ thị có hướng được mô tả như sau:

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

Trả lời câu hỏi Củng cố SGK tr.51:

Câu 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?

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

Câu 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.

Câu 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}]

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

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

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

MỘT SỐ KHÁI NIỆM LIÊN QUAN ĐẾN ĐỒ THỊ

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

Đỉnh kề

Bậc của đỉnh

Bậc (deg(u): là số lượng các đỉnh kề với u.

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 và chu trình trong đồ thị

Đồ thị liên thông

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

Ma trận kề

Danh sách kề

• Danh sách kề (Adj): là tập hợp danh sách đỉnh kề của các đỉnh của G.
• Với mỗi u ∈ V, danh sách các đỉnh kề của u là Adj(u) = {v | (u,v) ∈ E}.

Ví dụ

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

b) Ma trận kề

c) Danh sách kề

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

Trả lời câu hỏi Củng cố SGK tr.53:

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

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.

Trả lời câu hỏi Củng cố SGK tr.53:

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

a)

b)

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

a)

b)

BIỂU DIỄN ĐỒ THỊ

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.

a)

b)

Hình 11.12

Cho đồ thi G = (V,E). Ta cần biểu diễn dữ liệu đồ thị G trên máy tính như thế nào?

Bộ dữ liệu của đồ thị được cho bởi dãy các đỉnh V và dãy các cạnh E:

- Các đỉnh của đồ thị được đánh số từ 0 đến n – 1.

- Mỗi cạnh là một cặp hai đỉnh hoặc hai chỉ số tương ứng của hai đỉnh:

+ G là đồ thị vô hướng: cạnh là hai chiều.

+ G là đồ thị có hướng: mỗi cạnh là cặp có thứ tự các đỉnh hoặc chỉ số của các đỉnh.

• Cách thiết lập và biểu diễn dữ liệu đồ thị trên máy tính

Tập các đỉnh V được đánh số từ 0 đến n – 1:

V = [0, 1, 2,…, n – 1]

Ví dụ

Hình 11,12a)

Với đồ thị ở Hình 11.12a ta có n = 5 và V được xác định như sau:

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

Tập các cạnh E là dãy (danh sách) các cạnh, mỗi cạnh sẽ là một cặp hai chỉ số tương ứng với hai đỉnh:

• Mỗi cạnh của đồ thị vô hướng E được biểu diễn như một tập hợp, ví dụ e = {i, j}.
• Mỗi cạnh của đồ thị có hướng là cặp hai chỉ số có thứ tự, ví dụ kiểu tuple là e = (i, j) hoặc list là e = [i, j].

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

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

Ví dụ

Ví dụ

Ma trận kề của các đồ thị trong Hình 11.12 tương ứng như sau:

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