グラフ理論

グラフ理論（グラフりろん、）は、ノード（節点・頂点、点）の集合とエッジ（枝・辺、線）の集合で構成されるグラフに関する数学の理論である。

グラフ（データ構造）などの応用がある。

概要グラフによって、様々なものの関連を表すことができる。 frame|6つの節点と7つの辺から成るグラフの一例

例えば、鉄道や路線バス等の路線図を考える際には、駅（節点）がどのように路線（辺）で結ばれているかが問題となる一方、線路が具体的にどのような曲線を描いているかは本質的な問題とならないことが多い。

したがって、路線図では駅間の距離や微妙な配置、路線の形状などがしばしば実際の地理上とは異なって描かれている。つまり、路線図の利用者にとっては、駅と駅の「つながり方」が主に重要な情報なのである。

このように、「つながり方」に着目して抽象化された「点とそれらをむすぶ線」の概念がグラフであり概念、グラフがもつ様々な性質を探求するのがグラフ理論である。

つながり方だけではなく「どちらからどちらにつながっているか」をも問題にする場合、エッジに矢印をつける。このようなグラフを有向グラフ、または、ダイグラフという。矢印のないグラフは、無向グラフという。

グラフを表現するのに、図ではなく、隣接行列を用いることがある。無向グラフの隣接行列は、対称行列になる。例えば、上のグラフは、次の隣接行列で表現できる。

グラフの例

日常的な問題や工学的問題の多くをグラフとして考えることができる。路線図: 前節のとおり。電気回路: 回路図を書く場合、実際のリード線どおりの形状に図を描いたりはしない。この場合も、「接点がどうつながっているか」だけが問題であって、「つながり方」を保ちつつできるだけ見やすい形に絵を描く。回路図は一種のグラフである。 WWWの構造: WWWにおけるウェブページの、ハイパーリンク・被リンク関係がなす構造は、有向グラフの一種であるハイパーリンク。

起源グラフ理論は、1736年に「ケーニヒスベルクの問題」と呼ばれるパズルに対してオイラーが解法を示した (ラテン語) Leonhard Euler - Solutio problematis ad geometriam situs pertinentis, Commentarii academiae scientiarum Petropolitanae 8, 1741, pages 128–140.　Konigsberg Bridge problemを参照。Diestel, p. 20のが起源のひとつとされるグラフ理論の歴史を扱っているにオイラーの論文の英訳を含む節がある。。この問題は、一筆書きと深く関連している詳しくは、一筆書きの項を参照。。

形式的な定義有向グラフ集合 , と、の元（げん、要素）に、二つのを元の対で対応させる写像

の三つ組

を有向グラフという。の元をの頂点またはノード、の元をの辺または弧と呼ぶ。となるはループに対応し、となるは多重辺に対応する。

無向グラフをの冪集合とする。の元にの部分集合を対応させる写像

があって、の任意の元について、の像の濃度が1または2であるとき、三つ組

を無向グラフという無向グラフと有向グラフ。の元をの頂点、の元をの辺と呼ぶ。の濃度が1となるはループに対応し、となるは多重辺に対応する。

単純グラフに限って言えば、を最初からある集合の部分集合と考え、写像を用いずにグラフを定義することもできる：有向グラフでは、をの部分集合、無向グラフでは、をの部分集合で、2つの元の集合だけからなるものとすればよい。

用語以下では単にグラフといった時には無向グラフを指す。

頂点と辺頂点の集合は、辺の集合はで表す。グラフが先に与えられている場合には、頂点集合を、辺集合をと表すこともある。

数学以外の分野では、頂点を節点、辺を枝と呼ぶことが多い。辺を弧やリンクと呼ぶこともある。

重み付きグラフグラフの辺に重み（コスト）が付いているグラフを、重み付きグラフと呼ぶ。乗換案内図の場合、駅間の所要時間が「重み」にあたる。重み付きグラフはネットワークとも呼ばれる（フローネットワーク, ベイジアンネットワーク, ニューラルネットワークなど）。

接合と隣接辺の両端の点を端点といい、端点は辺に接合（または接続）しているという。また、辺と辺がある頂点を共有しているとき、その辺どうしは隣接しているという。

距離と直径 2頂点間（隣接している必要はない）を経由する辺数を長さと呼び、特に最短経路における辺数を距離と呼ぶ。グラフの最大頂点間距離を直径と呼び、と表す。

ループと多重グラフある辺の両端点が等しいとき、ループ（自己ループ）という。また、2頂点間に複数の辺があるとき、多重辺という。ループも多重辺も含まないグラフのことを単純グラフといい、ループや多重辺を含むグラフのことを多重グラフという多重グラフ。

部分グラフと拡大グラフ

2つのグラフとについて、の頂点集合と辺集合が共にの頂点集合と辺集合の部分集合になっているとき、はの部分グラフである、またははの拡大グラフであるといい、と表す。特に、との頂点集合が等しいとき、はの全域部分グラフであるという。また、の頂点集合の部分集合を取り出して、両端点がに属する全ての辺を辺集合とするの部分グラフを、誘導部分グラフという。グラフからある辺を取り除き、その辺の両端点を一つの頂点にまとめることを（辺の）縮約といい、縮約の結果得られるグラフをと表す。

なお、誘導部分グラフの「誘導」はinducedの訳語である。induceの訳としてはこの「誘導する」の他に「生成する」があるベルジュ「グラフの理論I」p.8.ディーステル, 2000。このため、誘導部分グラフのことを生成部分グラフということもある茨木「アルゴリズムとデータ構造」。一方、生成部分グラフは全域部分グラフのことを指すこともある。このため、生成部分グラフという語を使う際は、混乱がないか気を付ける必要がある。

次数と正則グラフ

頂点に接続する枝の数を次数といい、で表す。有向グラフにおいては、に入ってくる辺数のことを入次数、から出て行く辺数のことを出次数という。すべての頂点が同数の隣接点、つまり次数をもつグラフを正則グラフと呼ぶ。任意の頂点について、が成り立つとき、-正則という。-正則なグラフのことを -正則グラフという。グラフが持つ頂点の次数の最小値を、最大値をで表す。また、次数 0 の頂点のことを孤立点という。

道と閉路隣接している頂点同士をたどったの系列を長さの歩道（鎖・ウォーク）という。辺の重複を許さない歩道を路（小径・トレイル）という。頂点の重複を許さない場合、つまり、両端の2頂点の次数が1、それ以外のすべての頂点の次数が2であるグラフを、道（パス）、開いた歩道をパスという場合は単純パスという。また、始点と終点が同じ路のことを閉路（回路・循環・サーキット、サイクル）、始点と終点が同じ道（つまりという路でが相異なるもの）のことを閉道（サイクル）という閉路。

完全グラフとクリーク

任意の 2 頂点間に枝があるグラフのことを完全グラフ（完備グラフ）というDiestel, p. 115。頂点の完全グラフは、で表す。は三角形と呼ばれる。また、完全グラフになる誘導部分グラフのことをクリークという。大きさ（サイズ）のクリークを含むグラフは「-クリークである」という。辺をもつグラフは必ず2頂点の完全グラフを含むので 2-クリークである。また -クリークであって、直径が未満となるグラフを -クランという。

その他の用語

応用

グラフは物理学的、生物学的、社会的、および情報システムにおける多くの種類の関係と過程をモデル化するために使うことができる。多くの現実的問題はグラフによって表すことができる。現実世界のシステムへの応用を強調する時には、「ネットワーク」という用語がグラフを意味するために定義されることがある。このグラフでは、属性（例えば名前）が頂点および辺と関連付けられる。現実世界のシステムをネットワークとして表現し理解する主題はネットワーク科学と呼ばれる。

計算機科学計算機科学において、グラフはコミュニケーション、データ編成、計算装置、計算の流れ等のネットワークを表すために使われる。例えば、ウェブサイトのリンク構造は有向グラフとして表すことができる。ここでは、頂点がウェブページを表し、有向辺があるページから別のページへのリンクを表す。同様のアプローチを、ソーシャルメディア、旅行、生物学、コンピュータチップ設計、神経変性疾患の進行のマッピング、そしてその他多くの分野における課題について取ることができる。したがって、グラフを取り扱うためのアルゴリズムの開発が計算機科学における主要な興味である。はグラフ書換え系によってしばしば定式化され、表現される。グラフ変換系と相補的なグラフの規則に基づくメモリー内操作に注目したシステムが、グラフ構造を持つデータのトランザクションセーフで永続的な格納と問い合わせに対応したである。数値計算の分野では、疎行列を係数とする連立1次方程式を消去法により計算して解く際に、行列の非零構造をグラフと対応づけて消去の順序をうまく選ぶことで、消去法計算の過程で発生する非零要素の数をなるべく抑える方法などが多く研究されてきた。

言語学様々な形式のグラフ理論的手法は言語学において特に有用であることが証明されている。これは、自然言語がしばしば離散構造へとよく適しているためである。伝統的に、統語論と合成意味論は木構造に従い、それらの表現力は、階層的グラフによってモデル化される構成性の原理に密接に関係する。主辞駆動句構造文法といったより現代的な手法は型付き素性構造（これは有向非巡回グラフである）を用いて自然言語の構文をモデル化する。語彙意味論内、特に計算機へ応用としては、単語の意味のモデル化は、与えられた単語が関連する単語の観点から理解される時により容易である。したがって意味ネットワークは計算言語学において重要である。今で、哲学（例えば、を用いる最適性理論）や形態論（例えばを用いる有限状態形態論）におけるその他の手法は、グラフとしての言語の解析において一般的である。実際、この数学の分野の言語学への有用性は、TextGraphs、WordNetやといった様々な "Net" プロジェクトのような組織を生んできた。

物理学および化学グラフ理論は化学および物理学において分子を研究するためにも使われる。凝縮系物理学では、シミュレーションした複雑な原子構造の3次元構造は、原子のトポロジーに関連したグラフ理論的性質に関する統計量を集めることによって定量的に研究することができる。また、ファインマンの計算のグラフと規則は、理解したい実験的数字と密接に関係した形式で量子場理論を要約する。化学では、グラフは分子についての自然な模型を作り、ここでは頂点が原子、辺が結合を表わす。このアプローチは分子構造の計算処理（分子エディタからデータベース探索まで）において特に使われる。統計物理学では、グラフは系の相互作用している部位間の局所的つながりや、こういった系における物理的過程のダイナミクスを表わすことができる。同様に、計算論的神経科学では、グラフは様々な認知過程を生じさせるために相互作用する脳領域間の機能的結合を表わすために使うことができる。ここでは、頂点が脳の異なる領域を表わし、辺がそれらの領域間の結合を表わす。グラフ理論は電気回路網の電気的モデリングにおいて重要な役割を果たす。ここで、重みはネットワーク構造の電気的性質を得るために有線部分の抵抗と関連付けられる。グラフは多孔質材料のミクロスケールチャネルを表わすらために使うこともできる。ここでは、頂点が孔を表わし、辺が孔間をつなぐより小さなチャネルを表わす。化学グラフ理論は分子をモデル化する手段として分子グラフを使用する。

社会科学

グラフ理論は社会学においても、例えば、特にソフトウェアを使って、うわさの広がりを調査したりする手段として広く使われている。社会ネットワークの傘の下に、多くの異なる種類のグラフがある。知り合い関係グラフと友情関係グラフは人々が知り合いかどうかを記述する。影響グラフは特定の人々が他者の振る舞いに影響するかどうかをモデル化する。最後に、協調グラフは2人の人物が、映画で一緒に演技するといったある特定のやり方で協力するかどうかをモデル化する。

生物学同じく、グラフ理論は生物学および保全の取り組みにおいて有用である。ここでは、頂点が特定の種が存在（または生息）する地域を表わすことができ、辺は地域間の移動経路または移動を表わす。この情報は、繁殖パターンを見る時や、病気や寄生虫の広がり、移動が他の種にどのように影響しうるかを追跡するために重要である。

グラフ理論はコネクトミクスでも使われる。神経系はグラフとして見ることができる。ここで、節点はニューロンであり、辺はニューロン間のつながりである。

数学数学では、グラフは幾何学ならびに結び目理論といったトポロジーの特定の分野において有用である。代数的グラフ理論は群論と密接なつながりを持つ。代数的グラフ理論は動的系や複雑性を含む多くの分野に応用されている。

その他グラフ構造は、グラフのそれぞれの辺に重みを割り当てることによって拡張することができる。重み付きグラフは、対ごとのつながりが何らかの数値を持つ構造を表わすために使われる。例えば、グラフが道路網を表わすとすると、重みは各道路の長さを表わすことができるだろう。それぞれの辺に関連した複数の重み（距離、旅行時間、金銭的コストなど）が存在するかもしれない。このような重み付きグラフはGPSおよび飛行時間と費用を比較する旅行計画探索エンジンをプログラムするために一般的に使われる。

問題と定理

備考 2022年から日本で導入される高等学校新学習指導要領の数学C（公式配布されるのは2024年4月）には「図、表、統計グラフ、離散グラフ及び行列などを用いて、日常の事象や社会の事象などを数学的に表現し、考察すること」とあり、日本では初めてグラフ理論にかかわる分野が高等学校の数学教科書に掲載される予定である。ただし、その分野を入試に出題する大学は殆どない。

脚注出典と補足

参考文献

(現在は丸善に移管) Reinhard Diestel (2010), Graphentheorie. Springer-Verlag, Vierte Auflage, 2010 Korrigierter Nachdruck 2012 Heidelberg xviii+355 Seiten, 129 Abbildungen September 2010 (2006, 2000, 1996) EUR 32,99.

Rudolf Fritsch, Gerda Fritsch, translated by J.lie Peschke:The Four-Color Theorem (2012): History, Topological Foundations, and Idea of Proof, Springer; Softcover reprint of the original 1st edition 1998;

関連文献日本語の文献 László Lovász: 「組合せ論演習 1：数え上げの手法」、東海大学出版会、 (1988年3月14日). László Lovász: 「組合せ論演習 2：グラフの構造」、東海大学出版会、 (1988年3月28日). László Lovász: 「組合せ論演習 3：グラフの不変数」、東海大学出版会、 (1988年年4月11日). László Lovász: 「組合せ論演習 4：集合論的グラフ理論」、東海大学出版会、 (1988年4月11日).

秋山仁『グラフ理論最前線』朝倉書店（1998年8月） . 加納幹雄『情報科学のためのグラフ理論』朝倉書店 (2001年2月)、.

鈴木晋一編著『数学教材としてのグラフ理論』, 早稲田教育叢書 31, 学文社, （2012年3月）ノラ・ハーツフィールド&ゲーハード・リンゲル著鈴木晋一訳,『グラフ理論入門』,サイエンス社, （1992年6月1日）ボロバシュ・ベーラ著斎藤伸自, 西関隆夫訳,『グラフ理論入門』,培風館, （1983年4月30日）リウ：「組合せ数学入門II」、共立出版（1972年）。 R.J.ウィルソン：「グラフ理論入門」、近代科学社、 (1985年3月20日）．榎本彦衛：「グラフ学入門」、日本評論社(1988年)。佐藤公男：「グラフ理論入門：C言語によるプログラムと応用問題」、日刊工業新聞社、 (1999年4月15日)．ウィルソン：「グラフ理論入門」、近代科学社(2001年)。惠羅博、土屋守正：「［増補改訂版］グラフ理論」、産業図書、 (2010年2月25日). R.ディーステル：「グラフ理論」、丸善出版、（2012年6月5日）。舩曳信夫、渡邊敏正、内田智之、神保秀司、中西透：「グラフ理論の基礎と応用」、共立出版、 (2012年10月15日). 小林みどり：「あたらしいグラフ理論入門」、牧野書店、 (2013年4月1日). 宮崎修一：「グラフ理論入門：基本とアルゴリズム」、森北出版、（2015年6月） J.A.ボンディ、U.S.R.マーティ：「グラフ理論」、丸善出版、（2022年11月26日）。

日本語以外 Berge, Claude (1958), Théorie des graphes et ses applications, Collection Universitaire de Mathématiques II, Paris: Dunod. English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition, Dover, New York 2001.. Lowell W. Beineke, Bjarne Toft, and Robin J. Wilson (2025): Milestones in Graph Theory: A Century of Progress, AMS/MAA, (SPECTRUM, v.108), . Chartrand, Gary (1985), Introductory Graph Theory, Dover, . Leonhard Euler, Euler Complete Edition (Opera Omnia: Series 1, Volume 7, pp. 1 - 10) Hajnal Péter (2003), Gráfelmélet - Polygon jegyzet Harary, Frank (1969), Graph Theory, Reading, MA: Addison-Wesley. Harary, Frank; Palmer, Edgar M. (1973), Graphical Enumeration, New York, NY: Academic Press. Jeremy Kepner and John Gilbert (EDs) (2011): Graph Algorithms in the Language of Linear Algebra, SIAM, . Lovász László (2008), Kombinatorikai problémák és feladatok, Typotex Kiadó, . Manfred Nitzsche (2004), Graphen für Einsteiger, Rund um das Haus vom Nikolaus. XII, 233 S. Br. € 22,90 Peter Gritzmann, René Brandenberg (2003) Das Geheimnis des kürzesten Weges. Ein mathematisches Abenteuer. Springer, Berlin - Heidelberg (2.Aufl.). William Thomas Tutte (2001), Graph Theory, Cambridge University Press, .

グラフ理論

Źródło i licencja