計算の複雑さ

平
面
グ
ラ
フ
定義
電気回路の一層配線図のように平面上に辺が交差
しないように描けるグラフを平面グラフという。
チップ2
チップ1
チップ5
チップ6
チップ4
チップ3
グラフの厚さ
一般の回路網に対して、それを完全するには何枚の
プリント基板回路が必要かを知ることが重要である。
そのために、いくつかの平面的グラフを重ね合わせて、
グラフGをつくるときに必要な平面的の最小数をGの厚さ
(thickness)と定義し、t(G)と書く。
平
面
グ
ラ
フ
６点の完全グラフK6が平面グラフではない。
厚さt(G)＝２
一層目
二層目
定理3.9.1
オイラー公式
Gは連結平面グラフとし、点数をｎ、辺数をｍ、面数をｆ
とすると、
ｎ－ｍ＋ｆ＝２
が成り立つ。
系
(a) 連結な単純平面グラフGがｎ（≧3）個の点とm本の
辺をもつとき、次の式が成り立つ。
m≦3n－6
(b) さらにGに３角形がないならば、次の式が成り立つ。
m≦2n－4
課
題
以下のことを証明せよ。
1
単純グラフGにn(≧3)個の点およびm本の辺が
あるとき、Gの厚さt(G)は次の不等式を満足する。
m
t(G) ≧
3n – 6
2
3
t(G) ≧
m + 3n - 7
3n – 6
二部グラフKr,sの厚さt(G)は次の不等式を満足する。
rs
t(Kr,s) ≧ 2(r+s) – 4
偶数のrならば、t(Kr,s)≦r / 2である。
さらにs>(r – 2)2/2ならば、t(Kr,s)=r / 2である。
〆切：１2月09日１４：３０（情報数学講義終了後、回収する。）
課
以下のことを証明せよ。
記号
：切捨て記号
題
：切上げ
1 x単純グラフGにn(≧3)個の点およびm本の辺が
= xより小さい最大整数
x = xより大きい最小整数
あるとき、Gの厚さt(G)は次の不等式を満足する。
m
t(G) ≧
3n – 6
2
3
t(G) ≧
m + 3n - 7
3n – 6
二部グラフKr,sの厚さt(G)は次の不等式を満足する。
rs
t(Kr,s) ≧ 2(r+s) – 4
偶数のrならば、t(Kr,s)≦r / 2である。
さらにs>(r – 2)2/2ならば、t(Kr,s)=r / 2である。
〆切：１2月09日１４：３０（情報数学講義終了後、回収する。）
課
題
以下のことを証明せよ。
1
単純グラフGにn(≧3)個の点およびm本の辺が
あるとき、Gの厚さt(G)は次の不等式を満足する。
m
t(G) ≧
3n – 6
2
3
t(G) ≧
m + 3n - 7
3n – 6
二部グラフKr,sの厚さt(G)は次の不等式を満足する。
rs
t(Kr,s) ≧ 2(r+s) – 4
偶数のrならば、t(Kr,s)≦r / 2である。
さらにs>(r – 2)2/2ならば、t(Kr,s)=r / 2である。
〆切：１2月09日１４：３０（情報数学講義終了後、回収する。）

Download Report