Đồ thị vô hướng G được gọi là đầy đủ nếu giữa hai đỉnh bất kì

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

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) đều có cạnh nối. Hãy vẽ và thiết lập ma trận kề của đồ thị đầy đủ với số đỉnh n = 2, 3, 4.

Lời giải:

Để vẽ và thiết lập ma trận kề của đồ thị đầy đủ với số đỉnh n=2,3,4 ta sẽ xác định tất cả các cạnh có thể nối giữa các đỉnh.

1. Khi n=2:

- Đồ thị chỉ có hai đỉnh V={0,1}

- Vì đồ thị đầy đủ, nên có một cạnh nối giữa mọi cặp đỉnh.

- Ma trận kề sẽ có dạng:

2. Khi n=3:

- Đồ thị có ba đỉnh V={0,1,2}.

- Tương tự như trường hợp trên, có một cạnh nối giữa mọi cặp đỉnh.

- Ma trận kề:

3. Khi n=4:

- Đồ thị có bốn đỉnh V={0,1,2,3}.

- Đồ thị đầy đủ có một cạnh nối giữa mọi cặp đỉnh.

- Ma trận kề:

Trong ma trận kề, giá trị 1 ở hàng i và cột j thể hiện rằng có một cạnh nối giữa đỉnh i và đỉnh j.

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

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

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

---