Chuyên đề Tin 12 CTST Bài 3.2. Biểu diễn đồ thị

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 trong ngôn ngữ Python. Theo em, có thể sử dụng mảng hai chiều để biểu diễn một đồ thị được không?

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:

Trong ma trận này, các hàng và cột tương ứng với các đỉnh của đồ thị, và một giá trị ‘1’ trong ma trận biểu thị sự kết nối trực tiếp giữa hai đỉnh, trong khi giá trị ‘0’ biểu thị không có kết nối trực tiếp.

Em hãy dùng danh sách kề biểu diễn các đồ thị ở Hình 4 và Hình 5.

Từ danh sách kề ở Bảng 6. Hãy vẽ đồ thị có hướng tương ứng.

Cho hai đồ thị G₆ (Hình 6) và G₇ (Hình 7). Em hãy thực hiện biểu điễn bằng hai cách:

- Ma trận kê.

- Danh sách kề.

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 ma trận kể biểu diễn đồ thị G₂ (Hình 2) và G₃ (Hình 3). 

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 kể biểu diễn đồ thị G₄ (Hình 4) và G₅ (Hình 5).

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