グラフ理論で考える近畿地方

1

4 年Ａ組

辻春花

4 年Ａ組

中尾邦光

4 年Ｂ組

太田英利

指導教諭

河合士郎

指導教諭

川口慎二

要約
サイエンス研究会数学班は 3 つのテーマに分かれて研究活動を行っている。4 年生は、グラフ理論について研究しており、身近な事象に関連付けて、グラフの諸性質を考察している。このレポートでは、その一例を紹介したい。
キーワード

2

グラフ、頂点、辺、次数、オイラーの一筆書き定理

研究の背景と目的
私たちの生活はトラックの輸送に頼りきっている。例えば、近くのスーパーマーケ

3

研究内容
近畿地方の移動を考える前に、グラフ理論に関する基本知識をまとめておく。

ットに出かけると、そこには、生産地が遠方である品物が多くあることに驚かされる■グラフ
グラフのグラフの定義だろう。これらの多くは、鉄道による輸送グラフ(graph)とは、図1のように、いくグラフが容易ではなく、トラックによる輸送を余つかの点があり、それらがいくつかの線で儀なくされているらしい。しかし、これら結ばれている図形のことである。の輸送ルートは最適だろうか。
この疑問を「グラフ理論」を用いて考えるために、今回はその導入として身近な近畿地方の移動を例に考えよう。
この移動を独自に問題としてとらえ、これを解決するための準備として、このレポグラフにおいて、それぞれの点のことをグラフの頂点頂点(vertex)、それぞれの線のこ頂点とをグラフの辺辺(edge)という。
また、各頂点から出ている辺の数をその頂点の次数次数(degree)という。図1の頂点
次数

A, B, C の次数は、それぞれ1,2,1となる。

ートでは、先ずグラフ理論において、有名な定理のひとつである「オイラーの一筆書き定理」の証明をし、近畿地方の移動について考察する。
なお、数学班 4 年生は、グラフ理論に関する研究を進め、様々な現実の問題への応用を考察していく計画である。
図1

例1

図2の頂点 X の次数を考える。

■グラフのグラフの一筆書き一筆書き
さて、グラフが一筆書きできる場合について考えよう。グラフが一筆書きできるとき、それぞれの頂点から出る辺と入る辺の数が等しい。ただし、始点（出発点）と終点（到着点）は除いて考える。

図2

2つの頂点を除いた頂点の次数がそれぞ

頂点 X からは、辺が3本出ているので、れ偶数であるとき、このグラフは一筆書き

頂点 X の次数は3である。

できるといえる。そして、始点と終点が一このグラフは、図3のようにも書き換えら致する場合には、その頂点の次数も偶数にれる。

なるが、一致しなければその2つの頂点の次数はそれぞれ奇数となる。
以上のことは、オイラーの一筆書き定理という定理として導かれている。
定理(オイラーのオイラーの一筆書き一筆書き定理)
定理)

次数が奇数となる頂点が0個か2個であ
図3るグラフは、一筆書きができ、それ以外の場合は一筆書きできない。

図3が、図2から変形することができるので、図2,3はいずれも同型であることがいえる。ここで、2つのグラフが同型
同型[証明]
まずは、グラフ G が一筆書きできる(equivalent)であるとは、2つのグラフにおとき、 G の頂点のうち、次数が奇数であいて、それぞれ対応する各頂点の次数が等るものは0個か2個であることを示そう。

しいときをいう。すなわち、グラフにおい上述のように、グラフ G が一筆書きでては、頂点と頂点の結びつきは、方向や距きるとき、始点と終点以外の頂点 V では、離を考えず、単に各頂点がどの頂点と結びV に入ってくる辺と V から出て行く辺のついているかが重要なのである。

数が等しい。つまり、始点と終点の2つのさらに、グラフにおいて、同じ頂点を二頂点を除いた頂点の次数はすべて偶数であ度と通らない閉じた道をサイクルサイクル()とサイクル(cycle)る。そして、始点と終点が一致する場合にいう。

は、その2頂点の次数も偶数になるが、一サイクルをもたない、連結されたグラフを木木(tree))という。また、少なくとも一つ致しなければその2頂点の次数はそれぞれ奇数となる。の辺をもった木において、一つの辺の終点

次に、次数が奇数となる頂点が 0 またはである頂点を吊吊り頂点(pendant vertex))と2 個であるグラフ G が一筆書きできるこという。

を証明しよう。この証明には、辺の数に関する帰納法を用いる。

すると、帰納法の仮定により、これらの各(ⅰ) G は次数が奇数である頂点をもたな成分は一筆書きできることがわかる。したい、即ち、 G のすべての頂点の次数が偶がって、サイクルを一周して、連結成分と数である場合について考える。

共有する頂点に着いたとき、その成分を一まず、辺の数が 0 のとき、即ち始点のみの場合は、明らかに一筆書きできる。
ここで、辺の数が k 本以下のグラフ(ただし、すべての頂点の次数は偶数である)が一筆書きできていると仮定する。
さて、(すべての頂点の次数が偶数であり、) k + 1 本の辺からなるグラフ G につ

筆で書くことで、次数が奇数の頂点が 0 個の場合は証明できる。
(ⅱ) G は次数が奇数である頂点を 2 つもつ場合について考える。
まず、始点と終点を結ぶグラフ上の辺を取り除く。すると奇数の次数の頂点がなくなることがわかる。

いて考えてみよう。このグラフ G は、始このグラフは（ⅰ）において議論した、点と終点が一致するので、吊り頂点をもた次数が奇数である頂点をもたない、即ちすない。よって、木ではないことがわかる。

べての頂点の次数が偶数であるグラフになしたがって、 G にはサイクル（閉じたるので、あとは、（ⅰ）と同様に証明でき道）があることがわかる。ここで、このサる。

イクルに属する辺を一時的にすべて取り除（ⅰ）,（ⅱ）より、次数が奇数となる

くとグラフはいくつかの部分(これを連結連結

頂点が 0 または 2 個であるグラフ G が一筆成分()という)に分けられる成分(component)書きできる。
以上から、オイラーの一筆書き定理が証（図 4 参照）。
しかし、これらの部分は、一時的に明された。■

取り除いたサイクルと共通の頂点をもっている。これらの共通する頂点は、サイクルの頂点でもあるため、もともとの次数より一筆書きできるグラフのことを、オイラオイラーグラフ（）とも呼ぶ。
ーグラフ（Euler graph）

2 だけ小さくなる。よって、もとのグラフ

G からサイクルを除いてできる各部分は、 4 考察すべての頂点の次数が偶数であり、辺の数以上の準備のもと、次の問題を考察してみよう。

は k 本以下である。

■問題
近畿地方の全ての府県境を同じ府県境を通らず通れるか。ただし、始点と終点は一G致しなくてもよいものとする。ここで近畿地方は、京都、大阪、滋賀、兵庫、奈良、

図4

和歌山、三重の2府5県に属する地域を指す。

5

今後の課題
このレポートでは、オイラーの一筆書き定理の証明をすることができた。今後は、「結び目理論」にグラフ理論を関連付けた研究を進めたいと考えている。
6

参考文献[1]「数学のひろば-柔らかい思考を育てる問題集-Ⅰ,Ⅱ」、ドミトリ・フォミーン、セルゲイ・ゲンキン、イリヤ・イテンベル(http://www.asahi-net.or.jp/~aq9stmng/kinki/kinki.html)

ク著、志賀浩二、田中紀子訳、岩波書店(1998)

図5[2]「NHK 高校講座

数学基礎 2004 年度」、日本放送出版協会編、日本放送出版■考察
考察協会 (2004) p.86-89

まず、近畿地方の地図である図 5 をグラ[4]「数学とっておきの 12 話」(岩波ジ

フで表そう。2 府 5 県を点(頂点)で表し、

ュニア新書 417)、片山孝次、岩波書店

府県境を線(辺)で結ぶと図 6 のようなグラ(2002)

フを得る。すると、上述の問題は、「図 6で表されたグラフが一筆書きできるかどうか」という問題として考えることができる。

7

謝辞
本研究およびレポート作成にあたって御指導くださった河合先生と川口先生に深く感謝します。

図6
図 6 において、各頂点の次数を○内に示した。このグラフは、次数が奇数である頂点が 2 個のみなので、オイラーの一筆書き定理より、一筆書きができるとわかる。