グラフ理論りろん

グラフ理論りろん（グラフりろん、英えい: Graph theory）は、ノード（節点せってん・頂点ちょうてん、点てん）の集合しゅうごうとエッジ（枝えだ・辺あたり、線せん）の集合しゅうごうで構成こうせいされるグラフに関かんする数学すうがくの理論りろんである。

グラフ（データ構造こうぞう）などの応用おうようがある。

概要がいよう

グラフによって、様々さまざまなものの関連かんれんを表あらわすことができる。

6つの節点せってんと7つの辺あたりから成なるグラフの一いち例れい

例たとえば、鉄道てつどうや路線ろせんバス等ひとしの路線ろせん図ずを考かんがえる際さいには、駅えき（節点せってん）がどのように路線ろせん（辺あたり）で結むすばれているかが問題もんだいとなる一方いっぽう、線路せんろが具体ぐたい的てきにどのような曲線きょくせんを描えがいているかは本質ほんしつ的てきな問題もんだいとならないことが多おおい。

したがって、路線ろせん図ずでは駅えき間あいだの距離きょりや微妙びみょうな配置はいち、路線ろせんの形状けいじょうなどがしばしば地理ちり上じょうの実際じっさいとは異ことなって描えがかれている。つまり、路線ろせん図ずの利用りよう者しゃにとっては、駅えきと駅えきの「つながり方かた」が主おもに重要じゅうような情報じょうほうなのである。

このように、「つながり方かた」に着目ちゃくもくして抽象ちゅうしょう化かされた「点てんとそれらをむすぶ線せん」の概念がいねんがグラフであり、グラフがもつ様々さまざまな性質せいしつを探求たんきゅうするのがグラフ理論りろんである。

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

グラフを表現ひょうげんするのに、図ずではなく、隣接りんせつ行列ぎょうれつを用もちいることがある。無む向むかいグラフの隣接りんせつ行列ぎょうれつは、対称たいしょう行列ぎょうれつになる。例たとえば、上うえのグラフは、次つぎの隣接りんせつ行列ぎょうれつで表現ひょうげんできる。

${\begin{pmatrix}0&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{pmatrix}}$

グラフの例れい

詳細しょうさいは「グラフ (離散りさん数学すうがく)」を参照さんしょう

日常にちじょう的てきな問題もんだいや工学こうがく的てき問題もんだいの多おおくをグラフとして考かんがえることができる。

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

起源きげん

グラフ理論りろんは、1736年ねんに「ケーニヒスベルクの問題もんだい」と呼よばれるパズルに対たいしてオイラーが解法かいほうを示しめしたのが起源きげんのひとつとされる。この問題もんだいは、一筆ひとふで書がきと深ふかく関連かんれんしている。

形式けいしき的てきな定義ていぎ

有向ゆうこうグラフ

集合しゅうごう V, E と、E の元もと（げん、要素ようそ）に、二ふたつの V を元もとの対たいで対応たいおうさせる写像しゃぞう

$f\colon \ E\to V\times V$

の三みつ組ぐみ

$G:=(f,V,E)$

を有向ゆうこうグラフという。V の元もとを G の頂点ちょうてんまたはノード、E の元もとを G の辺あたりまたは弧こと呼よぶ。f(e) = (v,v) となる e ∈ E はループに対応たいおうし、f(a) = f(b) となる a, b ∈ E は多重たじゅう辺べに対応たいおうする。

無む向むかいグラフ

𝔓(V) を V の冪べき集合しゅうごうとする。E の元もとに V の 部分ぶぶん集合しゅうごうを対応たいおうさせる写像しゃぞう

$g\colon \ E\to {\mathfrak {P}}(V)$

があって、E の任意にんいの元もと e について、e の像ぞう g(e) の濃度のうどが1または2であるとき、三みつ組ぐみ

$G:=(g,V,E)$

を無む向むかいグラフという。 V の元もとを G の頂点ちょうてん、E の元もとを G の辺あたりと呼よぶ。g(e) の濃度のうどが1となる e ∈ E はループに対応たいおうし、f(a) = f(b) となる a, b ∈ E は多重たじゅう辺べに対応たいおうする。

単純たんじゅんグラフに限かぎって言いえば、E を最初さいしょからある集合しゅうごうの部分ぶぶん集合しゅうごうと考かんがえ、写像しゃぞうを用もちいずにグラフを定義ていぎすることもできる：有向ゆうこうグラフでは、E を V × V の部分ぶぶん集合しゅうごう、無む向こうグラフでは、E を 𝔓(V) の部分ぶぶん集合しゅうごうで、2つの元もとの集合しゅうごうだけからなるものとすればよい。

用語ようご

以下いかでは単たんにグラフといった時ときには無む向こうグラフを指さす。

頂点ちょうてんと辺あたり

頂点ちょうてんの集合しゅうごうは V、辺あたりの集合しゅうごうは E で表あらわす。グラフ G が先さきに与あたえられている場合ばあいには、頂点ちょうてん集合しゅうごうを V(G)、辺あたり集合しゅうごうを E(G) と表あらわすこともある。

数学すうがく以外いがいの分野ぶんやでは、頂点ちょうてんを節点せってん、辺あたりを枝えだと呼よぶことが多おおい。辺あたりを弧こやリンクと呼よぶこともある。

重おもみ付つきグラフ

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

接合せつごうと隣接りんせつ

辺あたり e の両りょう端はしの点てんを端点たんてんといい、端点たんてんは辺あたり e に接合せつごう（または接続せつぞく）しているという。また、辺あたりと辺あたりがある頂点ちょうてんを共有きょうゆうしているとき、その辺あたりどうしは隣接りんせつしているという。

距離きょりと直径ちょっけい

2頂点ちょうてん間あいだ（隣接りんせつしている必要ひつようはない）を経由けいゆする辺あたり数すうを長ながさと呼よび、特とくに最短さいたん経路けいろにおける辺あたり数すうを距離きょりと呼よぶ。グラフ G の最大さいだい頂点ちょうてん間あいだ距離きょりを直径ちょっけいと呼よび、diam(G) と表あらわす。

ループと多重たじゅうグラフ

ある辺あたりの両りょう端点たんてんが等ひとしいとき、ループ（自己じこループ）という。また、2頂点ちょうてん間あいだに複数ふくすうの辺あたりがあるとき、多重たじゅう辺べという。ループも多重たじゅう辺べも含ふくまないグラフのことを単純たんじゅんグラフといい、ループや多重たじゅう辺べを含ふくむグラフのことを多重たじゅうグラフという。

部分ぶぶんグラフと拡大かくだいグラフ

縮ちぢみ約やくの図示ずし

2つのグラフ G と G' について、G' の頂点ちょうてん集合しゅうごうと辺あたり集合しゅうごうが共ともに G の頂点ちょうてん集合しゅうごうと辺あたり集合しゅうごうの部分ぶぶん集合しゅうごうになっているとき、G' は G の部分ぶぶんグラフである、または G は G' の拡大かくだいグラフであるといい、G' ⊂ G と表あらわす。特とくに、G と G' の頂点ちょうてん集合しゅうごうが等ひとしいとき、G' は G の全域ぜんいき部分ぶぶんグラフであるという。また、G の頂点ちょうてん集合しゅうごう V の部分ぶぶん集合しゅうごう U を取とり出だして、両りょう端点たんてんが U に属ぞくする全すべての辺あたりを辺あたり集合しゅうごうとする G の部分ぶぶんグラフ G[U] を、誘導ゆうどう部分ぶぶんグラフという。グラフ G からある辺あたり e を取とり除のぞき、その辺あたりの両りょう端点たんてんを一ひとつの頂点ちょうてんにまとめることを（辺あたりの）縮ちぢみ約やくといい、縮ちぢみ約やくの結果けっか得えられるグラフを G/e と表あらわす。

なお、誘導ゆうどう部分ぶぶんグラフの「誘導ゆうどう」はinducedの訳語やくごである。induceの訳わけとしてはこの「誘導ゆうどうする」の他ほかに「生成せいせいする」がある。このため、誘導ゆうどう部分ぶぶんグラフのことを生成せいせい部分ぶぶんグラフということもある。一方いっぽう、生成せいせい部分ぶぶんグラフは全域ぜんいき部分ぶぶんグラフのことを指さすこともある。このため、生成せいせい部分ぶぶんグラフという語かたりを使つかう際さいは、混乱こんらんがないか気きを付つける必要ひつようがある。

次数じすうと正則せいそくグラフ

「次数じすう (グラフ理論りろん)」も参照さんしょう

3-正則せいそくグラフの例れい

頂点ちょうてん v に接続せつぞくする枝えだの数かずを次数じすうといい、d(v) で表あらわす。有向ゆうこうグラフにおいては、v に入はいってくる辺あたり数すうのことを入次数いりじすう、v から出でて行いく辺あたり数すうのことを出次数でじすうという。すべての頂点ちょうてんが同数どうすうの隣接りんせつ点てん、つまり次数じすうをもつグラフを正則せいそくグラフと呼よぶ。任意にんいの頂点ちょうてん v について、d(v) = k が成なり立たつとき、k-正則せいそくという。k-正則せいそくなグラフのことを k-正則せいそくグラフという。グラフ G が持もつ頂点ちょうてんの次数じすうの最小さいしょう値ちを δでるた(G)、最大さいだい値ちを Δでるた(G) で表あらわす。また、次数じすう 0 の頂点ちょうてんのことを孤立こりつ点てんという。

道みちと閉路へいろ

隣接りんせつしている頂点ちょうてん同士どうしをたどった v₀, e₀, v₁, e₁, ... , e_n−1, v_n の系列けいれつを長ながさ n の歩道ほどう（鎖くさり・ウォーク）という。辺あたりの重複じゅうふくを許ゆるさない歩道ほどうを路みち（小径しょうけい・トレイル）という。頂点ちょうてんの重複じゅうふくを許ゆるさない場合ばあい、つまり、両りょう端はしの2頂点ちょうてんの次数じすうが1、それ以外いがいのすべての頂点ちょうてんの次数じすうが2であるグラフを、道みち（パス）、開ひらいた歩道ほどうをパスという場合ばあいは単純たんじゅんパスという。また、始点してんと終点しゅうてんが同おなじ路ろのことを閉路へいろ（回路かいろ・循環じゅんかん ・サーキット、サイクル）、始点してんと終点しゅうてんが同おなじ道どう（つまり e₁, e₂, ... , e_n, e₁ という路みちで e_i が相あい異ことなるもの）のことを閉道（サイクル）という。

完全かんぜんグラフとクリーク

3頂点ちょうてんからなる完全かんぜんグラフ：三角形さんかっけい

任意にんいの 2 頂点ちょうてん間あいだに枝えだがあるグラフのことを完全かんぜんグラフ（完備かんびグラフ）という。n 頂点ちょうてんの完全かんぜんグラフは、K_n で表あらわす。K₃ は三角形さんかっけいと呼よばれる。また、完全かんぜんグラフになる誘導ゆうどう部分ぶぶんグラフのことをクリークという。大おおきさ（サイズ） n のクリークを含ふくむグラフは「n-クリークである」という。辺あたりをもつグラフは必かならず2頂点ちょうてんの完全かんぜんグラフを含ふくむので 2-クリークである。また n-クリークであって、直径ちょっけいが n 未み満まんとなるグラフを n-クランという。

その他たの用語ようご

• オイラー路ろ（オイラー閉路へいろ・オイラーグラフ）
• ハミルトン路ろ（ハミルトン閉路へいろ・ハミルトングラフ）
• 木き （根ねつき木き・森もり）
  • 全域ぜんいき木き
  • シュタイナー木き
• 直径ちょっけい
• カット
• 2部ぶグラフ （n 部ぶグラフ・彩色さいしき）
• 同型どうけいグラフ
• 連結れんけつグラフ （連結れんけつ成分せいぶん・連結れんけつ度ど）
• 平面へいめんグラフ （平面へいめん的てきグラフ）
• 隣接りんせつ行列ぎょうれつ
• 接続せつぞく行列ぎょうれつ
• 次数じすう行列ぎょうれつ
• 対称たいしょうグラフ
• マッチング
• 閉路へいろグラフ
• 有向ゆうこう非ひ巡回じゅんかいグラフ
• 独立どくりつ集合しゅうごう
• ランダム・グラフ
• マイナー (グラフ理論りろん)
• グラフ代数だいすう
• 空そらグラフ
• 量子りょうしグラフ

応用おうよう

• デッドロックの検出けんしゅつ
• ガベージコレクション
• ファイルシステム
• ニューラルネットワーク
• ペトリネット
• ループ量子りょうし重力じゅうりょく理論りろん
• スケジューリング問題もんだい
• 意味いみネットワーク
• パーコレーション
• 複ふく合あい進化しんか
• PERT
• 全域ぜんいき木き
• タングル
• 結むすび目め理論りろん

2013年ねんの夏なつの1カ月かげつの間あいだに異ことなる言語げんご版ばんのWikipedia（頂点ちょうてん）に貢献こうけんしたWikipedia編集へんしゅう者しゃ（辺あたり）によって形成けいせいされたネットワークグラフ。

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

計算けいさん機き科学かがく

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

言語げんご学がく

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

物理ぶつり学がくおよび化学かがく

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

社会しゃかい科学かがく

社会しゃかい学がくにおけるグラフ理論りろん: モレノのソシオグラム（1953年ねん）。

グラフ理論りろんは社会しゃかい学がくにおいても、例たとえば、特とくに社会しゃかいネットワーク分析ぶんせきソフトウェアを使つかって俳優はいゆうの名声めいせいを見積みつもったり、うわさの広ひろがりを調査ちょうさしたりする手段しゅだんとして広ひろく使つかわれている。社会しゃかいネットワークの傘かさの下したに、多おおくの異ことなる種類しゅるいのグラフがある。知しり合あい関係かんけいグラフと友情ゆうじょう関係かんけいグラフは人々ひとびとが知しり合あいかどうかを記述きじゅつする。影響えいきょうグラフは特定とくていの人々ひとびとが他者たしゃの振ふる舞まいに影響えいきょうするかどうかをモデル化かする。最後さいごに、協調きょうちょうグラフは2人ふたりの人物じんぶつが、映画えいがで一緒いっしょに演技えんぎするといったある特定とくていのやり方かたで協力きょうりょくするかどうかをモデル化かする。

生物せいぶつ学がく

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

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

数学すうがく

数学すうがくでは、グラフは幾何きか学がくならびに結むすび目め理論りろんといったトポロジーの特定とくていの分野ぶんやにおいて有用ゆうようである。代数だいすう的てきグラフ理論りろんは群論ぐんろんと密接みっせつなつながりを持もつ。代数だいすう的てきグラフ理論りろんは動的どうてき系けいや複雑ふくざつ性せいを含ふくむ多おおくの分野ぶんやに応用おうようされている。

その他た

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

問題もんだいと定理ていり

• 最短さいたん経路けいろ問題もんだい
• ハミルトン閉路へいろ問題もんだい
• 巡回じゅんかいセールスマン問題もんだい
• 中国人ちゅうごくじん郵便ゆうびん配達はいたつ問題もんだい
• 最小さいしょう全域ぜんいき木き問題もんだい
• 最大さいだいクリーク問題もんだい
• 頂点ちょうてん被覆ひふく問題もんだい
• 最大さいだい流りゅう最小さいしょうカット定理ていり
• グラフ彩色さいしき問題もんだい - 四よん色しょく定理ていり
• ワーシャル-フロイド法ほう (Warshall-Floyd 問題もんだい)
• 次数じすう直径ちょっけい問題もんだい
• 安定あんてい結婚けっこん問題もんだい
• グラフ・マイナー定理ていり
• グラフサンドウィッチ問題もんだい
• 小石こいし運動うんどう問題もんだい

備考びこう

2022年ねんから日本にっぽんで導入どうにゅうされる高等こうとう学校がっこう新しん学習がくしゅう指導しどう要領ようりょうの数学すうがくC（公式こうしき配布はいふされるのは2024年ねん4月がつ）には「図ず、表ひょう、統計とうけいグラフ、離散りさんグラフ及および行列ぎょうれつなどを用もちいて、日常にちじょうの事象じしょうや社会しゃかいの事象じしょうなどを数学すうがく的てきに表現ひょうげんし、考察こうさつすること」とあり、日本にっぽんでは初はじめてグラフ理論りろんにかかわる分野ぶんやが高等こうとう学校がっこうの数学すうがく教科書きょうかしょに掲載けいさいされる予定よていである。ただし、その分野ぶんやを入試にゅうしに出題しゅつだいする大学だいがくは殆ほとんどない。

参考さんこう文献ぶんけん

• ベルジュ, C. 著ちょ、伊い理り正夫まさお・伊い理由りゆう美び・岩坪いわつぼ秀一ひでかず・小林こばやし欣吾きんご・佐藤さとう創はじめ・星ほし守もり 訳やく『グラフの理論りろんI』サイエンス社しゃ、1976年ねん。ISBN 4-7819-0111-5。 
• ディーステル, ラインハルト 著ちょ、根上ねあがり生なま也・太田おおた克弘かつひろ 訳わけ『グラフ理論りろん』（原書げんしょ第だい2版はん）シュプリンガー・フェアラーク東京とうきょう、2000年ねん。ISBN 978-4-431-70876-6。https://books.google.co.jp/books?id=CZq8AAAAQBAJ。 (現在げんざいは丸善まるぜんに移管いかん)
• Reinhard Diestel (2010), Graphentheorie. Springer-Verlag, Vierte Auflage, 2010 Korrigierter Nachdruck 2012 Heidelberg xviii+355 Seiten, 129 Abbildungen September 2010 (2006, 2000, 1996) ISBN 978-3-642-14911-5 EUR 32,99.
• Biggs, Norman L.; Lloyd, E. Keith; Wilson, Robin J. (1998). Graph theory 1736–1936 (Reprint with corrections ed.). Oxford University Press. ISBN 0-19-853916-9. MR0879117. Zbl 0904.05001. https://books.google.co.jp/books?id=XqYTk0sXmpoC 
• Bondy, J. A.; Murty, U. S. R. (2008). Graph theory. Graduate Texts in Mathematics. 244. Springer. ISBN 978-1-84628-969-9. MR2368647 
• 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; ISBN 978-1-46127-254-0

関連かんれん文献ぶんけん

日本語にほんごの文献ぶんけん

• 根上ねあがり生なま也『離散りさん構造こうぞう』共立きょうりつ出版しゅっぱん〈情報じょうほう数学すうがく講座こうざ 3〉、1993年ねん。ISBN 4-320-02653-5。 
• 秋山あきやま仁ひとし、ロナルド・ルイス・グラハム『離散りさん数学すうがく入門にゅうもん』朝倉書店あさくらしょてん〈入門にゅうもん有限ゆうげん・離散りさんの数学すうがく 1〉、1993年ねん。ISBN 4-254-11419-2。 
• 秋山あきやま仁ひとし 『グラフ理論りろん最前線さいぜんせん』朝倉書店あさくらしょてん ISBN 978-4-254-11420-1.
• 加納かのう幹雄みきお 『情報じょうほう科学かがくのためのグラフ理論りろん』朝倉書店あさくらしょてん ISBN 978-4-254-11424-9.
• ハラリー, フランク 著ちょ、池田いけだ貞雄さだお 訳わけ『グラフ理論りろん』共立きょうりつ出版しゅっぱん、1971年ねん。ISBN 978-4-320-01073-4。 
• 茨木いばらぎ俊秀としひで『アルゴリズムとデータ構造こうぞう』昭あきら晃あきら堂どう、1986年ねん。ISBN 4-7856-0119-1。 
• 鈴木すずき晋一しんいち編著へんちょ 『数学すうがく教材きょうざいとしてのグラフ理論りろん』, 早稲田わせだ教育きょういく叢書そうしょ 31, 学文社がくぶんしゃ, ISBN 978-4-76202-253-1
• ノラ・ハーツフィールド&ゲーハード・リンゲル著しる 鈴木すずき晋一しんいち訳わけ,『グラフ理論りろん入門にゅうもん』,サイエンス社しゃ, ISBN 978-4-78190-654-6
• ボロバシュ・ベーラ著しる 斎藤さいとう伸しん自じ, 西にし関せき隆夫たかお訳わけ,『グラフ理論りろん入門にゅうもん』,培風館ばいふうかん, ISBN 978-4-56300-544-3
• R.ディーステル：「グラフ理論りろん」、丸善まるぜん出版しゅっぱん、ISBN 978-4621061855（2012年ねん6月がつ5日にち）。
• 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.

関連かんれん項目こうもく

• グラフ (離散りさん数学すうがく)
• ラムゼー理論りろん
• マトロイド
• スモール・ワールド現象げんしょう
• グラフ (データ構造こうぞう)
• ネットワーク理論りろん
• 存在そんざいグラフ
• 素す集合しゅうごうデータ構造こうぞう
• 名称めいしょうのあるグラフのギャラリー
• 全域ぜんいき木き
• 平面へいめんグラフ
• 応用おうよう数学すうがく

外部がいぶリンク

• A searchable database of small connected graphs
• Concise, annotated list of graph theory resources for researchers
• Digraphs: Theory Algorithms and Applications 2007 by Jorgen Bang-Jensen and Gregory Gutin
• Graph Theory, by Reinhard Diestel
• Graph Theory Software - tools to teach and learn graph theory
• Graph theory tutorial
• Phase Transitions in Combinatorial Optimization Problems, Section 3: Introduction to Graphs (2006) by Hartmann and Weigt
• rocs - a graph theory IDE
• The Social Life of Routers - non-technical paper discussing graphs of people and computers