Giáo án NLS chuyên đề Tin học 12 KHMT Bài 11: Khái niệm đồ thị

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 giao nhiệm vụ cho các nhóm: Sử dụng công cụ số (máy tìm kiếm hoặc Chatbot AI) kết hợp tìm hiểu nội dung mục 1 và trả lời câu hỏi:

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

- GV yêu cầu các nhóm sử dụng thiết bị số kết nối mạng, mở Chatbot AI và đặt câu lệnh: "Giải thích cấu trúc mạng nơ-ron nhân tạo của AI dưới góc độ lý thuyết đồ thị và cho biết vai trò của trọng số cạnh đối với quá trình học máy" để liên hệ ứng dụng AI mở rộ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.

- HS sử dụng công cụ số tìm kiếm thông tin trên Internet kết hợp đối chiếu với SGK để rút ra kết luận chính xác.

- HS thảo luận nhóm vẽ đồ thị và viết mã Python khai báo V, E.

- Các nhóm tương tác với AI theo hướng dẫn của GV.

- 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 (nếu cần). 

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

…………………………………………..

…………………………………………..

…………………………………………..

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.

a)	b)

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

…………………………………………..

…………………………………………..

…………………………………………..

- 1.1.NC1b: HS thực hiện tìm kiếm thông tin trên Internet.

- 5.2.NC1b: Sử dụng công cụ số để tìm kiếm thông tin trên Internet

- 1.2.NC1a: HS thực hiện đối chiếu, đánh giá tính chuẩn xác của các thông tin định nghĩa đơn đồ thị, ví dụ đồ thị thực tế do Chatbot AI gợi ý so với nội dung chuẩn hóa trong SGK.

- 12.C2.1: HS biết cách đặt prompt thích hợp cho Chatbot AI để thu thập và chọn lọc thông tin tri thức về nguyên lý biểu diễn mạng nơ-ron bằng mô hình đồ thị trong kỹ thuật học sâu.

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS đọc Hoạt động 3 – Tìm hiểu cách biểu diễn dữ liệu đồ thị trên máy tính SGK tr.53, từ đó dẫn dắt HS tìm hiểu kiến thức.

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

- GV hướng dẫn HS cách biểu diễn dữ liệu đồ thị G = (V,E) trên máy tính sau đó yêu cầu HS thảo luận theo nhóm và thực hiện Hoạt động 3.

Hãy biểu diễn dữ liệu của các đồ thị ở Hình 11.12. 

a)

b)

Hình 11.12

- GV giới thiệu một số cách thể hiện dữ liệu Adj trên máy tính. 

- 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.55 SGK:

Thiết lập bộ dữ liệu biểu diễn gồm (n, V, E, A, Adj) cho các đồ thị sau: 

a)

b)

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

- GV cho phép HS sử dụng Chatbot AI để đối chiếu kết quả bộ dữ liệu biểu diễn đồ thị ở Câu 2 Củng cố.

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

- HS tự thực hiện bài tập, sau đó tương tác máy tính, nhập đề bài nhờ Chatbot AI giải thích và tiến hành phân tích tính hợp lý của câu trả lời của AI.

- 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 lên bảng viết ma trận kề, danh sách kề của các đồ thị.

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

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

Cho đồ thị G = (V, E):

- 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, ta có dãy các đỉnh V như sau:

V = {, ,…, }

• Mỗi cạnh là một cặp hai đỉnh hoặc hai chỉ số tương ứng của hai đỉnh:
• Nếu G là đồ thị vô hướng thì cạnh là hai chiều.
• Nếu G là đồ thị có hướng thì mỗi cạnh là cặp có thứ tự các đỉnh hoặc chỉ số của các đỉnh. 

Khi đó ta có dãy các cạnh E như sau:

E = {, ,…, }

Mỗi cạnh có dạng e = (, ) hoặc e = (i, j) .

- Ma trận kề A và danh sách kề Adj đã được định nghĩa trong mục 2.

- Để thiết lập và biểu diễn dữ liệu đồ thị trên máy tính, thực hiện như sau:

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

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

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

Với hai đồ thị trong Hình 11.12, E được định nghĩa như sau:

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

• Ma trận kề A của đồ thị là mảng hai chiều kích thước n n được định nghĩa như sau: A[i][j] = 1 khi và chỉ khi tồn tại cạnh nối từ đỉnh đến . 

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

Hình 11.13. Ma trận kề

• Danh sách kề Adj của đồ thị được định nghĩa như sau: A[i] là danh sách các đỉnh kề với đỉnh .

Các bảng biểu diễn Adj của các đồ thị trong Hình 11.12 tương ứng như sau:

a) Danh sách kề của đồ thị 
trong Hình 11.12a

b) Danh sách kề của đồ thị 
trong Hình 11.12b

Hình 11.14. Danh sách kề

Có nhiều cách thể hiện dữ liệu Adj trên máy tính: 

1. Dùng danh sách liên kết (Linked List). 

Theo cách này, Adj là dãy các phần tử, phần tử thứ i, Adj[i] là một Linked List các phần tử là đỉnh kề với đỉnh thứ i của đồ thị.

1. Dùng list trong Python. 

Theo cách này thì danh sách kề Adj của các đồ thị ở Hình 11.12 tương ứng như sau:

Hình 11.15. Danh sách kề của các đồ thị 
ở Hình 11.12

- 1.3.NC1b: HS biểu diễn được đồ thị bằng ma trận kề và danh sách kề.

- 1.2.NC1a: HS thực hiện đối chiếu, đánh giá tính chuẩn xác kết quả do Chatbot AI gợi ý so với nội dung chuẩn hóa trong SGK.

- 12.A3.1: HS thể hiện trách nhiệm học thuật: tự giải toán củng cố trước, chỉ dùng Chatbot AI để tham khảo; thực hiện kiểm chứng chéo kết quả phân tích của AI bằng kiến thức SGK.

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

…………………………………………..

…………………………………………..

…………………………………………..