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

Giải Chuyên đề Tin 12 Bài 11: Khái niệm đồ thị - Kết nối tri thức

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

Lời giải bài tập Chuyên đề Tin 12 Bài 11: Khái niệm đồ thị hay, ngắn gọn khác:

• Khởi động trang 49 Chuyên đề Tin học 12: Năm 1751, 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 ở ....

• Hoạt động 1 trang 49 Chuyên đề Tin học 12: Tìm hiểu khái niệm về đồ thị: Trao đổi, thảo luận về mô hình đồ thị, các khái niệm cơ bản của đồ thị ....

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

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

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

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

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

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

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

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

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

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

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

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Kết nối tri thức hay, ngắn gọn khác:

• Chuyên đề Tin học 12 Bài 12: Biểu diễn đồ thị

• Chuyên đề Tin học 12 Bài 13: Thực hành thiết lập đồ thị

• Chuyên đề Tin học 12 Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu

• Chuyên đề Tin học 12 Bài 15: Thực hành duyệt đồ thị theo chiều sâu

• Chuyên đề Tin học 12 Bài 16: Kĩ thuật duyệt đồ thị theo chiều rộng

Xem thêm các tài liệu học tốt lớp 12 hay khác:

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều
• Giải lớp 12 Kết nối tri thức (các môn học)
• Giải lớp 12 Chân trời sáng tạo (các môn học)
• Giải lớp 12 Cánh diều (các môn học)

---