【摘要】本文对k-CARD树问题(k-Cardinality Tree Problem)进行研究，该问题是组合优化中一个典型的NP-Hard问题，其可描述为在一个给定的无向图G中寻找一棵含k条边的子树，使得该子树权值之和最小。文章首先研究该问题的数学性质，其中包括可以单个减小问题规模和成批减小问题规模的数学性质，然后提出其上下界子算法，最后根据这些性质和子算法设计了一个可以大幅缩减问题搜索解空间且保证获得全局最优解的降阶回溯算法。文章的末尾通过一个示例阐述该算法的执行过程，并通过数值实验说明算法的可行性与有效性。