主題
Search

擬陣


粗略地說,擬陣是一個有限集合,以及來自線性代數概念的推廣,該推廣滿足該概念的一組自然屬性。例如,有限集合可以是矩陣的行,而推廣的概念可以是矩陣的任何行子集的線性相關性和獨立性。

形式上,擬陣由一個有限集合 M 的元素以及一個族 C={C_1,C_2,...} 的非空子集(稱為迴路)組成,這些子集滿足以下公理:

1. 迴路的任何真子集都不是迴路,

2. 如果 x in C_1 intersection C_2C_1!=C_2,則 C_1 union C_2-{x} 包含一個迴路。

(Harary 1994,第 40 頁)。

一個等價的定義將擬陣視為一個有限集合 M 的元素以及一個 M 的子集族(稱為獨立集),使得:

1. 空集是獨立的,

2. 獨立集的每個子集都是獨立的,

3. 對於 M 的每個子集 A,包含在 A 中的所有最大獨立集都具有相同數量的元素。

(Harary 1994,第 40-41 頁)。

具有 n=0、1、... 個點的簡單擬陣(或組合幾何)的數量分別為 1、1、2、4、9、26、101、950、... (OEIS A002773),以及 n=0、1、... 個點上的擬陣的數量分別為 1、2、4、8、17、38、98、306、1724、... (OEIS A055545;Oxley 1993,第 473 頁)。(Oxley 1993,第 42 頁給出的 n=5 的值不正確。)


參見

組合幾何類圖定向擬陣

使用 探索

參考文獻

Björner, A.; Las Vergnas, M.; Sturmfels, B.; White, N.; 和 Ziegler, G. 定向擬陣,第 2 版。 英國劍橋:劍橋大學出版社,1999 年。Blackburn, J. E.; Crapo, H. H.; 和 Higgs, D. A. “組合幾何目錄。” Math. Comput. 27, 155-166, 1973.Crapo, H. H. 和 Rota, G.-C. “關於組合理論的基礎。二、組合幾何。” 馬薩諸塞州劍橋:麻省理工學院出版社,109-133, 1970.Harary, F. “擬陣。” 圖論。 馬薩諸塞州雷丁:艾迪生-韋斯利出版社,第 40-41 頁,1994 年。Minty, G. “關於有向線性圖、電路網路和網路程式設計理論的公理基礎。” J. Math. Mech. 15, 485-520, 1966.Oxley, J. G. 擬陣理論。 英國牛津:牛津大學出版社,1993 年。Papadimitriou, C. H. 和 Steiglitz, K. 組合最佳化:演算法和複雜性。 新澤西州恩格爾伍德崖:普倫蒂斯-霍爾出版社,1982 年。Richter-Gebert, J. 和 Ziegler, G. M. 在 離散和計算幾何手冊 (J. E. Goodman 和 J. O'Rourke 編輯)。佛羅里達州博卡拉頓:CRC 出版社,第 111-112 頁,1997 年。Sloane, N. J. A. 序列 A002773/M1197 和 A055545,見“整數序列線上百科全書”。Sloane, N. J. A. 和 Plouffe, S. 圖 M1197,見 整數序列百科全書。 加利福尼亞州聖地亞哥:學術出版社,1995 年。Tutte, W. T. “關於擬陣的講座。” J. Res. Nat. Bur. Stand. Sect. B 69, 1-47, 1965.West, D. B. “擬陣。” §8.2,見 圖論導論,第 2 版。 新澤西州恩格爾伍德崖:普倫蒂斯-霍爾出版社,第 349-378 頁,2000 年。Whitely, W. “擬陣和剛性結構。” 在擬陣應用中,數學及其應用百科全書 (N. White 編輯),第 40 卷。紐約:劍橋大學出版社,第 1-53 頁,1992 年。Whitney, H. “關於線性相關性的抽象性質。” Amer. J. Math. 57, 509-533, 1935.

在 上被引用

擬陣

請按如下方式引用:

Weisstein, Eric W. “擬陣。” 來源: Web 資源。 https://mathworld.tw/Matroid.html

主題分類