Абстрактная теория зависимости: роль матроидов в дискретной математике

A matroid is a classification of subsets of a certain set, which is a generalization of the idea of ​​independence of elements, analogous to the independence of elements of a linear space, into an arbitrary set.

Axiomatic definition

Matroid - a pair where - a finite set, called a matroid carrier, and - some set of subsets called the family of independent sets, i.e. . The following conditions must be met:

1. 
2. If a and then
3. If a and power A is more power B, then there is such that

The bases of the matroid are the maximal independent sets with respect to inclusion. Subsets not owned are called dependent sets. The minimal inclusion sets of dependent sets are called matroid cycles , this concept is used in the alternative definition of a matroid.

Definition in terms of cycles

Matroid - a pair where - carrier matroid, and - family of non-empty subsets , called the set of matroid cycles for which the following conditions are true: ^[1]

1. No cycle is a subset of another
2. If a then contains a loop

Definition in terms of a proper closure

Let be - partially ordered set. - short circuit in , if a

1. For any x from P :
2. For any x , y from P :
3. For any x from P :

Will consider the case when a partially ordered set is a Boolean algebra. Let be - closure .

1. A closure is correct (the axiom of a correct closure) if
2. for anyone there is such , what
   1. 
   2. 

Couple where - correct circuit to is called a matroid .

Examples

1. Universal Matroid U _nk . The set X has cardinality n; independent sets are subsets of cardinality at most k. The bases are subsets of capacity k.
2. Matroid cycles of the graph. The set X is the set of edges of the graph, the independent sets are the acyclic subsets of these edges, the cycles are the simple cycles of the graph. The bases are the spanning forests of the graph. A matroid is called a graphic if it is the matroid of the cycles of a certain graph. ^[2]
3. Matroid subsets of the set of edges of the graph, such that the removal of the subset leaves the graph connected.
4. Matroid cocycles graph. The set X is a set of edges, cocycles are minimal sets, the removal of which leads to a loss of connectivity of the graph. A matroid is called craphic if it is a cocycle matroid of some graph. ^[2]
5. Matrix Matroid. The family of all linearly independent subsets of any finite set of vectors of an arbitrary non-empty vector space is a matroid.

We define the set E as a set consisting of {1, 2, 3, .., n} - numbers of columns of a certain matrix, and the set I, as a set consisting of subsets of E, such that the vectors determined by them are linearly independent over the field real numbers R. Let us ask ourselves the question - what properties does the constructed set I have?

1. The set I is non-empty. Even if the initial set E was empty - E = ∅, then I will consist of a single element — a set containing an empty one. I = {{∅}}.
2. Any subset of any element of set I will also be an element of this set. This property is understandable - if some set of vectors is linearly independent over a field, then any subset of it will be linearly independent.
3. If A, B ∈ I, moreover, | A | = | B | + 1, then there exists an element x ∈ A - B, such that B ∪ {x} ∈ I.

We will prove that in the considered example the set of linearly independent columns is indeed a matroid. To do this, it suffices to prove the third property from the definition of a matroid. We carry out the proof by contradiction.

Evidence. Let A, B ∈ I and | A | = | B | + 1. Let W be the space of vectors spanned by A ∪ B. It is clear that its dimension will be at least | A |. Suppose that B ∪ {x} will be linearly dependent for all x ∈ A - B (that is, the third property will not hold). Then B forms a basis in the space W. From this it follows that | A | ≤ dim W ≤ | B |. But since, by assumption, A and B consist of linearly independent vectors and | A | > | B |, we obtain a contradiction. Such a set of vectors will be a matroid.

Additional concepts

• The dual of this matroid is called the matroid, the carrier of which coincides with the carrier of the given matroid, and the base is the addition of the bases of the given matroid to the carrier. That is, X ^* = X, and the set of bases of the dual matroid is the set of B ^* such that B ^* = X \ B, where B is the base of the given matroid.
• A cycle in a matroid is the set A⊂X such that A∉I, and for any B⊂A, if B ≠ A, then B∈I
• The rank of a matroid is the power of its bases. The rank of a trivial matroid is zero.

Froid Matroid

Froid Matroid

Matroids with a small number of elements are often depicted as diagrams. Points are elements of the main set, and curves are “stretched” through each three-element chain (3-element circuit). The diagram shows a 3-rank matroid, called Fano's matroid, an example that appeared in a 1935 article in Whitney.

The name comes from the fact that the Fano matroid is a second-order projective plane, known as the Fano plane, whose coordinate field is a two-element field. This means that Fano's matroid is a vector matroid associated with seven non-zero vectors in a three-dimensional vector space above the field of two elements.

It is known from projective geometry that a Froid matroid is not representable by an arbitrary set of vectors in a real or complex vector space (or in any vector space over a field whose characteristics differ from 2).

Theorems

• All base matroid have the same power.
• Matroid is uniquely defined by the carrier and bases.
• A cycle cannot be a subset of another cycle.
• If a and - cycles, then for any contains a loop
• If a - base and then contains exactly one cycle.

Application

• Matroids well describe a class of problems that allow for a “greedy” solution. See the greedy Rado-Edmonds algorithm
• Matroids in combinatorial optimization