[learning notes] matroid

“ Matroids are of vector space ‘ Linearly independent ’ Extension of concept .” —— Zhihu net friend

use $⊊$ Express “ Not included in ”.

one 、 Definition

1. Matroid

Matroid （$\mathrm{M}\mathrm{a}\mathrm{t}\mathrm{r}\mathrm{o}\mathrm{i}\mathrm{d}$）$\mathcal{M}=(\mathbb{U},\mathcal{I})$, among $\mathcal{I}$ yes $\mathbb{U}$ Set family on , Satisfy

• genetic ： about $I\in \mathcal{I},J\subseteq I$ Yes $J\in \mathcal{I}$ .
• Base exchangeability or Expansibility ： about $I,J\in \mathcal{I},|I|<|J|$ Yes $\exists x\in J\setminus I$ bring $I\cup \{z\}\in \mathcal{I}$ .

It may be stipulated that $|\mathcal{I}|\ne 0$, therefore $\varnothing \in \mathcal{I}$ .

about $I\in \mathcal{I}$, call $I$ by Independent set , namely $I$ It's independent . Otherwise, it is called $I$ Not independent .

2. Base and ring

The base （$\mathrm{b}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}$） Is a maximal independent set , Ring （$\mathrm{c}\mathrm{i}\mathrm{r}\mathrm{c}\mathrm{u}\mathrm{i}\mathrm{t}$） Is a minimal dependent set .

Lemma 1.  All bases in the matrix have the same size .

Corollary 1.  For different rings $X,Y$, If exist $e\in X\cap Y$, be $X+Y-\{e\}$ Is not independent .

Proof.  There is obviously $f\in X\setminus Y$, set up $Z$ by $X\cup Y$ Contained in the $X\setminus \{f\}$ The largest independent set of , because $Y⊊Z$ have to $|Z|<|X+Y-\{f\}|=|X+Y-\{e\}|$, because $Z$ It's the biggest , So the original proposition is proved .$■$

Corollary 2.  about $I\in \mathcal{I}$, if $I\cup \{e\}\notin \mathcal{I}$ be $I\cup \{e\}$ There is a unique ring in .

Proof.  If there are two rings $C_1,C_2$, obviously $e\in C_1\cap C_2$, from $\text{corollary 1}$ know $C_1+C_2-\{e\}$ Not independent , And $I$ It is the contradiction of independent sets .$■$

3. Rank function

about $S\subseteq \mathbb{U}$, Definition Rank （ function ）$r(S)$ by $S$ The size of the maximal independent set in .

• Boundedness ：$0⩽r(S)⩽|S|$ .
• monotonicity ：$\forall A\subseteq B$ Yes $r(A)⩽r(B)$ .
• Submodularity （$\text{submodular}$, Also called submodule ）：$r(A\cup B)+r(A\cap B)⩽r(A)+r(B)$ .

Proof.  prove $r(A\cup \{x\})-r(A)⩽r(B\cup \{x\})-r(B)$ among $B\subseteq A$ It's ordinary . And then from $*A,A\cap B*$ Start , take $B\setminus A$ Join... One by one $A$ Then we get $*A\cup B,A\cap B*$, Join in $A\cap B$ Then we get $*A,B*$, Already joined $S$ when , The former is gathering $A+S$ Internal increase , The latter in $(A\cap B)+S$ Internal increase , Bigger .$■$

4. Define by rank

“ We transform the combinatorial problem of matroids into algebraic problems on rank functions , The properties of matroids are obtained by studying the properties of rank functions .”

According to the rank function satisfying the above three properties $r:2^S\mapsto {\mathbb{N}}^{+}$, We can redefine matroids $\mathcal{M}=(\mathbb{U},\mathcal{I})$, among $\mathcal{I}=\{I:r(I)=|I|\}$ .

Proof.  genetic ： if $r(B)=|B|,A\subseteq B$, from Submodularity know $r(B)⩽r(A)+r(B\setminus A)$, from Boundedness know $r(A)=|A|$ .

Exchangeability ： Reduction to absurdity , set up $B=\{b_1,b_2,\dots ,b_{|B|}\}$, be $r(A\cup \{b_i\})=|A|$ . Prove by induction $r(A\cup \{b_1,b_2,\dots ,b_n\})=|A|$ . Yes $n>1$, take $X=A\cup \{b_1,b_2,\dots ,b_{n-1}\},Y=A\cup \{b_n\}$, from Submodularity Yes $r(A\cup \{b_1,b_2,\dots ,b_n\})+r(A)⩽r(X)+r(Y)$, from $r(A)=r(X)=r(Y)=|A|⩽r(A\cup \{b_1,b_2,\dots ,b_n\})$ Knowledge induction is established .

However $r(B)=|B|>r(A\cup B)=|A|$ A violation of the monotonicity .$■$

Ii. 、 Linear matroids and linear representations

“ Our linear matroids are the big brother of your graph matroids ！”

Linear matroid （$\text{linear matroid}$） namely $\mathbb{U}$ Is a set of vectors , and $\mathcal{I}=\{I\in 2^{\mathbb{U}}:\dim (\text{span}(I))=|I|\}$ Special matroid of .

The linear table out （$\text{linear representation}$） the $\mathbb{U}$ Each element in the is mapped to a vector , So that the linear matroids of these vectors are obtained $\mathcal{I}$ Is the independent set family of primitive matroids .

Press ： As $\mathrm{O}\mathrm{I}\mathrm{e}\mathrm{r}$ I don't want to study the base field of vector space , Therefore, the relevant content is briefly written

If matroids can be expressed linearly , The problem becomes linear matroid .

1. Uniform matroid

Uniform matroid （$\text{uniform matroid}$） by $\mathcal{I}=\{I:|I|⩽k\}$ .

It can be linearly expressed as $k$ Dimension vector $v_i=(1,{\alpha }_i,{\alpha }_i^2,\dots ,{\alpha }_i^{k-1})$, among $\{{\alpha }_i\}$ It's two different non-zero elements ： exceed $k$ A positive linear correlation , But not more than $k$ Time , The determinant of vandermond matrix is ${\prod }_{i<j}({\alpha }_j-{\alpha }_i)\ne 0$, So linear is irrelevant .

2. Graph matroid

Graph matroid （$\text{graph matroid}$） Defined in an undirected graph $G=(V,E)$ On ,$\mathbb{U}=E$ and $\mathcal{I}$ Is a set family of edge sets that do not form rings .

to $E$ Arbitrary orientation , Opposite side $e=(u,v)$, vector $v_e$ In the $u$ Weishang is $1$, In the $v$ Weishang is $-1$ . It is not difficult to verify its correctness .

“ Graph matroids are regular matroids ; The count of the basis of any regular matroid can be obtained by calculating the determinant of an incidence matrix , The matrix tree theorem is a special case .”

3 、 Optimization problems

1. Most powerful independent set

Given a function $\omega :\mathbb{U}\mapsto \mathbb{R}$, seek ${\max }_{I\in \mathcal{I}}{\sum }_{x\in I}\omega (x)$ . obviously $\omega (x)⩽0$ Can be ignored .

Just put the $\mathbb{U}$ The inner element follows $\omega$ Monotonous sequence , Then linear scanning , Join as soon as you can .

Proof.  Make $X=\{x_1,x_2,\dots ,x_r\}$ Is the real maximum weight independent set , among $\omega (x_i)$ Monotony does not increase , remember $X_n=\{x_1,x_2,\dots ,x_n\}$ . Make $S_n$ To join the second $n$ Independent set obtained after elements , To prove by induction $\omega (S_n)⩾\omega (X_n)$ . Yes $n⩾1$, set up $\{u\}=S_n\setminus S_{n-1}$, according to Expansibility Yes $\exists v\in X_n\setminus S_{n-1}$ bring $S_{n-1}\cup v\in \mathcal{I}$, However, according to the algorithm flow $\omega (u)⩾\omega (v)$, according to $X$ Sort by $\omega (v)⩾\omega (x_n)$, therefore $\omega (S_n)=\omega (S_{n-1}\cup \{u\})⩾\omega (X_{n-1})+\omega (x_n)=\omega (X_n)$ .$■$

notes ： among $\omega (S)$ yes ${\sum }_{x\in S}\omega (x)$ Abbreviation . The following questions may also be abbreviated .

2. Minimum weight basis

Given a function $\omega :\mathbb{U}\mapsto \mathbb{R}$, seek ${\min }_{|I|=r(I)=r(\mathbb{U})}{\sum }_{x\in I}\omega (x)$ .

Process and Most powerful independent set equally , It just can't be removed $\omega (x)⩾0$ Of .

3. Max min weighted ring

unfortunately , The maximum weighted ring is $\omega =1$ The existence of Hamiltonian paths can be determined on the graph matroid of , So it is $\text{NP-hard}$ .

The minimum weighted ring can be reduced to $\text{Even Set}$ On the issue of , and $\text{Even Set}$ yes $\text{NPC}$ problem , Therefore, the minimum weighted ring is also $\text{NP-hard}$ .

boss 、 Matroid operation

1. Dual matroids

${\mathcal{M}}^{\ast }=(\mathbb{U},{\mathcal{I}}^{\ast })$ yes $\mathcal{M}=(\mathbb{U},\mathcal{I})$ Of Dual matroids （$\text{dual matroid}$）, among ${\mathcal{I}}^{\ast }=\{I:\exists B\text{ is basis of }\mathcal{M},B\subseteq \mathbb{U}\setminus I\}$ .

let me put it another way , remember $\mathcal{B}(\mathcal{M})$ by $\mathcal{M}$ All of the $\mathrm{b}\mathrm{a}\mathrm{s}\mathrm{i}\mathrm{s}$ Set family of , be $\mathcal{B}({\mathcal{M}}^{\ast })=\{\mathbb{U}-I:I\in \mathcal{B}(\mathcal{M})\}$ .

Proof.  Direct proof is slightly difficult ; use Define by rank The method is feasible .
$$\begin{array}{rl}{r}^{\ast }(S)& =\max \{|S\setminus B|:B\in \mathcal{B}(\mathcal{M})\}\\ & =|S|-\min \{|S\cap B|:B\in \mathcal{B}(\mathcal{M})\}\\ & =|S|-r(\mathbb{U})+\max \{|B\cap (\mathbb{U}\setminus S)|:B\in \mathcal{B}(\mathcal{M})\}\\ & =|S|-r(\mathbb{U})+r(\mathbb{U}\setminus S)\end{array}$$

Boundedness 、 Monotonicity is obvious . Just verify the Submodularity . It is not difficult to find that at this time $|S|-r(\mathbb{U})$ Can eliminate , In fact, it is equivalent to “ The submodular function is still submodular after taking the complement ”. And this is $\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{v}\mathrm{i}\mathrm{a}\mathrm{l}$ Of .$■$

2. Delete and shrink

about $\mathcal{M}=(\mathbb{U},\mathcal{I})$ and $S\subseteq \mathbb{U}$, Definition $\mathcal{M}$ Delete $S$ The matroid of is $(\mathbb{U}\setminus S,{\mathcal{I}}^{\prime })$ among ${\mathcal{I}}^{\prime }=\{I:I\in \mathcal{I},I\subseteq \mathbb{U}\setminus S\}$, Write it down as $\mathcal{M}\setminus S$ . Definition $\mathcal{M}$ shrinkage $S$ The matroid of is $({\mathcal{M}}^{\ast }\setminus S{)}^{\ast }$, Write it down as $\mathcal{M}/S$ .¹

The former no longer considers these elements . The latter is equivalent to $S$ The base within must be selected —— stay ${\mathcal{M}}^{\ast }$ Removing the $S$, That is, we have to choose .

Of course, it can also be from $r$ From the perspective of function , Yes $r_{\mathcal{M}/S}(Z)=r_{\mathcal{M}}(Z\cup S)-r_{\mathcal{M}}(S)$ .

These operations are closed to matroids , This can be done by $r$ Function proof . Here I choose to believe the paper .

3. Minima

$\mathcal{M}$ after $\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$ and $\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$ Any matroid obtained ${\mathcal{M}}^{\prime }$ yes $\mathcal{M}$ Of Minima .

“ Say... Loosely , The minimal element of the matroid can be seen as a local feature of the original matroid .”

4. Matroid and

For a given $k$ Matroids ${\mathcal{M}}_i=({\mathbb{U}}_i,{\mathcal{I}}_i)(1⩽i⩽k)$, Define this $k$ individual Union of matroids by $\mathcal{M}=(\mathbb{U},\mathcal{I})$, among $\mathbb{U}={\bigcup }_{i=1}^k{\mathbb{U}}_i,\mathcal{I}=\{{\bigcup }_{j=1}^k{I}_j:\forall j,I_j\in {\mathcal{I}}_j\}$ .

Its heredity and expansibility are obvious , That is, the operation is closed .

This is a pit , Remember to fill in .🥺

For the time being, skip the change law of its rank function , And independent set decision method . Please remind me to make it up later .

wu 、 Matroid intersection

Hungarian algorithm is the origin of everything ！—— Bipartite graph matching is the intersection of matroids , Again matroid and .

because Matroid intersection It is not closed on matroids , So it is not listed in Matroid operation among .

$l$- Matroid intersection （$l\text{-matroid intersection}$）： Given ${\mathcal{M}}_i=(\mathbb{U},{\mathcal{I}}_i)(1⩽i⩽l)$, seek $\max \{I:\forall j\in [1,l],I\in {\mathcal{I}}_j\}$ .

Theorem 1. $3$- The intersection problem of matroids is $\text{NPC}$ problem .

Proof.  The Hamiltonian path problem on a bipartite graph is $\text{NPC}$ Of . On two points , Define matroids as “ Edge sets do not share vertices of this part ”, Then intersect with the graph matroid , We can find the Hamilton path on the bipartite graph , therefore $3$- The intersection problem of matroids is $\text{NPC}$ Of .$■$

So we only learn the following $P$ Of $2$- Just cross the matroid ！

Theorem 2.（ Max min theorem ） $\max \{|I|:I\in {\mathcal{I}}_1\cap {\mathcal{I}}_2\}={\min }_{S\subseteq \mathbb{U}}\{r_1(S)+r_2(\mathbb{U}\setminus S)\}$ .

The simple side , namely $\text{LHS}⩽\text{RHS}$ It's obvious . The proof of equivalence is the constructive algorithm .

1. Strong base exchange theorem

Definition Closure （$\text{closure}$） operator $\text{clos}(A)=\{x\in \mathbb{U}:r(A\cup \{x\})=r(A)\}$ .

Lemma 2.  if $A\subseteq S$ be $\text{clos}(A)\subseteq \text{clos}(S)$ .

Proof. $x\in \text{clos}(A)$ Equivalent to $A$ Some base of $B$ Satisfy $B\cup \{x\}\notin \mathcal{I}$, and $S$ Existential basis $B^{\prime }\supseteq B$, therefore $x\in \text{clos}(S)$ Set up immediately .$■$

Lemma 3.  if $x\in \text{clos}(A)$ be $\text{clos}(\text{clos}(A))=\text{clos}(A)=\text{clos}(A\cup \{x\})$ .

Theorem 3.（ Strong base exchange theorem ）  about $\mathcal{M}$ Two different bases of $A,B$, about $\forall x\in A\setminus B$ All exist $y\in B\setminus A$ bring $A-\{x\}+\{y\}$ and $B-\{y\}+\{x\}$ Are the basis of matroids .

Proof.  from $\text{corollary 2}$ have to $B+\{x\}$ Contains a unique ring $C\supseteq \{x\}$ . obviously $x\in \text{clos}(C-\{x\})$, from $\text{lemma 2,3}$ Yes $\text{clos}((A\cup C)\setminus \{x\})=\text{clos}(A\cup C)=\mathbb{U}$, Therefore exist $\mathcal{M}$ Base $A^{\prime }\subseteq (A\cup C)\setminus \{x\}$ . from Exchangeability , There is $y\in A^{\prime }\setminus (A-\{x\})$ bring $A-\{x\}+\{y\}$ yes $\mathcal{M}$ Base .

be aware $A^{\prime }\setminus (A-\{x\})\subseteq ((A\cup C)\setminus \{x\})\setminus (A-\{x\})\subseteq C\setminus \{x\}$, therefore $B+\{x\}-\{y\}$ hold $B+\{x\}$ The only ring in $C$ Tear it down , therefore $B-\{y\}+\{x\}$ It's also the foundation .$■$

2. Exchange diagram

about $\mathcal{M}=(\mathbb{U},\mathcal{I})$ and $I\in \mathcal{I}$, Definition Exchange diagram $D_{\mathcal{M}}(I)$ by $\mathfrak{X}=I,\mathfrak{Y}=\mathbb{U}\setminus I$ The bipartite graph of , among $x\in \mathfrak{X}$ and $y\in \mathfrak{Y}$ There are edges between them if and only if $I-\{x\}+\{y\}\in \mathcal{I}$ establish .

Lemma 4.  if $I,J\in \mathcal{I}$, And $|I|=|J|$, be $D_{\mathcal{M}}(I)$ in $I\setminus J$ and $J\setminus I$ A perfect match for .

Proof.  Let the size of independent sets not exceed $|I|$, be $I,J$ There are two bases . according to Strong base exchange theorem ,$\exists x\in I\setminus J,y\in J\setminus I$ bring $I-\{x\}+\{y\}$ It's the base . therefore $*x,y*$ Can match , Then a recursive $J^{\prime }=J-\{y\}+\{x\}$ that will do .$■$

Theorem 4.  if $I\in \mathcal{I},|I|=|J|$ And $D_{\mathcal{M}}(I)$ There is only one in the world $I\setminus J$ and $J\setminus I$ A perfect match for , be $J\in \mathcal{I}$ .

Proof.  Make $P$ Is the only match , take $P$ The edge orientation in is $\mathbb{U}\setminus I$ To $I$, The rest is the opposite . Matching uniquely indicates that there is no directed ring , Renumber with topological order （ Points with small numbers point to points with large numbers ）. set up $P=\{*y_i,x_i*\}$, among $y_i\in J\setminus I$ . Rearrangement makes $x_i\to y_j(i<j)$ There is no edge .

hypothesis $J$ Not independent , Take ring $C\subseteq J$ With the smallest $i$ bring $y_i\in C$, In this way $i$ There is obviously . here $\forall y\in C\setminus \{y_i\}$, because $y$ Actual position ratio of $y_i$ Bigger , therefore $x_i\to y$ There is no edge , namely $I-\{x_i\}+y\notin \mathcal{I}$, namely $C\setminus \{y_i\}\subseteq \text{clos}(I\setminus \{x_i\})$ . At this time there is $y_i\in \text{clos}(C\setminus \{y_i\})\subseteq \text{clos}(I\setminus \{x_i\})$, This is related to $*x_i,y_i*$ It is the edge contradiction in the exchange graph .$■$

3. Matroid intersection algorithm

Definition Exchange diagram $D_{{\mathcal{M}}_1,{\mathcal{M}}_2}(I)$ by $\mathfrak{X}=I,\mathfrak{Y}=\mathbb{U}\setminus I$ Directed bipartite graph of , among $x\in \mathfrak{X}$ and $y\in \mathfrak{Y}$ There are $*x,y*$ Side if and only if $I-\{x\}+\{y\}\in {\mathcal{I}}_1$ establish , Yes $*y,x*$ Side if and only if $I-\{x\}+\{y\}\in {\mathcal{I}}_2$ .

The initial order $I=\varnothing$ . Every order $X_i=\{x\notin I:I\cup \{x\}\in {\mathcal{I}}_i\}(i=1,2)$, And then in $D_{{\mathcal{M}}_1,{\mathcal{M}}_2}(I)$ Find $X_1$ To $X_2$ One of the most short circuit $P$, Then make $I=I\oplus P$, here $\oplus$ Indicates the symmetry difference . Until the path cannot be found . At this point, we get the biggest $|I|$, as well as Max min theorem Medium $S=\{z:z\text{ can reach }{X}_2\}$ .

3.1. independence

Make the shortest circuit $P=\{y_0,x_1,y_1,x_2,y_2,\dots ,x_t,y_t\}$, Make $J=\{y_1,y_2,\dots ,y_t\}\cup (I\setminus \{x_1,x_2,\dots ,x_t\})$ . You can get $|I|=|J|$, And $I\setminus J$ and $J\setminus I$ stay $D_{{\mathcal{M}}_1}(I)$ There is a perfect match in （ Keep only $\mathfrak{X}\to Y$ On the graph of side ; Because it's the shortest circuit ）.

from $\text{theorem 4}$ Immediate $J\in {\mathcal{I}}_1$ . Again because $P$ The shortest known $y_i\notin X_1(1⩽i⩽t)$ namely $I\cup \{y_i\}\notin {\mathcal{I}}_1$ namely $r_1(I\cup J)=r_1(I)$ . because $I\cup \{y_0\}\in {\mathcal{I}}_1$ so $J\cup \{y_0\}\in {\mathcal{I}}_1$, and $J\cup \{y_0\}=I\oplus P$ .

Empathy , Make $J=I\oplus P\oplus \{y_t\}$ be $J\in {\mathcal{I}}_2$, from $r_2(I\cup J)=r_2(I)$ have to $J\cup \{y_t\}\in {\mathcal{I}}_2$ .$■$

3.2. The biggest and the smallest

First prove that $r_1(S)⩽|I\cap S|$ . Reduction to absurdity . set up $r_1(S)>|I\cap S|$, By definition, that is $\exists x\in S\setminus I$ bring $(I\cap S)\cup \{x\}\in {\mathcal{I}}_1$ . because $x\in S$ namely $x$ It can reach $X_2$, There must be $x\notin X_1$ namely $I\cup \{x\}\notin {\mathcal{I}}_1$ .

from independence know $I\cup \{x\}$ There is a unique ring $C\supseteq \{x\}$ . from $(I\cap S)\cup \{x\}\in {\mathcal{I}}_1$ know $C⊊(I\cap S)$ . therefore $\exists y\in C\setminus (I\cap S)$ bring $I-\{y\}+\{x\}\in {\mathcal{I}}_1$ .

The above formula explains $y\to x$ Edge existence , therefore $y\in S$, And $y\in C\setminus (I\cap S)$ contradiction （ Be careful $C\subseteq I$ Oh ）.$■$

3.3. Complexity

The complexity of finding Zengguang road is $\mathcal{O}(r^{2}n)$ among $r=\min \{r_1(\mathbb{U}),r_2(\mathbb{U})\}$ .

We have some better Without application value upper bound ： The sum of the augmented path length is $\mathcal{O}(|I|\log |I|)$ Of , among $I$ Is the largest public independent set [3];$n$ spot $m$ The matroid intersection of graph matroids of edges can be completed within the following complexity [4]：

• $\mathcal{O}(n^{1/2}m)$ among $m=\Omega (n^{3/2}\log n)$ .
• $\mathcal{O}(n{m}^{2/3}{\log }^{1/3}n)$ among $m=\Omega (n\log n)$ And $m=\mathcal{O}(n^{3/2}\log n)$ .
• $\mathcal{O}(n^{4/3}{m}^{1/3}{\log }^{2/3}n)$ among $m=\mathcal{O}(n\log n)$ .

4. Weighted matroid intersection

This section $\mathsf{O}\mathsf{n}\mathsf{e}\mathsf{I}\mathsf{n}\mathsf{D}\mathsf{a}\mathsf{r}\mathsf{k}$ Do not understand , If someone understands, can you talk about it 🥺

Be similar to Optimization problems ： Given $\omega :\mathbb{U}\mapsto \mathbb{R}$ seek $\max \{{\sum }_{x\in I}\omega (x):I\in {\mathcal{I}}_1\cap {\mathcal{I}}_2\}$ . Press ： be suspected to be ${\mathbb{R}}^{+}$ .

Use authorized Max min theorem
$$\underset{I\in {\mathcal{I}}_1\cap {\mathcal{I}}_2}{\max }\sum _{x\in I}\omega (x)=\underset{{\omega }_1,{\omega }_2}{\min }\{\max \{{\omega }_1(I):I\in {\mathcal{I}}_1\}+\max \{{\omega }_2(I):I\in {\mathcal{I}}_2\}\}$$

among ${\omega }_1,{\omega }_2$ Are the two $\mathbb{U}\mapsto \mathbb{R}$ The function of satisfies $\forall x\in \mathbb{U},{\omega }_1(x)+{\omega }_2(x)=\omega (x)$ .

In the implementation of the algorithm , We define point weights in exchange graphs
$$\nu (x)=\{\begin{array}{ll}\omega (x),& x\notin I\\ -\omega (x),& x\in I\end{array}$$

Find the shortest path instead $X_1$ To $X_2$ In the path of , Under the premise of minimum point weight, the number of sides passing through is minimized .

“ It can be proved that there is no negative weight ring in commutative graphs , So this algorithm must have a solution .”

lu 、 Reference resources

[1] Yang Qianlan , On the expansion and application of matroids ,$\mathrm{I}\mathrm{O}\mathrm{I}2018$ Chinese national team candidate The paper .

[2] Good place bug, Matroids and Applications , You know special column .

[3] William H. Cunningham, Improved Bounds for Matroid Partition and Intersection Algorithms.[J]. SIAM J. Comput.,1986,15(4). 10.1137/0215066.

[4] H. N. Gabow and M. Stallman, Efficient algorithms for graphic matroid intersection and parity, extended abstract, in Automata, Languages and Programming, Lecture Notes in Computer Science, Springer, Berlin, 1985. 10.1007/BFb0015746.

[5] zghtyarecrenj, From matroid basis to Shannon Switch game ,luogu-blog.

---

1. The English name is $\text{deletion}$ and $\text{contraction}$, The author of the paper did not find a standard translation . ︎