オイラー閉路における同頂点間距離の最小値について野月麻衣

1(指導教員：萩田真理子)

はじめに

3.2


定理 2

n 人が順番に発表を行うとき，それぞれの発表を比較するための発表順序を考えたい．どの 2 人も連続して発表するようにし，同じ人の発表はなるべく近くならないようにする．また，最後の人の発表が終わった
とき，再び最初の人から順に発表を繰り返しても，同じ人の発表の間隔は近くならないようにする．このような問題を考えたとき，n が奇数ならば，全体の発表順序は完全グラフのオイラー閉路で辿られる頂点の順序に置き換えて考えることができる．すなわち，頂点数が奇数の完全グラフのオイラー閉路上の頂点を辿ったとき，同じ点の距離がなるべく近くならないようなオイラー閉路を求めることが本研究の目的である．

2

定義

基本的な定義グラフとは，頂点集合と，頂点同士を結ぶ辺集合からなるもので，完全グラフとは，任意の 2 頂点間が辺で結ばれているようなグラフである．各頂点とその次の頂点が辺で結ばれているような頂点の列を道といい，vk を頂点としたとき，v0 から vn までを辿る道を v0 , v1 , . . . , vn−1 , vn のように表記し，この例では v0 と vn の距離は n である．v0 = vn のとき，道v0 , v1 , . . . , vn−1 , v0 は閉路といい，グラフのすべての辺を 1 度だけ通るような閉路をオイラー閉路という．
また，頂点 v と w を結ぶ辺を {v, w} または {w, v} と表す．

2.2

3.3 n = 5 のとき
定理 3

本研究で導入する定義

4定理

D(n) の下限について

定理 1



オイラー閉路の全数探索

7 以上の n については，D(n) の値を簡単に求めることはできなかったため，指定した小さな n についてオイラー閉路の全数探索を行い，D(n) の値を調べた．
各 n について，同頂点間距離の最小値 i が 3 ∼ n − 2となるようなオイラー閉路を探した結果が表 1 である．

オイラー閉路が存在するための必要十分条件は，そのグラフのすべての頂点の次数が偶数であるということが知られている．これを用いて以下の定理を証明する．

3.1



D(5)=3(証明)
定理 1 と定理 2 より，ただちに導かれる．□

道上の同じ名前の頂点の距離を同頂点間距離といい，頂点数が n(ただし n は奇数とする) の完全グラフのすべてのオイラー閉路における同頂点間距離の最小値のうち，最も大きいものを D(n) と定義する．

3

5 以上のすべての奇数 n について，D(n) ≤ n − 2
(証明)
頂点の名前を，1, 2, . . . , n とする．
(i)D(n) = n とする．このとき，そのオイラー閉路には道 n, 1, 2, 3, . . . , n − 1, n が含まれているとしてよい．
道の最後の点 n の次に続く点を考えたとき，D(n) = nを満たすためには点 1 が続かなければいけないが，これでは辺 {n,1} を 2 回通ることになり，全体がオイラー閉路をなしていることに矛盾する．
(ii)D(n) = n − 1 とする．このとき，そのオイラー閉路には道 n, 1, 2, 3, . . . , n−2, n が含まれるとしてよい．道の最後の点 n の次に続く点を考えたとき，D(n) = n−1を満たすためには点 1 または点 n − 1 が続くはずである．点 1 については (i) と同様に矛盾するので，点 n−1が続くことになる．次に，最初の点 n の前の点を考えると，条件を満たすためには点 n − 2 または点 n − 1が続くはずである．点 n − 2 については上の場合と同様に矛盾するので，点 n − 1 が続かなければいけないが，これでは辺 {n,n-1} を 2 回通ることになり，矛盾する．□

ここで，本研究で用いるグラフ理論の用語をいくつか定義しておく．

2.1

D(n) の上限について

表 1: オイラー閉路の探索結果
HH
HH i 3 4 5 6 7 8 9HHn
5◦ -5 以上のすべての奇数 n について，D(n) ≥ 3

(証明)
頂点数が奇数の完全グラフは，すべての点の次数が偶数なので，オイラー閉路をもつ．オイラー閉路に含まれる部分閉路は少なくとも 3 つの辺からなり，同頂点間距離は必ず 3 以上となる．□

31011--

7911◦◦◦◦◦◦×◦◦◦◦×◦◦×--13◦◦◦◦◦◦◦◦×表 1 において，◦ は存在したもの，× は存在しなかったものを表している．15 以上の n については，最小値が 6 以上になる場合の計算に非常に時間がかかり，

(証明)A2 の先頭の要素を ap+1 = a1 +1 と表す．条件 1 により，列 B の先頭の p+1 個の要素である a1 , a2 , . . . , ap , ap+1
は，隣同士の差がすべて異なるように並ぶ．任意のu, v ∈ {1, 2, . . . , n}(u ̸= v) について，|u − v| = |al −al+1 | となる l ∈ {1, 2, . . . , p} がただ 1 つ存在する．u −v = al − al+1 のとき、k = u − al + 1 とおけば，Ak には，al +k−1 = u と al+1 +k−1 = al −u+v+k−1 = v
n(n−1)
が隣り合って現れる．u, v の選び方は 2 ，列 B で
n−1
隣り合う 2 点の数は 2 n より，1 回ずつ現れるので，A1 が条件 1 を満たすならば，列 B はオイラー閉路である．
また，同頂点間距離の最小値が p 以下になる場合について，A1 に同じ要素がある場合を条件 2 で除き，ない場合を条件 3 で除いている．□

最後まで計算することができなかった．この結果から，13 以下の n については，D(n) の値は表 2 のように決まった．また，見つけたオイラー閉路には，次のようなものがあった．
表 2: D(n) の値n D(n)5379461113810n = 7 のとき
7,1,2,3,4,1,5,2,4,6,1,3,5,7,2,6,3,7,4,5,65.2

それぞれの n について，定理 4 の条件を満たす A1を求め，同頂点間距離の最小値が n+12 のオイラー閉路を求めてみた．7 ≤ n ≤ 121 のすべての奇数 n について実行した結果，n = 9 のとき，全数探索ではD(9) = 6 が示されているにも関わらず，条件を満たすA1 は存在しないことがわかった．しかし，n = 9 を除
く 7 ≤ n ≤ 121 のすべての奇数 n に対しては，条件を満たす A1 を見つけることができた．以下に，n = 121のときの例をあげる．

n = 9 のとき
9,1,2,3,4,5,6,1,7,2,4,8,3,1,5,2,9,6,7,8,5,3,9,4,1,8,6,3,7,5,9,8,2,6,4,7
n = 11 のとき
11,1,2,3,4,5,6,7,8,1,9,2,4,10,3,5,7,1,6,2,8,9,11,10,5,1,3,6,4,7,11,2,5,9,10,1,4,8,3,11,6,9,7,2,10,8,5,11,4,9,3,7,10,6,8
n = 13 のとき
13,1,2,3,4,5,6,7,8,9,10,1,11,2,4,12,
3,5,7,9,6,1,8,11,13,12,2,5,10,4,7,1,
3,8,6,13,2,9,5,12,7,11,3,10,6,4,8,13,
9,12,1,5,11,10,7,2,6,3,13,4,1,9,11,12,10,2,8,5,13,7,3,9,4,11,6,12,8,10

5

A1 の探索n = 121 のときの A1
121,3,5,9,14,7,13,21,11,20,31,16,28,41,18,34,48,
23,40,58,25,44,64,27,51,30,56,78,33,60,88,36,66,95,38,69,101,43,77,112,46,86,50,91,53,109,55,114,75,119,68,118,71,117,74,116,63,111,62,2
5.3 一般的な n についての A1 の存在定理
定理 5n を用いて表現した下限最小値が n+12 のオイラー閉路を求める定理

11 以上のすべての奇数 n について，D(n) ≥ n+12



定理 4
証明は省略するが，流れとしては，n = 8k + 1, 8k +長さ p = n−13, 8k + 5, 8k + 7 の 4 つに場合分けし，それぞれの場合2 の列 A1 : a1 , a2 , a3 , . . . , ap を考について，定理 4 の条件をすべて満たすような A1 をえる．
作るための並べ方を決めるという方法をとる．このとA1 が以下の条件をすべて満たすとき，Ak を，A1き，n = 8k + 1 の場合は k = 2 以上で成立し，それ以の各要素にぞれぞれ k − 1 を足して n で剰余を外の場合は k = 1 以上で成立する．
とった列とすると，n 個の列を順に並べた列 B :6 まとめと今後の課題
A1 , A2 , . . . , An は同頂点間距離の最小値が p+1 =本研究では，D(n) の取り得る範囲について考察し，n+12 のオイラー閉路をなす．
n = 5 のとき D(5) = 3，n = 7, 9, 11, 13 のとき D(n) =n − 3，n≥15 のとき n+1• 条件 12 ≤ D(n) ≤ n − 2 ということがわかった．
|a1 −a2 |, |a2 −a3 |, . . . , |ap−1 −ap |, |ap −(a1 +今後は，D(n) の下限や上限をより狭める証明に取り
1)| に 1 から p がすべて現れる．
組んでいきたい．特に，n が小さいときの全数探索の結果より予測される，D(n) ≤ n − 3 の証明を目指し• 条件 2たい．
a , a , . . . , a はすべて異なる．

5.1

12p• 条件 3i < j としたとき，aj ̸= ai + 1

ただし |x| は、±x mod n の小さい方を表す．

参考文献[1] R.J. ウィルソン (原著)，西関隆夫・西関裕子 (共訳)，グラフ理論入門，近代科学社，2001
4