1 定義と基本概念
グラフは、対象同士の関係を点と線で表す数学的構造である。点は要素そのものを、線はそれらの間の結びつきを示し、離散的な配置や接続を扱う際の基本模型となる。頂点の集まりと辺の集合から構成され、抽象的な関係図としても、実世界のネットワークの表現としても用いられる。
1.1 頂点と辺
頂点は、グラフにおける個々の対象を表す。辺は、二つの頂点の間にある関係や接続を示す要素である。頂点は点として、辺は線として図示されることが多く、視覚的に構造を捉えやすい。
1.2 隣接と次数
二つの頂点が辺で結ばれているとき、それらは隣接しているという。ある頂点に接続する辺の本数は次数と呼ばれ、グラフの局所的な構造を測る基本量となる。次数は、頂点がどれほど多くの関係を持つかを示す指標でもある。
1.2.1 入次数と出次数
有向グラフでは、辺に向きがあるため、ある頂点へ流れ込む辺の数を入次数、そこから出ていく辺の数を出次数という。これらは、情報の流れや依存関係を分析する際に重要である。
1.2.2 自己ループと多重辺
自己ループは、1つの頂点が自分自身へ結ばれる辺である。多重辺は、同じ2頂点の間に複数の辺が存在する状態を指す。これらを許すかどうかで、グラフの分類や定理の適用範囲が変わる。
1.3 グラフの表現
グラフは、図として描くだけでなく、計算機上で扱いやすい形式に変換して表す。代表的な表現法には、隣接行列と隣接リストがある。用途や頂点数、辺の密度に応じて適切な方法が選ばれる。
1.3.1 隣接行列
隣接行列は、頂点の組ごとに辺の有無を行列で記録する表現である。ある位置の値が、2頂点が結ばれているかどうかを示す。実装が単純で、関係の判定が速い一方、頂点数が多いと記憶領域を多く使う。
1.3.2 隣接リスト
隣接リストは、各頂点に対して接続先の頂点を一覧で保持する方式である。辺が少ないグラフでは扱いやすく、空間効率がよい。探索や近傍確認を繰り返す場面で広く利用される。
2 グラフの種類
グラフには、辺の向きや重みの有無、頂点の分割の仕方などによって多くの型がある。分類を理解すると、理論の整理だけでなく、問題に適したモデル化もしやすくなる。
2.1 無向グラフと有向グラフ
無向グラフでは、辺に向きがなく、関係は対称的である。有向グラフでは、辺に方向が与えられ、片方向の関係を表現できる。前者は相互接続、後者は流れや順序を表す場面に向く。
2.1.1 単純グラフ
単純グラフは、自己ループも多重辺も持たない無向グラフである。最も基本的な形式であり、理論展開の出発点として頻繁に用いられる。
2.1.2 多重グラフ
多重グラフは、同じ2頂点間に複数の辺を許すグラフである。路線の重複や複数の関係を表すのに便利で、単純な結合だけでは表せない構造を記述できる。
2.2 重み付きグラフ
重み付きグラフでは、各辺に数値の重みが付与される。距離、費用、時間、容量などを表せるため、最適化問題と相性がよい。経路選択や資源配分で特に重要となる。
2.3 完全グラフと空グラフ
完全グラフは、任意の異なる2頂点が必ず辺で結ばれているグラフである。対照的に空グラフは、辺をまったく持たない。両者は、接続の極端な例として位置づけられる。
2.4 二部グラフ
二部グラフは、頂点集合を2 समूहに分け、辺が異なる集合間にのみ存在するグラフである。2種類の対象の対応付けを表しやすく、割当やマッチングの問題でよく現れる。
2.4.1 完全二部グラフ
完全二部グラフでは、片方の集合の各頂点が、もう一方の集合のすべての頂点と結ばれる。分割の規模を明示しやすく、組合せ的な性質を調べる際の典型例となる。
3 グラフの基本性質
グラフの本質は、どの頂点がどのようにつながっているかにある。連結性、閉路、距離などは、構造の全体像を理解するための中心的な観点である。
3.1 連結性
連結性は、任意の2頂点の間に経路が存在するかどうかを示す。連結なグラフでは、構成要素が一つのまとまりとしてつながっている。到達可能性の有無を判定する際の基本概念でもある。
3.1.1 連結成分
連結成分は、互いに経路で結ばれる頂点の最大部分集合である。グラフが複数のまとまりに分かれているとき、その分割を理解する手がかりになる。
3.1.2 強連結性
有向グラフにおける強連結性は、任意の2頂点について、両方向に到達可能である状態を指す。双方向の往来が保証されるため、循環的な構造や相互依存の分析に関係する。
3.2 閉路と木
閉路は、始点と終点が一致する経路である。これに対して木は、閉路を含まない連結グラフである。両者は、グラフ構造を特徴づける対照的な要素として扱われる。
3.2.1 木
木は、任意の2頂点の間にただ1本の経路がある連結グラフである。階層構造や分岐構造を表現しやすく、データ構造や探索アルゴリズムでも重要である。
3.2.2 森
森は、閉路を含まないグラフであり、複数の木の集まりとみなせる。連結である必要はなく、独立した部分構造が並ぶ状況を表す。
3.3 距離と経路
経路は、頂点を辺に沿って順にたどる列である。距離は、2頂点間の最短の経路長として定義されることが多い。これらは、到達のしやすさや移動コストを測る尺度となる。
3.3.1 最短経路
最短経路は、2頂点間を結ぶ経路のうち、重みや辺数が最小のものを指す。通信や移動の効率化に直結し、アルゴリズム研究の重要な対象である。
3.3.2 周回路
周回路は、同じ頂点で始まり同じ頂点で終わる閉じた経路である。繰り返しを含む回り道の有無を調べる際に用いられ、構造の複雑さを示す指標にもなる。
4 グラフ理論の主要概念
グラフ理論では、頂点の配置や接続だけでなく、色分け、平面上での描画、各種の数値的特徴も扱う。これらの概念は、問題の難しさや構造の制約を明らかにする。
4.1 彩色
彩色は、条件を満たすように頂点や辺へ色を割り当てる手法である。隣接要素が同じ色にならないようにするなど、制約充足の問題として研究される。
4.1.1 頂点彩色
頂点彩色では、隣接する頂点が異なる色になるように塗り分ける。必要な色の最小数は、グラフの構造の複雑さを反映する。
4.1.2 辺彩色
辺彩色は、隣接する辺どうしが同色にならないように色を付ける方法である。資源の衝突回避や時間割の割当などに対応づけられる。
4.2 平面グラフ
平面グラフは、辺の交差を避けて平面上に描けるグラフである。図としての見やすさだけでなく、理論的にも特別な性質を持つ。地図の分割や回路の配置にも関係する。
4.2.1 クラトフスキーの定理
クラトフスキーの定理は、あるグラフが平面的であるかどうかを判定するための代表的な結果である。特定の非平面構造を含むかどうかが基準となる。
4.2.2 オイラーの公式
オイラーの公式は、連結な平面グラフにおいて、頂点数、辺数、面数の間に成り立つ関係式である。平面グラフの構造を数え上げるうえで基本となる。
4.3 グラフ不変量
グラフ不変量は、同型変換をしても変わらない量で、グラフの性質を比較する指標になる。数として表せるものが多く、分類や評価に役立つ。
4.3.1 オイラー数
オイラー数は、グラフやその埋め込みに関連して定義される不変量である。特に平面構造では、頂点・辺・面の関係を要約する量として現れる。
4.3.2 彩色数
彩色数は、条件を満たして頂点を塗り分けるのに必要な最小色数である。彩色問題の難しさを示す代表的な値として用いられる。
4.3.3 最大次数
最大次数は、グラフ中で最も次数の大きい頂点の次数である。全体の密度や局所的な集中度を把握するための簡明な指標である。
5 代表的なアルゴリズム
グラフに対する処理では、探索、最短経路、全域木の構成などが基本課題となる。これらのアルゴリズムは、構造解析と実用計算の双方で重要である。
5.1 幅優先探索
幅優先探索は、始点から近い頂点を順に広げながら調べる方法である。距離の短い層から探索するため、最短辺数を求める際にも利用される。
5.2 深さ優先探索
深さ優先探索は、可能な限り一方向へ進み、行き止まりで戻りながら全体を調べる探索法である。閉路検出や連結性の確認、順序付けに有効である。
5.3 最短経路アルゴリズム
最短経路アルゴリズムは、重み付きグラフで2頂点間の最小コスト経路を求める手法群である。交通案内、通信路選択、資源節約など幅広い用途を持つ。
5.3.1 ダイクストラ法
ダイクストラ法は、負の重みを持たないグラフで最短経路を効率よく求める代表的手法である。始点からの距離を段階的に確定していく。
5.3.2 ベルマン・フォード法
ベルマン・フォード法は、負の重みがある場合にも適用できる最短経路法である。負閉路の検出にも利用され、より広い範囲の問題に対応する。
5.4 最小全域木
最小全域木は、すべての頂点を結びつつ、総重みが最小となる木である。配線や連結のコスト削減に関わる、重要な最適化対象である。
5.4.1 クラスカル法
クラスカル法は、重みの小さい辺から順に選び、閉路を作らないようにして全域木を構成する方法である。辺中心の手続きとして知られる。
5.4.2 プリム法
プリム法は、ある頂点から始めて、木に隣接する辺の中から最小重みのものを追加していく方法である。連続的に範囲を広げる構成法である。
6 応用
グラフ理論は純粋数学にとどまらず、複雑な関係を持つ実際の問題を記述するための共通言語として機能する。特に、ネットワーク化された対象の分析に強みを持つ。
6.1 計算機科学
計算機科学では、グラフは構造の表現と処理の基盤として広く使われる。データの結合、依存関係、経路探索など、多様な場面で現れる。
6.1.1 データ構造
グラフは、木やネットワーク型のデータ構造の理論的背景となる。ファイル関係、状態遷移、知識表現などの整理に役立つ。
6.1.2 ネットワーク設計
ネットワーク設計では、接続の配置や通信経路をグラフとして考える。効率、冗長性、コストのバランスを評価する際に有用である。
6.2 社会ネットワーク分析
社会ネットワーク分析では、人や組織の関係をグラフとして扱う。つながりの密度、中心性、コミュニティの構造などを調べることで、関係の全体像を捉えやすくなる。
6.3 化学における分子構造
化学では、分子を頂点と辺からなる図式で表すことがある。原子を頂点、結合を辺に対応させることで、構造異性や反応性の検討に利用される。
6.4 交通と物流
交通や物流では、都市や拠点を頂点、道路や輸送経路を辺としてモデル化する。最短経路や最小コストの考え方が、ルート計画や配送の最適化に直結する。
6.5 組合せ最適化
組合せ最適化では、グラフ上の選択問題が多く現れる。被覆、マッチング、彩色、巡回などの課題は、離散的な候補の中から最良の構成を探す枠組みとして重要である。