單模擬陣

單模擬陣亦稱正則擬陣，是一類特殊的可表示的擬陣，指在任何域上均可表示的擬陣。擬陣M(E)為單模擬陣，若且唯若M(E)有全單模的表示矩陣。

基本介紹

• 中文名：單模擬陣
• 外文名：unimodular matroid
• 適用範圍：數理科學

簡介

單模擬陣亦稱正則擬陣，是一類特殊的可表示的擬陣，指在任何域上均可表示的擬陣。

單模擬陣亦可等價地由其表示矩陣定義。設m×n矩陣A為擬陣M(E)在域F上的表示矩陣，m<n，且A的元素均取整數值，若對於任意k(1≤k≤m)，A的每個k×k子陣的行列式等於0或±1，則稱矩陣A為全單模的。

判定

擬陣M(E)為單模擬陣，若且唯若M(E)有全單模的表示矩陣。

此外，單模擬陣亦可用其子結構刻畫：M(E)為單模擬陣，若且唯若它沒有與均勻擬陣U_2,4、法諾擬陣F₇及其對偶同構的子擬陣。

套用

係數矩陣為全單模矩陣的線性規劃關聯許多組合最佳化問題，它們的優越性在於有多項式算法求其最優解。

擬陣

在組合數學中，擬陣是一個對向量空間中線性獨立概念的概括與歸納的數學結構。擬陣有許多等價的定義方式，最常見的定義方式是用獨立集，基，圈，閉集合，閉平面，閉包運算元或秩函式。

擬陣理論廣泛地借用了線性代數和圖理論的術語，因為它是這些領域的重點概念的抽象。擬陣在幾何，拓撲學，組合最佳化，網路理論和編碼理論上都有很多套用。它抽象了很多圖的性質．為組合最佳化問題和設計多項式算法提供了強有力的工具。