グラフ理論

数学とコンピュータサイエンスにおいて、グラフ理論はグラフの研究であり、グラフはオブジェクト間の一対一の関係をモデル化するために使用される数学的構造です。この文脈におけるグラフは、エッジ（弧、リンク、または線とも呼ばれる）によって接続された頂点（ノードまたはポイントとも呼ばれる）で構成されます。エッジが2つの頂点を対称的にリンクする無向グラフと、エッジが 2 つの頂点を非対称的にリンクする有向グラフは区別されます。グラフは、離散数学の主要な研究対象の 1 つです。

グラフ理論における定義はさまざまです。以下は、グラフと関連する数学的構造を定義するより基本的な方法の一部です。

限定的だが非常に一般的な意味では、^{[1] [2]}グラフとは、以下の要素からなる順序付きペア である。 ${\displaystyle G=(V,E)}$

• ${\displaystyle V}$頂点（ノードまたはポイントとも呼ばれる）の集合。
• ${\displaystyle E\subseteq \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}}$、エッジのセット（リンクまたはラインとも呼ばれる）であり、順序付けられていない頂点のペアです（つまり、エッジは 2 つの異なる頂点に関連付けられています）。

曖昧さを避けるために、このタイプのオブジェクトは、正確には無向単純グラフと呼ばれることがあります。

辺 では、頂点と は辺の端点と呼ばれます。辺 は と を結合し、およびに接続されると言われています。頂点はグラフ内に存在していても、辺に属していない場合があります。この定義では、 2 つ以上の辺が同じ頂点を接続する多重辺は許可されません。 ${\displaystyle \{x,y\}}$${\displaystyle x}$${\displaystyle y}$ ${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$

複数の辺を許容する用語のより一般的な意味では、^{[3] [4]}グラフは以下の要素からなる順序付き3つ組である: ${\displaystyle G=(V,E,\phi )}$

• ${\displaystyle V}$頂点（ノードまたはポイントとも呼ばれる）の集合。
• ${\displaystyle E}$、エッジのセット（リンクまたはラインとも呼ばれます）。
• ${\displaystyle \phi :E\to \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}}$すべてのエッジを順序付けられていない頂点のペアにマッピングする接続関数（つまり、エッジは 2 つの異なる頂点に関連付けられます）。

曖昧さを避けるために、このタイプのオブジェクトは、正確には無向多重グラフと呼ばれることがあります。

ループとは、頂点をそれ自身に接続する辺のことです。上の 2 つの定義で定義されているグラフはループを持つことができません。これは、頂点をそれ自身に接続するループが辺 (無向単純グラフの場合) であるか、に含まれないに接続する (無向多重グラフの場合) ためです。ループを許可するには、定義を拡張する必要があります。無向単純グラフの場合、 の定義を に変更する必要があります。無向多重グラフの場合、 の定義を に変更する必要があります。曖昧さを避けるために、これらのタイプのオブジェクトは、それぞれループを許可する無向単純グラフ、およびループを許可する無向多重グラフ(無向擬似グラフと呼ばれることもあります)と呼ばれることがあります。 ${\displaystyle x}$${\displaystyle \{x,x\}=\{x\}}$${\displaystyle \{\{x,y\}\mid x,y\in V\;{\textrm {and}}\;x\neq y\}}$${\displaystyle E}$${\displaystyle E\subseteq \{\{x,y\}\mid x,y\in V\}}$${\displaystyle \phi}$${\displaystyle \phi :E\to \{\{x,y\}\mid x,y\in V\}}$

${\displaystyle V}$および は通常有限であるとみなされ、多くのよく知られた結果は無限グラフに対しては正しくありません（またはむしろ異なります）。これは、多くの議論が無限の場合には成り立たないからです。さらに、は空でないとみなされることが多いですが、空集合であることが許されています。グラフの位数は 、つまりその頂点の数です。グラフのサイズは、つまりその辺の数です。頂点の次数または価数は、その頂点に接続する辺の数です。ループは 2 回カウントされます。グラフの次数は、その頂点の次数の最大値です。 ${\displaystyle E}$${\displaystyle V}$${\displaystyle E}$${\displaystyle |V|}$${\displaystyle |E|}$

n次数の無向単純グラフでは、各頂点の最大次数はn − 1であり、グラフの最大サイズは⁠ｎ（ｎ −１）/2⁠ .

ループを許容する無向単純グラフの辺は、の頂点に対称同次関係を誘導します。これはの隣接関係と呼ばれます。具体的には、各辺 について、その端点と は互いに隣接していると言われ、 と表記されます。 ${\displaystyle G}$ ${\displaystyle \sim}$${\displaystyle G}$${\displaystyle G}$${\displaystyle (x,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x\sim y}$

有向グラフまたはダイグラフは、エッジに方向があるグラフです。

限定的だが非常に一般的な意味では、^[5]有向グラフとは、以下の要素からなる順序付きペアである。 ${\displaystyle G=(V,E)}$

• ${\displaystyle V}$頂点（ノードまたはポイントとも呼ばれる）の集合。
• ${\displaystyle E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}}$頂点のペアが順序付けられている（つまり、エッジは 2 つの異なる頂点に関連付けられている）エッジのセット（有向エッジ、有向リンク、有向線、矢印、または円弧とも呼ばれます） 。

曖昧さを避けるために、このタイプのオブジェクトは、正確には有向単純グラフと呼ばれることがあります。集合論とグラフ理論では、は、の要素のn組の集合、つまり、必ずしも区別されない要素 の順序付けられたシーケンスを表します。${\displaystyle V^{n}}$${\displaystyle V,}$${\displaystyle n}$

からに向かう辺において、頂点および は、それぞれ辺の端点、辺の末尾、辺の先端と呼ばれます。辺は と を結合し、 および に接続されると言われています。頂点はグラフ内に存在していても、辺に属していない場合があります。辺はの反転辺と呼ばれます。上記の定義では許可されていない多重辺は、同じ末尾と同じ先端を持つ 2 つ以上の辺です。 ${\displaystyle (x,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$ ${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle (y,x)}$${\displaystyle (x,y)}$

複数の辺を許容する用語のより一般的な意味では、^[5]有向グラフは以下の要素を含む順序付き3つ組である。 ${\displaystyle G=(V,E,\phi )}$

• ${\displaystyle V}$頂点（ノードまたはポイントとも呼ばれる）の集合。
• ${\displaystyle E}$、エッジの集合（有向エッジ、有向リンク、有向線、矢印、または円弧とも呼ばれる）。
• ${\displaystyle \phi :E\to \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}}$すべての辺を頂点の順序付きペアにマッピングする接続関数（つまり、辺は 2 つの異なる頂点に関連付けられます）。

曖昧さを避けるために、このタイプのオブジェクトは、正確には有向多重グラフと呼ばれることがあります。

ループとは、頂点を自身に接続する辺のことです。上の 2 つの定義で定義されている有向グラフはループを持つことができません。これは、頂点を自身に接続するループが辺 (有向単純グラフの場合) であるか、に含まれないに入射する (有向多重グラフの場合) ためです。したがって、ループを許可するには、定義を拡張する必要があります。有向単純グラフの場合、の定義は に変更する必要があります。有向多重グラフの場合、 の定義は に変更する必要があります。曖昧さを避けるために、これらのタイプのオブジェクトは、それぞれループを許可する有向単純グラフとループを許可する有向多重グラフ(または矢印)と正確に呼ぶことができます。 ${\displaystyle x}$${\displaystyle (x,x)}$${\displaystyle \left\{(x,y)\mid (x,y)\in V^{2}\;{\textrm {and}}\;x\neq y\right\}}$${\displaystyle E}$${\displaystyle E\subseteq \left\{(x,y)\mid (x,y)\in V^{2}\right\}}$${\displaystyle \phi }$${\displaystyle \phi :E\to \left\{(x,y)\mid (x,y)\in V^{2}\right\}}$

ループを許容する有向単純グラフの辺は、の頂点上の同次関係~であり、これはの隣接関係と呼ばれます。具体的には、各辺 について、その端点と は互いに隣接していると言われ、これは~と表記されます。 ${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle (x,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$

^{グラフは、物理、生物、 [7] [8]}社会、情報システムにおける多くの種類の関係やプロセスをモデル化するために使用できます。 ^[9]多くの実用的な問題はグラフで表現できます。現実世界のシステムへの応用を強調して、ネットワークという用語は、属性（名前など）が頂点と辺に関連付けられたグラフを意味すると定義されることもあり、現実世界のシステムをネットワークとして表現および理解する分野はネットワーク科学と呼ばれます。

コンピュータサイエンスでは、「因果的」および「非因果的」なリンク構造は、通信ネットワーク、データ編成、計算デバイス、計算フローなどを表すために使用されるグラフです。たとえば、Webサイトのリンク構造は有向グラフで表すことができます。有向グラフでは、頂点がWebページを表し、有向エッジが1つのページから別のページへのリンクを表します。同様のアプローチは、ソーシャルメディア、^[10]、旅行、生物学、コンピュータチップ設計、神経変性疾患の進行のマッピング、^{[11] [12]、およびその他の多くの分野の問題にも適用できます。したがって、グラフを処理する}アルゴリズムの開発は、コンピュータサイエンスにおいて大きな関心事です。グラフの変換は、多くの場合、グラフ書き換えシステムによって形式化され、表されます。ルールベースのグラフのインメモリ操作に重点を置いたグラフ変換システムを補完するのが、トランザクションセーフで永続的なグラフ構造化データの保存とクエリを目的としたグラフデータベースです。

グラフ理論的手法は、様々な形で、特に言語学において有用であることが証明されている。自然言語は離散構造に適していることが多いためである。伝統的に、統語論と構成意味論はツリーベースの構造に従っており、その表現力は階層グラフでモデル化された構成性の原理にある。ヘッド駆動句構造文法などのより現代的なアプローチは、有向非巡回グラフである型付き素性構造を使用して自然言語の統語論をモデル化する。語彙意味論、特にコンピュータに適用される語彙意味論においては、特定の単語が関連する単語の観点から理解されると単語の意味をモデル化することが容易になる。したがって、意味ネットワークは計算言語学において重要である。それでも、音韻論（例えば、格子グラフを使用する最適性理論）や形態論（例えば、有限状態トランスデューサを使用する有限状態形態論）における他の手法は、グラフとしての言語の分析では一般的である。実際、この数学の分野が言語学に有用であることから、 TextGraphs などの組織や、WordNet、VerbNetなどのさまざまな「ネット」プロジェクトが誕生しました。

グラフ理論は化学や物理学の分子の研究にも利用されている。凝縮物質物理学では、原子の位相に関連するグラフ理論的特性に関する統計を収集することで、シミュレートされた複雑な原子構造の3次元構造を定量的に研究することができる。また、「ファインマングラフと計算規則は、理解したい実験数値と密接に関連する形で量子場理論を要約している」。 ^[13]化学では、グラフは分子の自然なモデルを作り、頂点は原子、辺は結合を表す。このアプローチは、化学エディタからデータベース検索まで、分子構造のコンピュータ処理に特に使用されている。統計物理学では、グラフはシステムの相互作用する部分間のローカルな接続や、そのようなシステム上の物理プロセスのダイナミクスを表すことができる。同様に、計算神経科学では、グラフは相互作用してさまざまな認知プロセスを生み出す脳領域間の機能的な接続を表すために使用でき、頂点は脳のさまざまな領域を表し、辺はそれらの領域間の接続を表す。グラフ理論は電気ネットワークの電気的モデリングにおいて重要な役割を果たしており、ここでは重みが配線セグメントの抵抗に関連付けられ、ネットワーク構造の電気的特性を取得します。^{[14]グラフは}多孔質媒体のマイクロスケールのチャネルを表すためにも使用され、頂点は細孔を表し、エッジは細孔を接続する小さなチャネルを表します。化学グラフ理論では、分子グラフを分子のモデル化の手段として使用します。 グラフとネットワークは、相転移や臨界現象を研究および理解するための優れたモデルです。 ノードまたはエッジを削除すると、ネットワークが小さなクラスターに分割される臨界遷移が起こり、これが相転移として研究されます。 この崩壊は、パーコレーション理論によって研究されます。^[15]

グラフ理論は社会学でも広く使われており、例えば俳優の名声を測ったり、噂の広がりを調査したりするために、特にソーシャルネットワーク分析ソフトウェアの使用を通じて使われています。ソーシャルネットワークにはさまざまな種類のグラフがあります。^[17]知人関係グラフと友人関係グラフは、人々がお互いを知っているかどうかを表します。影響グラフは、特定の人々が他の人の行動に影響を与えることができるかどうかをモデル化します。最後に、コラボレーショングラフは、2人の人々が映画で一緒に演技するなど、特定の方法で協力しているかどうかをモデル化します。

同様に、グラフ理論は生物学や保全活動にも役立ちます。頂点は特定の種が存在する（または生息する）地域を表し、辺は地域間の移動経路または動きを表します。この情報は、繁殖パターンを調べたり、病気や寄生虫の蔓延を追跡したり、動きの変化が他の種にどのような影響を与えるかを調べたりするときに重要です。

グラフは分子生物学やゲノミクスでも、複雑な関係を持つデータセットをモデル化して分析するためによく使用されます。たとえば、グラフベースの方法は、単一細胞トランスクリプトーム解析で細胞を細胞タイプに「クラスター化」するためによく使用されます。別の用途としては、代謝経路や遺伝子制御ネットワークなど、経路内の遺伝子またはタンパク質をモデル化し、それらの関係を研究することです。 ^[18]進化ツリー、生態学的ネットワーク、遺伝子発現パターンの階層的クラスタリングもグラフ構造として表されます。

グラフ理論はコネクトミクスでも使われています。^[19]神経系はグラフとして見ることができ、ノードはニューロン、エッジはそれらの間の接続です。

数学では、グラフは幾何学や、結び目理論などの位相幾何学の特定の部分で役立ちます。代数グラフ理論は群論と密接な関係があります。代数グラフ理論は、動的システムや複雑性を含む多くの分野に適用されてきました。

グラフ構造は、グラフの各辺に重みを割り当てることによって拡張できます。重み付きのグラフ、つまり重み付きグラフは、ペアワイズ接続が何らかの数値を持つ構造を表すために使用されます。たとえば、グラフが道路網を表す場合、重みは各道路の長さを表すことができます。各辺には、距離 (前の例のように)、移動時間、金銭的コストなど、複数の重みが関連付けられている場合があります。このような重み付きグラフは、GPS のプログラムや、飛行時間とコストを比較する旅行計画検索エンジンによく使用されます。

1736年に出版されたレオンハルト・オイラーのケーニヒスベルクの七つの橋に関する論文は、グラフ理論史上最初の論文とされている。^{[20]この論文は、}ヴァンデルモンドのナイト問題に関する論文と同様に、ライプニッツによって始められた位置分析を引き継いだものである。凸多面体の辺、頂点、面の数に関するオイラーの公式は、コーシー^[21]とルイリエ^{[22]によって研究・一般化され、位相}幾何学として知られる数学の一分野の始まりを表している。

オイラーのケーニヒスベルクの橋に関する論文から1世紀以上が経ち、リスティングが位相幾何学の概念を導入していた頃、微分積分から生じる特定の解析形式への関心から、ケイリーは特定のグラフのクラスである木を研究するようになった。^[23]この研究は理論化学に多くの影響を与えた。彼が使用した手法は主に、特定の特性を持つグラフの列挙に関するものであった。ケイリーの結果と、1935年から1937年にかけてポリアが発表した基本的な結果から、列挙型グラフ理論が生まれた。これらは1959年にデ・ブリュインによって一般化された。ケイリーは木に関する自身の結果を、当時の化学組成の研究と結び付けた。^[24]数学のアイデアと化学のアイデアの融合が、グラフ理論の標準用語の一部となったものである。

特に、「グラフ」という用語は、 1878年にネイチャー誌に発表された論文でシルベスターによって導入され、そこで彼は代数と分子図の「量子不変量」と「共変量」との類似性を説明しています。^[25]

「[…] すべての不変量と共変量は、ケクレ図またはケミコグラフと正確に同一のグラフで表現可能になります。[…] 私はグラフの幾何学的乗算、つまり、別個のグラフが与えられた不変量または共変量の積にグラフを構築するための規則を示します。[…]」（イタリック体は原文と同じ）。

グラフ理論に関する最初の教科書はデーネス・ケーニヒによって書かれ、1936年に出版された。^[26]フランク・ハラリによる1969年の別の本は「世界中でこの分野の決定的な教科書とみなされ」^[27]、数学者、化学者、電気技術者、社会科学者が互いに話し合うことを可能にした。ハラリは印税のすべてをポリア賞の資金として寄付した。^[28]

グラフ理論における最も有名かつ刺激的な問題の一つが、4 色問題である。「平面上に描かれた任意の地図において、その領域を 4 色で塗り分け、共通の境界を持つ任意の 2 つの領域が異なる色になるというのは本当か?」この問題は、1852 年にフランシス ガスリーによって初めて提起され、同年にド モルガンがハミルトンに宛てた手紙に初めて記録されている。ケイリー、ケンプ、その他による証明を含め、多くの誤った証明が提案されている。テイト、ヒーウッド、ラムゼー、ハドヴィガーによるこの問題の研究と一般化は、任意の種数の曲面に埋め込まれたグラフの彩色研究につながった。テイトの再定式化によって、因数分解問題という新しい種類の問題が生み出され、特にピーターセンとケーニッヒによって研究された。ラムゼーの色彩に関する研究、特にトゥランが 1941 年に得た結果は、グラフ理論の別の分野である極値グラフ理論の起源となりました。

4色問題は1世紀以上も未解決のままだった。1969年にハインリッヒ・ヒーシュはコンピュータを使って問題を解く方法を発表した。^{[29] 1976年に}ケネス・アペルとヴォルフガング・ハーケンが行ったコンピュータ支援による証明は、ヒーシュが開発した「放電」の概念を根本的に利用している。^{[30] [31]}この証明は1,936通りの構成の特性をコンピュータでチェックするものであり、その複雑さゆえに当時は完全には受け入れられなかった。20年後、ロバートソン、シーモア、サンダース、トーマスが633通りの構成のみを考慮したより単純な証明を行った。^[32]

1860 年から 1930 年にかけてのトポロジーの自律的な発展は、ジョーダン、クラトフスキー、ホイットニーの研究を通じてグラフ理論に栄養を与えました。グラフ理論とトポロジーの共通の発展のもう 1 つの重要な要素は、現代代数の技法の使用でした。そのような使用の最初の例は、物理学者グスタフ キルヒホフの研究に見られます。キルヒホフは 1845 年に、電気回路の電圧と電流を計算するためのキルヒホッフの回路法則を発表しました。

グラフ理論における確率的手法の導入、特にエルデシュとレーニによるグラフ連結性の漸近確率の研究により、ランダムグラフ理論として知られるさらに別の分野が生まれ、グラフ理論的成果の実り多い源泉となってきました。

グラフは、自然界に現れる関係を抽象化したものであるため、特定の表現と結び付けることはできません。グラフの表現方法は、その表現が特定のアプリケーションに提供する利便性の度合いによって異なります。最も一般的な表現は、通常、頂点が描画され、エッジで接続されるビジュアル表現と、テーブルの行がグラフ内の頂点間の関係に関する情報を提供する表形式です。

グラフは通常、各頂点に点または円を描き、2 つの頂点が辺で接続されている場合はそれらの頂点間に線を描くことで視覚的に表現されます。グラフに方向がある場合は、矢印を描いて方向を示します。グラフに重みがある場合は、矢印に重みが追加されます。

グラフ描画はグラフ自体 (抽象的で視覚的でない構造) と混同しないでください。グラフ描画を構成する方法はいくつかあるからです。重要なのは、どの頂点がどの頂点に何本のエッジで接続されているかであり、正確なレイアウトではありません。実際には、2 つの描画が同じグラフを表しているかどうかを判断するのは難しいことがよくあります。問題領域によっては、他のレイアウトよりも適していて理解しやすいレイアウトもあります。

WT タットの先駆的な研究は、グラフ描画の分野に大きな影響を与えました。彼の業績の中には、グラフ描画を得るための線形代数的手法の使用法も含まれています。

グラフ描画は、交差数とそのさまざまな一般化を扱う問題を包含しているとも言えます。グラフの交差数とは、平面上のグラフの描画に含まれる必要がある辺間の交点の最小数です。平面グラフの場合、交差数は定義により 0 です。平面以外の表面上の描画も研究されています。

頂点や辺から離れてグラフを視覚化する他の手法としては、円パッキング、交差グラフ、隣接行列のその他の視覚化などがあります。

表形式の表現は、計算アプリケーションに適しています。グラフをコンピュータシステムに保存する方法はいくつかあります。使用されるデータ構造は、グラフ構造とグラフを操作するために使用されるアルゴリズムの両方に依存します。理論的にはリスト構造と行列構造を区別できますが、実際のアプリケーションでは、最適な構造は両方の組み合わせであることがよくあります。リスト構造は、メモリ要件が少ないため、スパースグラフによく使用されます。一方、行列構造は、一部のアプリケーションでより高速なアクセスを提供しますが、大量のメモリを消費する可能性があります。現代の並列コンピュータアーキテクチャで効率的なスパース行列構造の実装は、現在調査の対象となっています。^[33]

リスト構造には、頂点のペアの配列であるエッジ リストと、各頂点の隣接頂点を個別にリストする隣接リストが含まれます。エッジ リストと同様に、各頂点には隣接する頂点のリストがあります。

行列構造には、行が頂点、列が辺を表す 0 と 1 の行列である接続行列 と、行と列の両方が頂点によってインデックス付けされる隣接行列があります。どちらの場合も、1 は 2 つの隣接するオブジェクトを示し、0 は 2 つの隣接しないオブジェクトを示します。次数行列は頂点の次数を示します。ラプラシアン行列は、頂点の次数に関する情報を組み込んだ隣接行列の修正版であり、グラフの全域木の数に関するキルヒホッフの定理などの計算に役立ちます。距離行列は、隣接行列と同様に、行と列の両方が頂点によってインデックス付けされますが、各セルに 0 または 1 を格納するのではなく、 2 つの頂点間の最短経路の長さが格納されます。

指定された条件を満たすグラフを数える問題で あるグラフィカル列挙に関する文献は多数あります。この研究の一部は Harary と Palmer (1973) に記載されています。

サブグラフ同型性問題と呼ばれる一般的な問題は、与えられたグラフのサブグラフとして固定グラフを見つけることです。このような問題に関心を持つ理由の 1 つは、多くのグラフ プロパティがサブグラフに対して継承されることです。つまり、グラフがそのプロパティを持つのは、すべてのサブグラフがそのプロパティを持っている場合のみです。残念ながら、特定の種類の最大サブグラフを見つけることは、多くの場合NP 完全問題です。たとえば、 次のようになります。

• 最大の完全サブグラフを見つけることは、クリーク問題(NP 完全) と呼ばれます。

部分グラフ同型性の特殊なケースの 1 つに、グラフ同型性問題があります。これは、2 つのグラフが同型であるかどうかを問うものです。この問題が NP 完全であるかどうか、また多項式時間で解決できるかどうかはわかっていません。

同様の問題として、与えられたグラフ内の誘導サブグラフを見つけることが挙げられます。ここでも、重要なグラフ特性の一部は誘導サブグラフに関して遺伝的であり、つまり、グラフが特性を持つのは、すべての誘導サブグラフにその特性がある場合に限ります。特定の種類の最大誘導サブグラフを見つけることも、NP 完全であることが多いです。たとえば、次のようになります。

• 最大のエッジのない誘導サブグラフまたは独立集合を見つけることは、独立集合問題(NP 完全)と呼ばれます。

マイナー包含問題という、さらに別の問題は、与えられたグラフのマイナーとして固定グラフを見つけることです。グラフのマイナーまたはサブコントラクションとは、サブグラフを取り、いくつかの (またはまったくない) エッジを縮約することによって得られるグラフです。多くのグラフ プロパティはマイナーに対して継承されます。つまり、グラフがプロパティを持つのは、すべてのマイナーがそのプロパティを持っている場合のみです。たとえば、ワグナーの定理は次のように述べています。

• グラフが平面グラフであるとは、マイナーグラフとして完全二部グラフ K _3,3 ( 3コテージ問題を参照) も完全グラフK ₅も含まれないことを意味します。

同様の問題である細分化包含問題は、与えられたグラフの細分として固定グラフを見つけることです。グラフの細分化または同相写像とは、いくつかの（または全く）辺を細分化することによって得られるグラフです。細分化包含は、平面性などのグラフ特性に関連しています。たとえば、クラトフスキーの定理は次のように述べています。

• グラフが平面グラフであるのは、そのグラフが完全二部グラフ K _3,3も完全グラフ K ₅も部分として含まないときである。

細分化の包含におけるもう一つの問題はケルマンス・シーモア予想である。

• 平面でない5 頂点連結グラフはすべて、 5 頂点完全グラフK _5のサブディビジョンを含みます。

別の種類の問題は、グラフのさまざまな種類と一般化が、点を削除したサブグラフによってどの程度決定されるかに関係しています。たとえば、

• 再建の推測

グラフ理論における多くの問題や定理は、グラフを色付けするさまざまな方法に関係しています。通常、グラフを色付けする際に、隣接する 2 つの頂点が同じ色にならないようにしたり、その他の同様の制限を設けたりすることが目的です。また、エッジの色付け (一致する 2 つのエッジが同じ色にならないようにするなど) やその他のバリエーションも検討できます。グラフの色付けに関する有名な結果や推測には、次のものがあります。

• 四色定理
• 強い完全グラフ定理
• エルデシュ・ファーバー・ロヴァーシュ予想
• 全彩色予想、別名ベザド予想（未解決）
• リストカラーリング予想（未解決）
• ハドヴィガー予想（グラフ理論）（未解決）

制約モデリング理論は、半順序によって関連付けられた有向グラフの族に関するものです。これらのアプリケーションでは、グラフは特異性によって順序付けられます。つまり、より制約のあるグラフ (より具体的で、したがってより多くの情報を含む) は、より一般的なグラフに包含されます。グラフ間の操作には、2 つのグラフ間の包含関係の方向 (存在する場合) の評価と、グラフの統合の計算が含まれます。2 つの引数グラフの統合は、入力と一致する (つまり、入力内のすべての情報を含む) 最も一般的なグラフ (またはその計算) として定義されます (そのようなグラフが存在する場合)。効率的な統合アルゴリズムが知られています。

厳密に構成的な制約フレームワークの場合、グラフの統一は十分な充足可能性と組み合わせ機能です。よく知られているアプリケーションには、自動定理証明や言語構造の詳細化のモデル化などがあります。

• ハミルトン経路問題
• 最小全域木
• 経路検査問題（「中国の郵便配達員問題」とも呼ばれる）
• ケーニヒスベルクの7つの橋
• 最短経路問題
• シュタイナーの木
• 3つのコテージの問題
• 巡回セールスマン問題（NP困難）

特に、ネットワーク内のフローのさまざまな概念に関係するアプリケーションからは、次のような数多くの問題が発生します。

• 最大フロー最小カット定理

• 博物館の警備員問題

グラフの被覆問題とは、頂点/サブグラフのサブセット上の さまざまな集合被覆問題を指す場合があります。

• 支配集合問題は、集合が閉じた近傍である集合被覆問題の特殊なケースです。
• 頂点カバー問題は、カバーする集合がすべての辺である集合カバー問題の特殊なケースです。
• 元のセットカバー問題 (ヒッティングセットとも呼ばれる) は、ハイパーグラフ内の頂点カバーとして記述できます。

分解は、グラフの辺集合を分割すること（分割の各部分の辺に必要な数の頂点を付加する）として定義され、さまざまな問題があります。多くの場合、問題はグラフを固定グラフと同型のサブグラフに分解することです。たとえば、完全グラフをハミルトン閉路に分解します。他の問題では、特定のグラフを分解するグラフの族を指定します。たとえば、閉路の族、または完全グラフK _{n を}それぞれ 1、2、3、...、n − 1の辺を持つn − 1 の指定された木に分解します。

研究されてきた特定の分解問題には次のようなものがあります。

• 樹木性、できるだけ少ない森林に分解する
• サイクル二重被覆、各辺を正確に2回被覆するサイクルの集合への分解
• エッジカラーリング、できるだけ少ないマッチングに分解する
• グラフ因数分解、正規グラフを与えられた次数の正規部分グラフに分解すること

多くの問題では、さまざまなクラスのグラフのメンバーを特徴付ける必要があります。以下に、そのような質問の例をいくつか示します。

• クラスのメンバーを列挙する
• 禁止されたサブ構造の観点からクラスを特徴付ける
• クラス間の関係を確認する（例：グラフの1つの特性が別の特性を意味するか）
• クラス内のメンバーシップを決定するための効率的なアルゴリズムを見つける
• クラスのメンバーの表現を見つける

• 名前付きグラフのギャラリー
• グラフ理論用語集
• グラフ理論のトピックのリスト
• グラフ理論における未解決問題の一覧
• グラフ理論に関する出版物
• グラフアルゴリズム
• グラフ理論家

• 代数的グラフ理論
• 幾何グラフ理論
• 極値グラフ理論
• 確率的グラフ理論
• 位相グラフ理論
• グラフ描画

• Bender, Edward A.; Williamson, S. Gill (2010) リスト、決定、グラフ。確率入門付き。
• ベルジェ、クロード (1958)。グラフとアプリケーションの理論。パリ：デュノー。英語版、Wiley 1961年; Methuen & Co、ニューヨーク 1962年; ロシア語、モスクワ 1961年; スペイン語、メキシコ 1962年; ルーマニア語、ブカレスト 1969年; 中国語、上海 1963年; 1962年初版英語版の第2刷、ドーバー、ニューヨーク 2001年。
• Biggs, N.; Lloyd, E.; Wilson, R. (1986).グラフ理論 1736–1936 . Oxford University Press.
• Bondy, JA; Murty, USR (2008).グラフ理論. Springer. ISBN 978-1-84628-969-9。
• Bollobás, Béla; Riordan, OM (2003)。スケールフリー ランダム グラフの数学的結果、「Handbook of Graphs and Networks」(S. Bornholdt および HG Schuster (編)) (第 1 版)。Weinheim: Wiley VCH。
• チャートランド、ゲイリー（1985年）。『グラフ理論入門』ドーバー。ISBN 0-486-24775-9。
• Deo, Narsingh (1974)。グラフ理論と工学およびコンピュータサイエンスへの応用( PDF )。ニュージャージー州エングルウッド: Prentice-Hall。ISBN 0-13-363473-62019年5月17日時点のオリジナルよりアーカイブ（PDF）されました。
• ギボンズ、アラン（1985年）。アルゴリズムグラフ理論。ケンブリッジ大学出版局。
• ゴルビック、マーティン（1980）。アルゴリズムグラフ理論と完全グラフ。アカデミックプレス。
• ハラリー、フランク (1969)。グラフ理論。マサチューセッツ州レディング:アディソンウェスレー。
• Harary, Frank; Palmer, Edgar M. (1973)。Graphical Enumeration。ニューヨーク、ニューヨーク：Academic Press。
• Mahadev, NVR; Peled, Uri N. (1995).閾値グラフと関連トピック. North-Holland .
• ニューマン、マーク（2010）。ネットワーク：入門。オックスフォード大学出版局。
• ケプナー、ジェレミー、ギルバート、ジョン (2011)。線形代数の言語によるグラフアルゴリズム。フィラデルフィア、ペンシルバニア: SIAM。ISBN 978-0-898719-90-1。

• 「グラフ理論」、数学百科事典、EMS Press、2001 [1994]
• グラフ理論チュートリアル 2012-01-16 にWayback Machineでアーカイブされました
• 小さな連結グラフの検索可能なデータベース
• 画像ギャラリー: Wayback Machineのグラフ(2006 年 2 月 6 日アーカイブ)
• 研究者向けのグラフ理論リソースの簡潔な注釈付きリスト
• rocs — グラフ理論 IDE
• ルーターの社会生活 — 人間とコンピューターのグラフについて論じた非技術的な論文
• グラフ理論ソフトウェア — グラフ理論を教え、学ぶためのツール
• グラフ理論に関するオンライン書籍、図書館や他の図書館の図書館資料
• グラフアルゴリズムのリスト。2019-07-13にWayback Machineにアーカイブされ、グラフライブラリの実装への参照とリンクが含まれています。

• 組合せ最適化問題における相転移、第3章：グラフ入門（2006年）HartmannとWeigt著
• 有向グラフ: 理論、アルゴリズム、アプリケーション 2007 Jorgen Bang-Jensen および Gregory Gutin 著
• グラフ理論、ラインハルト・ディーステル著