Skip to content

Matroids

Introduction

Matroid is an abstract algebraic structure introduced by Hassler Whitney in 1935, aiming to unify and generalize concepts of independence, such as linear independence in linear algebra and acyclicity in graph theory.

Matroids provide a powerful theoretical tool for handling optimization problems related to independence, widely applied in combinatorics, graph theory, algorithm design, and other fields. They play a significant role in providing mathematical theoretical support for optimization methods like greedy algorithms.

Definition

Matroid

A Matroid can be represented as \(M = (E, \mathcal{I})\), where:

  • \(E\) is a finite set, called the Ground Set.

  • \(\mathcal{I}\) is a family of subsets of \(E\), called the Family of Independent Sets, and the sets within it are called Independent Sets. It satisfies the following three properties:

    • Non-emptiness: The empty set is independent, i.e., \(\emptyset \in \mathcal{I}\).

    • Hereditary property: Any subset of an independent set is also independent. If \(I \in \mathcal{I}\), then for any \(I' \subseteq I\), we have \(I' \in \mathcal{I}\).

    • Exchange property: If \(I, J \in \mathcal{I}\) and \(|I| < |J|\), then there exists \(j \in J \setminus I\) such that \(I \cup \{j\} \in \mathcal{I}\).

If a structure of the form \((E, \mathcal{I})\) satisfies the above three properties, it is called a matroid.

Basis

A Basis is a maximal independent set in a matroid, i.e., an independent set to which no element can be added while preserving independence. The collection of all bases is called the Family of Bases, denoted by \(\mathcal{B}\).

Properties:

  1. Equal cardinality: All bases have the same size, called the Rank of the matroid.

  2. Extension property: Any independent set can be extended to a basis by adding elements from a basis.

Circuit

A Circuit is a minimal dependent set in a matroid, i.e., all its proper subsets are independent, but the set itself is not independent. No two circuits are contained within each other.

Rank

The Rank Function \(r: 2^E \rightarrow \mathbb{Z}_{\geq 0}\) maps subsets of the ground set \(E\) to non-negative integers. For any \(S \subseteq E\), \(r(S)\) is defined as the size of the largest independent set contained in \(S\), i.e.,

\[ r(S) = \max \{ |I| \mid I \subseteq S \wedge I \in \mathcal{I} \}. \]

Properties:

  1. Non-negativity: For any \(S \subseteq E\), \(0 \leq r(S) \leq |S|\).

  2. Monotonicity: If \(A \subseteq B \subseteq E\), then \(r(A) \leq r(B)\).

  3. Submodularity: For any \(A, B \subseteq E\), \(r(A \cup B) + r(A \cap B) \leq r(A) + r(B)\).

Typical Examples

1. Uniform Matroid

Definition: Given a ground set \(E\) and a non-negative integer \(k\), the independent set family of the uniform matroid \(U_{k,E}\) consists of all subsets of size at most \(k\), expressed as:

\[ \mathcal{I} = \{ I \subseteq E \mid |I| \leq k \}. \]

  • Bases: All subsets of size \(k\).

  • Circuits: All subsets of size \(k + 1\).

  • Rank: \(r(E) = \min(k, |E|)\), meaning an independent set can have at most \(k\) elements.

2. Graphical Matroid

Definition: Given an undirected graph \(G = (V, E)\), the graphical matroid \(M(G)\) has the edge set \(E\) as its ground set. Its independent set family consists of all edge sets that contain no cycles, i.e., all forests.

  • Bases: Spanning trees of the graph (in the case of a connected graph). A spanning tree is a maximal independent set; no edge can be added without creating a cycle.

  • Circuits: Simple cycles in the graph. Removing any edge from a cycle leaves an independent set.

  • Rank: \(r(E) = |V| - c\), where \(c\) is the number of connected components of the graph. For a connected undirected graph, its rank equals the number of vertices minus one, i.e., \(|V| - 1\).

3. Linear Matroid

Definition: Linear matroids are based on vector spaces. Given a vector space \(V\), the ground set \(E\) is a finite set of vectors in \(V\). Its independent set family consists of all linearly independent subsets of vectors from \(E\).

  • Bases: Maximal linearly independent sets of vectors, whose size equals the dimension of the vector space.

  • Circuits: Minimal linearly dependent sets of vectors; any proper subset is independent, but the set itself is linearly dependent.

  • Rank: The rank of a linear matroid is \(r(E) = \dim(V)\), the dimension of the vector space. The size of an independent set cannot exceed the dimension of the vector space.

4. Partition Matroid

Definition: The ground set \(E\) is partitioned into disjoint subsets \(E_1, E_2, \dots, E_m\), and a non-negative integer \(k_i\) is assigned to each subset \(E_i\). The independent set family of the partition matroid consists of subsets that pick at most \(k_i\) elements from each part, expressed as:

\[ \mathcal{I} = \left\{ I \subseteq E \mid \forall i,\, |I \cap E_i| \leq k_i \right\}. \]

  • Bases: Independent sets satisfying \(|I \cap E_i| = k_i\) are bases of the partition matroid. Each basis picks exactly \(k_i\) elements from each subset.

  • Circuits: Circuits of a partition matroid are minimal dependent sets, i.e., sets containing at least one subset where the element count exceeds \(k_i\).

  • Rank: The rank of a partition matroid is \(r(E) = \sum_{i=1}^m k_i\), meaning the size of the largest independent set equals the sum of the maximum allowed elements from each subset.

5. Colored Matroid

Definition: A colored matroid is a special form of a partition matroid where each element is assigned a color. Given a ground set \(E\) and a color set \(C\), each element \(e \in E\) is associated with a color \(c \in C\). The independent sets of a colored matroid must not only satisfy the usual matroid independence conditions but also adhere to restrictions specified by colors, e.g., at most a certain number of elements of the same color can be in an independent set.

  • Bases: Bases of a colored matroid are maximal independent sets that comply with both color restrictions and independence conditions.

  • Circuits: Circuits are minimal dependent sets containing at least one set of elements that violates independence or color restrictions.

  • Rank: The rank of a colored matroid is the size of the largest independent set under the given color restrictions. It depends on both the matroid structure and the specific color constraints.

Constructions and Operations

Dual

Given a matroid \(M = (E, \mathcal{I})\), its Dual Matroid \(M^* = (E, \mathcal{I}^*)\) is defined as:

\[ \mathcal{I}^* = \{ I^* \subseteq E \mid \exists B \in \mathcal{I}, |B| = r(E), B \subseteq E \setminus I^* \}. \]

Properties:

  • Bases: The bases of the dual matroid \(M^*\) are the complements in \(E\) of the bases of \(M\). In other words, if \(B\) is a basis of \(M\), then \(E \setminus B\) is a basis of \(M^*\).

  • Rank function: The rank function of the dual matroid is \(r^*(S) = |S| - r(E) + r(E \setminus S)\), where \(S\) is a subset of \(E\). This means the rank of the dual matroid can be computed from the size of the ground set, the rank of the original matroid, and the rank after removing \(S\) from the ground set.

  • Self-duality: The dual of the dual matroid is the original matroid, i.e., \((M^*)^* = M\).

Example:

For an undirected graph \(G = (V, E)\), the dual \(M(G)^*\) of the graphical matroid \(M(G)\) is the matroid formed by the cut-sets of the graph. The bases of \(M(G)\) are the spanning trees of the graph, while the bases of its dual \(M(G)^*\) are the complements of these spanning trees. The circuits of \(M(G)^*\) are the minimal cut-sets of the graph, i.e., the minimal sets of edges whose removal disconnects the graph.

For example, consider a simple triangle graph \(G\) with edge set \(E = \{e_1, e_2, e_3\}\). A basis of \(M(G)\) is a set of two edges (e.g., \(\{e_1, e_2\}\)), while a basis of the dual matroid \(M(G)^*\) is a set of one edge (e.g., \(\{e_3\}\)). A circuit of \(M(G)^*\) is a set of two edges (i.e., a minimal cut-set, e.g., \(\{e_2,e_3\}\)), because removing one of its edges would split the graph into two connected components.

Deletion and Contraction

Deletion:

For \(A \subseteq E\), the matroid \(M\) after deleting \(A\) yields a new matroid \(M \setminus A\), whose independent set family \(\mathcal{I}'\) is defined as:

\[ \mathcal{I}' = \{ I \subseteq E \setminus A \mid I \in \mathcal{I} \}. \]

Deletion removes certain elements from the matroid, retaining the independent sets formed by the remaining elements. The original independence structure is preserved, just with elements removed.

Contraction:

For \(A \subseteq E\), the matroid \(M\) after contracting \(A\) yields the matroid \(M / A\), whose independent set family \(\mathcal{I}''\) is defined as:

\[ \mathcal{I}'' = \left\{ I \subseteq E \setminus A \,\bigg|\, \exists B \subseteq A,\, B \in \mathcal{I},\, r(B) = r(A),\, I \cup B \in \mathcal{I} \right\} \]

Contraction can be understood as contracting the elements in set \(A\) and considering independent sets formed by the remaining elements together with a basis of \(A\). The result of contraction depends on a basis of \(A\); the contracted independent sets are essentially those obtained by reducing higher-rank subsets in the original matroid.

Example - Graphical Matroid:

  • Deletion: In a graphical matroid, deletion corresponds to deleting some edges from the graph. After deleting an edge from a graph \(G\), we consider the independent sets formed by the remaining edges, i.e., those edge sets that contain no cycles. For example, deleting one edge from a triangle graph leaves the remaining two edges, which still form a forest.

  • Contraction: Contraction corresponds to contracting an edge into a vertex. For a graphical matroid, contracting an edge merges its two endpoints into a single vertex and removes the edge. After merging vertices, the other edges in the graph can still form independent sets. For example, contracting any edge in a triangle graph merges two vertices into one, and the remaining two edges form a new matroid.

Matroids and Greedy Algorithms

Problem Description:

One application of matroids is solving optimization problems in greedy algorithms. Specifically, given a matroid \(M = (S, \mathcal{I})\), where \(S\) is the ground set and \(\mathcal{I}\) is the family of independent sets. Each element \(x \in S\) is assigned a positive integer weight \(w(x)\). The goal is to find the independent set with the maximum weight, formulated as:

\[ \max_{A \in \mathcal{I}} w(A) = \max_{A \in \mathcal{I}} \sum_{x \in A} w(x) \]

Clearly, a maximum-weight independent set must be a maximal independent set. If an independent set \(A\) is not maximal, then there exists an element \(x\) that can be added to \(A\), and since \(w(x) > 0\), adding it would increase the weight, indicating \(A\) is not maximum-weight.

Steps

The greedy algorithm for finding a maximum-weight independent set proceeds as follows:

  1. Sort elements: Sort the ground set \(S\) in descending order of weight, denoted as sequence \(e_1, e_2, \dots, e_n\).
  2. Initialize: Set independent set \(A = \emptyset\).
  3. Build independent set: Consider each sorted element \(e_i\) in order. If \(A \cup \{ e_i \} \in \mathcal{I}\), then update \(A = A \cup \{ e_i \}\).
  4. Output result: The final set \(A\) is the maximum-weight independent set.

Complexity Analysis:

Let \(n = |S|\) be the size of the ground set, and \(f(n)\) denote the complexity of checking whether a set is independent. The time complexity of the greedy algorithm is:

\[ O(n \log n + n f(n)) \]

where \(O(n \log n)\) is the complexity of sorting, and \(O(n f(n))\) is the complexity of checking independence for each element.

Note
  • In graphical matroids, Union-Find can be used to efficiently detect cycles, making \(f(n)\) nearly constant time.
  • In linear matroids, independence checking typically involves matrix operations, and its complexity depends on the specific implementation.

Correctness Proof:

Let \(M = (S, \mathcal{I})\) be a matroid, and \(A \in \mathcal{I}\) be an independent set that is a subset of some maximum-weight independent set \(T\). Define the set \(P = \{ x \in S \setminus A \mid A \cup \{x\} \in \mathcal{I} \}\), i.e., the set of all elements that, when added to \(A\), keep \(A\) independent.

Let \(y\) be the element in \(P\) with the maximum weight. Then \(A' = A \cup \{ y \}\) is also a subset of some maximum-weight independent set, proven as follows:

Assume \(A' = A \cup \{ y \}\) is not a subset of any maximum-weight independent set. Then there exists a maximum-weight independent set \(T\) such that \(|A'| < |T|\).

Since \(|A'|< |T|\), by the exchange property of matroids, there exists \(x \in T \setminus A'\) such that \(A' \cup \{ x \} \in \mathcal{I}\).

Using the exchange property, repeatedly add such \(x\) to \(A'\) to eventually construct a new independent set \(A''\) such that \(|A''| = |T|\).

Let \(K = A'' \cap T\). Then \(x = T \setminus K\) and \(y = A'' \setminus K\). Since \(y\) is the element with maximum weight in \(P\), we have \(w(x) \leq w(y)\).

Therefore, \(w(A'') = w(K) + w(y) \geq w(K) + w(x) = w(T)\). Now:

  • If \(w(A'') > w(T)\), then \(T\) is not a maximum-weight independent set, contradicting the assumption.
  • If \(w(A'') = w(T)\), then \(A''\) is a maximum-weight independent set, and \(A'\) is its subset, contradicting the assumption that \(A'\) is not a subset of any maximum-weight independent set.

Thus, the assumption is false, meaning \(A' = A \cup \{ y \}\) must be a subset of some maximum-weight independent set. Therefore, by repeatedly applying the greedy strategy, we can eventually find a maximum-weight independent set.

Example

Minimum Spanning Tree:

Given a connected undirected graph \(G = (V, E)\), each edge \(e \in E\) has a weight \(w(e)\). The goal is to find a spanning tree that includes all vertices and has minimum total weight.

Matroid Construction:

To formulate the Minimum Spanning Tree problem as a matroid problem, we can construct the graphical matroid \(M(G)\):

  • Ground set: \(S = E\), i.e., all edges in the graph.
  • Independent set family: \(\mathcal{I}\) consists of all edge sets that contain no cycles (i.e., all forests).

Greedy Algorithm:

Within the framework of graphical matroids, Kruskal's algorithm is a classic greedy algorithm based on matroid theory, used to construct a minimum spanning tree. While Prim's algorithm is also an effective greedy algorithm that can find a minimum spanning tree, it does not strictly rely on the matroid greedy framework. Therefore, in discussions of matroid theory, Kruskal's algorithm is the primary greedy algorithm example.

  • Kruskal's algorithm:

    1. Sort edges: Sort all edges in ascending order of weight.
    2. Iterative selection: Consider edges in order of increasing weight. If adding an edge does not create a cycle, add it to the spanning tree.
    3. Termination condition: Repeat until the spanning tree contains \(|V| - 1\) edges.

  • Prim's algorithm:

    • Principle: Prim's algorithm starts from an initial vertex and gradually expands the spanning tree, each time selecting the minimum-weight edge connecting the tree to vertices outside it.
    • Although Prim's algorithm is also greedy, its selection strategy differs from other greedy algorithms based on the matroid exchange property. Therefore, in the strict sense of matroid theory, Prim's algorithm is not considered a typical matroid greedy algorithm.

Matroid Intersection

For two matroids \(M_1 = (S, \mathcal{I}_1)\) and \(M_2 = (S, \mathcal{I}_2)\) defined on the same ground set \(S\), if \(\mathcal{I} = \mathcal{I}_1 \cap \mathcal{I}_2\) satisfies the three properties defining a matroid independent set family, then \(M = (S, \mathcal{I})\) is called the intersection of \(M_1\) and \(M_2\).

Note: The intersection of two arbitrary matroids is not necessarily a matroid. It constitutes a matroid only when the intersection of their independent set families satisfies the three defining properties of a matroid independent set family.

Problem Description

  1. Maximum independent set: Find the largest independent set (i.e., the independent set with maximum cardinality) in \(\mathcal{I}_1 \cap \mathcal{I}_2\).
  2. Weighted maximum independent set: Given a weight function \(w: S \to \mathbb{R}\), find the independent set in \(\mathcal{I}_1 \cap \mathcal{I}_2\) with the maximum sum of weights.

Algorithm

Unweighted version:

  1. Initialization: Choose an initial independent set \(I \in \mathcal{I}_1 \cap \mathcal{I}_2\), typically \(I = \emptyset\).
  2. Iteration:
    • Build exchange graph: Construct the exchange graph \(D_{M_1, M_2}(I)\) based on the current independent set \(I\).
    • Path selection: In the exchange graph, find an augmenting path \(P\) from source \(s\) to sink \(t\).
    • Augmentation: Traverse each node along path \(P\) from \(s\) to \(t\):
      • If the node belongs to the left part (i.e., elements in \(I\)), remove that element from \(I\).
      • If the node belongs to the right part (i.e., elements in \(S \setminus I\)), add that element to \(I\).
    • Repeat: After updating the independent set \(I\), repeat the above steps until no new augmenting path can be found.
  3. Result: The final independent set \(I\) is a maximum independent set in the matroid intersection \(M = M_1 \cap M_2\).

Weighted version:

To find the independent set with maximum weight sum, the algorithm needs to optimize the selection of augmenting paths.

  1. Weight assignment: For each element \(e \in S\), define its weight \(w'(e)\) in the exchange graph:
    • Left part (elements in \(I\)): \(w'(e) = -w(e)\).
    • Right part (elements in \(S \setminus I\)): \(w'(e) = w(e)\).
  2. Path selection: In the exchange graph \(D_{M_1, M_2}(I)\), find an augmenting path \(P\) from source \(s\) to sink \(t\) such that performing the augmentation operation along this path maximizes the increase in the total weight of the independent set \(I\).
    • Augmentation condition: The sum of weights of elements added along path \(P\) is greater than the sum of weights of elements removed, i.e., \(\sum_{y \in \text{added elements}} w(y) > \sum_{x \in \text{removed elements}} w(x)\).
  3. Augmentation operation: Traverse each node along path \(P\) from \(s\) to \(t\):
    • If the node belongs to the left part (i.e., elements in \(I\)), remove that element from \(I\).
    • If the node belongs to the right part (i.e., elements in \(S \setminus I\)), add that element to \(I\).
  4. Iteration: Repeat steps 1 to 3, continuously building the exchange graph and finding augmenting paths, gradually optimizing the total weight of the independent set \(I\).
  5. Termination condition: The algorithm terminates when no path satisfying the augmentation condition can be found in the exchange graph.
  6. Result: The final independent set \(I\) is a maximum-weight independent set in the matroid intersection \(M = M_1 \cap M_2\).

Complexity:

  • Number of augmentations: Let the maximum ranks of the two matroids be \(r_1\) and \(r_2\). The maximum number of augmentations is \(\min(r_1, r_2)\).

  • Complexity per augmentation:

    • Building the exchange graph has complexity \(O(n^2)\), where \(n = |S|\).
    • Finding an augmenting path depends on the path search strategy, typically \(O(n^2)\), e.g., using breadth-first search.

  • Total time complexity: The overall time complexity is \(O(r \cdot n^2)\), where \(r = \min(r_1, r_2)\).

Example Problems

Minimum Spanning Tree:

Given an undirected graph \(G = (V, E)\), each edge \(e \in E\) has a weight \(w(e)\). Find a spanning tree that includes all vertices and has minimum total weight.

Solution Approach

Use Kruskal's algorithm: sort all edges in ascending order of weight, then iteratively select edges. If adding an edge does not create a cycle, add it to the spanning tree. The resulting spanning tree is the minimum spanning tree.

Colorful Graph:

Given an undirected graph \(G = (V, E)\) with multiple colors assigned to edges, each edge has a color attribute. Find a maximum edge set such that:

  1. The selected edges form no cycles.
  2. The number of edges of each color does not exceed \(k\) (where \(k\) is a given positive integer).
Solution Approach
  1. Matroid modeling:
    • Graphical matroid (\(M_1\)): Defined as all edge sets that form no cycles, i.e., the independent set family \(\mathcal{I}_1\) contains all edge sets that do not contain cycles.
    • Color matroid (\(M_2\)): Defined as all edge sets where the number of edges of each color is at most \(k\), i.e., the independent set family \(\mathcal{I}_2\) contains all edge sets satisfying that the count of each color is \(\leq k\).
  2. Solve matroid intersection: By solving \(M = M_1 \cap M_2\), find the maximum edge set that both forms no cycles and satisfies the color count constraints.

Constrained Resource Allocation Problem:

In a resource allocation problem, there is a set of resources \(R = \{r_1, r_2, \dots, r_n\}\) and a set of projects \(P = \{p_1, p_2, \dots, p_m\}\). Each project \(p_i\) requires allocation of a certain amount of resources, and the total allocation of each resource cannot exceed its supply.

Goal: Find a resource allocation scheme that satisfies all project demands without exceeding resource supplies.

Solution Approach
  1. Matroid modeling:
    • Demand matroid (\(M_1\)): Defined as allocation schemes that satisfy the resource demands of all projects, i.e., the independent set family \(\mathcal{I}_1\) contains all resource allocation sets that meet project demands.
    • Supply matroid (\(M_2\)): Defined as allocation schemes that do not exceed the supply of each resource, i.e., the independent set family \(\mathcal{I}_2\) contains all resource allocation sets that satisfy resource supply limits.
  2. Solve matroid intersection: By solving \(M = M_1 \cap M_2\), find a resource allocation scheme that satisfies all project demands and does not exceed resource supplies.

References and Notes

  1. Wikipedia - Matroid
  2. Baidu Baike - Matroid
  3. Luogu - Matroids and Optimization Problems
  4. Luogu - From Matroid Basics to Shannon Switching Game
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用