Câu hỏi:

11/07/2024 385

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.

Xem lời giải

Câu hỏi trong đề: Giải chuyên đề Tin 12 KNTT Bài 11: Khái niệm đồ thị có đáp án !!

Bắt đầu thi

Quảng cáo

Trả lời:

Giải bởi Vietjack

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ề:

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

- 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ề:

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

- 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

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

Xem đáp án

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:

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

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ề:

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

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ề:

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