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

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

Câu 2 trang 56 Chuyên đề Tin học 12: XXét đơn đồ thị có hướng gồm 6 đỉnh, các đỉnh được đánh chỉ số tương ứng từ 0 đến 5 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.

Lời giải:

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

Lời giải bài tập Chuyên đề Tin 12 Bài 1: Đồ thị, phân loại đồ thị hay, chi tiết khác:

• Khởi động trang 53 Chuyên đề Tin học 12: Để 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 ....

• Hoạt động 1 trang 54 Chuyên đề Tin học 12: Việc mô tả mối quan hệ giáp ranh của bốn tỉnh Kiên Giang, Cà Mau, Bạc Liêu ....

• Câu 1 trang 56 Chuyên đề Tin học 12: Em hãy nêu ví dụ thực tế có thể sử dụng mô hình đồ thị để mô tả ....

• Vận dụng trang 56 Chuyên đề Tin học 12: Em hãy chọn ra 6 quận/huyện trong tỉnh/thành phố nơi em ở và xây dựng đồ thị ....

• Câu hỏi tự kiểm tra trang 56 Chuyên đề Tin học 12: Trong các câu sau đây, những câu nào đúng khi nói về đồ thị ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Cánh diều hay, chi tiết khác:

• Chuyên đề Tin học 12 Bài 2: Biểu diễn đồ thị trên máy tính

• Chuyên đề Tin học 12 Bài 3: Thực hành các thao tác cơ bản với đồ thị trên máy tính

• Chuyên đề Tin học 12 Bài 4: Duyệt đồ thị

• Chuyên đề Tin học 12 Bài 5: Thực hành duyệt đồ thị

• Chuyên đề Tin học 12 Bài 6: Dự án học tập: Tìm hiểu các vấn đề ứng dụng đồ 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

---