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.

a) Em hãy xây dựng đồ thị, biết rằng với hai đỉnh được đánh chỉ số u, v (0 ≤ u, v ≤ 5), nếu u > v và u - v là một số nguyên tố thì đỉnh có chỉ số u có cạnh tới được đỉnh có chỉ số v.

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

Xem lời giải

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

Bắt đầu thi

Quảng cáo

Trả lời:

Giải bởi Vietjack

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

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

Để 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 có cách mô tả nào khác về mối quan hê giáp ranh giữa các tỉnh đó không?

Xem đáp án

Lời giải

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

Câu 2

Em hãy nêu ví dụ thực tế có thể sử dụng mô hình đồ thị để mô tả.

Xem đáp án

Lời giải

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.

Câu 3