Cấu trúc dữ liệu và giải thuật: gói ôn nước rút

Lý thuyết đồ thị

Bổ đề bắt tay

Σ deg(v) = 2|E|

Đồ thị đầy đủ

|E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n

Đồ thị đều

|E| = n·k/2

Cây và rừng

|E| = n − 1, |E| = n − c

Lá của cây

L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3

Euler

chu trình: mọi bậc đều chẵn; đường đi: đúng 2 bậc lẻ

Chu trình Hamilton trong K_n

(n − 1)!/2

Cập nhật Dijkstra

d(v) = min(d(v), d(u) + w(u, v))

Đường đi độ dài L

(Mᴸ)_ij

Phương pháp

1. Hãy ghi bậc của mỗi đỉnh; tổng các bậc bằng hai lần số cạnh.
2. Với bài Euler, hãy kiểm tra đồ thị liên thông và đếm số đỉnh có bậc lẻ.
3. Với cây, hãy dùng n − 1 cạnh và bổ đề bắt tay.
4. Với Dijkstra, hãy lập bảng khoảng cách tạm thời và mỗi vòng chốt đỉnh chưa chốt có giá trị nhỏ nhất.
5. Với cây khung nhỏ nhất, hãy sắp xếp các cạnh theo trọng số và bỏ qua mọi cạnh tạo thành chu trình (Kruskal), hoặc mở rộng một cây từ một đỉnh xuất phát (Prim).