[科普中国]-分支问题

分支问题是2拟阵交问题的特殊情形。分支问题的重要性在于它与若干NP完全问题有密切的关系。

简介分支问题是2拟阵交问题的特殊情形。

分支有向图G=(V,A)，B为A的子集，若满足：

1、不含（无向）圈；

2、G的每个节点均是B中最多一条弧的终点；则称B为分支。

定义分支问题为max{C(B)|B为支撑分支}，其中

分支问题的重要性在于它与若干NP完全问题有密切的关系。1

2拟阵交问题2拟阵交问题是一类组合优化问题。它是建立在两个拟阵交集系统上的优化问题。

NP完全问题NP完全问题，又叫NP-C问题，是世界七大数学难题之一。 NP的英文全称是Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题。简单的写法是 NP=P？，问题就在这个问号上，到底是NP等于P，还是NP不等于P。

本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学