マトロイドの双対

本節ではマトロイドの双対について述べる。 マトロイドとしてみれば、グラフの双対の定義が ごく自然なものであることがわかる。 また双対に関する証明のいくつかは、単純(ほとんど自明)なものになってしまう。

$M=(E,\rho)$を階数関数で定義されたマトロイドとする。 $E$の部分集合に対して定義される関数$\rho^*$を、次式で定義する。 

\[ \rho^*(A):=|A|+\rho(E\setminus A)-\rho(E)\ \textrel{for}A\subset E. \]
定理
$M^*=(E,\rho^*)$は$E$上のマトロイドである。

証明

階数関数の性質 1 の証明。

任意の$A\subset E$に対して、$\rho(E\setminus A)\le\rho(E)$だから、$\rho^*(A)$は 

\begin{eqnarray*}
  \rho^*(A) & \le & |A|+\rho(E)-\rho(E) \\
            &  =  & |A| 
\end{eqnarray*}
をみたす。

階数関数の性質より \[ \rho(A\union (E\setminus A))+\rho(A\intersection (E\setminus A))\le \rho(A)+\rho(E\setminus A) \] が成り立つ。

ここで$A\union (E\setminus A)=E,\;A\intersection (E\setminus A)=\emptyset$より 

\begin{eqnarray*}
  \rho(E)+\rho(\emptyset)    & \le & \rho(A)+\rho(E\setminus A) \\
  \rho(E)-\rho(E\setminus A) & \le & \rho(A)-\rho(\emptyset) \\
                             &  =  & \rho(A) \\
                             & \le & |A| 
\end{eqnarray*}
となり、$|A|+\rho(E\setminus A)-\rho(E)\ge 0$が得られる。

従って$\rho^*(A)$は$\rho^*(A)\ge 0$をみたす。

階数関数の性質 2 の証明。

$E\setminus A=(E\setminus B)\union (B\setminus A), \;\emptyset=(E\setminus B)\intersection (B\setminus A)$より 

\begin{eqnarray*}
  \rho((E\setminus B)\union (B\setminus A))+\rho((E\setminus B)\intersection (B\setminus A)) %
    & \le & \rho(E\setminus B)+\rho(B\setminus A) \\
  \rho(E\setminus A)+\rho(\emptyset) & \le & \rho(E\setminus B)+\rho(B\setminus A) 
\end{eqnarray*}
が成り立つ。

従って 

\[
  \rho(E\setminus A)\le \rho(E\setminus B)+\rho(B\setminus A)
\]
となる。 

\begin{eqnarray*}
\rho^*(B)-\rho^*(A)
  &  =  & |B|+\rho(E\setminus B)-\rho(E)-|A|-\rho(E\setminus A)+\rho(E) \\
  &  =  & |B|-|A|+\rho(E\setminus B)-\rho(E\setminus A) \\
  & \ge & |B|-|A|+\rho(E\setminus B)-(\rho(E\setminus B)+\rho(B\setminus A)) \\
  &  =  & |B\setminus A|-\rho(B\setminus A) \\
  & \ge & 0\ (\textrel{階数関数の性質より})
\end{eqnarray*}
よって 
\[ \rho^*(A)\le \rho^*(B). \]

階数関数の性質 3 の証明。 

\begin{eqnarray*}
  \rho^*(A\union B)+\rho^*(A\intersection B)
  &  =  & |A\union B|+\rho(E\setminus (A\union B))-\rho(E) \\
  &     & \hspace*{2em} +|A\intersection B|+\rho(E\setminus (A\intersection B))-\rho(E) \\
  &  =  & |A\union B|+|A\intersection B| \\
  &     & \hspace*{2em} +\rho(E\setminus (A\union B))+\rho(E\setminus (A\intersection B))-2\rho(E) \\
  &  =  & |A|+|B|+\rho((E\setminus A)\union (E\setminus B)) \\
  &     & \hspace*{2em} +\rho((E\setminus A)\intersection (E\setminus B))-2\rho(E) \\
  & \le & |A|+|B|+\rho(E\setminus A)+\rho(E\setminus B)-2\rho(E) \\
  &  =  & |A|+\rho(E\setminus A)-\rho(E)+|B|+\rho(E\setminus B)-\rho(E) \\
  &  =  & \rho^*(A)+\rho^*(B)
\end{eqnarray*}
よって 
\[ \rho^*(A\union B)+\rho^*(A\intersection B)\le\rho^*(A)+\rho^*(B). \]

\hfill(証明終了)

このマトロイド$M^*$を$M$の双対と呼ぶ。 この定義には、次のとおり非常に単純な同値な表現がある。

定理
集合$E$上のマトロイド$M$に対して 
\[ \text{$B^*\subset E$が$M^*$の基}\iff E\setminus B^*\textrel{が$M$の基。} \]

証明

($\Rightarrow$)

$B^*$は$M^*$において独立だから、$|B^*|=\rho^*(B^*)$である。 よって 

\[ \rho^*(B^*)=|B^*|+\rho(E\setminus B^*)-\rho(E) \]
が成り立つ。

従って 

\[ \rho(E\setminus B^*)=\rho(E)\ (\ |B^*|=\rho^*(B^*)\textrel{より}) \]
となる。

よって$\rho(E\setminus B^*)$は、$\rho$の最大値である。

$B^*$が$M^*$の基なので、$|B^*|=\rho^*(B^*)=\rho^*(E)$が成り立つ。 従って 

\begin{eqnarray*}
  \rho^*(B^*) & = & |B^*|+\rho(E\setminus B^*)-\rho(E) \\
  \rho^*(E)   & = & |E|+\rho(E\setminus E)-\rho(E) \\
              & = & |E|-\rho(E) 
\end{eqnarray*}

よって$|B^*|+\rho(E\setminus B^*)-\rho(E)=|E|-\rho(E)$。 従って 

\[ \rho(E\setminus B^*)=|E|-|B^*|=|E\setminus B^*|\]
だから、$E\setminus B^*$は$M$において独立である。

($\Leftarrow$)

\begin{eqnarray*}
  (\rho^*)^*(A) %
    & = & |A|+\rho^*(E\setminus A)-\rho^*(E) \\
    & = & |A|+(|E\setminus A|+\rho(E\setminus (E\setminus A))-\rho(E))-(|E|+\rho(E\setminus E)-\rho(E)) \\
    & = & |A|+|E\setminus A|+\rho(A)-\rho(E)-|E|-\rho(\emptyset)+\rho(E) \\
    & = & |E|+\rho(A)-|E| \\
    & = & \rho(A) 
\end{eqnarray*}
よって$(M^*)^*=M$である。 従って$E\setminus B^*$が$M=(M^*)^*$の基ならば、 前半で示したことによって $B^*=E\setminus(E\setminus B^*)$は$M^*$の基である。

\hfill(証明終了)

上の定理の証明の中で示したとおり、 二重双対$M^{**}$は$M$と同型である。

グラフ$G$の閉路マトロイド$M(G)$の双対は、 カットセットマトロイド$M^*(G)$と同型であることがわかる．

定理
グラフ$G$に対して、$M^*(G)$は$(M(G))^*$と同型である。

証明

$C^*$が$(M(G))^*$の閉路であるための必要十分条件は、 $C^*$が$G$のカットセットであることを示せば十分である。

$C^*$は$G$のカットセットとする。 $C^*$が$(M(G))^*$において独立ならば、 $C^*$は$(M(G))^*$の基$B^*$に拡張できる。 よって$C^*\intersection(E\setminus B^*)$は空である。

ここで、$E\setminus B^*$は$M(G)$の基なので、 $E\setminus B^*$は$G$の全域林となる。 全域林の定理(i)より、 $G$のすべてのカットセットは 全域林と共通な辺がなければならないので、矛盾が生じた。

よって$C^*$は$(M(G))^*$において従属であり、 $(M(G))^*$の閉路を含む。

反対に$D^*$が$(M(G))^*$の閉路ならば、 $D^*$は$(M(G))^*$のどの基にも含まれない。

よって$D^*$は$M(G)$の任意の基、すなわち$G$の全域林と素でない。

もし$G\setminus D^*$と$G$の成分の個数が一致するならば、 $G\setminus D^*$の全域林は$G$の全域林でもあり、$D^*$と共通な辺をもたない。 これは上に示したことと矛盾する。 従って$G\setminus D^*$の成分の個数は$G$の成分の個数より少ない。 つまり$D^*$は$G$の非連結化集合である。 よってカットセットを含む。

結局

  1. $C^*$が$G$のカットセットならば、$M(G)^*$の閉路を含む
  2. $D^*$が$M(G)^*$の閉路ならば、$G$のカットセットを含む
が示された。

初めに戻って$C^*$を$G$の任意のカットセットとすると、 $C^*$は$M(G)^*$の閉路$D^*$を含む。 この$D^*$は$G$のカットセット$C^*_1$を含む。 $C^*$と$C^*_1$は共に$G$のカットセットで、 しかも$C^*_1\subset D^*\subset C^*$。 従ってカットセットの極小性により、$C^*_1=C^*$でなければならない。

よって$C^*=D^*$、つまり$C^*$は$M(G)^*$の閉路。

逆に$C^*$が$M(G)^*$の閉路ならば、 $G$のカットセット$C^*_1$を含み、 この$C^*_1$は$M(G)^*$の閉路$D^*$を含む。 $D^*$と$C^*$は共に$M(G)^*$の閉路で$D^*\subset C^*_1\subset C^*$。 従ってマトロイドの閉路の極小性により、$D^*=C^*$でなければならない。

よって$C^*_1=C^*$、つまり$C^*$は$G$のカットセット。

\hfill(証明終了)