熊本県立宇土中学校・宇土高等学校 S-M-1 Uto Junior and Senior High School 都道府県を一周しよう！！！『グラフ理論』を使って都道府県を巡る Let's go around the Japan! ! ! “Using the "graph theory” 小山河野要約各都道府県を一度ずつ巡り、日本一周できるかをグラフ理論のハミルトンサイクルを使って検証した。１．目的自転車で日本一周するニュースなどを見て、実際に熊本県を出発し各都道府県を一度ずつ巡り、熊本県に戻ってくることを目的とした。２．方法日本地図の各都道府県にそれぞれ一つずつ点を打ち、隣り合う都道府県同士と実際にある航空路を線で結び、日本地図をグラフ化した。そのグラフにおいて各点を一度ずつ通って元の点に戻るというハミルトンサイクルの有無を調べた。ハミルトンサイクルの有無については判別するための諸定理に当てはめ検証した。３．結果（ｎ≥ 3）ｎ個の頂点を持ったグラフがハミルトンパスを持ち、その始点をＡ、終点をＢとする。d(Ａ)+d(Ｂ)≥ n｛頂点 v からのびる枝の数を d(v)と表す｝が成り立てばグラフはハミルトンサイクルを持つ。ここでは、都道府県の数は 47 なのでｎ＝47、次数が最も多い東京（31）と大阪（22）は d(東京)+d(大阪)≥ 47 を満たす。東京と大阪を結ぶハミルトンパスの存在は確認できたため、ハミルトンサイクルを持つ。４．考察検証するとき、日本地図にたくさんの航空路、陸路を書いて日本地図がたくさんの線で埋もれてしまったので、もっとグラフを整理して検証してみたい。また、世界地図でも同じことができるかどうかチャレンジしてみたい。今回の都道府県一周は実在の道路や新幹線等は考慮していないので、無駄のない旅行経路まで発展させたい。５．結論都道府県をグラフ化したとき、ハミルトンサイクルは存在する。これより、各都道府県を一度ずつ巡り日本を一周することができるということがわかった。６．参考文献小学生の学習教材「ちびむすドリル」、Wikipedia、卒業論文 Hamiltonian、空から見える景色のご案内航空券 ANA 国内線、JAL JAPAN AIRLINES ７．キーワードグラフ理論、ハミルトンサイクル