2.19. Viết tập hợp các đỉnh và tập hợp các cạnh của mỗi đồ thị sau:

Giải chi tiết:

Đồ thị 2.37a có tập hợp đỉnh và tập hợp cạnh là: V = {A, B, C} và E = {AB, AC, BB, BC}.

Đồ thị 2.37b có tập hợp đỉnh và tập hợp cạnh là: V = {P, Q, R, Z, Y, X} và E = {PX, PY, PZ, QX, QY, QZ, RX, RY, RZ}.

2.20. Vẽ đồ thị G = (V, E) với các đỉnh và các cạnh như sau:

V= {1; 2; 3; 4; 5; 6; 7; 8} và E = {12; 13; 23; 34; 35; 67; 68; 78}.

Đồ thị này có phải là đơn đồ thị không? Có phải là đồ thị đầy đủ không?

Giải chi tiết:

Đồ thị này là một đơn đồ thị nhưng không phải là đồ thị đầy đủ.

2.21. Chứng minh rằng không có đơn đồ thị với 12 đỉnh và 28 cạnh mà các đỉnh đều có bậc 3 hoặc 6.

Giải chi tiết:

Gọi x là số đỉnh bậc 3 của đồ thị. Khi đó số đỉnh bậc 6 của đồ thị là 12 - x. Tổng tất cả các bậc của đỉnh là 3x + 6(12 - x).

Vì đồ thị có 28 cạnh nên ta có: 3x + 6(12 - x) = 2.28 = 56 ⇔ x = 16/3 (loại, vì số đỉnh phải là số tự nhiên).

Suy ra điều cần phải chứng minh.

2.22. Chứng minh rằng nếu G là một đơn đồ thị có ít nhất hai đỉnh thì G có ít nhất hai đỉnh có cùng bậc.

Giải chi tiết:

Gọi số đỉnh của đồ thị là n (n ≥ 2)

Theo Nguyên lí chuồng bồ câu: Nếu một số lượng n vật thể được đặt vào m chuồng bồ câu, với điều kiện n > m, thì ít nhất một chuồng bồ câu sẽ có nhiều hơn 1 vật thể.

Một bậc của một đỉnh coi như một chuồng: tối đa n - 1, tối thiểu là 1.

Ví dụ: n = 10, 10 đỉnh có tối thiểu: bậc 1; tối đa: bậc 9.

Đồ thị có 10 đỉnh thì có hai đỉnh cùng bậc. (đcpcm)

2.23. Tìm số đỉnh nhỏ nhất cần thiết để có thể xây dựng một đồ thị đầy đủ với ít nhất 1 000 cạnh.

Giải chi tiết:

Gọi số đỉnh của đồ thị là n.

Theo bài tập 2.4 trang 40 (Bài 8: Một vài khái niệm cơ bản) ta có: Một đồ thị đầy đủ có n đỉnh thì có cạnh.

2.24. Hãy chỉ ra ít nhất 5 đường đi từ S đến Y trong đồ thị trên Hình 2.38.

Giải chi tiết:

Đường đi từ S đến Y là: SVIZY, SVUIZY, SVIZXY, SIZY, SIZWXY.

2.25. Kiểm tra xem các điều kiện của định lí Ore có thỏa mãn với các đồ thị trên Hình 2.39 không.

Giải chi tiết:

Định lí Ore: Nếu G là đơn đồ thị có n đỉnh (n ≥ 3) và mỗi cặp đỉnh không kề nhau đều có tổng bậc không nhỏ hơn n thì G có một chu trình Hamilton.

Hình 2.39a có 5 đỉnh, các cặp đỉnh không kề nhau là B và D (tổng bậc hai đỉnh là 3 + 3 = 6 > 5); C và E (tổng bậc hai đỉnh là 3 + 3 = 6 > 5). Suy ra, đồ thị thỏa mãn với các điều kiện của định lí Ore.

Hình 2.39b có 5 đỉnh, các cặp đỉnh không kề nhau là M và Q (tổng bậc hai đỉnh là 2 + 2 = 4 < 5); M và P (tổng bậc hai đỉnh là 2 + 2 = 4 < 5); N và Q (tổng bậc hai đỉnh là 3 + 2 = 5); P và H (tổng bậc hai đỉnh là 2 + 3 = 5). Suy ra có cặp đỉnh M và Q, M và P không thỏa mãn điều kiện của định lí Ore.

2.26. Tìm một chu trình Euler trong đồ thị trên Hình 2.40.

Giải chi tiết:

Một chu trình Euler trong đồ thị trên Hình 2.40 là: ABCDEFAECA.

2.27. Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.41.

Giải chi tiết:

Vì đồ thị là liên thông và các đỉnh đều có bậc chẵn (đều là bậc 4) nên đồ thị có chu trình Euler.

Một chu trình Euler xuất phát từ đỉnh O (tâm đồ thị) là OABADCDOBCO và tổng độ dài của nó là 36.

2.28. Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.42.

Giải chi tiết:

Đồ thị có hai đỉnh bậc lẻ là D và E nên ta có thể tìm được một đường đi Euler từ D và E (đường đi này đi qua mỗi cạnh đúng một lần).

Một đường đi Euler từ D đến E là DBACBECDE và tổng độ dài của nó là: 2 + 4 + 4 + 5 + 3 + 1 + 2 + 6 = 27.

Để quay trở lại điểm xuất phát và có đường đi ngắn nhất, ta cần tìm một đường đi ngắn nhất từ E đến D theo thuật toán đã mô tả ở Mục 1.

Đường đi ngắn nhất từ E đến D là ECD và có độ dài là 1 + 2 = 3.

Vậy một chu trình cần tìm là DBACBECDECD và có độ dài là 27 + 3 = 30.