分支問題

分支問題是2擬陣交問題的特殊情形。分支問題的重要性在於它與若干NP完全問題有密切的關係。

基本介紹

• 中文名：分支問題
• 外文名：branching problem
• 適用範圍：數理科學

簡介

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

分支

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

1、不含（無向）圈；

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

定義

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

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

2擬陣交問題

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

NP完全問題

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