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

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

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

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

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

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

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

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

${\displaystyle {\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におけるウェブページの、ハイパーリンク・被リンク関係がなす構造は、有向グラフの一種である^[2]。

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

集合 V, E と、E の元（げん、要素）に、二つの V を元の対で対応させる写像

${\displaystyle f\colon \ E\to V\times V}$

の三つ組

${\displaystyle 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 の 部分集合を対応させる写像

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

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

${\displaystyle G:=(g,V,E)}$

を無向グラフという^[7]。 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) と表すこともある^[8]。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• ベルジュ, 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

• 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日).
• 根上生也『離散構造』共立出版〈情報数学講座 3〉、1993年。ISBN 4-320-02653-5。 
• 秋山仁、ロナルド・ルイス・グラハム『離散数学入門』朝倉書店〈入門有限・離散の数学 1〉、1993年。ISBN 4-254-11419-2。 
• 秋山仁 『グラフ理論最前線』朝倉書店（1998年8月） ISBN 978-4-254-11420-1.
• 加納幹雄 『情報科学のためのグラフ理論』朝倉書店 (2001年2月)、ISBN 978-4-254-11424-9.
• ハラリー, フランク 著、池田貞雄 訳『グラフ理論』共立出版、1971年。ISBN 978-4-320-01073-4。 
• 茨木俊秀『アルゴリズムとデータ構造』昭晃堂、1986年。ISBN 4-7856-0119-1。 
• 鈴木晋一編著 『数学教材としてのグラフ理論』, 早稲田教育叢書 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.

ウィキブックスにグラフ理論関連の解説書・教科書があります。

• グラフ (離散数学)
• ラムゼー理論
• マトロイド
• スモール・ワールド現象
• グラフ (データ構造)
• ネットワーク理論
• 存在グラフ
• 素集合データ構造
• 名称のあるグラフのギャラリー
• 全域木
• 平面グラフ
• 応用数学

プロジェクト 数学

ポータル 数学

• 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

表 話 編 歴 グラフ理論
要素・定義・表現	頂点 辺（英語版） グラフ 無向 有向 ラベル付き（英語版） 重み付き（英語版） ハイパーグラフ 接続行列 隣接行列 隣接リスト
指標	位数（英語版） サイズ（英語版） 次数 次数行列 距離（英語版） 半径 直径 内周 (頂点)彩色数 辺彩色数（英語版） 点連結度 辺連結度 交叉数（英語版）
部分構造	ループ（英語版） 多重辺（英語版） 部分グラフ（英語版） 誘導部分グラフ 道 閉道 連結成分（英語版） 強連結成分（英語版） 橋（英語版） カット クリーク 独立集合 支配集合（英語版） マッチング オイラー路 シュタイナー木 全域木 ハミルトン路
全体構造	連結グラフ 正則グラフ 立方体グラフ ケージ 強正則グラフ 木 平面グラフ 2部グラフ 有向非巡回グラフ 弦グラフ ムーアグラフ パーフェクトグラフ 対称グラフ 半対称グラフ 頂点推移グラフ 辺推移グラフ 距離推移グラフ 補グラフ 双対グラフ グラフ同型
固有名を持つグラフ	パスグラフ（英語版）Pn 閉路グラフCn 完全グラフKn 完全2部グラフKm,n スターSn = K1,n 車輪グラフWn 空グラフ ピーターセングラフ ヒーウッドグラフ マギーグラフ ホフマンシングルトングラフ フォークマングラフ
トピック・定理	一筆書き オイラーの多面体定理 クラトフスキの定理 四色定理 五色定理 ケイリーの公式 プリューファー列 最短経路問題 巡回セールスマン問題 中国人郵便配達問題 ダイクストラ法 ベルマン-フォード法 ワーシャル-フロイド法 ハミルトン閉路問題 最大クリーク問題 頂点被覆問題 最小頂点被覆問題 最大独立集合問題 最大流最小カット定理 支配集合問題 次数直径問題 安定結婚問題
カテゴリ / コモンズ

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形(無制約)	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性 信頼領域 ウルフ条件 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP法 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法（英語版）
非線形(制約付き)	一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）
凸最適化	凸縮小化 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および 二次 内点法 カチヤンの楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂単体法（英語版） 十文字法（英語版） レムケの主ピボット操作法（英語版） 有効制約法（英語版）
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 分枝カット法) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）