数理解析研究所講究録
第 1864 巻 2013 年 138-143

138

4-正則グラフの向きづけ問題
弘前大学大学院理工学研究科 南部友見 (Tomomi Nanbu)
Graduate School of Science and Technology, Hirosaki University
弘前大学大学院理工学研究科 金正道 (Masamichi Kon)
Graduate School of Science and Technology, Hirosaki University
概要

4. 正則連結無向グラフが与えられているとする。各点に対してその点に接続している 4 本の辺のうち 2 本はその点が始点になりその他の 2 本はその点が終点になるように、 すべての辺に向きをつける問題を向きづけ問題とよぶことにする。本稿では、 向きづけ問題の解がオイラー閉路を求める問題に帰着されることを示す。 この問
題は、 ユニット折り紙作品として多面体を作成する場合、 新たな作品を模索するとき有用になることが期待される。 1 枚の折り紙から 1 つのユニットを作成し、 いくつかのユニットを組み合わせて形を作るタイプの折り紙作品をユニット折り紙という。さまざまなタイプのユニットが考案されていて、 さまざまな多面体を作成する方法 (折り目の付け方と組み合わせ方) がいくつかある。

1. 折り紙ユニットで作る多面体

図 1 のように折り紙で作成したものをユニットとよぶ。いくつかのタイプのユニットが考案されていて、 図 1 のユニットはそのべ式ユニット 1 とよばれるものである。 その他のタイプのユニットについては、例えば、 [5,6,7] 参照。 いくつかのユニットを図 2 のようにが作差し込んで組み合わせていくと、 図 3 に示すような 4 種類の多面体$U_{3},$$U_{6},$$U_{12},$ $U_{30}$成できる。 ユニットのタイプや折り目の付け方によってさまざまな形の多面体が考案されを作成するために必要なユニットている (例えば、 [5,6,7] 参照) 多面体。

$U_{3},$ $U_{6},$$U_{12},$ $U_{30}$の数はそれぞれの添え字 3,6,12,30 である。
さまざまなタイプのユニットに共通する特徴として、「他のユニットに差し込む部分が2 つある」「他のユニットに差し込まれる部分が 2 つある」が挙げられる (図 2) 。この性質を利用して、 ユニットのタイプや折り目の付け方を無視して、 ユニットの組み合わせ方にのみ注目し、 ユニットの組み合わせ方を有向グラフとして表現し、 グラフ理論を用いて考察する。本稿で用いるグラフ理論に関する用語や記号は、特に断らない限りすべて [10]に従う。

図1ユニット図2

ユニットの差し込み方

1 そのべ式ユニ ノ トは、 薗部光伸によつて 1960 年代考案され、 シンプルな折り方ながら応用範囲が広く、ユニット折り紙の普及のきつかけになった。 折り方は、 http: $//wwwl$ .odn ne jp/asobo/4121-0.htm 参照。
$\grave{}$$\grave{}$139
美茎言–$\underline{=}\Rightarrow$

図 3–1

図 3–2 砺図 3–3$U_{3}$

図3$U_{12}$

図 3–4$U_{30}$

いくつかのユニットによって作成された多面体

2. グラフ論的考察

多面体砺が$n$個のユニットによって構成されているとする。 多面体砺に使用されている $n$ 個のユニットに 1 から $n$ まで番号を付け$V_{n}=\{1,2, \cdots, n\}$とする。 $i,j$ 欧琉に対して、 図 2 のように、 ユニットをユニットに差し込んでいる状態を $iarrow i$ で表す。 多面体砺に対して、 有向グラフ $D_{n}=(V, E_{n})$ を考える。
で、 $i,j\in V_{n}\iota$ ’ 魁して$i$$i$

ここ$(i,j)\in E_{n}\Leftrightarrow iarrow j$である。有向グラフ
は、多面体計図である。 ただし、 有向グラフ$D_{n}$$U_{n}$$D_{n}$を作成するときのユニットの組み合わせ方を表す設から多面体を作成する場合、 ユニットのタイプや折り目の付け方によって、実際に多面体が作成できる場合とできない場合があることに注意。
図 4 は、 図 3 の多面体表している。 多面体$U_{n}$

性質 1

それぞれに対応する有向グラフに魁応する有向グラフ
は、 次のような特徴をもつ。

$U_{3},$$U_{6},$$U_{12},$ $U_{30}$$D_{3},$ $D_{6},$$D_{12},$ $D_{30}$を$D_{n}$の基礎グラフ (弧の方向を無視した無向グラフ) は、 4. 正則連結平面無向グラ
フである。
$D_{n}$

性質 2の基礎グラフには、 ループは現れないが、 多重辺は現れる場合がある (例えば、 図 4 の$D_{n}$$D_{3})$。

性質 3$D_{n}$の各点 $i\in$ 琉の出次数 outdeg(i) と入次数 indeg(i) はともに 2 である。

140

図4

図 $4-1$$D_{3}$

図 4–3$D_{12}$多面体$U_{6},$$U_{3},$図 4–4$U_{12},$ $U_{30}$に対応する有向グラフ

逆に、 性質 1,2, 3 をもつ有向グラフ$D_{n}$$D_{30}$$D_{3},$ $D_{6},$ $D_{12},$ $D_{30}$が与えられたときに、 折り紙ユニットを用を設計図とする多面体を作成できるかを考えると、 作成できる場合とできない場合があるだろう。 多面体が作成できることは実際に多面体が作成できれば示されたことになるが、 多面体が作成できないことを結論づけるのは、 ユニットのタイプ (ユニットの折り方) や折り目の付け方が理論上無限にあるので注意が必要である。しかし、性質 1,2,3 をもつ有向グラフは、 ユニット折り紙作品として多面体を作成する場合、 新たな作品を模索するとき、 新たな作品の設計図の候補と考えることができる。 よって、 性質 1,2,3 をもつ有向グラフを列挙またはなるべくたくさん生成し、 新たな作品の設計図にないて$D_{n}$り得るかどうかを試行錯誤などによって検討することが、新たな作品を模索するとき有用になると期待される。 また、 性質 1,2, 3 をもつ有向グラフが列挙できれば、 使用するユニットの数とタイプと折り目のつけ方を固定した場合に、多面体が作成可能か不可能かの判定ができるようになる。 性質 1,2, 3 をもつ有向グラフを直接列挙またはなるべくたくさん生成するのは困難であると思われるので、以下のような手順に分けて考える。

141
手順 1

ループを含まない 4-正則連結平面無向グラフを列挙またはなるべくたくさん生成する。

手順 2 手順 1 で求めた各 4-正則連結平面無向グラフに対して、 性質 3 を満たすような辺の方向づけを列挙またはなるべくたくさん生成する。
手順 1 は、 [2,3,4,9] の方法によってある程度実現できる。 手順 2 を実現するために、 次節において、 4-正則連結無向グラフが与えられたとき、 性質 3 を満たすような辺の方向づけを列挙する問題が、 オイラー閉路を列挙する問題に帰着できることを示す。 ここで、 グラフの平面性の条件は後の議論を簡単にするわけではないので課さないことにした。 本稿では、 オイラー閉路を [10] におけるオイラー小道の意味で用いている。 オイラー閉路の列

挙は、 [1] の方法によってある程度実現できる。

3. 4-正則グラフの向きづけ問題
4-正則連結無向グラフ が与えられたとき、の各点 に対して outdeg(i)indeg $(i)=$となるようにのすべての辺に向きをつける問題を、 $G$ に対する向きづけ問題とよぶことにし、そのように辺が向きづけられた有向グラフを $G$ に対する向きづけ問題の解とする。
$G$$G$

$i$

$=$

$G$

$2$

ただし、本節で扱うグラフは、ループを含まないことを仮定する。図 4 のの基礎グラフは 4 正則連結無向グラフであり、 それぞれの基礎グラフに対する向きづけ$D_{3},$問題の 1 つの解が$D_{3},$ $D_{6},$ $D_{12},$ $D_{30}$$D_{6},$ $D_{12},$ $D_{30}$である。

4-正則連結無向グラフに対する向きづけ問題を考察するために、 いくっか定理を準備する。

定理 1([10] の定理 6.2) (Euler, 1736) 連結無向グラフ

めの必要十分条件は、$G$$G$がオイラー．グラフであるたの各点の次数がすべて偶数であることである。

定理 2([10] の定理 23.1) 連結有向グラフ $D$ がオイラーであるための必要十分条件は、の各点 で outdeg $(i)=$ indeg(i) が成立することである。

$D$$i$

定理 1 より直ちに、 次の系が得られる。

4-正則連結無向グラフは、 オイラー系1グラフである。

定理 2 より直ちに、 次の系がえら得られる。

系 24-正則連結無向グラフに対する向きづけ問題の解は、 オイラーである。
系 1 より、 4-正則連結無向グラフにはオイラー閉路が存在する。 次の定理は、 オイラー閉路を求めることによって、 向きづけ問題の解が得られることを示している。 よって、 向きづけ問題の解が必ず存在することもわかる。
定理 3を 4-正則連結無向グラフとし、 $P$ をの任意のオイラー閉路とする。 このとの辺を $P$ がたどる方向に沿って向きづけを行った有向グラフは $G$ に対する向きづき、け問題の解になる。
$G$

$G$

$G$

次の定理は、 向きづけ問題の任意の解はあるオイラー閉路に対応する向きづけによって得られることを示している。

142に対する向きづけ問題の任意の解とすを 4-正則連結無向グラフとし、 $D$ をのあるオイラー閉路 $P$ が存在して、 の辺を $P$ がたどる方向に沿っる。 このとき、て向きづけを行った有向グラフと $D$ が一致する。

定理 4$G$

$G$

$G$

$G$

を 4. 正則連結無向グラフとする。 定理 3 および 4 より、 $G$ のオイラー閉路が列挙できれば、 $G$ に対する向きづけ問題の解が列挙できることがわかる。 ただし、 $G$ の異なるオイラー閉路に対応する有向グラフが一致する ( $G$ の向きづけ問題の解として一致する)$G$場合があるので、 $G$ のオイラー閉路を列挙するということは、 $G$ の向きづけ問題の解の列挙に対して無駄 (重複) があるということになる。この無駄 (重複) がないように効率的に $G$ のオイラー閉路を列挙する工夫が、 今後の課題として残る。の異なる 2 つのオイラー閉路とする。の基礎グラフを
例えば、 図 4 の$G_{6}$$D_{6}$$G_{6}$$4arrow 6arrow 1arrow 4arrow 2arrow 1arrow 3arrow 2arrow 5arrow 3arrow 6arrow 5arrow 4$$2arrow 1arrow 3arrow 2arrow 5arrow 3arrow 6arrow 1arrow 4$

対する向きづけ問題の解$D_{6}$

および $4arrow 6arrow 5arrow 4arrow$にそれぞれ対応する有向グラフはどちらも$G_{6}$にになる。

4. 結論
4-正則連結無向グラフが与えられているとする。 各点に対してその点に接続している 4本の辺のうち 2 本はその点が始点になりその他の 2 本はその点が終点になるように、すべての辺に向きをつける問題を向きづけ問題とよんだ。本稿では、向きづけ問題の解の列挙がオイラー閉路の列挙に帰着されることを示した。向きづけ問題の解の列挙またはなるべくたくさん生成することは、 ユニット折り紙作品として多面体を作成する場合、 新たな作品を模索するとき有用になることが期待される。また、向きづけ問題の解の列挙またはなるべくたくさん生成することを効率的に行う工夫は今後の課題であり、ユニット折り紙作品として新たな多面体の模索も今後試みたい。

参考文献[1] 菊地洋右，オイラー路の列挙，情処学アルゴリズム研報，Vol. $10(AL-131(7))$ , pp.1-4,

2010[2] 松田洋一．榎原博之・中野秀男・堀内諭，正則グラフを生成するアルゴリズム，情処学
アルゴリズム研報，Vol. $92(AL-25(9))$ , pp.1-8, 1992
[3] 前川浩二・松田洋一．榎原博之・中野秀男，正則グラフを生成するアルゴリズムのランダム性について，情処学アルゴリズム研報，Vol. $92(AL-28(58))$ , pp.85-91, 1992
[4] M. Meringer, Fast generation of regular graphs and construction of cages. Journal ofGraph Theory, Vol.30, pp.137-146, 1999
[5] 三村文武，ユニットにより構成される多面体の模型，九州工業大学研究報告 (工学),Vol.47, pp.87-97, 1983

143
[6] 三村文武，ユニットにより構成される多面体の模型 II, 九州工業大学研究報告 (工学),Vol.49, pp.69-76, 1984

[7] 三村文武ユニットにより構成される多面体の模型 III, 九州工業大学研究報告 (工学 , Vol.49, pp.77-85, 1984$)$

[8] 南部友見金正道，折り紙ユニットで作る多面体の配色について，商経学叢 (掲載予定)[9] 西関隆夫，グラフの平面性判定法，情報処理，Vol.24, pp.521-528, 1983
[10] R. . ウィルソン (西関隆夫西関裕子訳), グラフ理論入門 (原書第 4 版), 近代科学社，2001$J$