グラフ理論

提供: testwiki
2025年3月18日 (火) 02:00時点におけるimported>パンダーズによる版 (→概要)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

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

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

概要

グラフによって、様々なものの関連を表すことができる。

6つの節点と7つの辺から成るグラフの一例

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

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

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

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

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

(010010101010010100001011110100000100)

グラフの例

テンプレート:Main 日常的な問題や工学的問題の多くをグラフとして考えることができる。

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

起源

グラフ理論は、1736年に「ケーニヒスベルクの問題」と呼ばれるパズルに対してオイラーが解法を示した[3][4]のが起源のひとつとされる[5]。この問題は、一筆書きと深く関連している[6]。

形式的な定義

有向グラフ

集合 テンプレート:Mvar, テンプレート:Mvar と、テンプレート:Mvar の元（げん、要素）に、二つの テンプレート:Mvar を元の対で対応させる写像

f: E→V×V

の三つ組

G:=(f,V,E)

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

無向グラフ

テンプレート:Math を テンプレート:Mvar の冪集合とする。テンプレート:Mvar の元に テンプレート:Mvar の 部分集合を対応させる写像

g: E→𝔓(V)

があって、テンプレート:Mvar の任意の元 テンプレート:Mvar について、テンプレート:Mvar の像 テンプレート:Math の濃度が1または2であるとき、三つ組

G:=(g,V,E)

を無向グラフという[7]。 テンプレート:Mvar の元を テンプレート:Mvar の頂点、テンプレート:Mvar の元を テンプレート:Mvar の辺と呼ぶ。テンプレート:Math の濃度が1となる テンプレート:Math はループに対応し、テンプレート:Math となる テンプレート:Math は多重辺に対応する。

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

用語

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

頂点と辺

頂点の集合は テンプレート:Mvar、辺の集合は テンプレート:Mvar で表す。グラフ テンプレート:Mvar が先に与えられている場合には、頂点集合を テンプレート:Math、辺集合を テンプレート:Math と表すこともある[8]。

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

重み付きグラフ

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

接合と隣接

辺 テンプレート:Mvar の両端の点を端点といい、端点は辺 テンプレート:Mvar に接合（または接続）しているという。また、辺と辺がある頂点を共有しているとき、その辺どうしは隣接しているという[8]。

距離と直径

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

ループと多重グラフ

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

部分グラフと拡大グラフ

縮約の図示

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

なお、誘導部分グラフの「誘導」はinducedの訳語である。induceの訳としてはこの「誘導する」の他に「生成する」がある[10][11]。このため、誘導部分グラフのことを生成部分グラフということもある[12]。一方、生成部分グラフは全域部分グラフのことを指すこともある。このため、生成部分グラフという語を使う際は、混乱がないか気を付ける必要がある。

次数と正則グラフ

テンプレート:See also

3-正則グラフの例

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

道と閉路

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

完全グラフとクリーク

3頂点からなる完全グラフ：三角形

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

その他の用語

テンプレート:Columns-list

応用

テンプレート:Columns-list

2013年の夏の1カ月の間に異なる言語版のWikipedia（頂点）に貢献したWikipedia編集者（辺）によって形成されたネットワークグラフ[15]。

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

計算機科学

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

言語学

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

物理学および化学

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

社会科学

社会学におけるグラフ理論: モレノのテンプレート:仮リンク（1953年）[24]。

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

生物学

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

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

数学

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

その他

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

問題と定理

テンプレート:Columns-list

備考

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

脚注

出典と補足

テンプレート:Reflist

参考文献

関連文献

日本語の文献

  • László Lovász: 「組合せ論演習 1：数え上げの手法」、東海大学出版会、ISBN 4-486-00996-7 (1988年3月14日).
  • László Lovász: 「組合せ論演習 2：グラフの構造」、東海大学出版会、ISBN 4-486-00997-5 (1988年3月28日).
  • László Lovász: 「組合せ論演習 3：グラフの不変数」、東海大学出版会、ISBN 4-486-00998-3 (1988年年4月11日).
  • László Lovász: 「組合せ論演習 4：集合論的グラフ理論」、東海大学出版会、ISBN 4-486-00999-1 (1988年4月11日).
  • テンプレート:Cite book
  • テンプレート:Cite book
  • 秋山仁 『グラフ理論最前線』朝倉書店（1998年8月） ISBN 978-4-254-11420-1.
  • 加納幹雄 『情報科学のためのグラフ理論』朝倉書店 (2001年2月)、ISBN 978-4-254-11424-9.
  • テンプレート:Cite book
  • テンプレート:Cite book
  • 鈴木晋一編著 『数学教材としてのグラフ理論』, 早稲田教育叢書 31, 学文社, （2012年3月）ISBN 978-4-76202-253-1
  • ノラ・ハーツフィールド&ゲーハード・リンゲル著 鈴木晋一訳,『グラフ理論入門』,サイエンス社, （1992年6月1日）ISBN 978-4-78190-654-6
  • ボロバシュ・ベーラ著 斎藤伸自, 西関隆夫訳,『グラフ理論入門』,培風館, （1983年4月30日）ISBN 978-4-56300-544-3
  • リウ：「組合せ数学入門II」、共立出版（1972年）。
  • R.J.ウィルソン：「グラフ理論入門」、近代科学社、ISBN 4-7649-0103-X (1985年3月20日）．
  • 榎本彦衛：「グラフ学入門」、日本評論社(1988年)。
  • 佐藤公男：「グラフ理論入門：C言語によるプログラムと応用問題」、日刊工業新聞社、ISBN 978-4-526-04361-1 (1999年4月15日)．
  • ウィルソン：「グラフ理論入門」、近代科学社(2001年)。
  • 惠羅博、土屋守正：「［増補改訂版］グラフ理論」、産業図書、ISBN 978-4-7828-5355-9 (2010年2月25日).
  • R.ディーステル：「グラフ理論」、丸善出版、ISBN 978-4621061855（2012年6月5日）。
  • 舩曳信夫、渡邊敏正、内田智之、神保秀司、中西透：「グラフ理論の基礎と応用」、共立出版、ISBN 978-4-320-12314-4 (2012年10月15日).
  • 小林みどり：「あたらしいグラフ理論入門」、牧野書店、ISBN 978-4-434-17727-9 (2013年4月1日).
  • 宮崎修一：「グラフ理論入門：基本とアルゴリズム」、森北出版、ISBN 978-4-627-85281-5（2015年6月）
  • J.A.ボンディ、U.S.R.マーティ：「グラフ理論」、丸善出版、ISBN 978-4621307564 （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.ISBN 978-0-48641-975-6.
  • Chartrand, Gary (1985), Introductory Graph Theory, Dover, ISBN 0-486-24775-9.
  • 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.
  • Lovász László (2008), Kombinatorikai problémák és feladatok, Typotex Kiadó, ISBN 978-963-9664-93-7.
  • Manfred Nitzsche (2004), Graphen für Einsteiger, Rund um das Haus vom Nikolaus. XII, 233 S. Br. € 22,90 ISBN 3-528-03215-4
  • Peter Gritzmann, René Brandenberg (2003) Das Geheimnis des kürzesten Weges. Ein mathematisches Abenteuer. Springer, Berlin - Heidelberg (2.Aufl.). ISBN 3-540-00045-3
  • William Thomas Tutte (2001), Graph Theory, Cambridge University Press, ISBN 978-0-521-79489-3.

関連項目

テンプレート:Wikibooks

外部リンク

テンプレート:ウィキプロジェクトリンク テンプレート:ウィキポータルリンク

テンプレート:Graph Theory-footer テンプレート:最適化アルゴリズム テンプレート:Normdaten

  1. ↑ 概念
  2. ↑ ハイパーリンク
  3. ↑ (ラテン語) Leonhard Euler - Solutio problematis ad geometriam situs pertinentis, Commentarii academiae scientiarum Petropolitanae 8, 1741, pages 128–140.　Konigsberg Bridge problemを参照。
  4. ↑ Diestel, p. 20
  5. ↑ グラフ理論の歴史を扱っているテンプレート:Harvtxtにオイラーの論文の英訳を含む節がある。
  6. ↑ 詳しくは、一筆書きの項を参照。
  7. ↑ 無向グラフと有向グラフ
  8. ↑ 8.0 8.1 8.2 8.3 テンプレート:Harvnb
  9. ↑ 多重グラフ
  10. ↑ ベルジュ「グラフの理論I」p.8.
  11. ↑ ディーステル, 2000
  12. ↑ 茨木「アルゴリズムとデータ構造」
  13. ↑ 閉路
  14. ↑ Diestel, p. 115
  15. ↑ テンプレート:Cite journal
  16. ↑ テンプレート:Cite journal
  17. ↑ 17.0 17.1 テンプレート:Cite journal
  18. ↑ テンプレート:Cite journal
  19. ↑ テンプレート:Cite Journal
  20. ↑ テンプレート:Cite Journal
  21. ↑ テンプレート:Cite web
  22. ↑ テンプレート:Cite book
  23. ↑ テンプレート:Cite journal
  24. ↑ Grandjean, Martin (2015). "Social network analysis and visualization: Moreno’s Sociograms revisited". Redesigned network strictly based on Moreno (1934), Who Shall Survive.
  25. ↑ テンプレート:Cite book
  26. ↑ テンプレート:Cite web
  27. ↑ テンプレート:Cite web
「https://ja.wiki.beta.math.wmflabs.org/w/index.php?title=グラフ理論&oldid=11」から取得