Một hãng hàng không đưa ra lịch bay trong ngày như sau trang 58 Chuyên đề Tin học 12

Giải Chuyên đề Tin 12 Bài 3.2: Biểu diễn đồ thị - Chân trời sáng tạo

Vận dụng trang 58 Chuyên đề Tin học 12: Một hãng hàng không đưa ra lịch bay trong ngày như sau:

- Từ TP.HCM: có một chuyến đến Hà Nội, Đà Nẵng, Phú Quốc, Nghệ An và Hải Phòng;

- Từ Hà Nội: có hai chuyến đến TP.HCM và một chuyến đến Đà Nẵng, Nghệ An, Hải Phòng;

- Từ Đà Nẵng: có một chuyến đến Hải Phòng, hai chuyến bay đến TP.HCM, một chuyến đến Hà Nội;

- Từ Nghệ An: có một chuyến đến Hà Nội, một chuyến đến TP.HCM;

- Từ Hải Phòng: có một chuyển đến Hà Nội, một chuyến đến TP.HCM, và một chuyến đến Đà Nẵng;

- Từ Phú Quốc: có một chuyến đến TP.HCM.

a) Vẽ đồ thị biểu diễn các thành phố có chuyến bay giữa chúng (không quan tâm đến số lượng các chuyến bay).

b) Từ đồ thị đã vẽ được trong câu a). Hãy biểu diễn đồ thị bằng hai cách:

- Ma trận kê.

- Danh sách kể.

Lời giải:

Một hãng hàng không đưa ra lịch bay trong ngày như sau:

- Từ TP.HCM: có một chuyến đến Hà Nội, Đà Nẵng, Phú Quốc, Nghệ An và Hải Phòng;

- Từ Hà Nội: có hai chuyến đến TP.HCM và một chuyến đến Đà Nẵng, Nghệ An, Hải Phòng;

- Từ Đà Nẵng: có một chuyến đến Hải Phòng, hai chuyến bay đến TP.HCM, một chuyến đến Hà Nội;

- Từ Nghệ An: có một chuyến đến Hà Nội, một chuyến đến TP.HCM;

- Từ Hải Phòng: có một chuyển đến Hà Nội, một chuyến đến TP.HCM, và một chuyến đến Đà Nẵng;

- Từ Phú Quốc: có một chuyến đến TP.HCM.

a) Vẽ đồ thị biểu diễn các thành phố có chuyến bay giữa chúng (không quan tâm đến số lượng các chuyến bay).

b) Từ đồ thị đã vẽ được trong câu a). Hãy biểu diễn đồ thị bằng hai cách:

- Ma trận kê.

- Danh sách kể.

a) Vẽ đồ thị biểu diễn các thành phố có chuyến bay giữa chúng

Để biểu diễn các thành phố và các chuyến bay giữa chúng, chúng ta có các đỉnh (vertices) là các thành phố và các cạnh (edges) là các chuyến bay giữa các thành phố đó.

Các thành phố:

TP.HCM (HCM)

Hà Nội (HN)

Đà Nẵng (DN)

Phú Quốc (PQ)

Nghệ An (NA)

Hải Phòng (HP)

Các chuyến bay (cạnh):

Từ TP.HCM: HCM -> HN, HCM -> DN, HCM -> PQ, HCM -> NA, HCM -> HP

Từ Hà Nội: HN -> HCM, HN -> DN, HN -> NA, HN -> HP

Từ Đà Nẵng: DN -> HP, DN -> HCM, DN -> HN

Từ Nghệ An: NA -> HN, NA -> HCM

Từ Hải Phòng: HP -> HN, HP -> HCM, HP -> DN

Từ Phú Quốc: PQ -> HCM

Đồ thị:

b) Biểu diễn đồ thị bằng hai cách:

1. Ma trận kề (Adjacency Matrix)

Ma trận kề là một ma trận vuông trong đó mỗi hàng và cột đại diện cho một đỉnh (thành phố) và các phần tử ma trận biểu thị sự tồn tại của một cạnh (chuyến bay) giữa các đỉnh.

	HCM	HN	DN	PQ	NA	HP
HCM	0	1	1	1	1	1
HN	1	0	1	0	1	1
DN	1	1	0	0	0	1
PQ	1	0	0	0	0	0
NA	1	1	0	0	0	0
HP	1	1	1	0	0	0

2. Danh sách kề (Adjacency List)

Danh sách kề biểu thị đồ thị bằng cách liệt kê các đỉnh kề nhau cho mỗi đỉnh trong đồ thị.

adj_list = {

   "HCM": ["HN", "DN", "PQ", "NA", "HP"],

   "HN": ["HCM", "DN", "NA", "HP"],

   "DN": ["HP", "HCM", "HN"],

   "PQ": ["HCM"],

   "NA": ["HN", "HCM"],

   "HP": ["HN", "HCM", "DN"]

}

Tóm tắt

Ma trận kề: Sử dụng một ma trận vuông để biểu diễn các kết nối giữa các thành phố. Mỗi hàng và cột tương ứng với một thành phố và phần tử tại hàng i cột j là 1 nếu có chuyến bay giữa thành phố i và j, ngược lại là 0.

Danh sách kề: Sử dụng một từ điển (dictionary) để liệt kê các thành phố kề nhau cho mỗi thành phố. Mỗi khóa của từ điển là một thành phố và giá trị tương ứng là một danh sách các thành phố có chuyến bay trực tiếp từ thành phố đó.

Lời giải bài tập Chuyên đề Tin 12 Bài 3.2: Biểu diễn đồ thị hay, chi tiết khác:

• Khởi động trang 53 Chuyên đề Tin học 12: Em hãy nhắc lại định nghĩa mảng hai chiều và cách khai báo mảng hai chiều ....

• Câu hỏi 1 trang 56 Chuyên đề Tin học 12: Cho đồ thị G3, như Hình 3. Hãy biểu diễn đồ thị bằng ma trận kề ....

• Câu hỏi 2 trang 56 Chuyên đề Tin học 12: Dựa trên mô tả của hình ảnh, đồ thị G3 có thể được biểu diễn bằng ma trận kề như sau ....

• Câu hỏi 1 trang 57 Chuyên đề Tin học 12: Em hãy dùng danh sách kề biểu diễn các đồ thị ở Hình 4 và Hình 5 ....

• Câu hỏi 2 trang 57 Chuyên đề Tin học 12: Từ danh sách kề ở Bảng 6. Hãy vẽ đồ thị có hướng tương ứng ....

• Luyện tập trang 58 Chuyên đề Tin học 12: Cho hai đồ thị G6 (Hình 6) và G7 (Hình 7) ....

• Thực hành 1 trang 58 Chuyên đề Tin học 12: Sử dụng chương trình trong bài học, hãy viết chương trình xuất ra ....

• Thực hành 2 trang 58 Chuyên đề Tin học 12: Sử dụng chương trình trong bài học, hãy viết chương trình xuất ra màn hình danh sách ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Chân trời sáng tạo hay, chi tiết khác:

• Chuyên đề Tin 12 Bài 2.4: Thực hành cây tìm kiếm nhị phân

• Chuyên đề Tin 12 Bài 3.1: Các khái niệm cơ bản của đồ thị

• Chuyên đề Tin 12 Bài 3.3: Duyệt đồ thị theo chiều rộng

• Chuyên đề Tin 12 Bài 3.4: Duyệt đồ thị theo chiều sâu

• Chuyên đề Tin 12 Bài 3.5: Thực hành kĩ thuật duyệt đồ thị

Xem thêm các tài liệu học tốt lớp 12 hay khác:

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều
• Giải lớp 12 Kết nối tri thức (các môn học)
• Giải lớp 12 Chân trời sáng tạo (các môn học)
• Giải lớp 12 Cánh diều (các môn học)

---