[科普中國]-分支問題

分支問題是2擬陣交問題的特殊情形。分支問題的重要性在于它與若干NP完全問題有密切的關(guān)系。

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

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

1、不含（無向）圈；

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

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

分支問題的重要性在于它與若干NP完全問題有密切的關(guān)系。1

2擬陣交問題2擬陣交問題是一類組合優(yōu)化問題。它是建立在兩個擬陣交集系統(tǒng)上的優(yōu)化問題。

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

本詞條內(nèi)容貢獻者為:

李嘉騫 - 博士 - 同濟大學(xué)