グラフ理論における一筆書きとn筆書き

データ分析
データ分析最適化問題物流
0

この記事ではまず、グラフ理論における一筆書きができる条件についてまとめる。
また、一筆書きができないとき何筆で書くことができるのか、すなわち、n筆書きの理論ついて数学的に紹介する。

スポンサーリンク

そもそもグラフ理論とは

グラフ理論におけるグラフとは頂点 $\boldsymbol{V}$ と辺 $\boldsymbol{E}$ からなる集合であり、$\boldsymbol{G} = (\boldsymbol{V}, \boldsymbol{E})$ と表す。(正確には有向グラフと無向グラフがあるが、この記事では無向グラフと単に「グラフ」と表現する。)
身近な例でいえば、電車の駅が頂点、線路が辺となるグラフや、交差点が頂点、道路が辺となるグラフを考えることができる。

頂点につながる辺の数を次数という。
一筆書きやn筆書きはこの次数が重要になる。

スポンサーリンク

一筆書きできる条件

「一筆書き」とは筆を机から一度も離さずに全ての辺をただ1回だけ通って描くことができることである。
一筆書きできる条件は結論から言うと、条件は以下の通りである。

次数が奇数となる頂点が2個または0個である

したがって、グラフが一筆書きできるかどうかを判別したいときは頂点の次数のみに注目すれば良いということになる。ちなみに、次数が奇数となる頂点が奇数個であるグラフは存在しない。

特に、全ての頂点の次数が偶数となるグラフをオイラーグラフという。
オイラーグラフではどの頂点から出発しても一筆書きをすることができ、出発した点が終点になる。
このような、ある頂点から全てを辺を通り、もとの頂点に戻るような閉路をオイラー閉路という。
「すべての頂点の次数が偶数 ⇔ 一筆書きできる」の証明はこの記事を参考にされたい。

次数が奇数となる頂点が2個であるグラフを準オイラーグラフという。
準オイラーグラフでは、次数が奇数となる2つの頂点がそれぞれ一筆書きの始点と終点になる。
このような、ある頂点から全ての辺を通るような道をオイラー路という。
上の証明を少し考察すると準オイラーグラフが一筆書きできる理由は簡単に示すことができる。

n筆書きとは

では、一筆書きができないグラフは何筆で書くことができるだろうか?
このようなグラフの理論はn筆書きと呼ぶことにする。

基本的な考え方

上の一筆書きできない例として挙げたグラフは何筆で書くことができるだろうか?
この図は左にある準オイラーグラフに1本の辺が追加されたグラフとも考えることができる。
したがって、準オイラーグラフの分の一筆と、もう一本の辺の分の一筆で、合わせて2筆と考えることができる。
つまり、n筆書きでは $n=$(オイラー路の数) として求めることができる。

オイラー路の数

このようにグラフをオイラー路(オイラー閉路を含む)に分解して考えるのがn筆書きポイントである。
では、オイラー路の数はどのようになるだろうか。

結論から言うと、奇数次数となる頂点の数を $2m~(m \in \mathbb{N})$ とすると、オイラー路の数は $m$ となる。(上述したように奇数次数の頂点の数が奇数になることはない。)
証明は帰納法によって簡単に示すことができる。

【証明】
1. $m=1$ のとき、このグラフ自体が準オイラーグラフなので、自明に成立する。
2. 自然数 $k$ を用いて $m=k$ のとき、奇数次数の頂点の数が $2k$ のグラフに含まれるオイラー路の数が $k$ 個であると仮定し、 $m=k+1$ のとき、すなわち奇数次数の頂点の数が $2k+2$ のグラフ $\boldsymbol{G}$ を考える。
任意の2つの奇数次数の頂点を始点と終点とするオイラー路 $C$ を除くと、残ったグラフ $G \setminus C$ の奇数次数の頂点の数は $2k$ である。(オイラー路に含まれる各頂点の次数が「入る」分と「出る」分で2の倍数だけ減るので、各頂点の次数の奇偶は変わらない。)
したがって、仮定により$\boldsymbol{G} \setminus \boldsymbol{C}$ に含まれるオイラー路は $k$ 個である。
すなわち、グラフ $\boldsymbol{G}$ に含まれるオイラー路は $k+1$ 個である。

以上の帰納法によって、奇数次数となる頂点の数を $2m~(m \in \mathbb{N})$ とすると、オイラー路の数は $m$ となる。

結論

結局、n筆書きの場合も頂点の次数に注目すればよく、奇数次数の頂点の数が $2m$ のとき、$n=m$ となる

ちなみに、n筆書きを構成するオイラー路は「書き方」や「書き順」のようなものに対応し、とてもたくさんの書き方が存在する。

まとめ

今回は一筆書きやn筆書きについて紹介した。
この理論は配達経路のようなものに応用され、関連として巡回セールスマン問題などが挙げられる。

スポンサーリンク
H-MEMO

コメント