Câu hỏi:

13/07/2024 179

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.

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

a) Sai. Vì cả đơn đồ thị vô hướng và đơn đồ thị có hướng đều có thể biểu diễn được bằng ma trận kề.

b) Đúng. Vì cách biểu diễn đồ thị bằng ma trận kề tuy đơn giản nhưng có thể lãng phí bộ nhớ trong trường hợp đồ thị có nhiều đỉnh nhưng có ít cạnh. Lý do là vì ma trận kề là một ma trận vuông có kích thước n x n, trong đó n là số đỉnh của đồ thị.

c) Sai.Vì cả đơn đồ thị vô hướng và đơn đồ thị có hướng đều có thể biểu diễn được bằng danh sách kề.

d) Đúng. Vì 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. Lý do là vì danh sách kề chỉ lưu trữ thông tin về các cạnh thực sự tồn tại trong đồ thị, do đó sẽ tiết kiệm bộ nhớ hơn so với ma trận kề, đặc biệt là khi đồ thị có nhiều đỉnh nhưng có ít cạnh.


 

Bình luận


Bình luận

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Lời giải

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

Đồ 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ề. (ảnh 2)

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

Đồ 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ề. (ảnh 3)

 

Lời giải

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) Đỉnh đến được đỉnh 2: là đỉnh 0 và đỉnh 1.

b) Biểu diễn đồ thị bằng danh sách kề:

- Đỉnh 0 kề với đỉnh [1, 2]

- Đỉnh 1 kề với đỉnh [0]

- Đỉnh 2 kề với đỉnh [0]

- Đỉnh 3 không kề với đỉnh nào

Vietjack official store
Đăng ký gói thi VIP

VIP +1 - Luyện thi tất cả các đề có trên Website trong 1 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +3 - Luyện thi tất cả các đề có trên Website trong 3 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +6 - Luyện thi tất cả các đề có trên Website trong 6 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +12 - Luyện thi tất cả các đề có trên Website trong 12 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay