Cây khung (Spanning Tree)
Định nghĩa đơn giản: cây là một đồ thị liên thông không có chu trình, nơi chu trình cho phép đi từ một nút về chính nút đó mà không lặp cạnh.
Cây khung cho một đồ thị liên thông G là một cây chứa tất cả các đỉnh của G.
Cây khung thường được dùng trong thuật toán định tuyến Internet. Trên Internet, máy tính (nút) thường được kết nối bằng nhiều kết nối vật lý dự phòng.
Tổng số cây khung trong đồ thị. Nếu đồ thị là đồ thị hoàn chỉnh với n đỉnh, tổng số cây khung là nn-2 (Công thức Cayley).
Kết nối (Connectivity)
Trong toán học và khoa học máy tính, kết nối là một trong những khái niệm cơ bản của lý thuyết đồ thị. Nó yêu cầu số lượng phần tử tối thiểu (đỉnh hoặc cạnh) cần loại bỏ để tách các đỉnh còn lại thành các đồ thị con cô lập.
Nó liên quan chặt chẽ đến lý thuyết bài toán luồng mạng.
Đồ thị này trở nên không liên thông khi cạnh nét đứt bị loại bỏ.
- Kết nối đỉnh (Vertex Connectivity): Số đỉnh tối thiểu cần xóa để làm ngắt kết nối đồ thị. Đôi khi gọi là "kết nối điểm" hoặc đơn giản là "kết nối".
- Kết nối cạnh (Edge Connectivity): Số cạnh tối thiểu cần xóa để làm ngắt kết nối đồ thị, cũng gọi là "kết nối đường". Kết nối cạnh của đồ thị không liên thông là 0, của đồ thị liên thông có cầu (bridge) là 1.
Khoảng cách (Distance)
Khoảng cách giữa hai nút có thể tính qua tổ tiên chung gần nhất (lowest common ancestor). Công thức:
Dist(d1, d2) = Dist(root, d1) + Dist(root, d2) - 2*Dist(root, lca)
'd1' và 'd2' là hai khóa cho trước
'root' là gốc của cây nhị phân cho trước
'lca' là tổ tiên chung gần nhất của d1 và d2
Dist(d1, d2) là khoảng cách giữa d1 và d2