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 lời giải

Câu hỏi trong đề: Giải chuyên đề Tin 12 Cánh diều Bài 2: Biểu diễn đồ thị trên máy tính có đáp án !!

Bắt đầu thi

Quảng cáo

Trả lời:

Giải bởi Vietjack

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

Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay

Sách thầy cô Vietjack biên soạn:

Xem thêm »

Bình luận

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

Câu 1

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

Xem đáp án

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

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?

Xem đáp án

Lời giải

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. Dựa trên mô tả của bảng thông tin về các tuyến xe buýt, chúng ta có thể trả lời các câu hỏi như sau:

- Từ D đến các địa điểm khác: 4 tuyến xe buýt

- Từ B đến D: có 1 tuyến xe buýt

Câu 3