トーラス格子の Metric Dimension
5416007 大野 達也

目次• Metric Dimension とは• 何の役に立つか• トーラス格子とは• 研究動機• M * N の Metric Dimension• まとめ• 今後の課題

Metric Dimensionとは• グラフの頂点を各センサーまでの距離で区別したい• グラフのいくつかの頂点にセンサーを置く

metric dimension = 必要なセンサーの最小数Metric Dimensionとは
12563

用語解説

47

• このグラフの場合、metric dimensionはいくつか？

Metric Dimensionとは

(0)

15(1)

(1)

(1)

2(2)

36(3)

(3)

センサー1からの距離↑• 1にセンサーを置く

47

用語解説

Metric Dimensionとは

(0)

15(1)

(1)

(1)

26(2)

3(3)(3)

用語解説

47• センサー1からの距離だけでは区別できないMetric Dimensionとは

(0,3)

(1,2)

56

1(1 ,3)2(1,2)(2 ,1)

3

用語解説

(3,0)

47(3 ,2)

センサー1からの距離↑ ↑センサー2からの距離• 4にセンサー2を置く

Metric Dimensionとは
(0,3)

(1,2)

56

1(1,3)

2(1,2)

(2,1)

3

用語解説

(3,0)

47(3,2)• センサー1,2からの距離だけでは区別できないMetric Dimensionとは(0,3,1 )(1,2,2)56(1,3,1 )(1,2 ,0)12(2,1,1 )3• 6にセンサー3を置く

用語解説(3,0,2 )47(3,2 ,2) ←距離ベクトル↑センサー3からの距離Metric Dimensionとは(0,3,1)(1,2,2)

5

6

1(1,3,1)2(2,1,1)

3(3,0,2)(1,2,0)4

7(3,2,2)

3つのセンサーで区別できる
2つのセンサーでは区別できない
metric dimension = 3

用語解説

何の役に立つか？
例えばどこかにフィッシングメールを流している人がいる。
その人がどこにいるかを特定するためにメールのホップ数に注目する。
ホップ数とは、通信ネットワーク上で通信相手に到達するまでに経由する転送・中継設備の数。
その情報を集めて場所を特定することができる。
では効率よくホップ数を数えるにはどこでホップ数を数えたら良いか？
→metric dimensionを用いればそれがわかるトーラス格子グラフとは?

すべての頂点から上下左右に辺が伸びているグラフ
1番上と1番下、1番右と1番左がつながっている
縦の頂点数がN 横の頂点数がMのトーラス格子を M
縦の頂点数をN(0, 0)
M*Nのトーラス格子という横の頂点数をMとする
各頂点を座標で表す(M - 1, 0)

N(0, N - 1)

M = 7 , N = 5 のトーラス格子(M, N)

研究動機
基本的なグラフであるトーラス格子グラフについて興味を持ったので調査した。

M * Nのトーラス格子のMetric Dimension①(M, N) = (odd, odd) のとき②(M, N) = (odd, even)のとき③(M, N) = (even , even)のとき

(M, N) = (odd, odd)のとき
M = 7 , N = 5 の場合で考えてみるセンサーを(0, 0) , (3, 0) , (0 , 4)に置く
(0,0)

(0,4)

(3,0)

(6,0)

(M, N) = (odd, odd)のとき(0, 0)からの距離は以下のようになる
(0,0)

(6,0)
1233211• 1234432234554323455431234432

(M, N) = (odd, odd)のとき(3, 0)からの距離は以下のようになる
(0,0)

(6,0)
123123432345432345321234321•4 1325454

(M, N) = (odd, odd)のとき(0, 4)からの距離は以下のようになる
(0,0)

(6,0)

1234432•2 134554323455431234432123321

(M, N) = (odd, odd)のとき

これらをまとめると以下のようになり、3つのセンサーで区別できる。
(0, 3, 1) (1, 2, 2) (2, 1, 3) (3, 0, 4) (3, 1, 4) (2, 2, 3) (1, 3, 2)(1, 4, 2) (2, 3, 3) (3, 2, 4) (4, 1, 5)(4, 2, 5) (3, 3, 4)(2, 4, 3)(2, 5, 2) (3, 4, 3) (4, 3, 4) (5, 2, 5) (5, 3, 5) (4, 4, 4) (3, 5, 3)(2, 5, 1) (3, 4, 2)(4, 3, 3) (5, 2, 4) (5, 3, 4) (4, 4, 3) (3, 5, 2)(1, 4, 0) (2, 3, 1)(3, 2, 2) (4, 1, 3) (4, 2, 3) (3, 3, 2) (2, 4, 1)

結果 1
定理
(M, N) = (odd, odd)のときM * Nのトーラス格子のmetric dimensionは3である

3つのセンサーで各頂点を区別できる
2つのセンサーで区別できない頂点が必ずある(M, N) = (odd, odd)のとき
証明
3つのセンサーで区別できることを示す。
センサーを(0, 0), (m, 0), (0, 2n)に置く。
(0, 0)

N = 2n + 1(0, 2n)M = 2m + 1(m,0)(2m, 0)(M, N) = (odd, odd)のとき(0, 0)から任意の点(s, t)までの距離 = K + L
K = (0,0)から(s, 0)までの距離
L = (0,0)から(0, t)までの距離(0, 0)(0,t)(0, 2n)(s,0)(s, t)(2m, 0)(M, N) = (odd, odd)のとき(0, 0)から任意の点(s, t)までの距離 = K + L
K = min{s, 1 + 2m - s}(0, 0)(0,t)(0, 2n)s(s,0)(s, t)

12m - s(2m, 0)(M, N) = (odd, odd)のとき(0, 0)から任意の点(s, t)までの距離 = K + L
L = min{t, 1 + 2n - t}
(0, 0)t
(0,t)

2n-t

1
(0, 2n)(s,0)(s, t)(2m, 0)(M, N) = (odd, odd)のとき(0, 0)から任意の点(s, t)までの距離 = min{s, 1 + 2m - s} + min{t, 1 + 2n - t}

(0, 0)

st

(0,t)

2n-t

1
(0, 2n)(s,0)(s, t)

2m - s1(2m, 0)(M, N) = (odd, odd)のとき(0, 2n)から任意の点(s, t)までの距離 = K + L
K = min{s, 1 + 2m - s}, L = min{1 + t, 2n - t}
K + L = min{s, 1 + 2m - s} + min{1 + t, 2n - t}(s,0)(0, 0)(2m, 0)1t(0,t)(s, t)

2n-t(0, 2n)(0, 2n)s

12m - s(M, N) = (odd, odd)のとき(m, 0)から任意の点(s, t)までの距離 = K + L
K は s ≦ m の場合 または m < s の場合によって決まる(m,0)(0, 0)(0,t)(0, 2n)(s, t)(2m, 0)(s, t)

(M, N) = (odd, odd)のとき(m, 0)から任意の点(s, t)までの距離 = K + Ls ≦ m の場合
K = min{m - s, 2m - m + 1 + s}1=m-s(0, 0)
s(0,t)(0, 2n)m-s(s, t)(m,0)

2m - m(2m, 0)(M, N) = (odd, odd)のとき(m, 0)から任意の点(s, t)までの距離 = K + L
m < s の場合
K = min{s - m, 3m + 1 - s }=s-m(0, 0)

m(0,t)(0, 2n)

(m,0)

1
s-m

2m - s(s, t)(2m, 0)(M, N) = (odd, odd)のとき(m, 0)から任意の点(s, t)までの距離 = K + L
L は(0,0)からの時と同様に決まる
L = min{t, 1 + 2n - t}(m,0)(0, 0)(0,t)(0, 2n)(2m, 0)t(s, t)2n-t

1

(M, N) = (odd, odd)のとき(m, 0)から任意の点(s, t)までの距離m – s + min{t, 1 + 2n - t} (s ≦ m )=s – m + min{t, 1 + 2n - t} (m < s)(m,0)(2m, 0)(0, 0)(0,t)(0, 2n)(s, t)(s, t)

(M, N) = (odd, odd)のときそれぞれのminをとると以下のような範囲にわけられる
0≦s≦mm + 1 ≦ s ≦ 2m0 ≦ t ≦ n- 1

A

Dt=nB

En + 1 ≦ t ≦ 2nCF距離ベクトル
それぞれの距離ベクトルは以下のように決まるA : (s + t, m – s + t, s + t + 1)
B : (s + t, m – s + t, s + 2n - t)
C : (s + 2n + 1 – t, m – s + 2n + 1 – t, s + 2n -t)
D : (2m + 1 – s + t, s – m + t, 2m + 2 – s + t)
E : (2m + 1 – s + t, s – m + t, 2m + 1 –s + 2n - t)
F : (2m + 2 + 2n – s – t, s – m + 2n + 1 – t, 2m + 1 – s + 2n - t)

3つのセンサーで区別する
A, B, C, D, E, Fの範囲の中に区別できない2点(s, t)と(s’, t’)が存在するとして矛盾を導く。
考えられる組み合わせのAA, AB, ~ EF, FFの21通りを調べる。
今回はその一例としてACを調べる。
AD

BECF三つのセンサーで区別する(s, t)からの距離ベクトル(s + t, m – s + t, s + t + 1)=(s’, t’)からの距離ベクトル(s’ + 2n + 1 –t’, m – s’ + 2n + 1 – t’, s’ + 2n – t’)s + t = s’ + 2n + 1 –t’m – s + t = m – s’ + 2n + 1 – t’(s, t)
s + t + 1 = s’ + 2n – t’

これらを満たす(s, t), (s’, t’)の組み合わせは存在しない
他の組み合わせも同じように解くとすべて矛盾になる
このことから3つ以下のセンサーですべての頂点を区別できる(s’, t’)(odd, odd)の時, metric dimensionが2ではない
2つのセンサーで頂点を区別できたとして矛盾を導く
1つ目のセンサーは(0, 0)にあるとしてよい (0,0)
2つ目のセンサーの座標を(a, b)とする(a, b)(0, 2n)(2m,0)

(odd, odd)の時, metric dimensionが2ではない(0, 0) から(0, b)までの距離は min{b, 2n + 1 - b} によって求められ、これを L = min{b, 2n + 1 - b}とする(0,0)

b(0, b)

2n-b

1(0, 2n)(2m,0)(a, b)

(odd, odd)の時, metric dimensionが2ではない
L = b の場合 (a - 1, b), (a + 1, b), (a, b - 1)が同時に区別されると仮定
(0,0)

b

(0, 2n)(2m,0)(a, b)

(odd, odd)の時, metric dimensionが2ではない(a - 1, b)の距離ベクトル (min{a – 1, 2m + 2 – a} + L, 1) ←(a, b)にあるセンサーからの距離はそれぞれ1になる(a + 1, b)の距離ベクトル (min{a + 1, 2m – a} + L, 1)(a, b - 1)の距離ベクトル (min{a - 1, 2m – a} + L, 1)(0,0)からの距離だけで区別しなくてはならない↑ (0,0)

b(0, 2n)(2m,0)(a, b)

(odd, odd)の時, metric dimensionが2ではない
これらの三点は同時に区別されることはないので L = b の場合、矛盾(odd, odd)の時, metric dimensionが2ではない
L = 2n + 1 – b の場合 (a – 1, b), (a + 1, b), (a, b + 1)が同様に区別されることはない(0,0)(2m,0)(a, b)

2n-b

1(0, 2n)(odd, odd)の時, metric dimensionが2ではない
L = b, 2n + 1 – b どちらの場合にも同時に三点が区別されることがないので矛盾(odd, odd)のトーラス格子は2つのセンサーでは区別できない定理(M, N) = (odd, odd)のときM * Nのトーラス格子のmetric dimensionは3である

結果 2定理(M, N) = (odd, even)または(even, odd)のときトーラス格子のmetric dimensionは3である
3つのセンサーで各頂点を区別できる
2つのセンサーで区別できない頂点が必ずある(M, N) = (odd, even)のときセンサーを(0, 0), (m, 0), (0, 2n - 1)に置き、以下の範囲別に距離ベクトルを特定していく
0≦s≦m0 ≦ t ≦ n- 1n + 1 ≦ t ≦ 2n - 1m + 1 ≦ s ≦ 2mA

CBD

結果 3定理(M, N) = (even, even)のときM*Nのトーラス格子のmetricdimensionは≦4である
4つのセンサーで区別できる
3つのセンサーで区別できない証明はできていない(M, N) = (even, even)のときセンサーを(0,0), (m,0), (2m-1,0)(0,2n-1)に置くと全ての頂点を区別する 1ことができた。

(0,n)(0, 2n-1)(0,0)

1(m,0)(2m-1,0)(M, N) = (even, even)のとき(0,0)

範囲は図のようになる

1(0,n)(0, 2n-1)1(m,0)(2m-1,0)(odd, odd), (odd, even)の時と同じ配置では…
1(odd, odd), (odd, even)と同じようなセンサーの配置にするとどうなるか
1(0, 2n-1)

(0,0)

(1,0)

(2m-1,0)(odd, odd), (odd, even)の時と同じ配置では…
1(2m-1,0)(0,0)(0,0)からの距離

1

1(0, 2n-1)1

(odd, odd), (odd, even)の時と同じ配置では…
1(0,0)(m,0)からの距離

(m,0)
m-1

1

(0, 2n-1)(2m-1,0)m-1

(odd, odd), (odd, even)の時と同じ配置では…
1(2m-1,0)(0,0)(0,2n-1)からの距離

21(0, 2n-1)2

(odd,odd), (odd,even)の時と同じ配置で区別できない(1,0), (2m-1,0)が区別できない(1,m-1,2)(1,m-1,2)

結果 3定理(M, N) = (even, even)のときM*Nのトーラス格子のmetricdimensionは≦4である

まとめ
M * Nのトーラス格子のmetric dimension= 3 (M, N)≠(even, even)のとき≦4 (M, N)=(even, even)のとき

今後の課題(M, N) = (even, even) のときの metric dimension は3でないことの証明

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