Cây kéo dài
Một định nghĩa đơn giản là cây là một đồ thị liên thông được liên kết với không có chu trình, trong đó một chu trình cho phép chúng ta đi từ một nút đến chính nó mà không lặp lại một cạnh.
Cây khung cho đồ thị liên thông G được định nghĩa là cây chứa tất cả các đỉnh của G.
Spanning tree thường được thực hiện cho các Thuật toán định tuyến Internet. Trong Internet, các máy tính (nút) thường được kết nối với nhiều kết nối vật lý dự phòng.
Tổng số cây kéo dài trong một biểu đồ. Nếu một đồ thị là một đồ thị hoàn chỉnh với n không. trong số các đỉnh, khi đó tổng số cây khung là n (n-2)
trong đó n được biểu thị là số nút trong đồ thị. Trong biểu đồ hoàn chỉnh, nhiệm vụ tương đương với việc đếm các cây được gắn nhãn khác nhau với n nút có công thức Cayley.
Khả năng kết nối
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ử (nút hoặc cạnh) tối thiểu cần được loại bỏ để tách các nút còn lại thành các đồ thị con riêng biệt.
Nó liên quan chặt chẽ đến lý thuyết về các vấn đề luồng mạng.
Biểu đồ này bị ngắt kết nối khi cạnh đứt nét bị loại bỏ.
Kết nối đỉnh. Kết nối đỉnh của biểu đồ là số lượng ít nhất các nút mà việc xóa sẽ ngắt kết nối nó.
Kết nối Vertex đôi khi được biểu thị là "kết nối điểm" hoặc đơn giản là "kết nối".
Kết nối cạnh. Số lượng ít nhất các cạnh mà việc xóa khỏi biểu đồ sẽ ngắt kết nối, cũng được biểu thị là kết nối đường.
Khả năng kết nối cạnh của một biểu đồ bị ngắt kết nối là 0, trong khi kết nối của một biểu đồ được kết nối được liên kết với cầu biểu đồ là 1.
Khoảng cách
Khoảng cách giữa hai nút có thể được tính theo tổ tiên chung thấp nhất. Sau đây là công thức.
Dist(d1, d2) = Dist(root, d1) + Dist(root, d2) - 2*Dist(root, lca) 'd1' and 'd2' are the two given keys 'root' is root of given Binary Tree. 'lca' is lowest common ancestor of d1 and d2 Dist(d1, d2) is the distance between d1 and d2.