请输入您要查询的百科知识：

　

词条 Matroid rank
释义

  1. Properties and axiomatization

  2. Other matroid properties from rank

  3. Ranks of special matroids

  4. See also

  5. References

{{Use American English|date = January 2019}}{{Short description|Maximum size of an independent set of the matroid}}

In the mathematical theory of matroids, the rank of a matroid is the maximum size of an independent set in the matroid. The rank of a subset S of elements of the matroid is, similarly, the maximum size of an independent subset of S, and the rank function of the matroid maps sets of elements to their ranks.

The rank function is one of the fundamental concepts of matroid theory via which matroids may be axiomatized. The rank functions of matroids form an important subclass of the submodular set functions, and the rank functions of the matroids defined from certain other types of mathematical object such as undirected graphs, matrices, and field extensions are important within the study of those objects.

Properties and axiomatization

The rank function of a matroid obeys the following properties.

  • The value of the rank function is always a non-negative integer.
  • For any two subsets and of , . That is, the rank is a submodular function.
  • For any set and element , . From the first of these two inequalities it follows more generally that, if , then . That is, the rank is a monotonic function.

These properties may be used as axioms to characterize the rank function of matroids: every integer-valued submodular function on the subsets of a finite set that obeys the inequalities for all and is the rank function of a matroid.[1][2]

Other matroid properties from rank

The rank function may be used to determine the other important properties of a matroid:

  • A set is independent if and only if its rank equals its cardinality, and dependent if and only if it has greater cardinality than rank.[3]
  • A nonempty set is a circuit if its cardinality equals one plus its rank and every subset formed by removing one element from the set has equal rank.[3]
  • A set is a basis if its rank equals both its cardinality and the rank of the matroid.[3]
  • A set is closed if it is maximal for its rank, in the sense that there does not exist another element that can be added to it while maintaining the same rank.
  • The difference is called the nullity of the subset . It is the minimum number of elements that must be removed from to obtain an independent set.[4]
  • The corank of a subset can refer to at least two different quantities: some authors use it to refer to the rank of in the dual matroid, , while other authors use corank to refer to the difference .

Ranks of special matroids

In graph theory, the circuit rank (or cyclomatic number) of a graph is the corank of the associated graphic matroid; it measures the minimum number of edges that must be removed from the graph to make the remaining edges form a forest.[5] Several authors have studied the parameterized complexity of graph algorithms parameterized by this number.[6][7]

In linear algebra, the rank of a linear matroid defined by linear independence from the columns of a matrix is the rank of the matrix,[8] and it is also the dimension of the vector space spanned by the columns.

In abstract algebra, the rank of a matroid defined from sets of elements in a field extension L/K by algebraic independence is known as the transcendence degree.[9]

See also

  • Rank oracle

References

1. ^{{citation|title=Combinatorial Optimization|first1=M. M.|last1=Shikare|first2=B. N.|last2=Waphare|publisher=Alpha Science Int'l Ltd.|year=2004|isbn=9788173195600|page=155|url=https://books.google.com/books?id=6N-wogwA7TcC&pg=PA155}}.
2. ^{{citation | last = Welsh | first = D. J. A. | authorlink = Dominic Welsh | isbn = 9780486474397 | page = 8 | publisher = Courier Dover Publications | title = Matroid Theory | year = 2010}}.
3. ^1 2 {{harvtxt|Oxley|2006}}, p. 25.
4. ^{{harvtxt|Oxley|2006}}, p. 34.
5. ^{{citation|title=The Theory of Graphs|first=Claude|last=Berge|authorlink=Claude Berge|publisher=Courier Dover Publications|year=2001|isbn=9780486419756|pages=27–30|contribution=Cyclomatic number|url=https://books.google.com/books?id=h5BjnaoKyOwC&pg=PA27}}.
6. ^{{citation | last1 = Coppersmith | first1 = Don | author1-link = Don Coppersmith | last2 = Vishkin | first2 = Uzi | author2-link = Uzi Vishkin | doi = 10.1016/0166-218X(85)90057-5 | zbl=0573.68017 | issue = 1 | journal = Discrete Applied Mathematics | pages = 27–45 | title = Solving NP-hard problems in 'almost trees': Vertex cover | volume = 10 | year = 1985}}.
7. ^{{citation | last1 = Fiala | first1 = Jiří | last2 = Kloks | first2 = Ton | last3 = Kratochvíl | first3 = Jan | doi = 10.1016/S0166-218X(00)00387-5 | zbl=0982.05085 | issue = 1 | journal = Discrete Applied Mathematics | pages = 59–72 | title = Fixed-parameter complexity of λ-labelings | volume = 113 | year = 2001}}.
8. ^{{citation | last = Oxley | first = James G. | authorlink = James Oxley | isbn = 9780199202508 | pages = 81 | publisher = Oxford University Press | series = Oxford Graduate Texts in Mathematics | title = Matroid Theory | volume = 3 | year = 2006}}.
9. ^{{citation | last = Lindström | first = B. | contribution = Matroids, algebraic and non-algebraic | location = Cambridge | mr = 1052666 | pages = 166–174 | publisher = Cambridge Univ. Press | series = London Math. Soc. Lecture Note Ser. | title = Algebraic, extremal and metric combinatorics, 1986 (Montreal, PQ, 1986) | volume = 131 | year = 1988}}.

2 : Dimension|Matroid theory
随便看

　

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

　

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间：2024/9/23 5:30:35