§１．グ　ラ　フ　と　は　？

　今、ここに６人の女の子がいます。名前を、今日子、成美、純子、保奈美、靖子、幸子といいます。この６人の友達関係は次のとおりです。

今日子は成美、純子、保奈美、靖子と友達であるが、幸子を知らない。
成美は純子、幸子と友達であるが、保奈美と靖子を知らない。
純子は保奈美、靖子と友達であるが、幸子を知らない。
保奈美は靖子、幸子を知らない。
靖子と幸子はお互いに知らない。

　 あなたは６人の友達関係を把握できましたか。２、３回読んだだけで把握することはとても難しいでしょう。では、上の文章をもっとわかりやすく表現する方法はないものでしょうか。その１つとして、図４のように表であらわす方法が考えられます。

　 今日子 成　美 純　子 保奈美 靖　子 幸　子
今日子 　 ○ ○ ○ ○ ×
成　美 ○ 　 ○ × × ○
純　子 ○ ○ 　 ○ ○ ×
保奈美 ○ × ○ 　 × ×
靖　子 ○ × ○ × 　 ×
幸　子 × ○ × × × 　

図４

　友達同士は○印を付け、そうでない場合は×印を付けているので、誰と誰が友達であるかがすぐにわかり、さらには、純子が何人と友達であるかなどもすぐにわかります。したがって、先の文章よりも６人の友達関係の表現としては、工夫されたわかりやすいものといえるのではないでしょうか。

　次に、６人の友達関係を、グラフを使って表わしてみることにします。６人それぞれを点で表わし、お互いに友達同士であればその２点を線で結びます。すると図５の①のような点と線で構成された図が出来上がります。これをグラフと呼びます。

③

図５

このグラフから

　　①　誰と誰が友達同士であるか。（２点が線で結ばれているか否か）
　　②　純子が何人と友達であるか。（純子を表わす点に接続している線の数）
　　③　保奈美、純子、今日子が互いに友達同士であること。
　　　　　（３人を表わす点をそれぞれ頂点とする３角形が存在する）
　　④　幸子の友達は成美だけであること。
　　　　　（幸子を表わす点が、成美を表わす点とのみ、線で結ばれている）
　　⑤　今日子、純子の共通の友達は、成美と保奈美と靖子である。

等のことが、視覚的に把握しやすい。したがって、図４の表からはわかりにくいいくつかの情報も得られる。

　図５の①では、点と点を結ぶ線はすべて直線で描かれています。しかし、グラフでは線はすべて直線である必要はなく、曲線でもかまいません。重要なことは、どの点とどの点を結んでいるか否かということなのです。　したがって、図５の①と②は同じ友達関係を表わしたグラフなのです。又、点の配置を変えた③のグラフも①、②と同じ友達関係を表わしたグラフなのです。　このような３つのグラフは同型なグラフと呼ばれています。
　②③のグラフは①のグラフと違って、線が６人それぞれに対応する点以外では交わっていません。このようなグラフは平面グラフと呼ばれています。又、点の配置を変えたり、線を曲げたりすることで平面グラフになるグラフは平面的グラフと呼ばれます。したがって、①は平面的グラフなのです。
　しかし、グラフによっては、どのように点の配置を変えても、又、線を曲げても平面グラフにならないものもあります。そのようなグラフは非平面的グラフと呼ばれます。例えば、図６は非平面的グラフです。

　

グラフとは、図５に示したように、６人の女の子に対応するような点集合Ｖと、２点間に友達関係が成り立つか否かを表わしたような線集合Ｅとのセットから成るものということができます。すなわち

Ｖ＝{ v1 , v2 , v3 , v4 , v5 , v6 }

Ｅ＝{v1v2,v1v3,v1v4,v1v5,v2v3,v2v6,v3v4,v3v5}

図7のグラフ ＝ G(V，E)

と表わすことにします。
　注意すべきことは、図６のような平面グラフでないグラフの線と線の交差している箇所は点ではないということです。

　それではここでグラフ理論についての必須用語について説明をしておきます。
　例えば、図７のグラフの点v1と点v3は線で結ばれています。このとき、点v1と点v3は隣接しているといいます。又、線同士についても、例えば、線v1v2と線v2v6は共に点v2に接続している。このとき、線v1v2と線v2v6は隣接しているといいます。
　図６のように、グラフのすべての点がお互いに隣接しているグラフのことを、特に、完全グラフといい、点の個数がn個の完全グラフを記号Ｋnで表わします。したがって、図６の完全グラフは、Ｋ5となります。
　各点に接続している線の本数をその点の次数といいます。例えば、図７の点v1の次数は４であり、d(v1)＝４という式で表わします。したがって、他の点については、d(v2)＝３，d(v3)＝４，d(v4)＝２，d(v5)＝２，d(v6)＝１となります。
　次数が奇数となる点を奇点、次数が偶数となる点を偶点と呼び、特に奇点の中でも次数が１の点を端点と呼びます。又、次数が０の点を孤立点と呼びます。　以上述べたグラフでは、隣接する２点を結ぶ線は１本であるが、同じ２点を結ぶ線が２本以上存在するグラフ（図８）も考えられます。このようなグラフを多重グラフと呼びます。又、ル－プといって、ある１点から出て、又その点に戻るような線を持つグラフ（図９）も考えられます。このようなグラフをル－プグラフと呼びます。そして、多重グラフ、ル－プグラフをまとめて擬グラフと呼びます。

　

　はじめに述べたように、グラフ理論は日常の様々な場面で利用され、又、応用範囲も広いものです。これより、そのいくつかを紹介しながら、グラフ理論の楽しさ、有用性を味わってもらうことにしましょう。

中高校生のためのグラフ理論　Top Menu　へ