独立性と従属性について

独立性と従属性について

matroid^{による相互関係記述}

「複雑系の構成論および計算論のための実験数学」研究会 講演資料

辻下   徹

北海道大学理学部

1996.2.16

1 相互関係の公理 2 matroid の諸定義 3 matroid^演算 4 matroid ^の効用 5 matroid研究小史

複雑系を多成分系として見るとき、その成分間には多様な関係が生ずる。

その諸関係を何らかの方法で精密に記述することは複雑系の理解に欠か せないが 、事の性質上、関係の具体的で詳細な記述は望めないし 、たとえ それが可能であるとしても複雑系の適切な記述とはならないと思われる。

関係概念自身の分析・分化・精密化は、複雑系研究の基盤¹ を形成する 数学的研究の一テーマとして重要性が高いだけでなく、可能性の多い方 向と思われる。

この講演では 、数学的な関係概念の例としてmatroidを取り上げる。

matroidは、数学の多様な領域に現れる種々の独立性・従属性に共通した

1 数学は基礎でなく基盤であるという位置づけは角田秀一郎氏による

構造を抽出した簡潔な組合的幾何的構造であり、豊かな数学的世界を伴っ ており、現在も多くの数学者達により研究されている。

matroid理論の概念と諸結果は、独立性・従属性にかかわる普遍的諸

現象の数学的表現と解釈できるものが多い。たとえば 、matroidのある種 の構成法は、相互作用による関係の変化を表現するものと解釈でる。

以下、matroid の基本事項とその構成法を説明し 、複雑系への応用の

可能性について述べる。

1 相互関係の公理

あるシステムの成分全体のなす有限集合を Sとし 、いくつかの成分の 集まり Γ の間になんらかの「 関係」があるとき `Γ と書く。このとき、

「関係」についての直観的内容を次のような要請に表現する（Γ∪ {s}を Γ∪s と略記する、また。s /∈Γのとき Γ +s:= Γ∪sとかく。）：

単調性 `Γ

`s∪Γ

推移性 k−s+ Γ k−s+ ∆ Γ6= ∆

`Γ∪∆ ,

ただし 、Γに関係があり、Γの真部分集合には関係がないとき、k− Γと 書く。

集合 S とこのような `の組 (S,`)を S 上の matroid 構造と呼ぶ。

典型例

S `Γ

線形matroid ベクトル空間の部分集合 Γは線形従属

代数的matroid 体の部分集合 Γは代数的従属

グラフmatroid グラフの辺の集合 Γはサイクルを含む

2 matroid の諸定義

matroid理論は種々のcryptomorphic² な理論を持つ。すなわちmatroid 理論は次の概念のいずれを基礎としても記述される。

2 [2]による

•circuit (Γがcircuit ⇐⇒ k−^def Γ )

•独立性

•基底

•階数写像

•特殊な演繹的 hyperdigraph

•特殊な閉作用素

•幾何学的束

どの概念を基礎としても公理は簡潔であるが 、同値性の証明の多くは 自明でない。

独立集合 I が独立 ⇐⇒ 6`^def I と定義する。

(I1) 空集合は独立である。

(I2) 独立な集合の部分集合も独立である。

(I3) U, V が独立で、U の個数が V の個数より大きければ 、V ∪xが独 立となるような要素 x∈U \V が存在する。

以下、(S,I)が matroidであるというとき、I は独立集合族を表す。

基底 包含関係について極大な独立集合を基底という。基底は次の性 質を満たす。

(B1) Bi (i= 1, 2)が基底で、x∈ B1\B2 ならばB1∪y\xが基底とな るような y∈B2\B1 が存在する。

階数写像 Γ ⊂ S に対して、Γ に含まれる独立集合の個数の最大値を Γ の階数といい ρΓ と書く。

(R1) ρ∅= 0, (R2) ρΓ≤ |Γ|,

(R3) ρ はsubmodular function, すなわち、

ρ(Γ∪∆)≤ρ(Γ) +ρ(∆)−ρ(Γ∩∆).

演繹的hyperdigraph Γ`b ⇐⇒<sup>def</sup> ρ(Γ∪b) =ρ(Γ)と定めると、`は 演繹的hyperdigraphとなる、すなわち、

(DH1) Γ `s ∀s∈Γ, (DH2)

Γ`s ∆∪s`t Γ∪∆`t . さらに

(DH3)

Γ∪s `t Γ6`t Γ∪t `s . 閉作用素

C(Γ) :={s|Γ`s} とおくと、閉作用素となる、すなわち、

(CL1) Γ⊂C(Γ),

(CL2) Γ⊂∆ならば C(Γ)⊂C(∆), (CL3) C(C(Γ)) =C(Γ),

が成り立つ。さらに交換律

(CL4) y∈C(Γ∪x)\CΓ⇒x∈C(Γ∪y) も成り立つ。

幾何学的束

Γが閉集合 ⇐⇒^def CΓ = Γ.

と定義すると、閉集合の全体は包含関係による順序集合として幾何学的 束をなす。幾何学的束とは、semimodular latticeでありかつ、どの元も 有限個のアトムの上限として表される。ただし 、seminodular latticeとは x, yが x∧yの直後の元であれば 、x∨yは x, yの直後の元であることを いう。また、アトムとは最小元の直後の元のことをいう。逆に geometric lattice は適当なmatroid の閉集合全体のlattice となることがしられて いる。

3 matroid 演算

matroid を操作する様々な方法があり、相互関係の関係を記述する方

法を提供する。M, M1, M2 をmatroidとする。主なものとしては

•双対（ 相互関係間の関係）

•部分集合への制限（ 主導的部分系）と縮約（ 追従的部分系）

•和（ 協調的相互作用）と交わり（ 競合的相互作用）

•貼り合わせ（ 部分系の結合）

がある。

双対

M^∗ := (S,{X |X∩B =∅となる基底 B が存在する}

は matroidとなる。{S\B |B は基底}は M^∗ の基底となる。したがっ て、M^∗∗=M となる。M^∗ の階数 ρ^∗ は次の式を満たす:

ρ^∗(S\A) = (|S| −ρS)−(|A| −ρA).

制限 部分集合 T ⊂S に対して、T の部分集合でM の独立集合であ るもの全体はT 上のmatroid構造となる。これを部分集合 T への制限と 呼ぶ。M|T の階数写像はM の階数写像の pow(T)への制限である。

縮約 部分集合 T ⊂S に対して

M.T := (T,{X⊂ T |X∪B ∈ I となるM|(S\T)の基底 B が存在する },

は matroidとなる。これを部分集合 T への縮約と呼ぶ。M.T の階数写

像 ρ^T は

ρ^T(A) = ρ(A∪(S\T))−ρ(S\T).

制限と縮約を組み合わせて得られるものを M のminorと呼ぶ。

和 Mi = (S,Ii) (i= 1, 2)に対して、

M1+M2 := (S,{X1 ∪X2 |Xi ∈ I_i (i = 1, 2)}) は matroidとなる。階数写像は

ρA= min

B⊂A{ρ1B +ρ2B +|A\B|}

で与えられる。

交わり M1∧M2 := (M₁^∗ ∨M₂^∗)^∗ は、

({X1∩X2 |Xi は Mi の基底を含む(i= 1, 2)},⊂) の極小元を基底とするmatroidとなる。

貼合わせ Mi (i= 1, 2)をmatroidとし 、κi :T→Si (i= 1, 2)を単射 とする。Si (i= 1, 2)の κによる張り合わせを

S :=S1∪κ S2 :=S1

aS2/κ1t∼κ2t

とし 、Siを Sの部分集合とみなす。このとき、Mi のκによる張り合わせ M1∪_κM2が、S 上のmatroidとして次のように定義される：M_i⁰ :=Mi+Pi

を Si 上のmatroid Mi の S 上への拡大とする、ただし 、Pi は S\Si 上 の自由マトロイド 、すなわち任意の部分集合を独立集合とするmatroidを 表す。そして、

M1∪κM2 :=M₁⁰ ∧M₂⁰

と定義する。交わりの定義より、Xi ⊂Siが Mi の基底を含む集合を動く ときに

(X1\S2)∪(X2\S1)∪(X1 ∩X2∩S1∩S2)

が成す集合族の、包含関係に関する極小元が 、M1∪_κM2 の基底となる。

貼り合わせと隠ぺい 前節の M1∩κM2 をS1∆_κS2 :=S\(S1∩S2)に 制限したものをM1∆_κM2 と書く。

4 matroid の効用

matroidを用いる事で、複雑系のコヒーレンスの様々な側面の表現が

得られると期待されるが 、いくつか例をあげよう。

•部分系の主導性・従属性：部分系T ⊂S 内のコヒーレンスが、全体 の中での主導性・従属性によって  異なるmatroidにより表現され る：主導的な場合には M|T 従属的な場合には M.T.

•部分系への自由度の配分：S =^`_iTi のとき、各 Ti に自由度 di を配 分できるための必要条件は

X

j∈Jdj ≤ρ(∪j∈JTi)

がすべての部分集合 J ⊂I について成立することである。

一般に 、ρΓ ≤ |Γ| とは限らない実数値非減少submodular function も各部分系の「 自由度」を表現するものと考えることができるが 、

polymatroidは自由度の配分を「独立集合」に相当する基礎とする概

念で、matroidの重要な一般化の一つとなっている。

•冗長性：matroidM の閉集合 T が機能FT の実現に寄与し得る成分 全体の集まりを表現すると考えるとき、T 中の最大独立集合 B（ 制 限M|T の基底）は機能 FT の実現に十分な成分系で極小なものに対 応する。機能FT の実現手段の冗長性は M|T の基底の数として表現 される。

•相互作用による相互関係の変化の諸様相の表現：matroidの貼り合わ せは 、相互作用により系内部の錯綜した関係がど のような変化を受 けるかを考える一つの手段を提供する。部分的変化の引き起こす広 範な相互関係の再編成の様相は想像以上に多様と思われる。

なお、matroid の応用の範囲は広く、大規模なシステムの制御理論へ の応用例もある [1]。

また、ハイパーカテゴ リーは複雑な成分からなる多成分系を記述する 可能性のある数学的枠組みであるが 、その「射」のインタフェース集合

にmatroid構造を付与することで、インタフェース同志の相互依存情報

を与えることができると思われる。これにより、マルチカット（複数のイ ンタフェースにおける結合）が成分の「凍結」をもたらす状況を明確に 表現する事が可能となり、インタフェースの修飾に基づく相互作用記述 の枠組みが単純化されると思われる。また、各射のインタフェース達の 間にある相互依存関係が合成によってどのように変化するかを、matroid の演算を通して詳細に記述する事が可能になると思われる。

matroidは、複雑系内部における錯綜した相互関係の緻密な記述法を与

える潜在力を持つ一方、数学的にも深い現象と構造を持っている。matroid とその種々の一般化は、精密でしかも的確な概念システムを提供すると いう、複雑系研究における数学独自の役割の一例となっていくことが 期 待される。

5 matroid 研究小史

1930’s van der Werden 線形従属と代数的従属の公理的研 究

1935 Whitney matroidの定義と基礎研究、 双対

matroid、 階数写像 1935 Birkoff geometric lattice

1936 MacLane projective geometryとの関係 1942 Rado 組み合わせ論への応用

1956 Kruskal greedy algorithm

1958 Tutte matroidの演算（ 制限・縮約）

1965 Mirsky et al transversal matroids の発見 1966 Edmonds & Rota submodular 関数による matroid

構成

1966 Nash-Williams matroidの和

1969 Perfect bipartiteグラフによるmatroid構 成

1970 Rota combinatorial geometryとしての matroid

1970 Edmonds polymatroid

1980– Iri et al matroidの種々の応用

参考文献

[1] K. Murota. Systems Analysis by Graphs and Matroids; Structural Solvability and Controllability. Springer 1987.

[2] H.H. Crapo and G.-C. Rota. On the Foundations of Combinatorial Theory: Combinatorial Geometries. MIT Press 1970.

[3] D.J.A. Welsh. Matroid Theory. Academic Press 1976.