システム理論Ⅱ ( 離散システム論 )

(1)

システム理論Ⅱ ( ^{離散システム論} )

中村政隆

March 2008

(January 15, 2012)

(2)

1

集合

1

1.1

集合と要素

. . . . 1

1.2

順序対、直積集合

. . . . 1

1.3

関数

(

写像

) . . . . 1

1.4

集合の位数

. . . . 2

1.5

関係の定義、同値関係

. . . . 2

1.6

数の概念とペアノの公理、数学的帰納法

. . . . 3

2

順序と束

7 2.1

順序集合

. . . . 7

2.2

束

(lattice) . . . . 8

2.3

分配束

. . . . 8

2.4

モジュラー束

. . . . 10

2.5

セミモジュラー束

. . . . 10

2.6

幾何束

. . . . 11

3

グラフ理論

:

諸定義、平面グラフ

13 3.1

グラフとは

. . . . 13

3.2

グラフの基本的な諸概念

. . . . 13

3.3

基本カットセット行列、基本サーキット行列

. . . . 15

3.4

平面グラフ、彩色、木

. . . . 16

3.5

交差グラフ

(Intersection Graph) . . . . 18

3.6

三角化グラフ

. . . . 20

3.7

区間グラフ

. . . . 21

4

線形計画法

Linear Programming 23 4.1

線形不等式系と多面体

. . . . 23

4.2

数理計画法、凸計画法

. . . . 24

4.3

線形計画問題

. . . . 25

4.4

双対問題の幾何学的解釈と

LP

の双対定理

. . . . 26

4.5 Blocker and Packing . . . . 32

4.6 Integer Programming and the MFMC property . . . . 32

4.7 Packing Theorems . . . . 33

4.8 Anti-blocker and the Perfect Graph Theorem . . . . 34

4.9

線形計画法の応用例

. . . . 37

4.9.1

２人零和ゲーム

. . . . 37

4.9.2

輸送問題

. . . . 38

4.9.3

ネットワーク・フロー

. . . . 38

4.10

凸関数とその共役関数

(conjugate functions) . . . . 39

5

整多面体と組合せ的最大最小定理

41

5.1

全ユニモジュラー行列と多面体

. . . . 41

(3)

6

ネットワーク・フローと組合せ的最大最小定理

46

6.1

最大流問題

. . . . 46

6.2

最小費用流問題

. . . . 48

6.3

二部グラフの最大マッチング問題

. . . . 50

6.4

マッチング多面体

. . . . 52

7

計算の複雑さと

N P -

完全問題

53 7.1

問題のクラス

NP . . . . 53

7.2 NP—完全性 . . . . 56

7.3

計算の複雑さ：時間計算量、領域計算量

. . . . 61

7.4 Worst Case Analysis and Mean Time Analysis . . . . 62

7.5

補遺

:

様々な

N P -

完全問題

. . . . 63

7.6

数の複雑さ

–

チェイティンの定義

. . . . 66

8

最短路問題

67 8.1

最短路問題

. . . . 67

8.2

最短路問題の

LP

による定式化

. . . . 68

8.3

アサイクリックグラフの場合

. . . . 70

8.4

辺の長さが非負である場合の最短路問題の解法

(

アルゴリズム

) . . . . 70

8.5

すべての点対間の最短路を求める

–

行列かけ算法

. . . . 71

9 Blocking and Anti-blocking Theory –

多面体的組み合わせ論

74 9.1

集合族、多面体のブロッカー

. . . . 74

9.2

集合族、多面体のアンチ・ブロッカー

. . . . 77

9.3

ブロッキングペアとアンチ・ブロッキングペアの関係

. . . . 78

10 Matroid Theory 80 10.1

マトロイドの公理系

. . . . 80

10.2

マトロイドの例

. . . . 85

10.3

マイナー

. . . . 86

10.4

マトロイドの基本分類定理

. . . . 86

10.5 Matroid Intersection Theorem

と合併マトロイド

. . . . 87

10.6 Tutte

多項式、特徴多項式

, β -

不変量

. . . . 89

10.7

最小重み全域木問題と欲張り算法

(Greedy algorithm) . . . . 92

10.8 Greedy Algorithm

とマトロイド、ポリマトロイド

. . . . 93

10.9 Poset

上の欲張りアルゴリズム

. . . . 96

10.10

アンチマトロイドと凸幾何

. . . . 97

10.11

アンチマトロイドと欲張り算法

. . . . 98

11

ポリマトロイドと劣モジュラー関数

100 11.1

定義と記法

. . . 100

11.2

ポリマトロイド

polymatroid . . . 100

11.3

劣モジュラー関数

. . . 101

11.4

ポリマトロイドの頂点の表現

. . . 101

11.5

ポリマトロイド交差定理

Polymatroid Intersection Theorem . . . 102

11.6 Matroid Intersection Problem . . . 104

(4)

11.6.1 Polymatroid Intersection Theorem . . . 104

11.7 Matroid Union . . . 104

12

ランダムウォーク、マルコフ連鎖、待ち行列

105 12.1

乱歩

(

ランダムウォーク

) . . . 105

12.2

マルコフ連鎖

. . . 105

12.3

ポアソン分布、指数分布、待ち行列

. . . 110

13

有限オートマトン、形式言語

114 13.1

有限オートマトン

. . . 114

13.2

有限状態機械

(finite state machine) . . . 115

13.3

生成規則と言語

. . . 116

13.4

正則表現

. . . 118

13.5 Post

システム：付録

. . . 120

14

帰納的関数とチューリング機械と決定不能問題

121 14.1

帰納的関数

. . . 121

14.2

チューリング機械

. . . 123

14.3

決定不能問題

. . . 125

15

自己言及とパラドックス

129

(5)

1 ^集合

1.1

集合と要素

•

集合：特定された元

(要素)

の集まり。

∅

は空集合

•

集合の指定の仕方：

A = { 2, 3, 5, 7, 11 } A = { x : x is prime, 1 6 x 6 12 }

• p ∈ A : p

が集合

A

の要素である。

•

部分集合：A

⊆ B (or A ⊂ B)

•

集合の合併、共通部分、補集合、差、差分和

A ∪ B, A ∩ B, A

^c

(A), A \ B, A ∆ B

• Demorgan

の法則

•

集合の位数

(cardinality): | A | = A

の要素の数

•

べき集合：

2

^E

,

または

P (E) | 2

^E

| = 2

^|^E^|

•

慣用の記法：

N , Z, Q, R, C

1.2

順序対、直積集合

•

順序対

(a, b) = (a’,b’) iﬀ a=a’ and b=b’

• cf.

２元集合では

{ a, b } = { b, a }

•

直積

(product) of A and B : A × B = { (a, b) : a ∈ A, b ∈ B }

• R

²

= R × R

２次元空間

, R

³

= R × R × R

1.3

関数

(写像)

•

関数

f

とは、ある集合

X

の各元

x ∈ X

に対してある集合

Y

の元

f (x) ∈ Y

が一意に定まっているとき、その対応の関係のことを言う。ここで、

X

を定義域、

Y

を値域と呼び

f : X → Y

と書く

•

関数の対応の示し方：

f : x 7→ x

²

+ x + 1, f(x) = x

²

+ x + 1

•

例：f

: R

²

→ R, f : (x

₁

, x

₂

) 7→ x

²₁

+ x

²₂

− 1

•

関数のグラフ：

{ (x, y) : x ∈ X, y = f (x) } (

グラフ理論で言うグラフとは異なる。

)

•

関数の性質：

f

単射

(

１対１写像

)

とは

x 6 = x

⁰ ならば

f (x) 6 = f (x

⁰

)

をみたすこと全射

(上への写像)

とは、任意の

y ∈ T

である

x ∈ X

があって

y = f (x)

となること全射かつ単射であるとき全単射写像という。

(6)

1.4

集合の位数

•

集合の位数

(cardinality,

濃度、基数

)

：

| A | , #(A), card(A)

•

集合

A

と

B

の位数が同じ

⇐⇒ A

から

B

への全単射写像

f : A ← B

が存在する。

•

有限：集合

A

が有限集合であるとはある非負の整数

n

に対して

A

が

{ 1, 2, . . . , n }

と同じ位数になること。

•

可算無限

ℵ

⁰ ：自然数、整数、有理数の位数

•

連続無限

ℵ

¹ ：実数の位数

•

命題可算集合の可算個の合併集合は可算である。

1.5

関係の定義、同値関係

関係という概念を形式化するのにはどのようにすればよいか考えてみる。人間のある集団

E

の中での親子という関係を考える。

a

が

b

の親であるような順序対

(a, b)

の全体を

R

とする。つまり、

R = { (a, b) ∈ E × E | a

が

b

の親である

}

逆に、この

R

を定めれば、集合

E

の中での「親子関係」が定まる。ゆえに、集合

E

上の関係という概念は、その直積集合の部分集合であると定めればよい。

Def. 1.1

集合

E

上の関係とは、その直積集合の部分集合

R ⊆ E × E

のことである。

普通

(a, b) ∈ R

のことを

a R b

と書く。

Def. 1.2

つぎを満たす関係

≡

は同値関係と呼ばれる。

(1) a ≡ a ( ∀ a ∈ E) [

反射的

(reflexive)]

(2) a ≡ b

ならば

b ≡ a [

対称的

(symmetric)]

(3) a ≡ b, b ≡ c

ならば

a ≡ c [推移的 (transitive)]

Def. 1.3

集合

E

上の同値関係

≡

がひとつ与えられているとする。ある元

a

に同値なもの全体の集合を

[a]

と書く。つまり、

[a] = { b : a ≡ b }

と定義する。

a

をこの同値類の代表元という。同値関係の性質から、ひとつの同値類の中の任意の２元は互いに同値になる。かつ、同値類は、代表元の取り方によらないで一意に定まる。つまり、

a ≡ b

ならば

[a] = [b]

となる。

同値類の全体を

E / ≡

と書くと、E /

≡

は集合

E

の分割をなす。これを

E

の

≡

による商と呼ぶ。

演習

1.1 rm

上に述べられた性質を証明せよ。

例

1.1 (1)

整数の集合の上で、ある整数

p

で割った余りが同じとき、

a ≡ b (mod p)

とすると、同値関係になる。

(2)

自然数

N

の組の全体の上に次で同値関係

∼

を導入する。

(a, b) ∼ (a

⁰

, b

⁰

) ⇐⇒ a + b

⁰

= b + a

⁰ この同値関係による同値類の全体

N × N / ∼

は、整数全体と同じと見なせる。

(3)

群

G

とその部分群

H

が与えられたとする。

a ≡ b iﬀ ax = b ( ∃ x ∈ H )

とすると同値関係になる。この同値関係の同値類を

H

による左同値類という。右同値類も同様に定義できる。

H

の右同値類の全体と左同値類の全体が一致するするための必要十分条件は、

H

が正則部分群であることである。

(7)

1.6

数の概念とペアノの公理、数学的帰納法

数は、自然数から始めて、整数、有理数、実数と拡張して規定することができる。自然数全体の集合

N

を特徴づけるものとして、ペアノの公理系がある。まず自然数

1

があり、各自然数

x

にその後者

(successor) x

⁺を対応させる写像

ψ

があり、以下を満たすものとして整数を定義できる。

(1) 1 ∈ N ,

(2) x ∈ N

ならば

x

⁺

∈ N , (3) x ∈ N

ならば

x

⁺

6 = 1,

(4) x

⁺

= y

⁺

(x, y ∈ N )

ならば

x = y,

(5)

集合

M

が

1 ∈ M

と

x ∈ M ⇒ x

⁺

∈ M

の２条件を満たせば

N ⊆ M .

x

⁺は通常の意味では

x + 1

に相応する。条件

(4)

より写像

ψ

は単射になる。また任意の

y ∈ N y 6 = 1

に対して、

y = x

⁺ となる

x

が存在する。もし存在しなければ、

M = N − { y }

に関して極小性の条件

(5)

が成立しなくなる。

数学的帰納法は、自然数

n

に関する性質

P (n)

が以下を満たせば、自然数全体で成立することを言うものである。

(1) P (1)

が成立する。

(2)

任意の自然数

k

で、

P(k)

が正しいならば

P(k + 1)

も正しい。

P (k)

が成立している数

k

の全体を

M

とすれば、ペアノの公理系の第５公理からただちに

M = N

ｔなる。つまり、数学的帰納法が正しいことを保証している。（ポアンカレは「科学と仮説」

(

岩波文庫

)

の中で、

なぜ数学のすべてがただの同語反復になってしまわないのかと次のように疑問を呈している。

「もし数学が演繹的なのは見かけだけにすぎないのならば、誰も夢にも疑おうとしないこの完全な厳密性はどこからくるのか。もし反対に数学で述べている命題全部が形式論理学の規則によって次から次へ引き出すことが出来るならば、どうして数学は大規模な同語反復に帰してしまわないのであろうか。三段論法は我々に何も本質的に新しいことを教えることは出来ないし、もしすべてが同一律から出てくるものであるのだとすれば、すべてはそこにまた帰着するはずである。

それではかくも多くの書物を充たしている定理の全部の叙述は「ＡはＡである」というのを回りくどい方法で言ったものに過ぎないということを承認しなければいけないのか。」

そこでポアンカレは、数学がかくも豊かな内容を持つ秘密のひとつは、数学的帰納法利用するところにあると書いている。）

自然数から整数を構成するのにつぎのような代数的方法がある。自然数の対

(k, l)

の全体

M = N×N

として、その上の同値関係

(k, l) ∼ (m, n)

を

k + m = l + n

で定義する。この同値類として整数の集合

Z = M/ ∼

が定義できる。

(

課題

1.1

を参照

)

有理数の構成。整数の対

(a, b)

で

b 6 = 0

であるものの全体を

P

として、その上の同値関係

(a, b) ∼ (c, d)

を

ad = bc

で定義したときの同値類の全体

P/ ∼

が有理数の全体

Q

になる。

実数の構成。Dedekindは集合の切断という概念をもとにして実数を構成してみせた。有理数の全体

Q

の非空集合への分割

Q = A ∪ B (A, B 6 = ∅ )

が

a ∈ A, b ∈ B → a < b

をみたすとき、切断と呼ばれる。この切断の全体として、実数が定義できる。別に、Cauchy列に基づく方法がある。有理数の列

{ a

_n

}

が、任意の正の有理数

e > 0

に対してある数

N

があって

N

より大きい任意の

n, m

に対して

| a

n

− a

m

| < e

となるとき、

Cauchy

列であるという。ここで２つの

Cauchy

列

{ a

_n

} , { b

_n

}

で

{ a

₁

, b

₁

, . . . , a

_n

, b

_n

, . . . }

が再び

(8)

Cauchy

列になるとき

{ a

n

} ∼ { b

n

}

とすると、これは同値関係になる。この同値類の全体として実数が定義

できる。

Dedekind

の実数と

Cauchy

の実数は同型であることが知られている。

Cauchy

の実数の定義から

は、実数の完備性が定義から直ちに成立することが保証される。

数の概念数の公理から、整数の加法、乗法の定義等を公理的に構成してみよう。

(

高木貞治「数の概念」より

)

ここでは、まず整数の集合

Z

を公理的に構成する。

(I) Z

は非空集合で、

Z

上の恒等写でない全単射写像

ϕ : Z → Z

が存在する。

(II) Z

の部分集合

M

上で

ϕ

が全単射になれば、M

= Z

である。

x

⁺

= ϕ(x), x

⁻

= ϕ

⁻¹ と書くことにする。M

⊆ Z

のとき

M

⁺

= { x

⁺

: x ∈ M } , M

⁻

= { x

⁻

: x ∈ M }

とする。これを使うと公理系は

(I) ϕ

は１対１対応で

Z

⁺

= Z

(II) ∅ 6 = M ⊆ Z

かつ

M

⁺

= M

ならば

M = Z

と書ける。

この公理系の枠組みで数学的帰納法の形は、

(1)

ある数

a

で命題

P(a)

が成立することを示す。

(2)

任意の

x

において、

P (x)

が真ならば

P (x

⁺

), P (x

⁻

)

が真になることを示す。

これから、任意の

x

で

P(x)

が成立すると結論するものである。ここで

M = { x ∈ Z : P (x)

が真である

}

とすると、(1)より

M

は非空でかつ

(2)

から

M = M

⁺

= M

⁻

.

公理から

M = Z

であるとわかる。ゆえに数学的帰納法が正しいとわかる。

Def. 1.4

数の集合

K

が

K

⁺

⊆ K

、つまり

x ∈ K

ならば

x

⁺

∈ K

であるとき、昇列であるという。また

a ∈ Z

に対して

a

を含むような昇列の全体の共通部分のなす昇列を

K(a)

と書く。

補題

1.1 M ⊆ L

ならば

M

⁺

⊆ L

⁺

. (Proof) ϕ

が写像であることから明らか。

¤

補題

1.2 K

が昇列ならば

K

⁺

, K

⁻ も昇列になる。

(Proof)

仮定から

K

⁺

⊆ K

ゆえに

(K

⁺

)

⁺

⊆ K

⁺すなわち

K

⁺ は昇列。

¤

命題

1.1 K(a

⁺

) = K(a)

⁺

, K(a

⁻

) = K(a)

⁻

(Proof) K(a

⁺

) = K(a)

⁺ を示す。定義から

a ∈ K(a)

、ゆえに

a

⁺

∈ K(a)

⁺

. K(a)

⁺ は昇列であるから、

昇列の定義より

K(a+) ⊆ K(a)

⁺

.

一方

a

⁺

∈ K(a

⁺

)

だから

a ∈ K(a

⁺

)

⁻

.

ここで

K(a

⁺

)

⁻ は昇列だから

K(a) ⊆ K(a

⁺

)

⁻ ゆえに

K(a)

⁺

⊆ K(a

⁺

).

これらをあわせると

K(a

⁺

) = K(a)

⁺

.

残りも同様。

¤

命題

1.2

ある数

a

に関して

K(a) = Z

ならば、任意の

x

で

K(x) = Z .

(Proof) M = { x | K(x) = Z}

とする。

a ∈ M

より

M 6 = ∅ . x ∈ M

つまり

K(x) = Z

とすると

K(x

^±

) = K(x)

^±

= Z

^±

= Z

ゆえに公理から

M = Z ¤

命題

1.2

により次の二つの場合のどちらかになると分かる。

(1)

すべての数

x

で

K(x) 6 = Z . [

無限列

]

(2)

すべての数

x

で

K(x) = Z . [

有限サイクル

]

(9)

加法の構成。加法は関数

x 7→ ϕ(x) = x

⁺ の反復として定義される。

x

に

a

を足す関数

x + a

の役割を果たす関数

F

a

(x)

を次のように導入する。まず、

ϕ

が次を満たすことに注意する。

ϕ(x

⁺

) = ϕ(ϕ(x)) = (ϕ(x))

⁺

Def. 1.5

数

Z

の中から任意にひとつの数を取り、それを記号

0

で表わす。さらに、

0 + = 1, 1 + = 2, . . .

と書くことにする。

定理

1.1

任意の

a

で、次の条件をみたす関数

F ( F(0) = a,

任意の

x

で

F(x

⁺

) = F (x)

⁺

(1.1)

が一意に存在する。これを

F

a

(x)

(Proof)

一意性。二つの関数

F (x), G(x)

がともに条件を満たしたとする。

F(x) = G(x)

となる数

x

の全体を

M

とする。

F (0) = G(0) = a

だから

0 ∈ M

で、

M

は非空。ある

x

で

F(x) = G(x)

であったとする。

F (x

⁺

) = F (x)

⁺

, G(x

⁺

) = G(x)

⁺ だから

F (x

⁺

) = G(x

⁺

).

同様に

F (x

⁻

) = F (x)

⁻

, G(x

⁻

) = G(x)

⁻ より

F (x

⁻

) = G(x

⁻

).

ゆえに数学的帰納法より

M = Z .

存在の証明。

a = 0, 1

の場合は

F

0

(x) = x, F

1

(x) = x

⁺ で自明。

a

に関する帰納法を使う。

F

a が存在したとして、F_a+

(x), F

_a−

(x)

の存在を示す。それには、

F

_a⁺

(x) = F

a

(x)

⁺

, F

_a−

(x) = F

a

(x)

⁻ と定義する。すると、

F

_a⁺

(0) = F

a

(0)

⁺

= a

⁺

F

_a⁺

(x

⁺

) = F

a

(x

⁺

)

⁺

= (F

a

(x)

⁺

)

⁺

= (F

_a⁺

(x))

⁺

となって、条件を満たす。

F

_a−

(x)

についても同様。よって数学的帰納法により任意の

a

で条件を満たす

F

_a

(x)

が存在する。

¤

Def. 1.6 F

a

(x) = x + a

今までに知られた事実

F

_a+

(x) = F

_a

(x

⁺

) = F

_a

(x)

⁺ を上の記法で書くと、

x + a

⁺

= x

⁺

+ a = (x + a)

⁺ 定理

1.2 (

交換律

) a + b = b + a

(Proof) G(a) = b + a = F

a

(b)

とおく。まず、

G(0) = F

0

(b) = b.

そして

G(a

⁺

) = F

_a+

(b) = F

_a

(b)

⁺

= G(a)

⁺ 故に定理

1.1

より

G(x) = F

b

(x).

ゆえに

b + a = G(a) = F

_b

(a) = a + b

¤

演習

1.2

次を示せ。

(1) 0 + a = a, a + 0 = a

(2) a + ( − a) = 0, ( − a) + a = 0

(10)

定理

1.3 (

結合律

) (a + b) + c = a + (b + c)

(Proof) φ(a) = (a + b) + c)

とおくと、

φ(0) = b + c

かつ

φ(a

⁺

) = (a

⁺

+ b) + c = (a + B)

⁺

+ c = ((a + b) + c)

⁺

= φ(a)

⁺ ゆえに、

φ(a) = a + (b + c).

ゆえに

(a + b) + c = a + (b + c). ¤

定理

1.4 (

引き算

)

任意の

a, b

に対して、次の式を満たす

x

が一意に存在する。

x + a = b

Def. 1.7 x + a = b

の解を

x = b − a

0 − a

を

− a

と略記する。

すると、

(b + ( − a)) + a = b + (( − a) + a) = b + 0 = b

だから引き算の一意性より、

b + ( − a) = b − a

とわかる。

乗法の定義。

定理

1.5 (

乗法

)

任意の数

a

に対して、次をみたす

x

の関数

f(x, a)

が一意に存在して定まる。

f (0, a) = 0, (1.2)

f (x

⁺

, a) = f (x, a) + a (1.3)

(Proof) (一意性) f (x, a), g(x, a)

がともに条件をみたすとする。x

= 0

で

f (0, a) = g(0, a) = 0. f (x, a) = g(x, a)

と仮定すると、

f (x

⁺

, a) = f (x, a) + a = g(x, a) + a = g(x

⁺

, a).

ゆえに

f (x

⁺

, a) = g(x

⁺

, a)

同様に

f (x

⁻

, a) = g(x

⁻

, a)

帰納法により

f = g

(

存在

)

略。

¤

次が成立する。

x · 0 = 0, 0 · x = 0, (1.4)

(x + 1)y = xy + 1, x(y + 1) = xy + x (1.5)

Def. 1.8

この

f (x, a)

を通常の記法として

xa

と書く。

定理

1.6 (

積の交換律

) xy = yx

(Proof) f (x) = yx

とする。上の

(1.4)

から

f (0) = 0 (1.5)

から

f (x

⁺

) = y(x + 1) = yx + y = f (x) + y

定理

1.5

より

f (x) = xy

つまり

yx = xy ¤

演習

1.3 (xy)z = x(yz) [結合律]

が成立することを示せ。

課題

1.1

ペアノの公理を出発点にとり、自然数から整数を構成し、そこで加法と減法を定義してその基本的な性質を証明してみよ。

(11)

2 ^順序と束

2.1

順序集合

Def. 2.1

半順序集合

P = (E, 6 )

とは、集合

E

とその上の２項関係

6

の組で、次の性質を満たすものである。

(1) x 6 x ( ∀ x ∈ E), [

反射的

(reflexive)]

(2) x 6 y, y 6 x ⇒ x = y, [

反対称的

(anti-symmetric)]

(3) x 6 y, y 6 z ⇒ x 6 z. [

推移的

(transitive)]

上の

(2)

を除いた条件で定義されるものを擬順序という。また、半順序集合がさらに

(4) ∀ x, y ∈ E

で

x 6

又は

y 6 x

の少なくとも一方が成立する。

を満たすとき、全順序という。もしくは線形順序とも言われる。

例

2.1 P

を人間の集合

E

上の親子関係とする。この

P

は反射的ではない。対称的でもない。推移的でもない。親子関係を、親子を含めた先祖－子孫関係とすると推移的になる。そこで関係

P

を拡張して

a ≺ b

となるのは

a = b

または

a

が

b

の祖先であるときとして定義するとこの関係

≺

は半順序関係になる。

例

2.2 (1)

正の整数の全体で、a

| b

を「

a

が

b

割り切る」という関係とするとこれは半順序になる。a, b が互いにどちらの約数にもならないときは、この２元は互いに比較不能である。

(2)

集合の包含関係も半順序になる。

(P, 6 )

を半順序集合とする。以下では、

P

が有限か局所有限、つまり任意の２元の間の鎖の長さが有限になる、ことを仮定する。

Def. 2.2 a 6 b

でかつ

a 6 c 6 b

ならば常に

a = c

または

c = b

が成り立つとき、つまり

a

と

b

の

”

あいだに入る元がない

”

とき、

b

は

a

をカバー

(cover)

する、

b

は

a

の直後にある、

a

は

b

の直前にある、という。

これを

x 6 · y

とも書く。

有限半順序集合は、図式にして表すと理解しやすい。直前直後の関係にある元の間に線を引き、半順序関係で大きい方のものを上のほうに書いて表した図を

Hassa

図という。

x

0

< x

1

< . . . < x

k

(x

i

∈ P )

となる元の列を鎖

(chain)

という。このとき

k

をこの鎖の長さという。

また、その中の任意の２元が比較不能であるような集合

A ⊆ P

を反鎖

(antichain)

という。この鎖の組と反鎖のサイズに関して次の最大最小定理が成立することがよく知られており、これは組み合わせ理論の中の

Max-min

型定理の代表的なもののひとつとである。

定理

2.1 (Dilworth

の定理) 有限な半順序集合で、全集合を被覆するのに必要な鎖の数の最小値は、反鎖

集合のサイズの最大値に等しい。

Def. 2.3

最小元

O

をもつ半順序集合において、任意の元

x

に対して最小元から

x

への極大鎖がすべて同じ長さを持つとき、Jordan-Dedekind鎖条件を満たすという。このときこの極大鎖の長さを

x

の高さと言い、

h(x)

と書く。特に最大元

I

が存在するときは、その高さを

P

の高さという。

例

2.3

ある数

a

が

b

を割り切るとき

a 6 b

と書くとする。

(

これは通常

a | b

と書かれる。

)

ある数

K

とその約数の全体はこの順序関係に関して、半順序集合になる。

また、整数全体の集合

Z

もこの関係に関して、半順序集合になる。これは無限集合の半順序集合の例である。

(

これは束にもなる。

)

(12)

例

2.4

正の整数

n

の分割とは、足して

n

になるような正の整数の組のことである。ひとつの分割

π

をさらに細分することにより分割

π

⁰ が得られるとき

π

⁰

6 π

とするとこれは半順序関係になる。例えば、

(1, 1, 1, 1, 1) 6 (2, 2, 1) 6 (3, 2) 6 (5)

となる。(これは束にもなる。

)

2.2

束

(lattice)

Def. 2.4 (P, 6 )

を半順序集合とする。その２元

x, y

に対して

x 6 z, y 6 z

となる

z

を共通上界という。

z 6 x, z 6 y

となるとき、共通下界という。共通上界の全体の中に最小元があるとき、これをこの２つの元

の結び

(join)

と言い

x ∨ y

と書く。共通下界の中に最大元が存在するとき、これを２つの元の交わり

(meet)

と言い、

x ∧ y

と書く。任意の

x, y

に対してその結びと交わり

x ∨ y, x ∧ y

がともに存在するとき、この半順序集合は束であるという。

結び

∨

と交わり

∧

を２項演算子とみなして、この２項演算子がみたすべき公理系から束を定義することもできる。このときもっとも基本的な次の関係がその二つを結びつける。

a 6 b ⇐⇒ a ∧ b = a ⇐⇒ a ∨ b = b

Def. 2.5 L

が最小元

O

を持つとき、

O

をカバーする元を原子

(atom)

と言う。

Def. 2.6

束

L

の部分集合

M

が部分束であるとは、

M

がもとの集合

L

の

∨

と

∧

に関して閉じていることである。

Def. 2.7

元

x, y (x 6 y)

に対して、集合

[x, y] = { z ∈ L | x 6 z 6 y }

を区間という。区間は、部分束の特別な場合である。

ここでは、簡単のため特に断らない限り「束はすべて有限束である」とする。

束の種類として、主なものとして次のようなものがある。

•

分配束

(distributive lattices)

•

モジュラー束

(modular lattices)

• (semimodular lattices

•

幾何束

•

ブール代数

クラスの包含関係は次のようになっている。

⊃

モジュラー束

⊃

分配束

⊃

ブール代数

2.3

分配束

Def. 2.8

束が次の分配律

x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) (2.1)

x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) (2.2)

を満たすとき、分配束という。

(13)

分配束の部分束は分配束になる。分配束の直積は再び分配束になる。鎖は常に分配束である。サイズが

n

の集合

S

の部分集合の全体が包含関係に関してなす束は、

Boole

代数

B(n)

と呼ばれる。これは、長さ１の鎖

n

個の直積なので、特に分配束になる。さらに、集合の合併と交差に関して閉じている集合族は、Boole 代数の部分束になり、特に分配束になる。

Def. 2.9 L

の元

p 6 = O

が既約元

(join-irreducible)

であるとは、

p = a ∨ b = ⇒ p = a or p = b

補題

2.1 p

が分配束の既約元とする。すると、

p 6 a

₁

∨ . . . ∨ a

_k

⇒ ∃ i p = a

_i

(Proof)

分配律より

p = p ∧ ( W

k

i=1

a

i

) = W

k

i=1

(p ∧ a

i

)

ゆえにある

i

で

p = p ∧ a

i つまり

p 6 a

i

. ¤

原子は自明に既約元であり、

{ p

₁

, p

₂

, . . . }

が原子の集合であれば

p

₁

< p

₁

∨ p

₂

< p

₁

∨ p

₂

∨ p

₃

< . . .

はどの２つの元も異なる上昇列になる。

補題

2.2 L

を最小元

O

をもつ分配束とする。

O

以外の任意の元

a

は

join-ireducible

な元のある組

p

₁

, p

₂

, . . . , p

_k の結び

a = p

1

∨ p

2

∨ . . . , ∨ p

k として一意に分解できる。これから

P (a) = { p

1

, . . . , p

k

} , P (0) = ∅

とおく。

(Proof) a

が分解できなればそれ自身が既約であり、分解をできる限り続ければ結局、既約元の結びに書け

ることは明らか。一意性を示す。

a = p

1

∨ . . . ∨ p

k

= q

1

∨ ∧ ∨ q

m

とする。任意の

i

で

p

_i

6 q

₁

∨ . . . ∨ q

_m だから補題

2.1

よりある

j

で

p

_i

6 q

_j

.

同様にある

h

で

q

_j

6 p

_h

.

ゆえに

p

i

= q

j

.

これを繰り返せば

{ p

i

}

と

{ q

j

}

が集合として一致することが分かる。

¤

分配束の元

a ∈ L

に対して定まる

P (a)

は半順序集合

P

の中の反鎖になっている。

Def. 2.10 poset P

の部分集合

I

がイデアルとは、

x ∈ I

かつ

y 6 x = ⇒ y ∈ I.

イデアルの補集合をフィルターという。つまり、フィルターは双対束のイデアルのことである。ひとつの元で生成されるイデアルを主イデアル

principal ideal

という。

P

のイデアルの全体

I(P )

は集合の合併と交わりについて閉じているので分配束になる。I(P

)

の既約元

(join-irreducible)

は、

P

の

principal ideal

になる。

定理

2.2 (Birkhoﬀ,

分配束の表現定理

) L

を有限な分配束で、その

join-irreducible

元の全体を

P

とする。

このとき、つぎの同型射

φ : a 7→ I(a) = { p ∈ P | p 6 a } (a ∈ L)

のもとで同型

L ∼ = I(P )

が成立する。

逆に、Iは分配束になり、その既約元の全体は半順序集合として

P

に同型になる。特に、

L

が有限ならば、

L ∼ = I

である。

(14)

(Proof)

補題

2.2

より各元

a

は

I(a)

中の既約元の結びとして一意に書けるので、

φ

は単射である。

I ∈ I(P )

として

b = sup I

とすると

I ⊆ I(b).

しかし各

p ∈ I(b)

に対して

p 6 sup I

ゆえに補題

2.1

より

p ∈ I.

結局

P

の有限なイデアルは

I(a)

のかたちになり、ゆえに

φ

は全射でもある。L 中で

a 6 b

ならば

I(a) ⊆ I(b)

は明らか。逆に

I(a) ⊆ I(b)

ならば

a = sup I(a) 6 sup I(b) = b.

ゆえに

φ

は束の同型射になる。また、分配束

I(P)

の中の元、つまり

P

のイデアル、は空集合であるか、主イデアル

I(a) (a ∈ P)

である。

¤

系

2.1

有限分配束において、その

join-irreducible

元の全体の半順序集合

P

と

meet-irreducible

元の全体のなす半順序集合

Q

は同型である。

(Proof) ¤

定理

2.3

最小元

0

を持つ分配束は、ある

Boole

代数の部分束に同型になっている。

2.4

モジュラー束

Def. 2.11

モジュラー束。任意の

x, y, z

について

x 6 y

ならば

(z ∨ x) ∧ y = (z ∧ y) ∨ x

区間

[a ∧ b, a]

と

[b, a ∨ b]

との間の写像を次のように定義する。

φ

_b

: [a ∧ b, a] → [b, a ∨ b], z 7→ z ∨ b

ψ

a

: [b, a ∨ b] → [a ∧ b, a], z 7→ z ∧ a (2.3)

命題

2.1

束

L

がモジュラーであるための必要十分条件は、任意の

a, b ∈ L

で

φ

_b

, ψ

_aが

[a ∧ b, a]

と

[b, a ∨ b]

の間の同型射になり、かつ互いに逆写像になることである。

Def. 2.12

区間

[a ∧ b, a]

と

[b, a ∨ b]

は互いに転置であるという。区間

I, J

に対して区間の列

I = I

1

, I

2

, . . . , I

k

= J

があって隣り合うどの二つも互いに転置になっているとき、

I

と

J

は射影的であるという。

系

2.2

モジュラー束の中で、射影的な区間は互いに同型であり、かつこの逆も私立する。

命題

2.2

束がモジュラー束であるための必要十分条件は、

N

₅に同型な部分束を含まないことである。

命題

2.3

束が分配束であるための必要十分条件は、

N

₅または

M

₅に同型な部分束を含まないことである。

2.5 Def. 2.13

(semimodular lattice)。

a ∧ b < · a = ⇒ b < · a ∨ b

下半セミモジュラー束。

b < · a ∨ b = ⇒ a ∧ b < · a

セミモジュラーかつ下半セミモジュラーであれば、モジュラーになり、かつその逆も成立する。

補題

2.3

セミモジュラー束は、

Jordan-Dedekind

条件を満たす。

(15)

定理

2.4 L

が最小元

0

をもつ束とする。このとき、

L

がセミモジュラーであれば、その階数関数

r

は以下を満たすし、その逆も成立する。

r(x ∧ y) + r(x ∨ y) 6 r(x) + r(y)

また、

L

がモジュラーであるための必要十分条件は、上で常に等号が成立することである。

例

2.5 (1)

束

S

7

= {∅ , { 1 } , { 2 } , { 1, 2 } , { 1, 3 } , { 2, 3 } , { 1, 2, 3 }}

はモジュラーでないセミモジュラー束の最小のものである。モジュラー束がセミモジュラーになるための必要十分条件は、

S

₇ を区間

(

部分束

?)

として含まないことである。

(2)

サイズが

3

より大きい集合の分割束

P (n) (n > 3)

はセミモジュラーだが、モジュラーにならない。

Def. 2.14 2

^S 上の写像

σ

が以下を満たすとき、閉包作用素という。

(1) A ⊆ σ(A),

(2) A ⊆ B = ⇒ σ(A) ⊆ σ(B), (3) σ(σ(A)) = σ(A).

A = σ(A)

のとき

A

を閉集合と呼ぶ。閉集合の全体は次の演算で束になる。

A ∧ B = A ∩ B, A ∨ B = σ(A ∩ B)

さらに、

σ

が次の

Steinitz

交換公理を満たせば、閉集合の全体はセミモジュラー束になる。

p 6∈ σ(A), p ∈ σ(A ∪ q) = ⇒ q ∈ σ(A ∪ p)

例

2.6

このような閉包作用素から与えられるセミモジュラー束として、

(1) division ring

上のベクトル空間

V

上で

A ⊆ V

に対して

A

の張る線形部分空間を

< A >

とすれば、

これは

Steinitz

の交換公理を満たす閉包作用素である。ゆえに、この閉集合の全体、つまり

V

の線形

部分空間の全体はセミモジュラー束になると分かるが、さらに階数関数がモジュラー等式を満たすので、モジュラー束になっている。

(2)

体

F

が体

K

の拡大体であるとき、各

A ⊆ F

に対して

K

上

A

に代数的に従属な元の全体を加える操作は、上の閉包作用素の交換公理をみたす。

Def. 2.15

束

L

の任意の元

a ∈ L

が

a

以下の

atom

の全体の

join

に同じになるとき、L は

atomic

又は

point lattice

と呼ばれる。

例

2.7

上の例のような閉包作用素で定義される束は

point lattice

になる。つまり、次で述べる幾何束になる。

2.6

幾何束

Def. 2.16 atomic

なセミモジュラー束で無限長の鎖を含まないものを、幾何束

(geometric lattice)

という。

命題

2.4

マトロイドの閉集合

(flat, closed set)

の全体は幾何束をなす。

Def. 2.17

射影平面又は射影幾何とは、集合

P

とその部分集合の族

G

で以下を満たすもののこと。Pの元

は点、

G

の元は直線と呼ばれる。

(16)

(i)

どの２つの点に対してもそれらを含む直線がちょうどひとつある。

(ii)

点

P, Q, R

が同一直線上になく三角形をなすととする。ある直線

L

がその３辺の直線の内２本と交わ

れば、残りの１本とも交わる。

(iii)

書く直線は互いに異なる点を少なくとも２つ持つ。

(iv) P

の次元は有限である。

この

(P, G)

を射影空間という。特に次元が２の射影空間は、射影平面と呼ばれる。

Def. 2.18 division ring K

上の

n-

次元ベクトル空間

V (n, K )

を考える。

V

の階数１の部分空間を点、階数２の部分空間を直線とする射影空間を、次元

n − 1

の射影幾何学

P G(n − 1, K )

と呼ぶ。

命題

2.5

射影空間

(P, G)

の部分空間全体

L(P, G)

はモジュラーな幾何束になる。

逆に、モジュラーな幾何束は射影空間で構成できる。

定理

2.5 (Birkhoﬀ )

モジュラー幾何束は、射影空間の束

L(P, G)

の直積になる。

定理

2.6

分配的な幾何束は

Boole

代数にほかならない。

Def. 2.19

相補束。束が

0, 1

を持ち、任意の元

a

に対してその補

a’

が存在して

a ∧ a

⁰

= 0, a ∨ a

⁰

= 1

となるとき、相補束であるという。またその中の任意の区間が相補束になるとき、相対相補束という。

命題

2.6

有限なセミモジュラー束が幾何束であるための必要十分条件は、それが相対相補束であることである。

(17)

3 ^{グラフ理論} : ^{諸定義、平面グラフ}

3.1

グラフとは

• Def.

有向グラフ

G = (V, E)

とは：

V

は有限集合、V の元は点と呼ばれる。E

⊆ V × V

は辺集合と呼ばれる。各辺

e = (u, v) ∈ E

に対して

u

は始点、

v

は終点という。

有向グラフの辺集合

E

は点集合

V

上の関係にほかならない。

• Def.

無向グラフとは：G=(V, E)で、Vは点集合と呼ばれる有限集合、Eは辺の集合。ここで辺とは

V

の２点からなる集合

{ u, v }

のことである。

•

グラフと呼ぶゆえんは、点を描いてそれを向きのついた辺で結ぶという幾何学的イメージを使うから。

この観点からはグラフは関係の幾何学的表現とみなせる。このほかにトポロジーでの１次元としてのグラフ、平面・局面上に実現されたグラフなど。

•

グラフで表現できるシステム

システム点点

i

と

j

を結ぶ辺

(i, j)

の意味

電気回路端子端子と端子を結ぶ素子

道路網、鉄道網都市、駅都市を結ぶ道路、駅を結ぶ路線ガス、水道などの供給網源流点、分岐点、供給点パイプラインで結ばれた点

ひとつの分子構成原子原子間の化学結合

ゲームコマの配置配置

i

から

j

へ１手で到達できるとき

会社組織社員

i

が

j

の上級管理者である

国家経済財とサービス

i

が

j

の生産に必要である

計算機プログラム命令

(実行文) i

の実行の後にすぐ

j

の実行ができるとき階層的ファイルシステムディレクトリ、ファイルディレクトリ

i

が

j

の親ディレクトリ凸多面体頂点頂点

i, j

が隣接しているとき

斉次方程式変数変数

j

を定める方程式中に

i

が独立変数として表れる

3.2

グラフの基本的な諸概念

• G = (V, E)

が単純無向グラフであるとき、その補グラフ

G = (V, E

⁰

)

とは同じ点集合上のグラフで

uv ∈ E

⁰

⇔ uv 6∈ E

で辺が定まる無向グラフである。自明に補グラフの補グラフはもとのグラフに一致する。

•

部分グラフ、誘導部分グラフ：

•

セルフループ、並列辺、単純グラフ：

•

特殊なグラフのクラス：完全グラフ

K

n、完全２部グラフ

K

m,n

•

点の次数、正則グラフ：例正多面体の頂点グラフは正則グラフ。

•

道

(

路、

path)

：

(u

0

, e

1

, u

1

, e

2

, . . . u

n−1

, en, u

n

)

となる点と辺の列で、各

i

で

e

i

= { u

i−1

, u

i

} ∈ E(G)

となりかつ同じ点を重複して含まないもののこと。

•

閉路

(circuit)

：始点と終点が一致する道のこと。

•

点集合

V

のふたつの非空集合への分割

(V

1

, V

2

)

をカットという。カットの異なる点集合を結ぶ辺の全体

c(V

₁

, V

₂

) = { e = uv | u ∈ V

₁

, v ∈ V

₂

}

が非空であるときこれをカットセットと呼ぶ。

(18)

•

グラフが連結であるとは：任意の２点についてそれを結ぶ道がある。

•

グラフの連結成分、孤立点：

•

木森とは：

•

グラフの木、グラフの全域木、全域森：

全域森のサイズ

=

点集合のサイズ

−

連結成分の数

•

２部グラフとは：点集合

V (G)

が２つの非空集合

V

₁

, V

₂ に分割されて、同じ成分

V

_i に含まれるどの２つの点の間に辺が存在しないこと。このとき

２部グラフである

⇔

奇数長の閉路を持たない

⇔

２彩色可能

•

オイラー路、オイラー閉路とは：

グラフにオイラー路、オイラー閉路が存在するための必要十分条件：

•

ハミルトン路、ハミルトン閉路とは：

ハミルトングラフ：ハミルトン閉路の存在するグラフ例ハミルトン閉路の存在する例、存在しない例演習

3.1

次の問に答えよ。

(1)

単純グラフで

min { deg(v) : v ∈ V } > k

であれば、長さ

k

以上の道が存在することを示せ。

(2)

連結グラフに最大長の道が二つあれば、それらは少なくとも１点で交わることを示せ。

(3)

グラフ

G

の直径とは、その中の２点の距離の最大値を言う。すると、次が成立することを示せ。

G

の直径

> 3 ⇐⇒ G

の直径

< 3

(4)

連結グラフ

G

が

m

本の辺を持つとき、各点を一度ずつ以上通る長さ

2m

以下の閉路が存在することを示せ。

(5) ( Minty

のぬり分け定理

) G

を有向グラフ、

(s, t)

をその辺とする。辺

(s, t)

を黄色にぬり、そのほかの辺を緑、赤、黄色に任意に彩色したとすると次のいずれか一方そして一方だけが必ず成立することを示せ。

a)

黄色辺、緑色辺からなり辺

(s, t)

を含む有向閉路があって、その閉路の上ではすべての黄色辺が同じ向きに並んでいる。

b)

黄色辺、赤色辺からなり辺

(s, t)

を含むカットセットがあって、そのカットセットの上で黄色の辺はすべて同じ向きになっている。

(6) G

を有向グラフとする。

M

をその辺

—

点接続行列、

N

を点

—

点隣接行列とすると、以下が成立することを示せ。

M · M

^T

= diag(d(u

1

), d(u

2

), . . . , d(u

n

)) − N

ここで、

diag(d(u

1

), . . . , d(u

n

))

は各点の次数を対角成分にもつ対角行列である。

(19)

3.3

基本カットセット行列、基本サーキット行列

Def. 3.1 G = (V, E )

を連結な有向グラフとする。向きを定めてある閉路

C ⊆ E

に対して以下で定まるベクトルを、その向きのついた特徴ベクトルと呼ぶ。

ξ(C) ∈ R

^E

, ξ(C)

_e

=

⎧ ⎪

⎨

⎪ ⎩

1 e

が順向きに

C

に含まれる

− 1 e

が逆向きで

C

に含まれる

0

それ以外

カット

(V

1

, V

2

)

に伴うカットセット

D

に対してその向きのついた特徴ベクトルも以下のように同様に定義される。

η(D) ∈ R

^E

, η(D)

_f

=

⎧ ⎪

⎨

⎪ ⎩

1 f = uv, u ∈ V

1

, v ∈ V

2

− 1 f = uv, u ∈ V

1

, v ∈ V

2

0

それ以外

Def. 3.2 G

のすべてのカットセットの向きのついた特徴ベクトル全体を行ベクトルとして持つ行列を

P

all

と書き、

G

のカットセット行列と呼ぶことにする。サーキットの向きづけられた特徴ベクトルの全体を行ベクトルとして持つ行列を、Q_all と書き

G

のサーキット行列と呼ぶ。

G

の全域木

T ⊆ E

に関して定義される

(

基本

)

閉路の向きのついた特徴ベクトルの全体を行ベクトルとして持つ行列を

Q

_T を

T

に対する基本サーキット行列という。補木

T ˜ = E \ T

に対する基本カットセットの向きのついた特徴ベクトル全体のなす行列を

P

T˜ と書き、基本カットセット行列と呼ぶ。

補題

3.1

全域木

T

とその補木

T ˜ = E \ T

に対して、

T ˜

に対する基本カットセット行列が

P

T˜

=

⎡

⎢ ⎢

⎣ 1

. .. N

1 ⎤

⎥ ⎥

⎦

であるとき、

T

に関する基本サーキット行列は次になる。

Q

_T

=

⎡

⎢ ⎢

⎣

1 −

^t

N . ..

1 ⎤

⎥ ⎥

⎦

任意のサーキットベクトル

ξ(C)

とカットセットベクトル

η(D)

に対し

< ξ(C), η(D) >= 0

だから

Q

_T^t

P

T˜

= 0, Q

_all^t

P

_all

= 0

また自明に

rank(P

T˜

) = | T | , rank(Q

T

) = | E \ T |

n = | T | + | E \ T |

だから、P_T_˜ の行ベクトルの張る空間と

Q

_T の行ベクトルの張る空間は

R

^E 中で互いに直行補空間になる。特に

P

all の行の張る空間は

P

T˜ の行空間に、

Q

all の行ベクトルの張る空間は

Q

T の行空間に一致する。

基本カットセット行列

P = (p

ve

)

に対してそれを

GF (2)

上の値の行列と見なしたものを

P ˆ

とする。つまり

p ˆ

_ve

≡ p

_ve

(mod 2)

で定める。

システム理論Ⅱ ( 離散システム論 )