Giải chuyên đề Tin 12 Cánh diều Bài 1: Đồ thị, phân loại đồ thị có đáp án

Để mô tả các cặp tỉnh có địa giới giáp ranh nhau, ta có thể nêu bằng lời, ví dụ, quan sát lược đồ bốn tỉnh Bạc Liêu, Cà Mau, Sóc Trăng và Kiên Giang trong Hình 1, ta nói "Các cặp tỉnh: (Bạc Liêu, Cà Mau), (Bạc Liêu, Sóc Trăng), (Bạc Liêu, Kiên Giang), (Kiên Giang, Cà Mau) giáp ranh nhau; còn (Kiên Giang, Sóc Trăng) và (Sóc Trăng, Cà Mau) không giáp ranh nhau". Em mô tả nào khác về mối quan hê giáp ranh giữa các tỉnh đó như sau:

Bạc Liêu ---- Cà Mau

|            |

|            |

Sóc Trăng ---- Kiên Giang

Trong biểu đồ này, mỗi đường nối giữa hai điểm biểu thị rằng hai tỉnh đó giáp ranh nhau. Như vậy, ta có thể thấy rằng Bạc Liêu giáp ranh với Cà Mau, Sóc Trăng, và Kiên Giang; Cà Mau giáp ranh với Bạc Liêu và Kiên Giang; Sóc Trăng giáp ranh với Bạc Liêu; và Kiên Giang giáp ranh với Bạc Liêu và Cà Mau. Còn Sóc Trăng và Cà Mau không có đường nối, cho thấy hai tỉnh này không giáp ranh nhau. Tương tự, Kiên Giang và Sóc Trăng cũng không giáp ranh nhau.

- Hậu Giang giáp với: Bạc Liêu, Sóc Trăng, Kiên Giang.

- Cần Thơ giáp với: Kiên Giang, Hậu Giang

Ví dụ về Mạng xã hội: Trong mạng xã hội, mỗi người dùng là một đỉnh và mối quan hệ bạn bè hoặc theo dõi là các cạnh. Điều này giúp phân tích mạng lưới xã hội và tìm ra các mối quan hệ quan trọng.

Ví dụ về Mối quan hệ dinh dưỡng giữa các loài: Chuột là thức ăn của Rắn nhưng Rắn không phải là thức ăn của Chuột, Rắn là thức ăn của Diều hâu.

Xét đơn đồ thị có hướng gồm 6 đỉnh, các đỉnh được đánh chỉ số tương ứng từ 0 đến 5:

Xác định các số nguyên tố từ 1 đến 5 (vì u và v có giá trị từ 0 đến 5 và u > v). Các số nguyên tố trong khoảng này là 2, 3 và 5. Vậy, chúng ta sẽ có một cạnh từ đỉnh u đến đỉnh v nếu u - v bằng một trong những số nguyên tố này.

a) Xây dựng đồ thị:

- Đỉnh 1 không có cạnh tới bất kỳ đỉnh nào khác vì không có số nguyên tố nào khi trừ đi 1.

- Đỉnh 2 sẽ có một cạnh tới đỉnh 0 (2 - 0 = 2).

- Đỉnh 3 sẽ có cạnh tới đỉnh 0 (3 - 0 = 3).

- Đỉnh 4 sẽ có cạnh tới đỉnh 1 và 3 (4 - 1 = 3 và 4 - 3 = 1, nhưng 1 không phải là số nguyên tố).

- Đỉnh 5 sẽ có cạnh tới đỉnh 0, 2 và 3 (5 - 0 = 5, 5 - 2 = 3 và 5 - 3 = 2).

Dựa vào cách xây dựng trên, ta có thể vẽ đồ thị như sau:

0 ← 2 ← 4

↓   ↓

1   3 ← 5

b) Xác định bậc ra và bậc vào của từng đỉnh:

- Đỉnh 0: Bậc vào = 3 (từ đỉnh 2, 3, 5), Bậc ra = 0.

- Đỉnh 1: Bậc vào = 1 (từ đỉnh 4), Bậc ra = 0.

- Đỉnh 2: Bậc vào = 1 (từ đỉnh 5), Bậc ra = 1 (tới đỉnh 0).

- Đỉnh 3: Bậc vào = 2 (từ đỉnh 4, 5), Bậc ra = 0.

- Đỉnh 4: Bậc vào = 0, Bậc ra = 2 (tới đỉnh 1 và 3).

- Đỉnh 5: Bậc vào = 0, Bậc ra = 3 (tới đỉnh 0, 2 và 3).

Các quận/huyện được chọn là:

1.    Quận Ba Đình

2.    Quận Hoàn Kiếm

3.    Quận Đống Đa

4.    Quận Hai Bà Trưng

5.    Quận Thanh Xuân

6.    Quận Cầu Giấy

Theo thông tin giáp ranh, đồ thị vô hướng được xây dựng như sau: