Giải chuyên đề Khoa học máy tính 12 cánh diều bài 1: Kiểu dữ liệu hàng đợi
Giải chuyên đề Khoa học máy tính 12 cánh diều bài 2: Kiểu dữ liệu ngăn xếp
Giải chuyên đề Khoa học máy tính 12 cánh diều bài 3: Thực hành kiểu dữ liệu hàng đợi và ngăn xếp
Giải chuyên đề Khoa học máy tính 12 cánh diều bài 4: Dự án học tập: Xây dựng chương trình sử dụng kiểu dữ liệu hàng đợi và ngăn xếp
Giải chuyên đề Khoa học máy tính 12 cánh diều bài 1: Giới thiệu cây nhị phân
Giải chuyên đề Khoa học máy tính 12 cánh diều bài 2: Thực hành duyệt cây nhị phân
Giải chuyên đề Khoa học máy tính 12 cánh diều bài 3: Cây tìm kiếm nhị phân
Giải chuyên đề Khoa học máy tính 12 cánh diều bài 1: Đồ thị, phân loại đồ thị
Giải chuyên đề Khoa học máy tính 12 cánh diều bài 2: Biểu diễn đồ thị trên máy tính
Giải chuyên đề Khoa học máy tính 12 cánh diều bài 3: Thực hành các thao tác cơ bản với đồ thị trên máy tính
Giải chuyên đề Khoa học máy tính 12 cánh diều bài 4: Duyệt đồ thị
Giải chuyên đề Khoa học máy tính 12 cánh diều bài 5: Thực hành duyệt đồ thị
Giải chuyên đề Khoa học máy tính 12 cánh diều bài 6: Dự án học tập: Tìm hiểu các vấn đề ứng dụng đồ thị

Giải chuyên đề Khoa học máy tính 12 cánh diều bài 2: Biểu diễn đồ thị trên máy tính

Hướng dẫn giải bài 2: Biểu diễn đồ thị trên máy tính bộ sách mới chuyên đề học tập Khoa học máy tính 12 cánh diều. Bộ sách được biên soạn theo định hướng đổi mới giáo dục phổ thông nhằm phát triển toàn diện phẩm chất, năng lực của học sinh. Hi vọng, với cách hướng dẫn cụ thể và giải chi tiết dưới đây các em sẽ nắm bài học tốt hơn.

B. Bài tập và hướng dẫn 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...

KHỞI ĐỘNG

Câu hỏ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. 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 hướng dẫn giải

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. BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN KỀ

Hoạt động 1:

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 g?

=> Xem hướng dẫn giải

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

2. BIỂU DIỄN ĐỒ THỊ BẰNG DANH SÁCH KỀ

Hoạt động 2:

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 hướng dẫn giải

Một đồ thị gồm 4 đỉnh, các đỉnh được đánh số từ 0 đến 3, được biểu...

3. MỘT SỐ THUẬT NGỮ VÀ TÍNH CHẤT TRÊN ĐỒ THỊ

LUYỆN TẬP

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

=> Xem hướng dẫn giải

Đồ thị khối Q, (Hình 4) là đồ thị có 8 đỉnh, mỗi đỉnh là một dãy bit...

VẬN DỤNG

Đồ 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 hướng dẫn giải

Trong các câu sau đây, những câu nào đúng? a) Chỉ có đơn đồ thị có...

TỰ KIỂM TRA

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 hướng dẫn giải

Thêm kiến thức môn học

Giải tin học 12 định hướng Khoa học máy tính cánh diều

Giáo án khoa học máy tính 12 cánh diều

Giáo án chuyên đề Khoa học máy tính 12 cánh diều

Bài giảng điện tử khoa học máy tính 12 Cánh diều

Bài giảng điện tử chuyên đề học tập Khoa học máy tính 12 cánh diều

Trắc nghiệm Tin học KHMT 12 cánh diều

Siêu nhanh giải tin học khoa học máy tính 12 cánh diều

5 phút giải tin học khmt 12 cánh diều

Giải chuyên đề Khoa học máy tính 12 Cánh diều

Slide bài giảng tin học máy tính 12 cánh diều

Đáp án tin học máy tính 12 cánh diều

Dễ hiểu giải tin học máy tính 12 cánh diều

Video bài giảng tin học máy tính 12 cánh diều

Từ khóa tìm kiếm:

Giải chuyên đề học tập Khoa học máy tính 12 cánh diều, Giải chi tiết bài 2: Biểu diễn đồ thị trên máy chuyên đề học tập Khoa học máy tính 12 cánh diều, Giải chuyên đề học tập Khoa học máy tính 12 cánh diều bài 2: Biểu diễn đồ thị trên máy