曲面上のグラフの Krushkal 多項式

(1)

曲面上のグラフの Krushkal ^多項式

山村瑠納

(

奈良女子大学

)^∗¹

村井紘子

(

奈良女子大学

)^∗2

概要

2011^年，V. Krushkal[3]が向き付け可能な曲面に埋め込まれたグラフの不変

量であるKrushkal多項式を定義し，これは2018年，C. Butler[1]により向き付け不可能な曲面に対して拡張された（：一般化されたKrushkal^{多項式と呼} ぶ）．（一般化された）Krushkal^多項式はTutte^多項式[4]^{と同様の双対性や，}

グラフの辺の消去と縮約に関する再帰的な性質をもつこと，またKrushkal多

項式からTutte多項式を復元できることが示されている．さて，2^{つの抽象グ}

ラフのone-point join^{で表されるグラフの}Tutte^{多項式は元のグラフの}Tutte^多項式の積で表されることが知られている([2])が，本稿では曲面に埋め込まれたグラフに対してone-point join^{を定義し，}Tutte^{多項式と同様に，}2^つの曲面上のグラフのone-point join^{で表されるグラフの}Krushkal^{多項式は元のグラ}

フのKrushkal多項式の積で表されることを示す．

1.

グラフの基本事項

本研究では

, 2

つの頂点を結ぶ辺が

2

本以上ある多重辺も許し，同じ頂点同士を結ぶ辺

(

ループ

)

の存在を許した一般グラフを扱う

.

正確には次の通りとする．

定義

1.1.

一般グラフ

(general graph),

又は単にグラフ

(graph)G

とは

,

対

(V(G), E(G))

のことをいう

.

ここで

,V(G)

は頂点

(vertex)

と呼ばれる元から成る空でない有限集合であり

, E(G)

は

V(G)

の

(

必ずしも相異なるとは限らない

)

元の非順序対の有限な族である

とする

. E(G)

の元は辺

(edge)

と呼ばれる

.

ただし

,

複数個の同じ元が入っていても良い

集まりを「族」と呼んで

,

「集合」とは区別することにする

. E(G)

は「族」であるから

,

複数個の同じ辺

(

これを多重辺という

)

があっても良いことに注意する

. V(G)

を

G

の頂点集合といい

, E(G)

を

G

の辺族と呼ぶ

. v, w ∈ V(G)

に対し

,{v, w} ∈ E(G)

であ

るとき

,

辺

{v, w}

は頂点

v

と

w

を結ぶ

(join)

といい

, vw

と略記する

.

頂点

v, w

のことを

辺

vw

の端点と呼ぶ

.

定義

1.2.

グラフ

G

の辺のうち

,

頂点

v

とそれ自身を結ぶ辺

vv

のことをループ

(loop)

という

.

また

,

その辺を消去すると

G

の連結成分が増えるような辺を橋

(bridge)

という

.

通常

,

グラフを図で表すときには

,

各頂点

v ∈ V(G)

に対して点を

1

つ描き

, 2

つの頂点

v, w∈V(G)

に対し

,{v, w} ∈E(G)

のとき

, v

に対応する点と

w

に対応する点を線で結ぶ.

定義

1.3.

グラフ

G

に対し

,G

の頂点の個数を

v(G),

辺の本数を

e(G),

連結成分数を

c(G)

で表す

.

また

,n(G) = e(G)−v(G) +c(G)

とし

,n(G)

を

G

の

nullity

という

.

定義

1.4.

グラフ

G

に対し

,V(H)⊆V(G), E(H)⊆E(G)

となるようなグラフ

H

を

G

の部分グラフ

(subgraph)

といい

,

特に

V(H) =V(G)

となるとき

,

グラフ

H

を

G

の全域部分グラフ

(spanning subgraph)

という

.

∗1〒630-8506奈良市北魚屋西町奈良女子大学大学院人間文化研究科

∗2〒630-8506奈良市北魚屋西町奈良女子大学研究院自然科学系

e-mail:[email protected]

(2)

定義

1.5. 2

つのグラフ

G, H

に対して

, V(G)

から

V(H)

への全単射

f

が存在して

xy ∈ E(G)⇔ f(x)f(y)∈ E(H)

を満たし，多重辺に関してはその本数まで込めて対応がつくときに

G

と

H

は同型であるという

.

以下では同型なグラフは同じと見なす．定義

1.5

からも分かるように

,

グラフを図で表すときに点や線がどのように描かれているかは関係なく

,

大切なのはどの頂点の組が何本の辺で結ばれているかという情報だけである

.

定義

1.6. G

をグラフとし

,e∈E(G)

とする

. G\e = (V(G), E(G)\ {e})

と定め，

G\e

を

G

から辺

e

を消去して得られるグラフという

.

また

, G

から辺

e

の端点を同一視して

e

を消去して得られるグラフを

G/e

で表す

. G/e

を

G

から

e

を縮約して得られたグラフという

.

定義

1.7.

グラフ

G₁, G₂

に対し

,V(G) = V(G₁)∪V(G₂), E(G) = E(G₁)∪E(G₂)

となるようなグラフ

G= (V(G), E(G))

を

G=G₁∪G₂

と表す

.

特に

,V(G) = V(G₁)∩V(G₂)

＝

∅

のとき

,G=G₁⊔G₂

と表す

.

定義

1.8. G₁, G₂

を互いに

disjoint

なグラフとする.

v₁ ∈ V(G₁), v₂ ∈ V(G₂)

に対し,

G₁ ∪ G₂

から

v₁, v₂

を同一視して得られるグラフを

G = G₁ ∗

v1=v2

G₂

で表し

, G₁

と

G₂

の

v1, v2

における

one-point join

という

.

より正確に述べると

, G = G1 ∗

v1=v2

G2

はその頂点集合が

, V(G) = (V(G₁)\ {v₁})∪ (V(G₂) \ {v₂})∪ {v_o}(

ただし

, v_o

はこの操作で生まれた新しい頂点で

, v_o ∈/ V(G₁)∪V(G₂)

である

.),

その辺族が

, E(G) = {vw ∈ E(G1)∪E(G2)|{v, w} ∩ {v1, v2} =∅} ∪ {vow|v1w ∈ E(G1)

または

v2w∈ E(G2)}

であるようなグラフである

.

例

1.1.

グラフ

G₁, G₂

とその頂点

v₁, v₂

を図

1

の左図の通りとすると，

G₁

と

G₂

の

v₁, v₂

における

one-point joinG₁ ∗

v1=v2

G₂

は図

1

の右図のようになる．

図

1: one-point join

の構成

2.

^{曲面上のグラフ}

この節では曲面に埋め込まれたグラフを取り扱う

.

定義

2.1. Σ

を曲面とする.

Σ

上に, 辺同士はその端点でのみ交わるように埋め込まれ

たグラフのことを曲面上に埋め込まれたグラフ

,

または曲面上のグラフといい

, G = (V(G), E(G))⊂Σ

または

G

の

Σ

への埋め込み写像

i

を明記して

(G,Σ, i)

で表す

.

曲面上

のグラフと区別するために

, 1

節で定義した埋め込む前のグラフを抽象グラフとも呼ぶ

.

定義

2.2. (G₁,Σ₁, i₁)

と

(G₂,Σ₂, i₂)

を曲面に埋め込まれたグラフとする

. Σ₁

から

Σ₂

への

(Σ₁

が向き付け可能な曲面のときは向きを保つ

)

同相写像

h

が存在して

h(G₁) =G₂

を満

たし

,h

の

G₁

への制限

h|G1 :G₁ →G₂

が抽象グラフとしての同型となるものが存在す

るとき

,(G₁,Σ₁, i₁)

と

(G₂,Σ₂, i₂)

は同値であるといい

,(G₁,Σ, i₁) = (G₂,Σ, i₂)

と書く

.

(3)

定義

2.3.

平面

R²

に埋め込むことのできるグラフを平面的グラフ

(planar graph)

といい

,

埋め込み写像

i

によって平面に埋め込まれたグラフ

(G,R², i)

を平面グラフ

(plane graph)

という

.

定義

2.4.

平面グラフ

(G,R², i)

に対し

,G

の辺で囲まれた連結な領域および外側の開い

た領域を

G

の面

(face)

という．G の各面に新たな頂点を対応させ

, G

の各辺に対し

,

辺

の両側にある新たな頂点同士を

G

の辺を横切るように結んで得られる平面上のグラフを

(G,R², i)

の

dual

といい

,G^∗

で表す

.

定義

2.5.

平面的グラフ

G

に対し

,

その平面への埋め込み写像

i

を

1

つ固定することにより

, i(G)

の

duali(G)^∗ ⊂R²

が定まる

.

この

i(G)^∗(

または

, i(G)^∗

に対応する抽象グラフ

)

を

G

の

dual

とも呼び

,

同じ記号

G^∗

で表す

.

注意

2.1.

グラフの

dual

は埋め込み

i

のとり方に依存する

.

例えば

G

を図

2

上図の平面的グラフとし

,

その

2

つの埋め込み

i₁, i₂

を図

2

下図の黒の実線のように定めると

,

それらの

duali₁(G)^∗, i₂(G)^∗

はそれぞれ赤の点線のグラフとなり，これらは同型ではない

.

G

( , , )G R i1

2 とそのduali₁( )G₁^* ( , , )G R²i2とそのduali₂( )G2^*

図

2: dual

が一意的でない例

定義

2.6.

コンパクトで境界のある向き付け可能とは限らない曲面

R

＝

(DV,DE)がリボン

グラフであるとは

,

以下の条件

1∼4

を満たす

2

種類の円板の集合

DV ={D₁, D₂, . . . , D_m}, DE ={d₁, d₂, . . . , d_n}

が存在して

,R =D₁∪ · · · ∪D_m∪d₁∪ · · · ∪d_n

となるときにいう

.

1. DV

の各元

D_i,

および

DE

の各元

d_j

は円板と同相である

.

2.

任意の

i∈ {1· · ·m}, j ∈ {1· · ·n}

に対し,

D_i∩d_j

は互いに交わらないいくつかの線分から成る

.

3. 2

の各線分

r

に対し

, r = ∂Di∩∂dj

を満たす

Di ∈ DV

と

dj ∈ DE

の組

(Di, dj)

がただ

1

つ存在する

.

4. DE

の各元

d_j

は

2

の線分をちょうど

2

つ含む

.

注意

2.2.

リボングラフ

R = (DV,DE)

が与えられると

, R

に対応する抽象グラフ

G = (V(G), E(G))

が次のように自然に定まる

. R = (DV,DE)

をリボングラフとする

. DV

の各元

D_i

に対し

, 1

つの頂点

v_i

を対応させ

,

これを

V(G)

の元とする

.

定義

2.6

の条件

4

(4)

と条件

3

により

, DE

の各元

d_j

に対し

, ∂D∩∂d_j ̸=∅

となる

D ∈ DV

がちょうど

2

つ存在する

.

このような

D

につけられている添字

(

ここでは

,k

と

l

とする

)

を用いて

,{v_k, v_l}

を

G

の辺とすることにより

,

抽象グラフ

G = (V(G), E(G))

が定まる

.

よって

,

リボングラフの

DV

を頂点集合

,DE

を辺族とよび

,

頂点

,

辺などの抽象グラフに対する用語や

R = (V(R), E(R))

等の記法を流用することにする

.

なお

,

抽象グラフは

,

リボングラフの頂点円板の境界に現れる辺円板の順などの貼り合わせに関する情報は持たないため

,

この対応は単射ではない

.

例

2.1.

図

3

はリボングラフ

(

左

)

と

,

それに対応する抽象グラフ

(

右

)

の例である

. Di

が

vi

に

,d_j

が

e_j

にそれぞれ対応している

.

D₁ D₂

d

1

2

3

v

v v

1 2

e e

e

1 2

3

図

3:

リボングラフと抽象グラフ

注意

2.3.

曲面上のグラフ

G⊂Σ

に対し

,G

の

Σ

における正則近傍をとると

,

リボングラフが得られる

.

注意

2.2

で述べたように

,

リボングラフは抽象グラフにはない

,

辺円板がどのように頂点円板につながるか

,

という情報を持つ

.

この情報を保ったまま簡素化した表現が次に述べる

arrow presentation

である.

定義

2.7.

いくつかの円板の境界に

marking arrow

と呼ばれるラベル付きの矢印が付けられたものを

arrow presentation

という

.

ただし

,

各ラベルをもつ

marking arrow

はちょうど

2

本ずつあるものとし

, marking arrow

同士は互いに交わらないものとする

.

リボングラフ

R = (DV,DE)

が与えられると,

DE

の各元

d_j

に対し, その境界に適当に向きを入れ

, d_j

が

R

の頂点円板と交わるところに

∂d_j

の向きに合うように向きを付けた矢印をおき

,dj

とラベルをつけることにより

,

対応する

arrow presentation

が

1

つ決ま

る

.

逆に

arrow presentation

が与えられると

,

次のように対応するリボングラフが

1

つ決

まる

.

あるラベル

d_j

が付けられた

2

つの

marking arrow

に対し

, 1

枚の円板

d_j

を用意し

,

∂dj

に任意に向きを入れる

.

次に

∂dj

上に互いに交わらない

2

つの弧をとり

,

それらの弧

と

marking arrow

を向きが合うように同一視する

.

全ての

marking arrow

に対してこの操

作を行うと

,

これらの円板

d_j

を辺としてもつリボングラフが得られる

(

図

4).

R

d_j d_j d_j

arrow presentation

図

4:

(5)

定義

2.8. R

をリボングラフとし

, A ⊂ E(R)

とする

. R

の各辺に任意に向きをつける（この向きはリボングラフ全体の向きに拡張しなくて良い

) .

全域リボン部分グラフ

(V(R), A)

は自然に

R

に埋め込まれていると考えることができ，その境界成分は

,R

の

辺と互いに交わらない弧で交わる

.

この各弧に対し

,

それが乗っている辺から決まる向きを入れ

,

その辺のラベルを付ける

.

このようにして得られる

arrow presentation

に対応するリボングラフを

R

の

A

に関する

partial dual

と呼び

,R^δ(A)

で表す

.

例

2.2.

図

5

は

,

定義

2.8

に沿って

R

の

A⊂ E(R)

に関する

partial dualR^δ(A)

を構成する方法を示している

.

リボングラフ

R

を図

5−a

とし

,A={1,3}

とする

.

図

5−b

の青のグラフは全域リボン部分グラフ

(V(R), A)

を表しており

,

その境界成分と

R

の辺と共通部分

(

赤い弧

)

に向きとラベルを与えたものである

.

図

5−c

は得られた

arrow presentation,

図

5−d

はそれを整えたもの

,

図

5−e

は対応するリボングラフ

R^δ(A)

を表す

.

a.

(各辺に向きを⼊れた) A={1,3}のときの

(V( ),A)⊂

R R R

5 5

3 2 1 1 4

3

2 4

d.

A={1,3}のときのを表すarrow presentation^δ(A) e.

リボングラフ ^δ(A) R

R

図

5: partial dual

の構成

注意

2.4.

リボングラフ

R

のある辺

e

に関する

partial dual

は局所的には表

1

のようにな

る

. e

がループでないとき

,

向き付け可能なループのとき

,

向き付け不可能なループのと

(6)

きのそれぞれで取り扱いが異なる

.

表

1:

リボングラフの

partial dual

辺の種類

R R^δ(e)

ループではない

^e

向き付け可能なループ

e

向き付け不可能なループ

曲面上のグラフに対する

2

つの操作

(

辺の消去と辺の縮約

)

を導入する

.

まずリボングラフに対して定義する

.

定義

2.9. R

をリボングラフとし

,e

を

R

の辺とする

. R\e := (V(R), E(R)\e)

と定め，

R\e

を

R

から辺

e

を消去することによって得られるグラフという

.

また，

R/e:=R^δ(e)\e

と定め，

R/e

を

R

から辺

e

を縮約することによって得られるグラフという

.

注

2.4,

表

1

より

,

リボングラフ

R

を

e

で縮約することによって得られるグラフは表

2

のように表されることがわかる

.

表

2:

リボングラフの縮約

辺の種類

R R/e=R^δ(e)−e

ループではない

^e

向き付け可能なループ

e

向き付け不可能なループ

(7)

定義

2.10. G

を曲面

Σ

上のグラフとし

, e

を

G

の辺とする

. G

の

Σ

での正則近傍をとることによって得られるリボングラフを

R

とし

,e

に対応する

R

の辺も同じ記号

e

で表すことにする

.

このとき

e

の近傍のみが

G

と異なる

Σ

上のグラフで

,

その正則近傍が

R\e

であるようなものが定まる

.

このグラフを

G\e⊂Σ

とかき

,G

から辺

e

を消去することによって得られるグラフという

.

またこのとき，

∂R

と

∂(R/e)

との間には自然な対応が存在するので，

e

の近傍のみが

G

と異なる

Σ

上のグラフで

,

その正則近傍が

R/e

であるようなものが定まる

.

このグラフを

G/e

とかき

,G

から

e

を縮約することによって得られるグラフという

.

定義

2.11. Σ

を閉曲面とし

,(G,Σ, i)

を

Σ

上のグラフとする

. Σ\i(G)

の各連結成分が円板と同相であるとき

,i

は

Σ

の

cellulation

であるという

.

誤解の恐れがないときには

,G

とその像

i(G)

と同一視する

.

したがって，

G

は

Σ

の

cellulation

であるともいう

.

命題

2.1.

リボングラフと

cellulation

は同値である

.

すなわち

,

全てのリボングラフの集合と全ての

cellulation

の集合の間には全単射が存在する

.

証明

. G⊂Σ

を

cellulation

とすると

,G

の

Σ

における正則近傍をとることによりリボン

グラフが得られる

.

逆に

, G

をリボングラフとする

.

このとき

, G

は穴あき曲面である

. G

の各境界成分に円板でふたをすることにより閉曲面に埋め込まれたリボングラフが得られる

.

ここから各頂点の円板を点に

,

各辺の円板

(

帯

)

を頂点同士をつなぐ線分になるまで幅を狭めることにより

,

閉曲面上の

cellulation

が得られる

.

例

2.3.

図

6

は

cellulation

と

,

それに対応するリボングラフを表している

.

図

6: cellulation

とリボングラフ

閉曲面

Σ

の

cellulationG

に対して

,

次のように新しい

(Σ

の

) cellulationG^∗

を構成するこ

とができる

.

定義

2.12. Σ

を閉曲面とし

,G

を

Σ

の

cellulation

とする

. Σ\G

の各連結成分に１つの頂

点をおき

,

これを

G^∗

の頂点とする

. G

の各辺

e

に対して，

e

の両側にある

Σ\G

の成分

に対応する

G^∗

の頂点同士を

e

を横断的に交わるように辺

e^∗

でつなぐ

.

このようにして

得られた

Σ

上のグラフ

G^∗

を

G

の

Poincare dual

という

.

このとき

,G^∗

は

Σ

の

cellulation

となる

.

(8)

3. Tutte

多項式

この節では

Tutte

多項式の定義を述べ，辺の消去と縮約に関して成り立つ性質を紹介する．また，その性質を用いた具体例の計算も紹介する．本論文では

, Butler[1]

による定義を紹介するが

,

これは良く知られている

Tutte

多項式の定義を変数変換したものになっていることを注意しておく.

定義

3.1. ([1])

G

をグラフとする

.

次の式で定義される

2

変数多項式

T_G(X, Y)

を

G

の

Tutte

多項式という

.

T_G(X, Y) = ∑

F⊆G

X^c(F⁾⁻^c(G)Y^n(F⁾ (1)

ここで

,F

は

G

の全ての全域部分グラフを渡るものとする

.

Tutte

多項式

T_G(X, Y)

について，以下の性質が成り立つことが知られている

.

定理

3.1. ([2, Definiton 2, Definition 3, Proposition 1]) (1) e(∈E(G))

が橋でもループでもない辺のとき

,

T_G(X, Y) = T_G_\_e(X, Y)

＋

T_G/e(X, Y).

(2) G

が

i

個の橋と

j

個のループで構成されているとき,

T_G(X, Y) = (X

＋

1)ⁱ(Y

＋

1)^j.

(3) G

が

G₁

と

G₂

の

one-point join

で構成されているとき

, T_G₁ _∗

v1=v2

G2(X, Y) = T_G₁(X, Y)T_G₂(X, Y).

任意のグラフ

G

から，橋でもループでもない辺の消去と縮約を繰り返し行うことにより，橋とループのみから成るグラフが得られる．このことから，任意のグラフに対

し，定理

3.1

の

(1), (2)

を用いて再帰的に

Tutte

多項式を計算することができる

.

ある

グラフ

G

から辺の消去と縮約により橋とループのみから成るグラフを得る操作は，消去，縮約に用いる辺の選び方に依存するので一意的ではないが，

Tutte

多項式が辺の選び方に依らず定理

3.1

の

(1), (2)

で定義できることもわかる

.

実際この

(1), (2)

を定義としている文献も多いことを断っておく

.

図

7

は

,

この方法で

Tutte

多項式を求める手順を示す

.

ここで

,

実線は辺の縮約を表し

,

点線は辺の消去を表す

.

全ての葉に対応するグラフに対し定理

3.1

の

(2)

を適用した結果がグラフの下に書かれた項であり，これらを全て足し合わせることにより

,

図

7

中央上のグラフ

G

の

Tutte

多項式は

T_G(X, Y) =X³+ 5X²+ 2XY + 10X+Y²+ 5Y + 8

となることがわかる

.

Tutte

多項式は次に述べるような双対性をもつことが知られている．

定理

3.2. ([3, Theorem 3.1])

G

を平面的グラフとする．

G

の任意の

dualG^∗

に対し，次が成り立つ

. T_G(X, Y) = T_G∗(Y, X).

(9)

図

7: Tutte

多項式の再帰的な計算例

4. Krushkal

^多項式

V. Krushkal

は

2011

年に向き付け可能な曲面に埋め込まれたグラフの多項式不変量を定

義した

([3]).

さらに

2018

年，C. Butler [1] により

Krushkal

多項式は向き付け不可能な

曲面に対して拡張された．この節では

Butler

の論文の一部を紹介する．

一般に，空間

X

に対し

X

の連結成分の数を

c(X)

で表す

.

またコンパクトな曲面

M

に対し,

M

の種数を

g(M)

で表す．G をグラフ,

Σ

をコンパクトな曲面とする．i を

G

の

Σ

への埋め込みとし

,F

を

G

の全域部分グラフとする

. F

を全域部分グラフ

F

の像

i(F)

の

Σ

における正則近傍とすると，

F

の境界はいくつかの円周の非交和である

. F

の各境界成分に円板を貼ることによって得られる閉曲面を

S(F)

，

Σ

での

F

の補集合の各境界成分に円板を貼ることによって得られる閉曲面を

S^⊥(F)

で表す

. s(F) = 2c(F)−χ(S(F)), s^⊥(F) = 2c(Σ\F)−χ(S^⊥(F))

と定めると

,

s(F) =

{2g(S(F)) (S(F)

が向き付け可能なとき

) g(S(F)) (S(F)

が向き付け不可能なとき

)

s^⊥(F) =

{2g(S(F)) (S^⊥(F)

が向き付け可能なとき)

g(S(F)) (S^⊥(F)

が向き付け不可能なとき

)

となることに注意する

.

以上の記号のもと，次のように一般化された

Krushkal

多項式を定義する．

定義

4.1. ([1], (2.7)

式

)

(

向き付け可能とは限らない

)

コンパクトな曲面

Σ

上のグラフ

(G,Σ, i)

の（一般化された）

Krushkal

多項式

P_G,Σ,i(X, Y, A, B)

を以下で定義する

.

P_G,Σ,i(X, Y, A, B) = ∑

F⊆G

X^c(F⁾⁻^c(G)Y^c(Σ^\^F⁾⁻^c(Σ)A^s(F^)/2B^s^⊥^(F^)/2 (2)

(10)

ここで

, F

は

G

の全ての全域部分グラフを渡るものとする

.

なお

,

誤解の恐れがないときは埋め込み

i

を省略し単に

P_G,Σ(X, Y, A, B)

と表す

.

これは

Σ

が向き付け可能である場合

, Krushkal

多項式の定義

[3]

と一致する

.

曲面

S(F)

と

S^⊥(F)

が向き付け可能のとき，対応する不変量

s(F),s^⊥(F)

は常に偶数で，P

_G,Σ

は変数

X, Y, A, B

の多項式であるが，

S(F)

が向き付け不可能のとき

, s(F), s^⊥

は奇数になるかもしれない

.

したがって，

P_G,Σ

は，

X, Y, A^1/2, B^1/2

の多項式である

. Butler

は

[1]

で

, Krushkal

多項式が満たすいくつかの基本的性質を示している

.

これは

Krushkal

が向

き付け可能な曲面に埋め込まれたグラフに対して示したもの

([3])

を向き付け不可能な曲面に拡張したものである

.

定理

4.1. ([1, Proposition 2.3])

G

をグラフ

,Σ

を

(

向き付け可能とは限らない

)

コンパクトな曲面

,i

を

G

から

Σ

への埋め込みとし

,e

を

G

の辺とする

.

このとき以下が成り立つ

.

(1) e

が橋でもループでもないとき

,

P_G,Σ(X, Y, A, B) = P_G_\_e,Σ(X, Y, A, B)

＋

P_G/e,Σ(X, Y, A, B).

(2) e

が橋のとき

,

PG,Σ(X, Y, A, B) = (1

＋

X)PG/e,Σ(X, Y, A, B).

(3) c(Σ) = 1

かつ

e

がループであり

,c(Σ\e) =2

のとき

,

P_G,Σ(X, Y, A, B) = (1

＋

Y)P_G_\_e,Σ(X, Y, A, B).

(4) Σ

＝

Σ₁ ⊔ Σ₂, G = G₁ ⊔ G₂, G₁ ⊂ Σ₁, G₂ ⊂ Σ₂

のとき,

P_G,Σ(X, Y, A, B) =P_G₁_,Σ₁(X, Y, A, B)P_G₂_,Σ₂(X, Y, A, B).

また

Butler

は

[1]

において，次が成り立つことを示している

.

定理

4.2. ([1, Thorem 2.4])

Σ

をコンパクトな曲面とする

. Σ

上のグラフ

(G,Σ, i)

に対して次が成り立つ

. TG(X, Y)

＝

Y^2c(Σ)^−X^(Σ)PG,Σ(X, Y, Y, Y⁻¹).

これは,

G

の

Tutte

多項式がその

Krushkal

多項式

P_G,Σ

から復元できることを示して

いる

.

5.

^主結果

この節では

,

主定理を述べるために必要な用語の定義を与え，主定理とその証明を与える

.

定義

5.1. G1, G2

をグラフ

,Σ1,Σ2

を

(

向きつけ可能とは限らない

)

コンパクトな曲面とし

, i₁

を

G₁

の

Σ₁

への埋め込み

,i₂

を

G₂

の

Σ₂

への埋め込みとする

. v₁ ∈V(G₁), v₂ ∈V(G₂)

に対し

,G₁

と

G₂

の

v₁,v₂

における

one-point joinG=G₁ ∗

v1=v2

G₂

の

Σ = Σ₁♯Σ₂

曲面上のグラフの Krushkal 多項式

曲面上のグラフの Krushkal 多項式

山村 瑠納

奈良女子大学

村井 紘子

奈良女子大学

グラフの基本事項

本研究では

つの頂点を結ぶ辺が

本以上ある多重辺も許し，同じ頂点同士を結ぶ辺

ループ

の存在を許した 一般グラフ を扱う

正確には次の通りとする．

定義

一般グラフ

又は単に グラフ

とは

対

の ことをいう

ここで

は頂点

と呼ばれる元から成る空でない有限集合であ り

は

の

必ずしも相異なるとは限らない

元の非順序対の有限な族である

とする

の元は辺

と呼ばれる

ただし

複数個の同じ元が入っていても良い

集まりを「族」と呼んで

「集合」とは区別することにする

は「族」であるか ら

複数個の同じ辺

これを多重辺という

があっても良いことに注意する

を

の頂点集合といい

を

の辺族と呼ぶ

に対し

であ

るとき

辺

は頂点

と

を結ぶ

といい

と略記する

頂点

のことを

辺

の端点と呼ぶ

定義

グラフ

の辺のうち

頂点

とそれ自身を結ぶ辺

のことをループ

と いう

また

その辺を消去すると

の連結成分が増えるような辺を橋

という

通常

グラフを図で表すときには

各頂点

に対して点を

つ描き

つの頂 点

に対し

のとき

に対応する点と

に対応する点を線で 結ぶ.

定義

グラフ

に対し

の頂点の個数を

辺の本数を

曲面上のグラフの Krushkal ^多項式

山村瑠納

村井紘子

の存在を許した一般グラフを扱う

又は単にグラフ

のことをいう

と呼ばれる元から成る空でない有限集合であり

は「族」であるから

という

つの頂点

に対応する点を線で結ぶ.

の部分グラフ

の全域部分グラフ

を満たし，多重辺に関してはその本数まで込めて対応がつくときに

は同型であるという

グラフを図で表すときに点や線がどのように描かれているかは関係なく

大切なのはどの頂点の組が何本の辺で結ばれているかという情報だけである

を縮約して得られたグラフという

となるようなグラフ