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