#1
|
|||
|
|||
Matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite matroid is equivalent to a geometric lattice. wiki 14 ธันวาคม 2020 07:49 : ข้อความนี้ถูกแก้ไขแล้ว 2 ครั้ง, ครั้งล่าสุดโดยคุณ share |
#2
|
|||
|
|||
In mathematics, a uniform matroid is a matroid in which the independent sets are exactly the sets containing at most r elements, for some fixed integer r. An alternative definition is that every permutation of the elements is a symmetry. |
#3
|
|||
|
|||
In mathematics and computer science, a matroid oracle is a subroutine through which an algorithm may access a matroid, an abstract combinatorial structure that can be used to describe the linear dependencies between vectors in a vector space or the spanning trees of a graph, among other applications. |
#4
|
|||
|
|||
Roughly speaking, a matroid is a finite set together with a generalization of a concept from linear algebra that satisfies a natural set of properties for that concept. For example, the finite set could be the rows of a matrix, and the generalizing concept could be linear dependence and independence of any subset of rows of the matrix. https://mathworld.wolfram.com/Matroid.html |
#5
|
|||
|
|||
In combinatorics, a greedoid is a type of set system. It arises from the notion of the matroid, which was originally introduced by Whitney in 1935 to study planar graphs and was later used by Edmonds to characterize a class of optimization problems that can be solved by greedy algorithms. Around 1980, Korte and Lovász introduced the greedoid to further generalize this characterization of greedy algorithms; hence the name greedoid. |
#6
|
|||
|
|||
Greedoid Besides mathematical optimization, greedoids have been connected to graph theory, language theory, order theory, and other areas of mathematics. In general, a greedy algorithm is just an iterative process in which a locally best choice, usually an input of maximum weight, is chosen each round until all available choices have been exhausted. In order to describe a greedoid-based condition in which a greedy algorithm is optimal (i.e., obtains a basis of maximum value), we need some more common terminologies in greedoid theory. Without loss of generality, we consider a greedoid G = (F, E) with E finite. Wikipedia |
|
|