Đường Kính Của Cây

Trong lý thuyết đồ thị, đường kính của một cây được định nghĩa là độ dài của đường đi đơn dài nhất giữa bất kỳ cặp nút nào trong cây.

Phương Pháp Tìm Đường Kính

Một thuật toán hiệu quả để xác định đường kính của cây bao gồm hai bước Duyệt Sâu (DFS):

1. Chọn một nút bất kỳ trong cây (ví dụ, nút có chỉ số 1) và thực hiện thuật toán DFS từ nút đó. Mục tiêu của lần DFS đầu tiên này là tìm ra nút xa nhất so với nút khởi đầu. Gọi nút này là nodeA.
2. Tiếp theo, thực hiện một lần DFS thứ hai, lần này bắt đầu từ nodeA. Nút xa nhất tìm được trong lần DFS này (gọi là nodeB) sẽ là đầu mút thứ hai của đường kính cây. Khoảng cách từ nodeA đến nodeB chính là độ dài đường kính của cây.

Ví Dụ Mã Nguồn (C++)

#include <iostream>
#include <vector>
#include <algorithm> // Cho std::max

const int MAX_NODES = 1010;
// Danh sách kề: lưu cặp {nút lân cận, trọng số cạnh}
std::vector<std::pair<int, int>> adjacencyList[MAX_NODES];
int maxPathLengthFound;
int nodeFarthestFromStart;

// Hàm DFS để tìm nút xa nhất từ một điểm xuất phát
void findFarthestNodeDFS(int currentNode, int parentNode, int currentPathDistance) {
    // Cập nhật nếu tìm thấy đường đi dài hơn
    if (currentPathDistance > maxPathLengthFound) {
        maxPathLengthFound = currentPathDistance;
        nodeFarthestFromStart = currentNode;
    }

    // Duyệt qua tất cả các nút lân cận
    for (const auto& edge : adjacencyList[currentNode]) {
        int neighborNode = edge.first;
        int edgeWeight = edge.second;

        // Bỏ qua nút cha để tránh đi ngược lại
        if (neighborNode == parentNode) {
            continue;
        }
        // Gọi đệ quy cho nút con
        findFarthestNodeDFS(neighborNode, currentNode, currentPathDistance + edgeWeight);
    }
}

int main() {
    std::ios_base::sync_with_stdio(false); // Tăng tốc độ nhập xuất
    std::cin.tie(NULL);

    int totalNodes;
    std::cin >> totalNodes;

    // Đọc thông tin các cạnh và xây dựng danh sách kề
    for (int i = 0; i < totalNodes - 1; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        adjacencyList[u].push_back({v, w});
        adjacencyList[v].push_back({u, w}); // Vì là cây vô hướng
    }

    // Lần DFS thứ nhất: Tìm một đầu mút của đường kính
    maxPathLengthFound = 0;
    nodeFarthestFromStart = 1; // Bắt đầu từ nút 1 (hoặc bất kỳ nút nào)
    findFarthestNodeDFS(1, 0, 0); // 0 là nút cha giả

    int diameterEndpoint1 = nodeFarthestFromStart;

    // Lần DFS thứ hai: Tìm đường kính từ đầu mút đã tìm được
    maxPathLengthFound = 0; // Đặt lại để tìm đường kính thực sự
    findFarthestNodeDFS(diameterEndpoint1, 0, 0); // Bắt đầu từ diameterEndpoint1

    std::cout << maxPathLengthFound << std::endl;

    return 0;
}

Các Tính Chất Quan Trọng Của Đường Kính Cây

• Nút xa nhất từ bất kỳ nút nào trong cây luôn là một trong các điểm cuối của một đường kính.
• Nếu một cây có nhiều hơn một đường kính, tất cả các đường kính này sẽ có điểm giữa chung hoặc một cạnh chung. Điểm hoặc cạnh này chứa "tâm" của cây.

Trọng Tâm Của Cây

Trọng tâm của một cây là một nút mà khi ta loại bỏ nó, kích thước của thành phần cây con lớn nhất còn lại (hoặc thành phần chứa nút cha) sẽ là nhỏ nhất.

Định Nghĩa và Tính Chất

Một nút C được xem là trọng tâm nếu khi lấy C làm gốc, kích thước của cây con lớn nhất trong số các cây con của C và thành phần chứa nút cha của C (phần còn lại của cây) được tối thiểu hóa.

• Mục tiêu là tìm một nút mà việc loại bỏ nó sẽ chia cây thành các thành phần có kích thước càng cân bằng càng tốt.
• Tổng khoảng cách từ trọng tâm đến tất cả các nút khác trong cây là nhỏ nhất.
• Một cây có thể có một hoặc hai trọng tâm. Nếu có hai trọng tâm, chúng luôn kề nhau.
• Nếu hai cây được nối với nhau bằng một cạnh, trọng tâm của cây mới sẽ nằm trên đường đi nối giữa trọng tâm của hai cây ban đầu.
• Khi một nút được thêm hoặc bớt khỏi cây, vị trí của trọng tâm chỉ dịch chuyển tối đa một cạnh.

Phương Pháp Tìm Trọng Tâm

Để tìm trọng tâm của cây, chúng ta có thể sử dụng một lần duyệt DFS:

1. Thực hiện DFS từ một nút gốc tùy ý (ví dụ, nút 1).
2. Trong quá trình duyệt, tính toán kích thước của mỗi cây con (số lượng nút trong cây con đó) cho từng nút.
3. Đối với mỗi nút u, tính toán kích thước của thành phần lớn nhất còn lại nếu u được chọn làm gốc:
   • Kích thước của cây con lớn nhất trong số các con trực tiếp của u.
   • Kích thước của thành phần chứa nút cha của u (được tính bằng tổng số nút của cây trừ đi kích thước cây con của u).
4. Trọng tâm (hoặc một trong các trọng tâm) là nút mà giá trị lớn nhất trong số các thành phần trên là nhỏ nhất. Chúng ta thường quan tâm đến giá trị nhỏ nhất của kích thước thành phần lớn nhất này.

Ví Dụ Mã Nguồn (C++)

#include <iostream>
#include <vector>
#include <algorithm> // Cho std::max, std::min

const int MAX_NODES_CENTROID = 1010;
std::vector<int> adjCentroid[MAX_NODES_CENTROID]; // Danh sách kề cho cây không trọng số
int totalNodesCentroid;
int subtreeSizes[MAX_NODES_CENTROID];
int minMaxComponentSize; // Lưu giá trị nhỏ nhất của kích thước thành phần lớn nhất

// Hàm DFS để tính toán kích thước cây con và tìm trọng tâm
void findCentroidDFS(int currentNode, int parentNode) {
    subtreeSizes[currentNode] = 1; // Khởi tạo kích thước cây con của nút hiện tại
    int maxChildSubtreeSize = 0;   // Kích thước cây con lớn nhất trong số các con

    // Duyệt qua các nút lân cận (con)
    for (int neighbor : adjCentroid[currentNode]) {
        if (neighbor == parentNode) {
            continue; // Bỏ qua nút cha
        }
        findCentroidDFS(neighbor, currentNode); // Gọi đệ quy cho nút con
        subtreeSizes[currentNode] += subtreeSizes[neighbor]; // Cộng dồn kích thước cây con
        maxChildSubtreeSize = std::max(maxChildSubtreeSize, subtreeSizes[neighbor]); // Cập nhật kích thước cây con lớn nhất
    }

    // Kích thước của thành phần chứa nút cha (phần cây phía trên nút hiện tại)
    int parentComponentSize = totalNodesCentroid - subtreeSizes[currentNode];
    
    // Kích thước thành phần lớn nhất nếu currentNode là trọng tâm
    int currentMaxComponent = std::max(maxChildSubtreeSize, parentComponentSize);
    
    // Cập nhật giá trị nhỏ nhất của kích thước thành phần lớn nhất
    minMaxComponentSize = std::min(minMaxComponentSize, currentMaxComponent);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> totalNodesCentroid;

    // Đọc thông tin các cạnh và xây dựng danh sách kề
    for (int i = 0; i < totalNodesCentroid - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        adjCentroid[u].push_back(v);
        adjCentroid[v].push_back(u);
    }

    // Khởi tạo minMaxComponentSize với giá trị lớn nhất có thể (tổng số nút)
    minMaxComponentSize = totalNodesCentroid;
    findCentroidDFS(1, 0); // Bắt đầu DFS từ nút 1, 0 là nút cha giả

    // In ra giá trị nhỏ nhất của kích thước thành phần lớn nhất
    std::cout << minMaxComponentSize << std::endl;

    return 0;
}