1. KHÁI NIỆM ĐỒ THỊ

Hoạt động 1

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

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

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

Hoạt động 2

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

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

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

2. Cho đồ thị G vô hướng với ma trận kề như hình bên. Hãy vẽ đồ thị trên.