木のRadial性を判定する
高速なアルゴリズム

斎藤研究室 五十嵐正広

目次
・dominating setとは・broadcast dominationとは・直径、半径とは・radialとは・先行研究、研究動機
・split-setとは・結果
・木のradial性判定アルゴリズム
・実装と実験
・まとめ・今後の研究課題2dominating setとはいくつかの市に電波塔を設置したい。
ただし、電波塔がない市の隣には必ず電波塔があるようにする。
電波塔は少なくなるようにする。

a市

b市

c市

d市

e市

f市

g市

h市
3

dominating setとは
例 {a , d}b , eの隣にはaがある。
fは支配されていない。
(b , eはaに支配されている。)
正しい電波塔の配置ではない。
c , g , hはdに支配されている。

aebcdfgh4

dominating setとは
例 {a , d , f}b , eはa(とf)に支配されている。
c , hはdに支配されている。

aebcdfghgはd(とf)に支配されている。

5

dominating setとは
例 {a , g}b , c , d , e , f , hはaとgで支配されている。

aebcdfgh
6

dominating setとはグラフGのいくつかの頂点の集合Sをとり、「Sに属していない頂点の近傍にはSの頂点が存在する」という条件を満たすSを支配集合（dominating set）と呼び、最小の支配集合の頂点数をGの支配数（domination number）と呼ぶ。

7

broadcast dominationとは
例acbdgjfehik
8broadcast dominationとは
例 {a}acbdjfegaとの距離１の点： b , c２の点： d , e , f３の点： g , h , i４の点： j , khik9broadcast dominationとは
例 {a}

a4
cbdj

fe

gaとの距離１の点： b , c２の点： d , e , f※これは正しい配置ではない。
３の点： g , h , i４の点： j , khi

k10broadcast dominationとは
例 {c , g}a2

cbdjfeg1

a , b , d , e , f , h , i , j , kはcとgで支配されている。

h１ + ２ = ３ （＜ ４）ik11

broadcast dominationとはグラフGのいくつかの頂点の集合Sをとり、Sの各頂点xに正の整数f(x)を割り振る。このとき、「Gの各頂点vについて、Sのどれかの頂点xとの距離≤f(x)」という条件を満たすSを
broadcast dominating set と呼ぶ。
f(x)の和の最小値をGの broadcast domination number と呼び、 γb (G) で表す。

12直径、半径とは
例. G
１

任意の点vから最も遠い点までの距離を離心値 といい、e(v)で表す。

１３v
１２１２３４13直径、半径とは
例. G
５

任意の点vから最も遠い点までの距離を離心値といい、e(v)で表す。

５離心値が最小となる点をグラフの中心と言う。
中心の離心値を半径と言い、rad(G)で表す。

５離心値の最大値を直径と言い、diam(G)で表す。

ax６５４３４５y６14直径、半径とは例. G５

また、このときのxからyへの道を「diametrical path」と言う。

５５ax６５４３４５y６15直径、半径とは任意の点vから最も遠い点までの距離を離心値といい、e(v)で表す。
離心値が最小となる点をグラフの中心と言う。
中心の離心値を半径と言い、rad(G)で表す。
離心値の最大値を直径と言い、diam(G)で表す。
グラフGの最も長い道を「diametrical path」と言う。

16

目次
・dominating setとは・broadcast dominationとは・直径、半径とは・radialとは・先行研究、研究動機
・split-setとは・結果
・木のradial性判定アルゴリズム
・実装と実験
・まとめ・今後の研究課題17

任意のグラフGについて、以下の不等式が成り立つ。

𝛾𝛾𝑏𝑏 𝐺𝐺 ≦ rad(G)𝛾𝛾𝑏𝑏 𝐺𝐺 = rad(G) = 2

𝛾𝛾𝑏𝑏 𝐺𝐺 = 3 , rad(G) = 418

radialとはグラフGがradialであるとは、𝛾𝛾𝑏𝑏 𝐺𝐺 = rad(G) となっていることである。

１点の最適なbroadcast dominating setが存在する。

19

radialとは例.G
𝛾𝛾𝑏𝑏 𝐺𝐺 = rad G = 3 より、Gはradialである。

３20

radialとは
例.G
rad(G) = 4𝛾𝛾𝑏𝑏 𝐺𝐺 = 3４

１

１γb G ≠ rad G より、Gはradialではない。
（nonradialである。）
１21

先行研究・研究動機
木Ｔがradialである。
⇔Ｔが空でないsplit-setを持たない。 （Ｓ．Ｈｅｒｋｅ，Ｃ．Ｍ．Ｍｙｎｈａｒｄｔ ２００９）22

split-setとは
Ｐ：木Ｔのdiametrical path
Ｐの辺の集合ＭがＰに関してsplit-setであるとは以下の条件を満たすことである。
（１）任意のｅ∈Ｍについて、ｅの両端点のＴにおける次数は２である。
（２）Ｔ-Ｍの各成分Ｔ’について、
ＰかつＴ’はＴ’のdiametrical pathであり、その長さは偶数である。

23

split-setとは
例.Ｔ （rad(T) = 5）（１）任意のｅ∈Ｍについて、ｅの両端点のＴにおける次数は２である。
（２）Ｔ-Ｍの各成分Ｔ’について、
ＰかつＴ’はＴ’のdiametrical pathであり、その長さは偶数である。

Pabcdefghij24

split-setとは
例.Ｔ （rad(T) = 5）（１）任意のｅ∈Ｍについて、ｅの両端点のＴにおける次数は２である。
（２）Ｔ-Ｍの各成分Ｔ’について、
ＰかつＴ’はＴ’のdiametrical pathであり、その長さは偶数である。

（１）を満たすもの：｛ｃｄ，ｄｅ，ｅｆ｝

Pabcdefghij25

split-setとは
例.Ｔ （rad(T) = 5）
（ｄｅを取り除いた場合）（１）任意のｅ∈Ｍについて、ｅの両端点のＴにおける次数は２である。
（２）Ｔ-Ｍの各成分Ｔ’について、
ＰかつＴ’はＴ’のdiametrical pathであり、その長さは偶数である。

⇒｛ｄｅ｝はsplit-setでない。

Pab
長さ：３cdefgh
長さ：５ij26

split-setとは
例.Ｔ （rad(T) = 5）
（ｅｆを取り除いた場合）（１）任意のｅ∈Ｍについて、ｅの両端点のＴにおける次数は２である。
（２）Ｔ-Ｍの各成分Ｔ’について、
ＰかつＴ’はＴ’のdiametrical pathであり、その長さは偶数である。

⇒｛ｅｆ｝はsplit-setでない。

Pabc
長さ：４defghij27

split-setとは
例.Ｔ （rad(T) = 5）（ｃｄを取り除いた場合）（１）任意のｅ∈Ｍについて、ｅの両端点のＴにおける次数は２である。
（２）Ｔ-Ｍの各成分Ｔ’について、
ＰかつＴ’はＴ’のdiametrical pathであり、その長さは偶数である。

⇒｛ｃｄ｝はsplit-setである。

Pab
長さ：２cdefg
長さ：６hij28

split-setとは
例.Ｔ （rad(T) = 5）
（ｃｄを取り除いた場合）（１）任意のｅ∈Ｍについて、ｅの両端点のＴにおける次数は２である。
（２）Ｔ-Ｍの各成分Ｔ’について、
ＰかつＴ’はＴ’のdiametrical pathであり、その長さは偶数である。

γb T = 1 + 3 = 4

Pab１cdefg３hij29

先行研究・研究動機
木Ｔがradialである。
⇔Ｔが空でないsplit-setを持たない。 （Ｓ．Ｈｅｒｋｅ，Ｃ．Ｍ．Ｍｙｎｈａｒｄｔ ２００９）

木Ｔのradial性を判定するには、高々２本までの辺を調べれば良いのではないか。

30

結果
定理
木Tがsplit-setを持つならば、高々２本の辺を含むsplit-setが存在する。

31

結果
定理
木Tがsplit-setを持つならば、高々２本の辺を含むsplit-setが存在する。

木Ｔがsplit-setを持つかどうか調べるには、高々２本の辺を調べれば良い。
この定理を用いて、木のradial性を判定するアルゴリズムを構築した。

32

木のradial性判定アルゴリズム
１．木Tのdiametrical path（P とする）を見つける。
２．Pにおける両端の頂点の次数が２の辺をei （i = 1,2,…,n | n ≦ diam(T) - 2）とする。
ei（i = 1,2,…,n）をちょうど１本ずつ取り除き、それぞれがsplit-setか判定する。
３．split-setが存在する ⇒nonradialである。
split-setが存在しない⇒radialである。

Pe1

e2

e3

e4e5
33

木のradial性判定アルゴリズム（i）Pの長さが奇数の場合
任意の２辺から成るsplit-set{ei,ej}を取った際、残りの道の長さの組み合わせは、奇数ｘ１、偶数ｘ２または奇数ｘ３となるので、２辺のsplit-setは存在しない。
⇒１辺のsplit-setのみを考える。
例 Pの長さ：７34

木のradial性判定アルゴリズム
１．各辺ei ∈E(P）について、P- eiの左側の道をPl(ei)、右側の道をPr(ei)とし、 Pl(ei)の長さが偶数か調べる。

（i）Pの長さが奇数の場合

P

Pl(ei)ei

Pr(ei)
35

木のradial性判定アルゴリズム
２． Pl(ei) を含む木をTiとし、Pr(ei)を含む木をTi’とする。
Pl(ei)の長さと木Tiの直径が同じ値か調べる。

（i）Pの長さが奇数の場合

Ti

P

Pl(ei)Ti’ei

Pr(ei)
36

木のradial性判定アルゴリズム
３． Pr(ei)の長さと木Ti’の直径が同じ値か調べる。

（i）Pの長さが奇数の場合

TiPPl(ei)Ti’eiPr(ei)
37

木のradial性判定アルゴリズム（i）Pの長さが奇数の場合
１．各辺ei ∈E(P）について、P- eiの左側の道をPl(ei)、右側の道をPr(ei)とし、 Pl(ei)の長さが偶数か調べる。
True

２． Pl(ei) を含む木をTiとし、Pr(ei)を含む木をTi’とする。
Pl(ei)の長さと木Tiの直径が同じ値か調べる。

False
(i+1)

３． Pr(ei)の長さと木Ti’の直径が同じ値か調べる。
４． {ei}がsplit-setである。
４にたどり着く（Tはnonradialである）、または i が n 以上になる（Tはradialである）まで続ける。

38

木のradial性判定アルゴリズム（ii）Pの長さが偶数の場合任意の１辺から成るsplit-set{ei}を取った際、残りの道の長さは、どちらかが奇数になるので、１辺のsplit-setは存在しない。
⇒２辺のsplit-setのみを考える。
例 Pの長さ：８39

木のradial性判定アルゴリズム
１．各辺ei ∈E(P）について、P- eiの左側の道をPl(ei)、右側の道をPr(ei)とし、 Pl(ei)の長さが偶数か調べる。
（iは1からnまで昇順に調べる。）（ii）Pの長さが偶数の場合

P

Pl(ei)ei

Pr(ei)

40

木のradial性判定アルゴリズム
２． Pl(ei) を含む木をTiとし、Pr(ei)を含む木をTi’とする。
Pl(ei)の長さと木Tiの直径が同じ値か調べる。

（ii）Pの長さが偶数の場合

TiP

Pl(ei)Ti’eiPr(ei)41

木のradial性判定アルゴリズム
３．各辺ej ∈E(P）について、P- ejの左側の道をPl(ej)、右側の道をPr(ej)とし、 Pr(ej)の長さが偶数か調べる。
（jはiの最大値からiより大きい数を降順に調べる。）
Pl(ej)かつPr(ei)なる道をPc(ei)とする。

（ii）Pの長さが偶数の場合

P

Pl(ei)ei

Pc(ei)ej

Pr(ej)

42

木のradial性判定アルゴリズム
４． Pr(ej)を含む木をTj’とする。
Pr(ej)の長さと木Tj’の直径が同じ値か調べる。

（ii）Pの長さが偶数の場合

Tj’P

Pl(ei)ei

Pc(ei)ej

Pr(ej)

43

木のradial性判定アルゴリズム
５． Pc(ei)を含む木をT’とする。
Pc(ei)の長さと木T’の直径が同じ値か調べる。

（ii）Pの長さが偶数の場合T’P

Pl(ei)ei

Pc(ei)ej

Pr(ej)

44

木のradial性判定アルゴリズム（ii）Pの長さが偶数の場合１．Pl(ei)の長さが偶数か調べる。
（iは1からnまで昇順に調べる。）(i+1)

２． Pl(ei)の長さと木Tiの直径が同じ値か調べる。
True

３．Pr(ej)の長さが偶数か調べる。
（jはiの最大値からiより大きい数を降順に調べる。）
４． Pr(ej)の長さと木Tj’の直径が同じ値か調べる。

False
(j–1)

５． Pc(ei)の長さと木T’の直径が同じ値か調べる。
６．{ei , ej}がsplit-setである。
45

木のradial性判定アルゴリズム（ii）Pの長さが偶数の場合
Pc(ei)の長さと木T’の直径が同じ値でない⇒ Pc(ei) はT’のdiametrical pathでない。

①T’のdiametrical pathの端点がPc(ei)上に存在するとき②T’のdiametrical pathの端点がPc(ei)上に存在しないとき
T’PPl(ei)eiPc(ei)ejPr(ej)46

木のradial性判定アルゴリズム（ii）Pの長さが偶数の場合
Pc(ei)の長さと木T’の直径が同じ値でない ⇒ Pc(ei) はT’のdiametrical pathでない。
①T’のdiametrical pathの端点がPc(ei)上に存在するとき
T’
zl3
Pai
Pl(ei)eiaj
l1y

Pc(ei)l2ej

Pr(ej)

47

木のradial性判定アルゴリズム（ii）Pの長さが偶数の場合
Pc(ei)の長さと木T’の直径が同じ値でない ⇒ Pc(ei) はT’のdiametrical pathでない。
①T’のdiametrical pathの端点がPc(ei)上に存在するときl1,l2,l3の組み合わせ
・l1 > l3 かつ l2 > l3・l1 > l3 かつ l2 > l3・l1 > l3 かつ l2 < l3・l1 < l3 かつ l2 > l3・l1 < l3 かつ l2 = l3・l1 < l3 かつ l2 < l3・l1 = l3 かつ l2 > l3・l1 = l3 かつ l2 > l3・l1 = l3 かつ l2 < l3z

l3aiajl1yPc(ei)l248

木のradial性判定アルゴリズム（ii）Pの長さが偶数の場合
Pc(ei)の長さと木T’の直径が同じ値でない ⇒ Pc(ei) はT’のdiametrical pathでない。
①T’のdiametrical pathの端点がPc(ei)上に存在するとき
・l1 > l3 かつ l2 < l3⇒yからl3以上離れているei寄りの辺ekを調べる。
（ j = k とし、３の処理へ戻る。）

zl3ajaiek

Pc(ei) yl249

木のradial性判定アルゴリズム（ii）Pの長さが偶数の場合
Pc(ei)の長さと木T’の直径が同じ値でない ⇒ Pc(ei) はT’のdiametrical pathでない。
①T’のdiametrical pathの端点がPc(ei)上に存在するとき
・l1 < l3 かつ l2 > l3⇒yからl3以上離れているej寄りの辺ekを調べる。
（ i = k とし、１の処理へ戻る。）

zl3ajail1y P (e )c iek50

木のradial性判定アルゴリズム（ii）Pの長さが偶数の場合
Pc(ei)の長さと木T’の直径が同じ値でない②T’のdiametrical pathの端点がPc(ei)上に存在しないとき⇒z1からz2への道がdiametrical pathT’・l1 = l4
z1・l3 = l5z2・l2 ≧ l5 + l4 + 4l4P

l5ai
Pl(ei)

ei

l1

y1

l2
Pc(ei)

y2 l3ajej

Pr(ej)

51

木のradial性判定アルゴリズム（ii）Pの長さが偶数の場合①

Pc(ei)の長さと木T’の直径が同じ値でない②T’のdiametrical pathの端点がPc(ei)上に存在しないとき⇒z1からz2への道がdiametrical path・l2 ≧ l5 + l4 + 4のとき
⇒y1からl4以上離れているej寄りの辺ek 、y2からl5以上離れているei寄りの辺ehを調べる。
（ i = k 、 j = h とし、１の処理へ戻る。 ）①z1z2l4l5

ai
l1y1l2Pc(ei)aj

y2 l352

木のradial性判定アルゴリズム
・木Tのdiametrical path（Pとする）を見つける。
⇒Pの長さの偶奇を調べる。

・split-setが存在する ⇒nonradialである。
split-setが存在しない⇒radialである。
53

実装と実験
Q1.位数とnonradial treeの出現確率にはどのような関係があるのか？

Q2.diametrical pathの長さに比例してnonradial treeの出現確率は増えるのでは？

Q3.diametrical path 上に存在し、両方の頂点の次数が２の辺の出現確率に比例してnonradial treeの出現確率は増えるのでは？

54

実装と実験
Q1.位数とnonradial treeの出現確率にはどのような関係があるのか？
位数
⇒実験方法
10
位数を１０～１００まで１０ずつ増やしていく。
各位数について木をランダムに１００回生成し、nonradial treeの出現確率を求める。 2030
⇒結果位数が極端に小さい場合以外では、nonradial treeの出現確率は位数に依存しない。

nonradial tree
8%
0%
2%

400%

501%

601%

700%

800%

900%

1001%
55

実装と実験
Q1.位数とnonradial treeの出現確率にはどのような関係があるのか？
⇒極端に位数が小さい場合以外ではnonradial treeの出現確率は位数に依存しない。
Q2.diametrical pathの長さに比例してnonradial treeの出現確率は増えるのでは？
⇒diametrical pathの最低数が小さい範囲では増加関係だが、ある程度大きくなると、両者の間には関係はなくなる。
Q3.diametrical path 上に存在し、両方の頂点の次数が２の辺の出現確率に比例してnonradial treeの出現確率は増えるのでは？
⇒両者に関係はない。

56

まとめ・木Tのradial性判定は、直径が奇数の場合は１辺から成るsplit-setを、直径が偶数の場合は２辺から成るsplit-setを探索することで実現可能である。
・nonradial treeの出現確率との関係
位数 ⇒ 極端に小さい場合以外では関係しない。
diametrical pathの最低数 ⇒ 小さい範囲では増加関係だが、ある程度大きくなると両者の間には関係はなくなる。
diametrical path 上に存在し、両方の頂点の次数が２の辺の出現確率 ⇒ 関係はない。

57

今後の研究課題
・このアルゴリズムを内側の木に繰り返すことで、 γb T を求めることはできるのだろうか。
・nonradial treeの出現確率と比例関係にある条件は存在するのか。

58

ご清聴ありがとうございました。

59