Câu hỏi:
13/07/2024 200
Đồ thị khối Q, (Hình 4) là đồ thị có 8 đỉnh, mỗi đỉnh là một dãy bit độ dài 3, hai đinh có cạnh nối nếu hai dãy bit sai khác nhau đúng một bit.
Em hãy biểu diễn đồ thị bằng ma trận kề và danh sách kề.
Đồ thị khối Q, (Hình 4) là đồ thị có 8 đỉnh, mỗi đỉnh là một dãy bit độ dài 3, hai đinh có cạnh nối nếu hai dãy bit sai khác nhau đúng một bit.
Em hãy biểu diễn đồ thị bằng ma trận kề và danh sách kề.
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
Đồ thị khối Q, (Hình 4) là đồ thị có 8 đỉnh, mỗi đỉnh là một dãy bit độ dài 3, hai đinh có cạnh nối nếu hai dãy bit sai khác nhau đúng một bit.
- Biểu diễn đồ thị bằng Ma trận kề: Ma trận kề sẽ có kích thước 8x8, với mỗi hàng và cột tương ứng với một đỉnh của đồ thị. Nếu hai đỉnh khác nhau đúng một bit, chúng sẽ được nối với nhau và ô tương ứng trong ma trận sẽ được đánh dấu là 1. Còn lại sẽ là 0.
- Biểu diễn đồ thị bằng Danh sách kề: Danh sách kề sẽ liệt kê các đỉnh kề với mỗi đỉnh trong đồ thị.
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Một đồ thị gồm 4 đỉnh, các đỉnh được đánh số từ 0 đến 3, được biểu diễn bằng ma trận kề như Hình 3. Ma trận kề cho thấy từ đỉnh 1 đến được đỉnh 0 và đỉnh 2.
a) Em hãy cho biết những đỉnh nào đến được đỉnh 2.
b) Em hãy biểu diễn đồ thị bằng danh sách kề.
Một đồ thị gồm 4 đỉnh, các đỉnh được đánh số từ 0 đến 3, được biểu diễn bằng ma trận kề như Hình 3. Ma trận kề cho thấy từ đỉnh 1 đến được đỉnh 0 và đỉnh 2.
a) Em hãy cho biết những đỉnh nào đến được đỉnh 2.
b) Em hãy biểu diễn đồ thị bằng danh sách kề.
Xem đáp án »
13/07/2024
169
Câu 2:
Nam thu thập thông tin về tuyến xe buýt giữa các địa điểm và kí hiệu như trong Bảng 1.
Ví dụ, trên hàng bắt đầu bằng kí tự A cho biết từ địa điểm A có hai tuyến xe buýt, tuyến thứ nhất từ A tới B và tuyến thứ hai từ A tới D. Với thông tin Nam thu thập được, em hãy cho biết: Từ địa điểm B có tuyến xe buýt nào tới địa điểm D không? Từ địa điểm D có những tuyến xe buýt tới các địa điểm nào?
Nam thu thập thông tin về tuyến xe buýt giữa các địa điểm và kí hiệu như trong Bảng 1.
Ví dụ, trên hàng bắt đầu bằng kí tự A cho biết từ địa điểm A có hai tuyến xe buýt, tuyến thứ nhất từ A tới B và tuyến thứ hai từ A tới D. Với thông tin Nam thu thập được, em hãy cho biết: Từ địa điểm B có tuyến xe buýt nào tới địa điểm D không? Từ địa điểm D có những tuyến xe buýt tới các địa điểm nào?
Xem đáp án »
13/07/2024
86
Câu 3:
Trong các câu sau đây, những câu nào đúng?
a) Chỉ có đơn đồ thị có hướng mới biểu diễn được bằng ma trận kề.
b) Cách biểu diễn đồ thị bằng ma trận kề đơn giản nhưng lãng phí bộ nhớ trong trường hợp đồ thị có nhiều đỉnh nhưng có ít cạnh.
c) Chỉ có đơn đồ thị vô hướng mới biểu diễn được bằng danh sách kề.
d) Cách biểu diễn bằng danh sách kề sẽ phù hợp khi đồ thị có nhiều đỉnh nhưng có ít cạnh.
Trong các câu sau đây, những câu nào đúng?
a) Chỉ có đơn đồ thị có hướng mới biểu diễn được bằng ma trận kề.
b) Cách biểu diễn đồ thị bằng ma trận kề đơn giản nhưng lãng phí bộ nhớ trong trường hợp đồ thị có nhiều đỉnh nhưng có ít cạnh.
c) Chỉ có đơn đồ thị vô hướng mới biểu diễn được bằng danh sách kề.
d) Cách biểu diễn bằng danh sách kề sẽ phù hợp khi đồ thị có nhiều đỉnh nhưng có ít cạnh.
Xem đáp án »
13/07/2024
86
Câu 4:
Quan sát Hình 2, em hãy xây dựng mảng g biểu diễn đồ thị cho mối quan hệ giáp ranh giữa 8 tỉnh (các tỉnh được đánh số từ 0 đến 7): Sơn La (0), Điện Biên (1), Lai Châu (2), Lào Cai (3), Hà Giang (4), Cao Bằng (5), Lạng Sơn (6), Quảng Ninh (7). Mảng g có kích thước như thế nào? Em có nhận xét gì về số lượng số 0 và số 1 trong mảng g?
Quan sát Hình 2, em hãy xây dựng mảng g biểu diễn đồ thị cho mối quan hệ giáp ranh giữa 8 tỉnh (các tỉnh được đánh số từ 0 đến 7): Sơn La (0), Điện Biên (1), Lai Châu (2), Lào Cai (3), Hà Giang (4), Cao Bằng (5), Lạng Sơn (6), Quảng Ninh (7). Mảng g có kích thước như thế nào? Em có nhận xét gì về số lượng số 0 và số 1 trong mảng g?
Xem đáp án »
13/07/2024
68
Câu 5:
Nếu coi các địa điểm A, B, C, D trong Bảng 1 tương ứng là các đỉnh 0, 1, 2, 3 của đồ thị thì mảng hai chiều g trong Hình 1 biểu diễn đồ thị mô tả tuyến xe buýt giữa các địa điểm.
Nếu Nam bổ sung thêm thông tin có một tuyến xe buýt từ B đến D, thì mảng g biểu diễn đồ thị thay đổi như thế nào?
Em có nhận xét gì về tính đối xứng của mảng ?
Nếu coi các địa điểm A, B, C, D trong Bảng 1 tương ứng là các đỉnh 0, 1, 2, 3 của đồ thị thì mảng hai chiều g trong Hình 1 biểu diễn đồ thị mô tả tuyến xe buýt giữa các địa điểm.
Nếu Nam bổ sung thêm thông tin có một tuyến xe buýt từ B đến D, thì mảng g biểu diễn đồ thị thay đổi như thế nào?
Em có nhận xét gì về tính đối xứng của mảng ?
Xem đáp án »
13/07/2024
63
về câu hỏi!