主题
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 的值不正确。)


参见

组合几何类图定向拟阵

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 上被引用

拟阵

请按如下方式引用:

Weisstein, Eric W. “拟阵。” 来源: MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Matroid.html

主题分类