| 释义 |
matroid, n. Math.|ˈmeɪtrɔɪd|
[f. matrix n. + -oid.]
An entity consisting of a non-empty finite set together with a collection of subsets, none of which contains another, and such that if an element of one subset in the collection is replaced by an element of another subset in the collection, the resulting subset is also in the collection.
1935H. Whitney in Amer. Jrnl. Math. LVII. 509 Let C1, C2,.., Cn be the columns of a matrix M . Any subset of these columns is either linearly independent or linearly dependent; the subsets thus fall into two classes. These classes are not arbitrary; for instance, the two following theorems must hold: (a) Any subset of an independent set is independent. (b) If Np and Np+1 are independent sets of p and p + 1 columns respectively, then Np together with some column of Np+1 forms an independent set of p + 1 columns... Let us call a system obeying (a) and (b) a ‘matroid’. 1958Trans. Amer. Math. Soc. LXXXVIII. 144 By a matroid on a finite set M we understand a class M of non-null subsets of M which satisfies the following axioms: [etc.]. 1966Math. Rev. Jan. 16/1 This is strikingly analogous to Tutte's characterization of graphic matroids. 1972R. J. Wilson Introd. Graph Theory i. 7 Matroid theory is merely the study of sets with ‘independence structures’ defined on them, generalizing not only properties of linear independence in vector spaces but also several of the results in graph theory obtained earlier in the book. 1979Q. Jrnl. Math. XXX. 271 (heading) Binary matroid sums. |