Scientific and Educational Reports of the Facultyof Science and Technology, Kochi University
Vol. 2 (2019), No.2

T 構造による UMP を持つ完全グラフの辺着⾊法

伊藤宗彦 Munehiko Ito（⾼知⼤学理⼯学部）
概要

距離空間
は，同相な距離が存在して条件「の任意の異なる2 点に対して中点が唯⼀つ存在する」を満たす時，UMP(uniquemidset property)を持つと⾔う。有限集合においては，完全グラフの辺着⾊問題として⾔い換える事が出来る。即ち，有限距離の辺空間 が UMP を持つ事は『と同じ濃度の完全グラフ着⾊が存在して条件「の任意の異なる 2 点 , に対して第 3 点が唯⼀つ存在して辺 ,の⾊と辺 ,の⾊が同じ」を満たす』と同値である。
この論⽂において，ump
7, 9, 11, 13, 15, 17 を⽰す。（ umpは UMP を持つの辺着⾊数の最⼩値を表す。
）

１．序⽂
UMP は実数直線の特徴的な性質の⼀つである[1]。伊藤，⼤⽥，⼩野は論⽂[2], [3]において実数直線の重要な部分集合に対して UMP の研究を⾏い⼀連の成果を得た。無限集合上の代表的な成果としては「無理数空間は UMP を持つ」があげられる。有限集合については，「ump1 」があるが，正21⾓形を考えれば良いので⾃明で，問題は偶数濃度に限られる。偶数濃度については「
ump213 」が得られたが，最⼩着⾊数を決定できたのは「ump4, ump5, ump5」位であった。
今回の成果は「ump5」を発展させたものである。10濃度から⼀気に34濃度まで拡張できたのは，辺着⾊の核となる T 構造を今回発⾒できた事と，辺と mid point を類別してコード化しコンピューターに乗せる事に成功した事による。T 構造という辺着⾊の核を基礎に置き，それをグラフ全体に広げる事で計算量を⾶躍的に削減できた事も成功の鍵である。

1
Received: January 20, 2019
Reviewed by anonymous referee(s), and accepted: Jannuary 29, 2019
Published: March 27, 2019

２．本論,の3, 5, 7, 9, 11, … の頂点の組,を次の様にして類別する。
, , ,…,とし，同じ点を中⼼とする, , , …,正⾓形を 2 重に配置し，外側の正⾓形の頂点を時計回りに，内側の正⾓形の頂点を時計回りに,,,…,とする。
頂点の組,のタイプが O
1, 2, 3, … ,1 であるとは，頂点の順序対,を正⾓形の中⼼を回転中⼼として 2 ⁄ 回転させた時,グラフと等しくなる整数がある時であり，type ,O と書く。頂のタイプが I
1, 2, 3, … ,1 であるとは，頂点の順序対を正⾓形の中⼼を回転中⼼として 2 ⁄ 回転させた時,或いは ,と等しくなる整数がある時であり，type ,I と書く。頂点の組,のタイプが B
0, 1, 2, … ,1 であるとは，,を正⾓形の中⼼を回をで割った余りを として頂点の順序対転中⼼として 2 ⁄ 回転させた時,或いは ,と等しくなる整数がある時であり，type ,B と書く。この類別に O1 から O
1 ，I1 からI
1 ，B0 から B
1 を⽤意したが，実際には約半分の O1 から O ⁄2 ，⁄2 の同値類が出来る。(ここで ⁄2 は ⁄2 以
I1 から I ⁄2 ，B0 から B下の最⼤の整数) これら全ての同値類の集合を T で表す。辺,のタイプは頂点の組 ,のタイプと定義する。
次に， の各頂点に対して前述の頂点の組の同値類を要素とする集合を定義する。type , ∈ MPtypeとは，ある , ∈ type , がMPtype
存在して， , , ,∈ で，辺 ,の⾊と辺 ,の⾊が同じになる時である。
或いは点の組,補題 1. T,,は完全グラフ

補題 2. |T |2

1

3, 5, 7, 9, 11, …
3, 5, 7, 9, 11, …の辺集合の分割である。

。

定理 1. グラフ,の頂点集合 を, , ,…,とする時，次の条件を満たす 上の置換 と結合位置を⽰す整数 が存在するならば，全ての辺が着⾊された辺集合が存在してグラフ,は完全グラフでである。
5, 7, 9, 11, 13, …
UMP を持ち，ump
100。
2 123 。
3 辺集合を,∶023 ∪,2とした時， type : ∈T 。
（の様に 4 点以上の頂点列の最後を除く頂点を順番に辺で結び，この内の両端点以外のある 1 頂点に除いていた最後の 1 頂点を辺で結んでできる構造を T 構造と呼ぶ。）の辺を全て同じ⾊0で塗った時, type , ∶ type , ∈ MPtype,4∈T 。
証明：条件(3)の,∶023 の濃度は 22 であるから，全体では 1 増えた | | 21 である。この事と補題 2 より条件(3)の等式はから T への対応が全単射である事を意味するので，は各タイプの辺をちょうど 1 つずつ含んでいる。そうすると， を 2 ⁄ 回転させたものをとすれば，∶0, 1, 2, … ,1 は互いに素となり，|∶0, 1, 2, … ,1 |21 となるから， ∪∶0,1, 2, … ,1 とすればは完全グラフになる。
また，∶0, 1, 2, … ,1 は互いに素である事から，を⾊ で塗っても塗り替えは起きないので，全てのを塗り終えた状態で以外の各についても条件(4)の等式が成り⽴つ。
1, 2, 3, … ,1
グラフ,
において， MPtype
1
1, 2, 3, ⋯ , 23,，MPtype
3， MPtype00, 22 であるので条件(4)の等式と補題 2 より MPtype∶ ∈は互いに素である。これが他の各についても成り⽴つ。
1, 2, 3, … ,1が UMP を持つ事を⽰す為に，先ず，どの頂点の組 ,に対しグラフても mid point となる頂点がある事を⽰す。補題 1 と条件(4)より , ,∈が 存 在 し て ， type ,type,， type,∈ MPtype
即ち辺,の⾊と辺,の⾊が 0 である。 ,は,を 2 ⁄ 回転させたものだとすると， を 2 ⁄ 回転させた頂点は ,の mid point となる。
次に，どの頂点の組 ,に対しても mid point となる頂点は⾼々1 つである事を⽰す。これを否定して，ある頂点の組,に対して異なる頂点とが存在して辺,と辺,の⾊が同じ で，辺,と辺,の⾊が同じ であったとする。
であったとすると， MPtype∶ ∈は互いに素である事に⽭盾する。
であったとする。 , ,をそれぞれ⁄ 回転させたものを, ,とする。
であった場合は，2,なのでから 4 本以上の辺が出ている事になり， の構成⽅法，つまりは条件(3)のの辺構成⽅法と⽭盾する。
であった場合は，グラフ,においては，type , ∈ MPtype，type , ∈ MPtypeで3あるから MPtype∶ ∈は互いに素である事に⽭盾する。従って，どの頂点の組 ,に対しても mid point となる頂点は⾼々1 つである。
故に，グラフ,は UMP を持つ。使った⾊は 0 から1 である事と論⽂[2]の Proposition 2 (3,ump21 )からumpである。
定理 2. ump
7, 9, 11, 13, 15, 17 。
証明：
各7, 9, 11, 13, 15, 17 について定理 1 の条件を満たす上の置換と結合位置を⽰す整数 を⽰す。 の着⾊は定理 1 の証明における着⾊と同じである。
7：00112
73346596 7 8 9 10 11 12 13
8 12 5 10 2 11 13 4,4と定めると，辺集合,,,,,,,,,,,,,,,,,,,,,,,,,となり辺のタイプ
は O1, B1, B3, O3, B‐3, I1, I3, B0, B2, B‐1, B‐2, I2, O2 となるので条件(3)を満たしている。
グラフ,におけるMPtype
は，MPtype∅, MPtype
B0 ,MPtype
O2 , MPtype
B‐1 ,MPtype
B1, O1, B2 ,MPtype
B‐2 , MPtype
I3 , MPtype
B‐3 , MPtype
I2 , MPtype
O3 , MPtype
I1 , MPtype
B3 ,はMPtype∅ となるので条件(4)を満たしている。従って定理 1 より完全グラフで UMP を持ち，ump7 である。
9：00112339485 6 7 8 9 10 11 12 13 14 15 16 17,4 11 2 15 13 14 6 17 12 7 10 16 54と定めると，辺集合,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,となり辺のタイプは O1,O2, B3, B‐1, O4, B2, B0, B‐4, I2, I1, B1, B‐2, I4, B4, B‐3, I3, O3となるので条件(3)を満たしている。グラフ,に お け る MPtype
は ， MPtype∅,MPtype
O3 , MPtype
B1 , MPtype
O4 , MPtype
B4, B‐4, O1 , MPtype
B‐3 , MPtype
O2 , MPtype
I4 ,4MPtype
B‐2,MPtype
I1,MPtype
B2,MPtype
I3 ,MPtype
B3 ,MPtype
B‐1 ,MPtype
I2 , MPtype
B0 , MPtype∅ とな る の で 条 件(4)を満たしている。従って定理 1 よりは完全グラフで UMP を持ち，ump9 である。

11：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 1 3 6 2 11 9 13 20 14 7 21 5 15 17 18 10 4 16 19
20 21と定めると，辺集合,,,,3,,,
8 12,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,となり辺のタイプは O1, O2, O3, O4, B2, B‐2, B‐4, I4, I5, B4,
B‐3, B‐5, B1, I2, I1, B3, O5, B‐1, I3, B0, B5 となるので条件(3)を満たしている。グラフ,における MPtype
は，MPtype∅, MPtypeO3 ,MPtypeO5 , MPtype
O1, B2, B1 , MPtype
B‐5 ,MPtypeO4,MPtypeI2,
MPtypeB0,
MPtypeI1,
MPtypeB‐2,MPtype
I4,MPtype
O2 ,MPtype
I5 ,MPtypeB‐1 ,MPtypeI3,
MPtypeB4,MPtypeB‐3,MPtypeB5,
MPtypeB‐4,MPtypeB3,はMPtype∅ となるので条件(4)を満たしている。従って定理 1 より完全グラフで UMP を持ち，ump
11 である。
13：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 1 3 6 2 8 13 12 4 17 20 19 15 9 24 16 7 23 21 11
20 21 22 23 24 25,4と定めると，辺集合,,
22 5 25 18 10 14,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,となり辺のタイプは O1, O2, O3, O4, O6, B‐5, B‐1, O5, B0, I3, I1, I4, B‐6, B‐2, I5, B4,B‐3, I2, B3, B2, B‐4, B6, I6, B5 となるので条件(3)を満たしている。グラフ,における MPtype
は，MPtype∅, MPtype
O3 , MPtype
5

O5 , MPtype
O1 , MPtype
O2, B5, B‐6 , MPtype
B2 ,MPtypeO4,MPtypeB4,MPtypeB‐5,
MPtypeB‐3,MPtypeI2,
MPtypeI5,
MPtypeB3 ,MPtypeI4 ,MPtypeB6 ,MPtypeB‐4,MPtypeI6,
MPtypeB‐1,MPtype
B1,
MPtypeI1,
MPtypeO6,
MPtypeI3,
MPtypeB0,
MPtypeB‐2,MPtype∅ となるので条件(4)を満たしている。従って定理 1 よりは完全グラフで UMP を持ち，ump13 である。
15：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 190 1 3 6 2 8 13 15 4 11 27 21 24 12 19 5 26 25 10 2320 21 22 23 24 25 26 27 28 29,4と定めると，辺集合
28 17 7 16 18 14 22 29 9 20,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,となり辺のタイプは O1,O2, O3, O4, O6, O5, B‐2, B4, O7, B‐1, I6, I3, B3, B‐7, B1, B‐6, I1, B0, B2, I5, I4, B5, B6,I2, B‐4, B7, I7, B‐5, B‐3 となるので条件(3)を満たしている。グラフ,におけ る MPtype
は ， MPtype∅ , MPtype
O3 , MPtype
O5 , MPtype
O1 , MPtype
O2, B1, B3 , MPtype
O4 ,MPtype
B‐7,
MPtypeO6,
MPtypeB‐4,MPtypeB7,
MPtypeB5,
MPtypeI3,
MPtypeB6 ,MPtypeI5 ,MPtype
O7 ,MPtype
I7,
MPtypeB‐5,
MPtypeB‐1,
MPtypeI2,
MPtypeB‐3,MPtypeI6,
MPtypeB‐6,MPtypeI1,
MPtypeB4,MPtypeB‐2,MPtype
I4,MPtype
B0,MPtypeB2 , MPtype∅ となるので条件(4)を満たしている。従って定理 1 よりは完全グラフで UMP を持ち，ump15 である。
17：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 1 3 6 2 8 13 4 17 11 18 21 9 28 33 16 20 29 14 76

20 21 22 23 24 25 26 27 28 29 30 31 32 33,
25 15 31 32 12 23 27 5 30 19 10 24 26 2217と定めると，辺集合,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, となり辺のタイ
プは O1, O2, O3, O4, O6, O5, O8, B4, B‐6, B‐7, I3, B5, B‐2, I5, B0, B‐4, I8, B2, O7, B‐1,B7, B1, I1, B‐3, B6, I4, B‐5, B‐8, I6, B8, B3, I2, I7 となるので条件(3)を満たしている。グラフ ,におけるMPtype
は，MPtype∅, MPtype
O3 , MPtype
O5 , MPtype
O1 , MPtype
O2 ,MPtype
O6,MPtype
O4,MPtype
B‐4,MPtype
O7,MPtype
I1,MPtype
B7,
B8 ,MPtype
I7 ,MPtype
B‐7 ,MPtypeMPtype
B5,MPtype
I4,MPtype
B4,
MPtypeB‐6, I2, B‐8 , MPtype
B‐5 , MPtype
B6 ,MPtypeO8,
MPtypeI6,
MPtypeB0,
MPtypeB‐2,MPtypeI8,
MPtypeB2,
MPtypeB‐1,
MPtypeI3,
MPtypeB3,
MPtypeB‐3,MPtype
I5,
MPtypeB1,
MPtype∅ となるので条件(4)を満たしている。従って定理 1 よりは完全グラフで UMP を持ち，ump17 である。
参考⽂献
[1] A. D. Berard Jr., Characterizations of metric spaces by use of their midsets:intervals, Fund. Math. 73(1971), 1-7.
[2] M. Ito, H. Ohta and J. Ono, A graph-theoretic approach to the unique midset
property of metric spaces, J. London Math. Soc. 60(1999), 353-365.
[3] 伊藤宗彦，⼤⽥春外，⼩野仁, A graph theoretic approach to the UMP, 京都
⼤学数理解析研究所講究録 953(1996), 49-60.

7