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

Trang trước Trang sau

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:

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:

Xem thêm các tài liệu học tốt lớp 12 hay khác:

Trang trước Trang sau
Giải bài tập lớp 12 sách mới các môn học