オイラーグラフの定理(一筆書きできる条件)とその証明

一筆書きできる条件

連結なグラフにおいて,

  • 一筆書きして戻ってこれる     \iff 全ての頂点の次数が偶数
  • (スタートとゴールが異なるような)一筆書きができる     \iff 次数が奇数であるものがちょうど2つ

例えば,という漢字は一筆書きできますが,という漢字はどうがんばっても一筆書きできません。

この記事では,一筆書きできる条件を示したオイラーグラフの定理について紹介します。

用語・記号の準備

一筆書きできる条件について理解するために,グラフ理論の用語を説明します。

  • グラフとは,「頂点」と頂点同士をつなぐ「辺(枝)」の集合を表します。頂点の集合を VV,辺の集合を EE と書き,グラフを G=(V,E)G=(V, E) と表すことが多いです。→グラフ理論の基礎

  • オイラーグラフとは オイラーグラフとは,一筆書きしてもどってこれる,つまりある頂点から全ての辺を通ってもとの頂点にもどってくるような閉路が存在するグラフのことを言います(そのような閉路のことをオイラー閉路といいます)。

  • 準オイラーグラフとは,(スタートとゴールが異なるような)一筆書きができる,つまりある頂点から全ての辺を通るような道が存在するグラフのことを言います(そのような道のことをオイラー路といいます)。

  • 頂点の次数とは,その頂点から出ている辺の数を表します。 連結グラフとは

  • 連結とは,全ての頂点どうしが何本かの辺を通って行き来できることをいいます(任意の2頂点の間に道がある)。

一筆書きの条件

「日」や「田」くらいなら一筆書きできるかどうか試せば分かりますが,もっと大きなグラフになると判断するのは難しそうですね。

そこで使えるのが,冒頭でも述べたオイラーグラフに関する定理です。

一筆書きできる条件

連結なグラフにおいて,

  • オイラーグラフ     \iff 全ての頂点の次数が偶数
  • 準オイラーグラフ     \iff 次数が奇数であるものがちょうど2つ

各頂点の次数が偶数なのか奇数なのかを数えていけば一筆書きできるかどうか分かるという定理です。

例題

図のようなグラフは一筆書きできるか?

オイラーグラフ

上の図では,次数が3の点が2つ(青い点)で残りの頂点の次数は偶数なので準オイラーグラフです(実際に青い点から始めれば一筆書きできるので試してみてください)。

オイラーグラフの定理の証明

「オイラーグラフ     \iff 全ての頂点の次数が偶数」を証明します。証明の途中で実際に一筆書きの方法も構成しています。

「オイラーグラフ→次数が偶数」の証明

CC をオイラー閉路とする。CC において頂点 vv が現れたら,vv に入る枝と出る枝を通るので,1回につき2つの枝を通る。全ての枝を1度通るので vv の次数は偶数となる。

「次数が偶数→オイラーグラフ」の証明

辺の数 kk に関する帰納法で証明する。全ての頂点の次数が偶数なので k2k\geq 2 であり,k=2k=2 のときにオイラーグラフなのは自明。k<nk < n のとき定理を仮定して k=nk=n のときも成立することを証明する。

オイラーグラフの証明

全ての頂点の次数が偶数のときグラフ GG は閉路 CC を持つ(行き止まりがないので,適当な頂点からスタートしてつながった点に移動していけばいつかは通った点のどこかに戻ってくる)。GG から CC を除いたグラフを GCG\setminus C と書く。

帰納法の仮定より,GCG\setminus C の各連結成分 HiH_i にはオイラー閉路 CiC_i が存在する。 CC をまわりつつ HiH_i との共通点に到達したら CiC_i を一周してもとの頂点にもどってくることで一筆書きが構成できる(図参照:オイラー閉路は,0,1,2,0,3,4,5,6,7,4,8,9,10,8,10,00,1,2,0,3,4,5,6,7,4,8,9,10,8,10,0)。

※連結成分とは,極大で連結な部分グラフのことをいいます。「島」をイメージしていただきたいです。

後半はわりと長い証明になってしまいましたが,厳密にやろうとするとこのようになります(他のいくつかのサイトでは間違っている証明が載っていました)。

また,準オイラーグラフに関しても同様に証明できます。

練習問題

例題

という漢字は一筆書きできて,という漢字はどうがんばっても一筆書きできないことを確認せよ。

解答
  • 日は次数が3の頂点が2つあるので,準オイラーグラフ。
  • 田は次数が3の頂点が4つあるので,オイラーグラフでも準オイラーグラフでもない。

これで一筆書きできるか簡単に判定できます。

Tag:数学的帰納法をわかりやすく【例題3問、応用5パターン】