マトロイド理論の基礎( 6)大山達雄

前回にひき続いて双対マトロイドについてのベる.まずグラフ G を対象とした閉路マトロイド M(G) の双対マトロイドについて考えてみよう.

ない.したがってこれらの 2 つのマトロイド (M(G))* ，M*(G) は同一であることがわかる.

図

前にものべたように，グラフ G のカットセットは，弧〔閉路マトロイドとカットセットマトロイド〕の集合 E の部分集合のうちで，その部分集合に含まれる

グラフ G が与えられた時，狐の集合 E 上で定義され弧をグラフ G から除去すると G の連結成分の数が増加た閉路マトロイド M(G) の双対マトロイド川d(G) )*とするような特性を有する要素数極小のものである.上の3.3 節で定義したカットセットマトロイド M*(G) の聞

定理 4.3 からもわかるように，グラフ G のカットセットには，次の定理にある関係が成立する.

は，閉路マトロイド M(G) の双対マトロイド川1(G))*

定理 4.3のサーキットであることから ， M(G) のサーキットであグラフ G の弧の集合E上で定義された閉路マトロイド M(G) の双対マトロイドリd(G)) 本とカットセるグラフ G の閉路に対応して，双対閉路( cocycle) とよットマトロイド M*(G) の聞には次の関係が成立する.

ばれることもある.したがってマトロイド (M(G))* は，

(4.
18)

カットセットマトロイド M*(G) であると同時に，双対グラフ G の弧の集合 E 上で定義された閉路マト閉路マトロイド (cocycle matroid) とよばれる場合があ(M(G))*=Mホ (G).

匹明

ロイド M(G) の双対マトロイド凶1(G) けとカットセッ
トマトロイド M*(G) のサーキットが同一であることをる.

上の定理 4.3 から次の系は自明であろう.
系 4.4示す.
まず川1(G)) 本のサーキット Cホを考えると，cホはマ弧の集合 E を有するグラフ G において，弧の部分集合 AçE がカットセットマトロイド M*(G) の基底

トロイド川d(G) )*のいずれの基底にも含まれない.しであるということは，集合 A の E に関する補集合 A(=たがって c* はマトロイド M(G) のすべての基底と共通

E\A) がグラフ G の完全木あるいは完全森であることとな要素を有する.閉路マトロイド M(G) の基底はグラフ等価である.

G の完全木あるいは完全森であるから， cホは G のどの完全木あるいは完全森とも共通な弧を有する.

3.3 節の議論からもわかるように， c* はグラフ G のカットセッ

これまでに与えたいくつかの概念をより明確にするために，例を掲げよう.図 4.13 にあるようなグラフ G を考える.
G の弧の集合を E={1 ， 2 ， 3, 4, 5 ， 6} とする.たとえばトを含まなければならない.
また一方 ， D* をグラフ G のカットセットすると ， D*集合{l， 2 ， 3 }，{l, 5, 6} , {2 ， 4 ， 6} などはグラフ G の閉はグラフ G のすべての完全木あるいは完全森と共通な要路であるので ，E 上の閉路マトロイド M(G) のサーキ素を有する，したがって Dホは双対マトロイド同d(G) )*ットに棺当する.それに対して集合 {1 ， 3 ， 5} ，のいずれの基底にも含まれない.つまり D* は (M(G))*{2, 3, 4 }, {4， 5 ， 6} などはグラフ G のカットセットあるにおいて従属集合でなければならず ， D* は (M(G))* のいは双対閉路であるので， E 上のカットセットマトロイサーキットを含むことになる.

ド M*(G) のサーキットに相当する.

{1 , 2 , 6 },以上から閉路マトロイド M(G) の双対マトロイド川f

また一方，集合 {1 ， 3 ， 5 }，{1 , 2, 4} , {1 ， 4， 6} などはグ(G))* のサーキット Cホの集合とカットセットマトロイ

ラフ G の完全木であるので ，M(G) の基底をなしていド M*(G) のサーキット D本の集合は同ーでなければならる.それに対してい， 4 ， 6 }，{3 , 5, 6 }, {2 , 3 , 5} などはグラフ G の完全木の補集合であるので，系 4.4 からもわかおおやま

42 (42)

たつお埼玉大学

るように，カットセットマトロイド M*(G) の基底の集© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサ}チ

双対性の概念を用いることによって，定理 4.5 としてひとつの形にまとめることが可能であることが理解されるであろう.
定理 4.5 および系 4.6 におけるマトロイドのサーキットあるいは双対サーキットの特徴づけをもとにして，これらの聞の一般的な関係を求めてみよう.そのために，まずマトロイドの独立集合の“拡大定理 (augmentation2
図 4.13theorem)" とも言うべき定理 2.1 (2.1 節参照)を双対マグラフ Gトロイドにまで“拡張"した結果を掲け.る.
補題 4. 7 集合 E 上でマトロイド M={E ， ‘f) とその双合となる.

マトロイド理論における双対性の概念は，グラフ理論

対マトロイド M*={E ， 巴f*) が定義されている .E の部とも密接に関連して非常に数多く用いられ，多くの有用分集合 I r;;;， E ， I* r;;;， E に対して ， InI*= 仇 IEJT ， I*Eな結果を提供している.たとえば一般のマトロイドで成JT* とすると ，立する事実において，を満足するような M， M* の基底 B， Bホが存在する.

í マトロイド j を「双対マトロイド JI r;;;, B, I* r;;;， Bホかっ BnB*= φ( 空集合)と置き換えて別の表現を用いることによって，新しい事証明

実を得ることが可能となることがよくある.したがっておよび f本 {=E\I勺はグラフ理論等におけるひとつの事実をマトロイド理論の集合 Iホは M* における独立集合であるから ，

1*戸店、/場。 σ (l *)=E双対性を用いることによって，より広く一般的に表現すなる関係を満たしている(前回に紹介した式 (4.11) を参ることも可能である.

照にしたがって集合戸はマトロイド M における基底例を示そう.定理 4.3 の証明のところでも用いた，“連を含む.いま IE 、/であるから，集合 I を拡大して M

結グラフの完全木とカットセットが必ず共通の弧を有すの基底 B を作ることができる.つまり B r;;;， Ï* であるかる"という事実は，マトロイドの双対性の概念を用いる

ら，と次の定理のようになる.

たことになる.

定理 4.5マトロイド M のすべての双対サーキットは，M のすべての基底と共通な要素を有する.

B* =B=E\B とすれば補題にある B， B* が得られ
図上の補題 4.7 に前述の定理 4.5 および系 4.6 を合わせて用いると，マトロイドのサーキットと双対サーキヴト

証明有限な集合 E 上で定義されたマトロイド M の双との関係を表わす次の定理が得られる.

対サーキットを C* とする.いま C* が M のある基底 B

定理 4.8に対して C*nB= ゆ(空集合)とすると， C率三 B{=E\ B)

キットをそれぞれ C ，でなければならない.の関係が成り立つ.

したがって B は M* の基底であることから ， M* におけるサーキット C* が M* の基底に含まれることになるので矛盾である.

図

なお上の定理 4.5 の逆に関しては，マトロイド M のすべての基底と共通な要素を有するもののうちで極小な集合が M に関する双対サーキットであると言うことがで

マトロイド M の任意のサーキット，双対サーCホとすると，

(4.
19)

ICnC*1""1.
征明

いまマトロイド M={E ， 、f) のサーキット C と双対マトロイド M*={E ， JT ホ)のサーキットびとの簡にjCnC車 j=1が成立していると仮定する. CnC*={e} とすると，きる.また定理を双対マトロイドにおいて考慮すること

I=C\ {e} ε 、f ，によって次の系が得られる.

InI*= ゆ(空集合)系 4.6'"<トロイド M のすべてのサーキットは ， M のすべての双対基底と共通な要素を有する.
系 4.6 の逆に関しては，マトロイド M のすべての双これらの聞には次

I*=C*\ {e} ε 、f*であるから，補題 4. 7 よりl r;;;, B , 1ホ r;;;， B本
BnB*= ゆ(空集合)対基底と共通な要素を有するもののうちで極小な集合がを満足するような M の基底 B と M* の基底 B* が存在

M に関するサーキットであると言うことができる.

する.ところが B r;;;， 戸 =E\1* であって，グラフ理論における用語を用いると，定理 4.51主連結グラブの任意のカットセットと完全木とが共通の弧を有さらには定理4.5 よりjC本 nBj 註 1することを示し，また系 4.6 は連結グラフの任意の閉路でなければならない.したがって C と C事の共通部分でと完全木の補集合とが共通の弧を有することを示していある要素 e は eεB となるので ， M の基底 B が IU {e}る.このような 2 つの命題を，マトロイド理論における=C なるサーキット C を含むことになり，これは基底の1982 年 1 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(43)43

性質に矛盾する.

図

弧を赤の弧の集合 R ， 糞の弧の集合 Y， 緑の弧の集合 G

グラフ理論において連結グラフの閉路とカットセットとが共有する弧の数が偶数個であるとし、う命題を，マトの 3 つの集合に分割し，特定の黄色の弧を e= (uo , v o),

UOEV , VoEV と表わす.

ロイドの分野に一般化したものが上の定理 4.8 に相当す

次のようなラベリングを考える.

ることは明らかであろう.

(i) S={vo} とする.

(ii) 弧 (u ， v)EE に対して(Minty の彩色定理〕

定理 4.8 と密接に関連しているものとして 1966 年にG.J.Minty注)が紹介した彩色定理 (paintingtheorem)(1) u ε s ， v$S かっ (U ， V)EGU Y ならば Su{V} を新しい S とする.とよばれる興味ある定理がある.結果のみを掲げること(2) uEド S ，V εS かっ (U ， V)EG ならば Su {v}を新しい S とする.にする.

集合 E の要素を R ， Y， G の 3 つの部分集合(共通部分上の (ii )の操作をそれ以上 S の要素数を増加できなくを有しない排反な部分集合とする)，ただし IYI=I ， になるまでくり返す.この時 UoES であれば ，分割する.それぞれの部分集合 R ，Y , G に含まれる要ら UOEV へいたる緑と黄の弧から成る閉路が存在し，そ素を赤 (red) ，黄 (yellow) ，緑 (green) に彩色する.に含まれる黄色の弧はすべて同じ向きを有する.したがこの時，集合 E の任意の分割に対して次の定理が成立すれってこの場合には定理の (a) が成立する.

VoEV か一方的 $S とすると ， S の V に関する補集合 S=V\Sる.

定理 4.9 (Minty) 上述のような集合 E の任意の分割，に対して，集合 {(u， v)luES , VES) に含まれる弧は彩色が与えられている.この時，集合 E 上で定義されたすべて赤である.また集合 {(u， v)lu εS ， VES} に含任意のマトロイド M に関して，以下の (a) ，(b) のうちのいずれか一方が成り立つ.

(a) Y と G に含まれる要素のみから成る M のサーキットが存在する.

(b)

カットセットを含む.とのようにして定理の (b) が成立する.

Y と R に含まれる要素のみから成る M の双対サーキットが存在する.

緑のいずれかに彩色した場合(ただし黄色の弧は 1 本のみとする)にあてはめると，定理 4.9 における (a) ，(b) ,の意味するところは明らかとなるであろう.また有向グ
ラフの弧の集合を対象とする

図

定理4.9 および定理4.8 の式 (4.19) を同時に満たすようなサーキットおよび双対+ーキットの集合族を <e， 量1"*

Minty の定理を(無向)グラフのすべての弧を赤，黄，Minty との定理は次のようにのべることができる.
定理 4.10

まれる弧はすべて赤か黄でなければならない.したがってこれらの 2 つの弧の集合は，黄と赤のみの弧から成るとして，これらを有限集合 E 上で定義づけた系 (E， <e,室内)を Minty はグラフォイド (graphoid) とよんでいることをつけ加えておこう.
〔マイナーマトロイドの双対性〕

4.
1節に紹介したマトロイドの限定あるいは縮約について考えてみよう.

有向グラフの 1 本の弧 e を黄色に彩色する.

双対マトロイドの概念を用いると，限定マトロイド，他の弧をすべて赤，黄，緑のいずれかに彩色すると，以締約マトロイドあるいはそれらの限定，締約の操作の組

下の (a) ，合せによって得られるマイナーマトロイドに関して多く(b) のうちのいずれか一方が成立する.

(a) 弧 e を含み，黄と緑の弧のみから成る閉路が存のことが容易に得られる.そのような例をいくつか以下在する.ただしこの閉路における黄色の弧はすべて弧 eに紹介しよう.と同じ向きを有する.

定理 4.11(b) 弧 e を含み，黄と赤の弧のみから成るカットセットが存在する.ただしこのカットセットにおける黄色集合 E 上で定義されたマトロイド M の部分集合 TcE 上への限定マトロイド，縮約マトロイドに関しては，以下の関係が成り立つ.の弧はすべて弧 e と向じ向きを有する.

{川f ・ T)*=M*IT

liE明有向グラフの頂点の集合を V， 有向弧の集合をl(MIT) 本 =M*.T

E={(u , v) lu ε V， VEV} とする.さらに E に含まれる(4.
20)

つまり有限集合 E 上で定義されたマトロイド M の部
分集合 T r;;;， E 上への限定マトロイド M ・ T の双対マトロ

注G. J.Minty:On the axiomatic foundations

イドは ， M の双対マトロイド M* の T 上への締約マトof the theoriesof directed line graphs , electｭ

ロイドと向型であり，また M の T 上への縮約マトロイ

rical networks and network programming ,ド MIT の双対マトロイドは ， M* の T 上への限定マトJourn.Math. Mech. , Vol.l5. 1966 , pp.485‑520

ロイドと同型であることが上の定理の示唆するところで

44 (44)© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オベレーショ γ ズ・リサーチ

=(MIS)*.

ある.

証明(c) は両辺のマトロイドの階数関数が同一であること

まず (4.20) の最初の式を示そう.

マトロイド M およびその双対マトロイド M* の階数を示すことによって得られる.

関数をそれぞれ r， r* とする.さらに M の T 上への限

いまマトロイド M， M ・ T， MI(E\ (T \S)) の階数関定マトロイド M ・ T の階数関数を rM ・ T とし，その双対数をそれぞれ r， r1J rz とし，またマトロイド (M ・ T)ISマトロイド (M ・ Tけの階数関数を fM.r とすると次の関および (MI(E\ (T \ S))) ・ S の階数関数をそれぞれげ，係が成り立つ.

T2F とすると，関数げ (X) ，(4.
21)=r(XU(T¥S))‑r(T¥S).
η '(X)= η (X)

双対マトロイド M* の T 上への縮約マトロイ=r(XU(1'¥S))‑r(T¥S).

ド M*IT の階数関数 rM*IT は，以下のように表わすこ

XçT， )(=T \X , T=E\T とすると

したがって

rM*IT(X)=同 (XUT)-r*(T)r.'(X)= η '(X) ，=r*(E¥)(J‑r*(TJX ç, Sが得られる.

=IE\XI-r(E)+r( 主)ー (ITI-r(E)+r(T))また (c) の両辺のマトロイドの双対マトロイドを考える.

= IXI-r(T)+r(T \ X) , Xç二 T.
したがって (4.21) ，はそれぞη '(X)= η (XU(T \ S)) ー η (T \ S)

=IXI-r(T)+r(T \ X) , X 躓 .とができるX ç， S ，れ九九 f を用いて以下のように書くことができる.

rM ・ T*(X)=IXI-rM ・ r( T)+rM ・ r( T \X)

一方，r 2'(X) ,((M ・ T)IS)*=((MI(E\ (T \ S))) ・ S)*

(4.
22)

(M ・ T)*.S=(MI (E\ (T \ S))) 引 S(4.22) から ， rM ・ T* と rM*IT の 2(M*IT) ・ S=(M* ・ (E\ (T \S)))IS.

つの階数関数は等しくなる.このようにして川f ・ T)*=

したがって上式において M* を M に置き換えると，(d) の関係が得られる.

M勺 T の関係が証明された.

図

またもうひとつの関係 (MI 1' げ =M*.T は，式 (4.20)

以上で本節の主題である双対マトロイドの概要の紹介の最初の式において，マトロイド M を M* と置き換えを終えるが，マトロイド全般における双対性の概念、とグた上で河辺のマトロイドのあ(対をとることによってただラフの双対性との関連については，後に 5.2 節で詳細にちに得られる.

のべることにする.

図

さて上の定理 4.11 を用いて得られる，マイナーマトロイドに関する結果を紹介しよう.有限集合 E の部分集合を TçE ，Sç二 E かっ Sç二 T とする.

マトロイド M の昭和55年度S あるいは T への限定，縮約の操作の組合せによって得

鹿島学術振興財団研究助成決定られるマイナーマトロイドに関しては，次の定理が成立

鹿島学術振興財団の昭和 55年度研究助成に本学会する.

推薦のうち下記 2 件が採択され，研究を進めており

定理 4.12

有限集合 E 上のマトロイドを M とし ，Eの部分集合である S， T が S ç， T ç， E なる関係を有するとすると，以下の関係が成立する.

研究代表者:伊理正夫(b) MIS=(MITJIS共同研究者:原野秀永，緯豊太郎，阿部篤行，

I (c)(M ・ 1') IS=(MI(E¥(T¥S))).Sl(d)川11 1' ).S=(M ・ (E\ (T\S)))IR

腰塚武志，四方野英彦，中森真理雄，浅野孝雄，室田一般(4.
23)(a) は明白であろう.

助成金額: 400万円

2. 研究課題:都市廃棄物の処理に関する研究(b) は両辺のマトロイドの双対マトロイドが同一であることによって，以下のように示される.
((MI 1' )IS) 九 (MI 1' )*.S((4.20) より)=(M*.T) ・ s((4.20) より)=Mホ .S((a)より)1982 年 1 月号

1. 研究課題:地理的情報に関する基本アルゴリ
ズムの調査研究1(a)MJ=(M ・1')・ s

証明

ます.

研究代表者:青木兼一
共同研究者:藤永靖彦，尾崎俊治，桑原兵二郎，平木秀作
助成金額: 300万円© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

(45)45