Lý thuyết đồ thị: bài tập có lời giải từng bước

1Đỉnh, cạnh và bậc

Một đồ thị gồm các đỉnh (điểm) và các cạnh (đường nối giữa hai đỉnh). Trong đồ thị đơn không có khuyên và không có cạnh kép.

Bậc của một đỉnh là số cạnh gặp đỉnh đó. Mỗi cạnh có hai đầu, nên nó cộng 1 vào bậc của mỗi đầu. Điều đó cho ta bổ đề bắt tay:

Hai hệ quả: tổng các bậc luôn chẵn, và số đỉnh có bậc lẻ cũng chẵn.

• Đồ thị đầy đủ K_n nối mọi cặp đỉnh: n(n − 1)/2 cạnh.
• Đồ thị hai phần đầy đủ K_m,n nối mọi đỉnh ở một phía với mọi đỉnh ở phía kia: m·n cạnh.
• Một đồ thị k-đều trên n đỉnh có n·k/2 cạnh.

Ma trận kề có số 1 tại (i, j) khi i và j được nối. Với đồ thị vô hướng nó đối xứng, tổng một hàng là một bậc, và phần tử (i, j) của Mᴸ đếm số đường đi độ dài L từ i đến j.

2Euler và Hamilton

Một chu trình Euler đi qua mọi cạnh đúng một lần và trở về điểm xuất phát. Một đường đi Euler đi qua mọi cạnh một lần nhưng có thể kết thúc ở nơi khác. Với một đồ thị liên thông:

• mọi bậc đều chẵn: tồn tại chu trình Euler;
• đúng hai bậc lẻ: tồn tại đường đi Euler, từ một đỉnh lẻ đến đỉnh lẻ kia;
• nhiều hơn hai bậc lẻ: không có cái nào.

Một chu trình Hamilton thăm mọi đỉnh đúng một lần. Không có phép thử bậc đơn giản cho nó. Trong K_n có (n − 1)!/2 chu trình Hamilton khác nhau: cố định điểm xuất phát, sắp xếp n − 1 đỉnh còn lại, và chia cho 2 vì hai chiều đi.

3Cây

Một cây là đồ thị liên thông không có chu trình. Mọi cây có n đỉnh có đúng n − 1 cạnh. Thêm bất kỳ cạnh nào sẽ tạo ra một chu trình; bỏ bất kỳ cạnh nào sẽ làm nó mất liên thông.

Một rừng gồm c cây trên n đỉnh có n − c cạnh. Một đồ thị liên thông có m cạnh sẽ còn lại một cây khung sau khi bỏ m − n + 1 cạnh.

Bổ đề bắt tay đếm được số lá: Σ deg = 2(n − 1). Dạng ngắn gọn là L = 2 + Σ (d − 2) trên các đỉnh có bậc d ≥ 3. Một cây có hai đỉnh bậc 3 còn lại là lá có 2 + 1 + 1 = 4 lá.

4Dijkstra và cây khung nhỏ nhất

Thuật toán Dijkstra tìm khoảng cách ngắn nhất từ một đỉnh xuất phát trong đồ thị có trọng số không âm.

1. Gán khoảng cách 0 cho đỉnh xuất phát và ∞ cho mọi đỉnh khác.
2. Chốt đỉnh chưa chốt có khoảng cách nhỏ nhất; khoảng cách của nó giờ là cuối cùng.
3. Với mỗi đỉnh kề v, cập nhật d(v) = min(d(v), d(u) + w(u, v)).
4. Lặp lại cho đến khi đỉnh đích được chốt.

Một cây khung nhỏ nhất nối tất cả các đỉnh với tổng trọng số nhỏ nhất. Kruskal sắp xếp các cạnh từ nhẹ đến nặng và lấy từng cạnh trừ khi nó tạo thành chu trình. Prim mở rộng một cây từ một đỉnh xuất phát, luôn thêm cạnh nhẹ nhất đi ra khỏi cây. Cả hai dừng sau n − 1 cạnh.

5Lỗi thường gặp

• Quên chia tổng bậc cho 2 để có số cạnh.
• Kiểm tra chu trình Euler mà không kiểm tra đồ thị có liên thông hay không.
• Chốt một đỉnh trong Dijkstra trước khi nó có khoảng cách tạm thời nhỏ nhất.
• Lấy n − 1 cạnh nhẹ nhất mà không kiểm tra chu trình.
• Đếm chu trình Hamilton của K_n là n! thay vì (n − 1)!/2.

6Các câu hỏi thi trông như thế nào

• Dễ: bậc và cạnh. Bạn dùng bổ đề bắt tay, đếm số cạnh của K_n, K_m,n, đồ thị đều và cây, đọc một ma trận kề, hoặc nhấp vào đỉnh có bậc cho trước.
• Trung bình: đường đi Euler và cây. Bạn xác định đồ thị có chu trình hay đường đi Euler hay không, đếm lá của một cây, đếm số cạnh cần bỏ để được cây khung, hoặc đếm chu trình Hamilton trong K_n.
• Khó: đường đi ngắn nhất và cây khung. Bạn chạy thuật toán Dijkstra, tìm đỉnh được chốt ở một vòng cho trước, tìm trọng số của cây khung nhỏ nhất, nhấp vào cạnh mà Kruskal hoặc Prim thêm tiếp theo, hoặc đếm số đường đi bằng ma trận kề.