日本大百科全書(ニッポニカ) 「グラフ理論」の意味・わかりやすい解説
グラフ理論
ぐらふりろん
グラフ理論というときのグラフは、棒グラフや折れ線グラフ、また二次関数のグラフのように、量の変化を視覚的に表すときのグラフではない。たとえば鉄道網や道路網の図形を思い浮かべてみよう。そこでは現実の方位や距離などは無視され、かなり省略された図が描かれているのが普通である。それにもかかわらずその図が役にたつのは、必要とされる情報が、駅と駅とが何線で結ばれているかとか、乗り換えは何駅で行えばよいか、というようなことだからである。またたとえば会社の組織図や家系図、トーナメントの組合せ、電気回路の配線図なども同様の事情にある。そこで重要なのは、点で表されるもの（各部所、親や子、対戦相手、抵抗や半導体）の結合関係のみである。グラフ理論は、このような質的関係を表現し、研究する分野であり、応用領域は数学のみにとどまらず非常に広い。歴史的には後に述べるオイラーが出発点である。
いくつかの点とこれらを結ぶ線分（曲線でもよい）からできる図形をグラフという。このとき点は頂点、線分は辺とよばれる。どの二つの頂点も、一方から出発して他方へと達する辺の列で結べるとき、そのグラフは連結であるという。連結なグラフは直観的には、ひとかたまりの図形をなしている。連結グラフのすべての辺を1回通るような周遊道が存在するかどうかという問題がある。これが18世紀に「ケーニヒスベルクの橋の問題」としてオイラーによって考えられた問題である。すなわちのようなケーニヒスベルク（現、ロシア領カリーニングラード）のプレーゲル川に架かっていた七つの橋をすべて1回ずつ回って元の出発点に戻るような散歩道を考えよという問題である。オイラーは、町のA、B、C、Dの部分を頂点で、それらを結ぶ橋をこれらの点を結ぶ辺とみて、のようなグラフを考えた。すると、散歩道をみいだす問題は、このグラフの周遊道をみいだす問題になる。オイラーは、「各頂点から出る辺の数がすべて偶数であるか、二つの頂点では奇数であるが他は偶数であるならば、連結グラフは周遊道をもつ」という定理を証明して、この問題に否と答えたのである。実際、この問題では各頂点から出る辺の数はすべて奇数である。したがってまた、AとBにもう1本の橋が架かっていれば（元の場所へは戻れないが）周遊道があり、さらにCとDにもう1本の橋が架かっていれば元に戻る周遊道が存在する。この定理はグラフの「一筆書きの定理」ともよばれ、逆も成り立つ。
のような正十二面体の各頂点を世界の都市とみて、各辺をそれらの間を行き来する旅行路としたとき、この旅行路に沿って各都市をちょうど1回通る世界旅行コースをみいだせというのがハミルトンの問題であり、旅行時間や旅費を考慮に入れれば旅行業者がいつも直面する問題でもある。この正十二面体の頂点のつくるグラフは、のような平面上のグラフとなるので、このグラフの各頂点をちょうど1回通る通路を考えればよい。この場合には太線のような道が求める通路になる。同様な問題が任意の連結グラフで考えられるが、この一般の場合の解（一筆書きの定理のような）はまだ得られていない。
グラフは、それらの辺が頂点以外では互いに交わることのないように平面に描けるとき平面グラフという。のグラフを平面に描くと、かならずどれかの2辺が頂点以外の点で交わってしまうので、これは平面グラフではない。これに関してクラトウスキーによる、「グラフが平面グラフとなるためには、の①または②のグラフが部分として含まれないことが必要十分である」という結果がある。
グラフの一つの頂点から出る辺の個数をその頂点における局所次数という。頂点がA1、A2、…、Anであるグラフの各頂点Aiの局所次数がρ(Ai)であり、辺の数をNとするならば、
となる。このことから、局所次数が奇数であるような点はかならず偶数個あることがわかる。のようなグラフは、閉じた道（ある点から出発して元に戻り、途中では自身と出会うことのない道）のないグラフであり、こうした連結グラフは英語のtreeを訳して木という。木はn個の頂点をもつとn－1個の辺をもつ。よって木の辺の個数をN、頂点の個数をnとすると、r＝N－n＋1＝0となる。しかし一般の連結グラフでは、この数r＝N－n＋1は0ではなく、このrをそのグラフの回路階数という（）。グラフの回路階数は、そのグラフに含まれる回路の数が多くなるほど多くなり、そのグラフの複雑さを示す数である。これは、この図形の一次元ベッチ数とよばれる位相不変量である。
四色問題(よんしょくもんだい)（地図を国で色分けする場合、線で接する国を違う色で塗るとすると、必要な色の最大数は4である、ということの証明問題）も、各国を頂点に境界を接する国に対応する頂点を辺で結ぶと、頂点の彩色問題としてグラフ理論の一部とみられる。
［野口 廣］
『O・オア著、野口廣訳『グラフ理論』（1970・河出書房新社）』
グラフ理論（ケーニヒスベルクの橋の問題…
グラフ理論（ケーニヒスブルクの橋のグラ…
グラフ理論（正十二面体）〔図C〕
グラフ理論（正十二面体の頂点のつくるグ…
グラフ理論（どれかの2辺が頂点以外の点…
グラフ理論（平面グラフとなるための条件…
グラフ理論（閉じた道のないグラフ）〔図…
グラフ理論（グラフの回路階数）〔図H〕