For faster navigation, this Iframe is preloading the Wikiwand page for 拟阵.

拟阵

拟阵组合数学中的一个结构,是对向量空间线性独立这一概念的概括与归纳。拟阵有许多等价的定义,其中最主要的几个定义分别是基于独立集、基底、环路、闭集、平坦、闭包算子和秩函数。

拟阵理论从线性代数图论中借用了大量术语,主要是因为它是对这些领域中很多重要的核心概念的概括。拟阵理论在几何拓扑学组合优化网络理论编码理论中都有应用。

定义

[编辑]

拟阵有很多等价的定义方式[1]

独立集

[编辑]

就独立集来说, 一个有限的拟阵 是一个二元组 , 其中 是一个 有限集 (称之为 基础集) , 是一个由的子集构成的 集族 (称之为 独立集) 它需要满足下面的条件:[2]

  1. 空集 是独立的, 也就是说, . 换个说法就是, 至少有一个 的子集是独立的, 即:.
  2. 每个独立集的子集是独立的, 即: 对于每个子集 , 如果 . 有时我们称之为 遗传特性.
  3. 如果 的两个独立子集,有更多的元素, 则在中存在一个元素,当其加入 时得到一个比更大独立子集. 有时我们称之为 扩充特性 或者叫 独立集交换特性.

头两个特性定义了一个公认的组合结构,叫做独立系统。

[编辑]

对于有限拟阵 ,若其基础集的子集是一个极大的独立集(即添加任何一个新的元素得到的子集都不是独立集),则将称为一个基底(英文:basis)。拟阵的一种等价定义为二元组,其中 是一个有限集, 是一个由基底构成的的子集族,称为,满足以下条件:[1]

  1. ;(即至少存在一个基底)
  2. 对于中不同的集合以及任一元素,存在元素使得。(该条件被称为交换公理)

可以证明,一个有限拟阵的所有基底的元素个数都相同,这个数被称为拟阵的

环路

[编辑]

对于有限拟阵 ,若其基础集的子集是一个极小的非独立集(即去掉其中任一元素得到的子集都是独立集),则将称为一个环路(英文:circuit)。拟阵的一种等价定义为二元组,其中 是一个有限集, 是一个由环路构成的的子集族,称为的环路集,满足以下条件:[1]

  1. 如果,则
  2. 对于中不同的集合以及元素,存在使得

可以证明,基础集的一个子集是独立集当且仅当它不包含任一环路作为子集。

秩函数

[编辑]

类似线性代数基底的性质,拟阵的基底具有类似的性质:的任意两个基底具有相同的元素个数。这个数字被称为拟阵的秩。

闭包

[编辑]

参考资料

[编辑]
  1. ^ 1.0 1.1 1.2 A standard source for basic definitions and results about matroids is Oxley (1992). An older standard source is Welsh (1976). See Bryzlawski's appendix in White (1986) pp.298–302 for a list of equivalent axiom systems.
  2. ^ Welsh (1976), Section 1.2, "Axiom Systems for a Matroid", pp. 7–9.
{{bottomLinkPreText}} {{bottomLinkText}}
拟阵
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.

X

Get ready for Wikiwand 2.0 🎉! the new version arrives on September 1st! Don't want to wait?