文教大学大学院 ■ 情報学研究科■ IT News Letter ■グラフ理論事始め・道草編 —グラフの定義を巡って—
文教大学大学院情報学研究科 教授

惠 羅博†

Hiroshi Era†
あらましコンピュータ科学基礎分野と扱われることが多いグラフ理論だが，その考察対象であるグラフの定義記述は歴史的な経緯のためか多様性が見られる．同値の概念となることがほとんどでありその違いを問題にすることはないかもしれないが，グラフを捉える観点に注目するのであれば，それらの違いを集めてみるのも一興と考え本文を寄稿した．
キーワード：グラフ理論，数学史のであるが，そこには，「graph」の述語もなく概念的定義の1. は じ め に示唆もない．しかし，地域を有限個の要素の集合 A, B, · · ·歴史的には，雑多な問題の定式化が次第に統合されて「グとするだけでなく，それらを「結ぶ」という関係をも要素ラフ」という概念に至ったことから，グラフの捉え方や扱いの集合 a, b, · · · と置いて行った思考過程は，現代のグラフ

方は研究者のあいだで多様性がみられる．そのためか，グの概念に限りなく近づいたものといってよく，グラフ理論

ラフの定義の記述には定番がなく著者ごとに些細な違いがの最初の論文と称される所以である．

あるのが普通である．さらに，「graph」という述語がいつ頃点集合とそれらの関係という組合せ論的捉え方からグラから用いられ始めたのか，著者にとっては今のところ不明

フ的考察を行った論文としては，根付き木の数え上げで有でありその定義の多様性とともに気に掛っている．幸いグ

名な A. Caley(1857) がある 1) ．そこで用いられる述語は，ラフ理論の歴史について学ぶに格好の文献 1) があり，1800

tree, root, branches，knots 等で，現代でも用いられてい年代から 1900 年代初期のグラフ理論「的」な研究についてるこれらの述語の起源はこのあたりにあるかと思われる．の文献が手際よく蒐集されている．著者にはこれを凌駕す

定義内容も現代と同じである．

る資料も調査の時間もないので，ありがたくこの良書と他同様に木を扱ったものに，C. Jordan(1869) があり，文のいくつかの文献を参照しながら，グラフ黎明期の述語や献 1) に次の英訳文が引用されている．
「Let x, y, z, u, · · · be

「graph」の定義についてあれこれ随想してみようと思う．に隔てられた 4 区域を，それらの間に架かる 7 本の橋すべ

any number of points, and xy, xz, yu, · · · straight lines
or curves without self-intersections, such that each one
joins just two of these points. We shall call such a system an assemblage of lines · · ·」．ここでは，root 等の述語はなく，points, lines, a system of an assemblage oflines の記述があり，幾何学的な観点で捉えていることがわ
かる．Cayley, Jordan のいずれにも，graph という単語はてを一度だけ通って一巡できるかという問題である．この見えない．

2. グ ラ フ の 述 語
グラフ理論の分野における最初の論文は有名な「ケーニヒスベルグの橋」の問題を考察した 1736 年のレオンハル
ト・オイラー 1) のものとされている．これは，水路で互いの中で，オイ化学の分野で，分子構造式の木を扱った論文に，E. Fran-ラーは 4 地域を A, B, C, D, 7 つの橋を a, b, c, d, e, f, g とし，一巡可能かを地域の幾何学的形状の条件ではなく，記kland(1866) がある 1) ．ここでは，graphic formulae という言葉で，分子構造式を指している．graphic という言葉

号 A, B, · · · と a, b, · · · の交互の列の存在条件として整理しはここでは文字通りの形容詞として用いられているだけで特徴づけた．オイラーはこの論文の中で「位置関係だけがあるが，その後の graph の述語への指向程度の意味はあっ問題となる幾何学的問題」の本質を的確に考察して見せたたかもしれない．少し後の「化学と代数」というタイトル

問題およびその一般化について論じた文献

1)の J.J.Sylvester(1877)1) には，graph, valence という述語
2011 年 12 月 1 日受付† 〒 253–8550 神奈川県茅ヶ崎市行谷 1100が登場する．1 つのシステムとして認識し graph の一単語

era@shonan.bunkyo.ac.jpをあてたものとしては，かなり早いものであろう．さらに† Graduate School of Infomation and Communications,Bunkyo University

後年の J.Petersen(1891)1) には次の記述 (原文英訳) がみられる．
「English Authors have given the name graph to

文教大学大学院情報学研究科 IT News Letter Vol. 7, No. 2, pp. 7〜8 (2011)(3) 7

such a diagram;· · ·」したがって，1800 年代の終わり頃には一部の研究者たちの間では graph という述語が定着していたと思われる．O.Veblen(1922)1) は位相幾何学の観点からグラフを考察したもので，1 次元単体複体としてグラフを定義している．そこでの呼称は linear graph であり，論文のタイトルも Linear Graphs となっている．この述語はしばらく後まで用いられていたようで，R .G. Busacker,T. L. Saaty(1965)2) に「グラフはしばしば線形 (リニヤ)グラフとも呼ばれる」(矢野, 伊理訳,1970, 培風館) という記述がある．しかし，1930 年代以降は，graph の述語が普及したようで，ほとんどの論文が graph を用いている．

3. 定 義 の 比 較

辺の端点 (ends) と呼ぶ．
」一見，シンプルな定義に見えるが，実は接続関係という概念に着目しているところが特徴
で，深い洞察力で知られる Tutte らしくなかなか一筋縄ではいかない．この定義をさらに明示的に述べた次の文献をみればそのことがよくわかる．日本のグラフ理論の祖というべき師弟，浜田，秋山の共著 6) (1982) から．
「1 つの空でない有限集合を V (G) = {v1 , v2 , · · · , vp } とし，V (G) とはまったく異なった有限集合を E(G) = {e1 , e2 , · · · , eq } とし，E(G) から V (G) の要素の非順序対 {vi , vj }(2 つの要素が異なることを要しない) の 1 つの族 W の上への写像 ΦGがあるとする．このとき順序組 G = (V (G), E(G), ΦG ) を一般グラフまたは単にグラフといい，· · ·」.
最後に，グラフ理論書に一時代を画したと言われる現代近現代のいくつかの著書から，グラフの定義を引用しその名著 R. Diestel7) (1997) から．
「グラフ (graph) とは 2 つの違いをみてみよう．日本語は邦書以外，筆者の訳である．の集合の対 G = (V, E) で E ⊆ [V ]2 を満たすようなもの

はじめに，マトロイドの生みの親として有名な H.Whitenyである．したがって，E の各要素は V の 2-点部分集合での論文 3) (1931) から. 「グラフ (graph)G とは 2 つの記号ある．記法の曖昧さを避けるために，常に V ∩ E = ∅ がの有限集合，頂点 (vertex) 集合 a, b, c, · · · , f , 弧 (arc) 集合成り立つことを暗黙の仮定とする．V の要素を G の頂点α(ab), β(ac), · · · , δ(cf ) からなる．弧 α(ab) がグラフに存在するときその端点 (end vertices)a, b もまた存在する．(中略) このようなグラフ (抽象的グラフ (abstract graph)) の明らかな幾何学的表現 (解釈) を位相幾何学的グラフ (topological graph) と呼ぶ．
」Whiteny の定義は，やや直観的で(verteices) (または，節点 (node)，点 (point))，E の要素をその辺 (edge)(または，線 (line)) と呼ぶ．
」Tutte 流とは違い，あるのは集合のみである．この定義は，C. Berge が提唱したグラフの集合論的一般化 Hypergraph の概念と整曖昧な表現だが，直ぐにでも厳密な公理化が可能であるよは考えすぎか．述語もここまでの歴史を踏まえ網羅的にあうな抽象性を内包している．公理主義の時代的な雰囲気とげていて親切である．Diestel のグラフ理論書のスタンダーWhitney の個性が合わさったようで興味深い．

ドを目指す気概が伝わってくる．

次は，グラフ理論書初のベストセラーとして知られる F.
Harary の著書 4) (1969) から．
「グラフ (graph)G とは，空でない p 個の点 (points) の有限集合 V ＝ V (G) と，適当に与えられた V の異なる点の非順序対 q 個の集合 X からなるものである．X の点の各非順序対 x = {u, v} を G の線 (line) といい，x は u と v を結ぶ (join) という．(中略)通常，グラフを図で表し，その図を元のグラフそのものと合性があり，極値集合論への指向すら感じとれるというの

4. 終 わ り に
C.Berge, G.C.Rota, O.Ore など現代のグラフ理論の礎を築いた他の碩学たちにも触れたかったが限られた字数では紹介しきれなかった．またの機会を待ちたい．文献も原著を示すべきだが同じ理由で孫引きの体裁となり心苦しい限りである．読者のご寛容を乞う次第である．

して言及する．
」Harary の定義の特徴は，昔の Jordan と〔文同じ point, line という幾何学的述語を用いたことにある．
他の多くの著者は point よりも vertex(vertices) ，line よりも edge を用いている．多面体がグラフとして表現できるので，歴史的な多面体の研究の経緯から，そこで用いられる vertex, edge が自然に感じられたのであろうか．また，

Harary はグラフの図表現をグラフそのものと同一視する
便宜的な認識法をことさら奨励しているように見えるのも献〕

1）N.L.Biggs et.all, Graph Theory 1736-1936, Clarendon Press, 1976
2）R.G.Busacker, T.L.Saaty, Finite Graphs and Networks, McGrawHill, 1965
3）H.Whitney, Non-Separable and Planar Graphs, Trans Amer.
Math Soc. 34,1932, 339-362
4）F. Harary, Graph Theory, Addison-Wesley, 1969
5）W.T. Tutte, Graph Theory, Addison-Wesley, 19846）浜田隆資, 秋山仁, グラフ論要説, 槇書店, 1982
7）R. Diestel, Graph Theory (3rd ed.), Springer, 2000

特徴である．

Harary と同時代の大御所 W.T.Tutte の定義をみてみよう．手元には比較的後年の著書 5) (1984) しかないが，それを引用させてもらう．
「グラフ (graph) とは，頂点 (vertices)と呼ばれる要素の集合 V (G) と辺 (edge) と呼ばれる要素の集合 E(G)，および，接続 (incidence) 関係から (なる体系として) 定義されるものである．接続関係とは，各辺に1 つまたは 2 つの頂点を付随させるもので，それらをその8 (4)えら惠羅ひろし

博 1949 年生．1972 年 3 月東京都立大学理学部数学科卒業．1980 年 3 月東海大学大学院理学研究科博士課程単位取得後退学 (数学専攻)．1985 年学位取得 (理学博士, 東海大学). 1986 年 4 月文教大学情報学部講師に着任．現在，文教大学情報学部教授．2005
年 4 月より文教大学大学院情報学研究科教授兼任．情報学研究科では，「情報数学演習」を担当．専門分野はグラ
フ理論．

文教大学大学院情報学研究科 IT News Letter Vol. 7, No. 2 (2011)