分支問題

分支問題是2擬陣交問題的特殊情形。

有向圖G=(V,A)，B為A的子集，若滿足：

1、不含（無向）圈；

2、G的每個節點均是B中最多一條弧的終點；則稱B為分支。

分支問題為max{C(B)|B為支撐分支}，其中

分支問題的重要性在於它與若干NP完全問題有密切的關係。 ^[1] 

2擬陣交問題是一類組合優化問題。它是建立在兩個擬陣交集系統上的優化問題。

NP完全問題，又叫NP-C問題，是世界七大數學難題之一。 NP的英文全稱是Non-deterministic Polynomial的問題，即多項式複雜程度的非確定性問題。簡單的寫法是 NP=P？，問題就在這個問號上，到底是NP等於P，還是NP不等於P。