1 無向グラフの基本

無向グラフは、頂点と辺の組により対象の関係構造を表す離散数学の基礎概念である。辺は向きを持たないため、ある頂点同士が結ばれていることは相互的な関連として扱われる。頂点は要素（人、装置、状態など）を、辺はそれらの結びつき（通信、関係、可能な遷移など）を表し、組合せ構造を通じてネットワークの解析に用いられる。

1.1 定義と表記

無向グラフは一般に \(G=(V,E)\) の形で表される。ここで \(V\) は頂点集合、\(E\) は辺集合であり、各辺は頂点の2要素からなる集合として与えられるのが基本である。

1.1.1 頂点集合と辺集合

頂点集合 \(V\) は離散的な要素の集まりである。辺集合 \(E\) は \(V\) の2頂点の組を要素として含む。典型的には \(E\subseteq \{\{u,v\}\mid u,v\in V, u\neq v\}\) のように書けるが、後述するようにループや多重辺を許す拡張では定義が変わる。

1.1.2 単純グラフ・多重辺・ループ

単純グラフは、同じ2頂点間に同種の辺が複数存在しないこと（多重辺なし）と、頂点と同じ頂点を結ぶ辺が存在しないこと（ループなし）を満たす。 多重辺を許す場合、同一の頂点対に対して複数の辺が存在しうる。ループを許す場合、頂点 \(v\) 自身を結ぶ辺が含まれ、構造的・計数的な性質に影響が出る。多くの理論では単純グラフを基礎として、必要に応じて拡張が導入される。

1.2 各種表現

無向グラフは計算機上の扱いやすさに応じて異なる形式で表現される。代表例として隣接リスト、隣接行列、辺リストがある。表現の選択は、探索の効率やメモリ使用量、アルゴリズムの実装方針に影響する。

1.2.1 隣接リスト

隣接リストは、各頂点ごとに「そこから出る（結ばれる）相手頂点の集合」を列として保持する方法である。無向グラフでは、\(u\) が \(v\) と辺で結ばれていれば、\(u\) のリストにも \(v\) が載り、\(v\) 側にも \(u\) が載る。疎なグラフで特に効率が良く、合計メモリはおおむね辺数に比例する。

1.2.2 隣接行列

隣接行列は、頂点数を \(n=V\) として \(n\times n\) の行列で表す。行列要素は、対応する頂点対が辺で結ばれているかどうかを0/1（あるいは重みを持つなら実数）で記録する。判定が定数時間でできる一方、メモリは \(O(n^2)\) を要し、密な場合に適する。

1.2.3 辺リスト表現

辺リストは、辺を列として保持する表現である。各要素は結ばれる2頂点の対として格納される。実装が簡潔である反面、特定頂点の近傍を列挙するには走査が必要になりがちで、探索処理では追加の工夫が要ることがある。

1.3 次数と次数列

次数は、頂点がどれほど多くの他頂点と結びついているかを表す量である。グラフの局所的な構造を反映し、連結性や彩色可能性など多くの性質と結びつく。

1.3.1 頂点の次数

単純無向グラフでは、頂点 \(v\) の次数 \(\deg(v)\) は \(v\) に接する辺の本数として定義される。隣接リストで数えればそのリストの長さに一致する。多重辺がある場合は同一の相手との複数の辺を別々に数える。ループは定義規約により次数への寄与が変わりうるため、扱うクラスでの定義を明確にする必要がある。

1.3.2 手数の等式（次数の総和）

無向グラフでは、全頂点の次数の総和は、辺数の2倍に等しい。これは各辺が2つの端点に対して1ずつ寄与するためである。形式的には \[

\sum_{v\in V}\deg(v)=2E

\] が成り立つ。単純性や多重辺の有無に応じて解釈の注意は要るが、一般的な辺の端点数の数え上げにより同様の関係が得られる。

2 グラフ理論の中心概念

グラフ理論では、連結性、距離、経路、閉路、木構造など、基本的な概念を通じてグラフの形を理解する。これらの概念は、アルゴリズム設計や最適化問題の定式化にも直結する。

2.1 連結性と成分

連結性は、頂点同士が辺に沿って到達可能かどうかを表す。到達不能な部分は成分として分解でき、解析を局所化する助けになる。

2.1.1 連結グラフ

連結グラフとは、任意の2頂点の間に辺をたどることで到達できるものを指す。到達の意味は、経路の存在として形式化される。連結性が崩れると、グラフは複数の独立した塊に分かれ、全体の振る舞いはそれらの和として理解しやすくなる。

2.1.1.1 連結成分とその性質

連結成分は、連結性の観点で同値関係を作ったときの同値類に相当する。各成分は連結であり、異なる成分の間には辺が存在しない。次数や閉路の有無など多くの性質は、成分ごとに観察できるため、計算量の削減につながることがある。

2.1.2 距離と連結性の関係

距離は、2頂点間の経路の最小の長さ（通常は通過する辺の本数）として定義される。無向グラフにおいて、距離が有限であることと、その2頂点が同一連結成分に属することは同値である。したがって、距離の計算は到達可能性の情報を含む。

2.2 経路・閉路・木

経路は到達の方法を記述し、閉路は循環構造を表す。木は制約の強い構造であり、探索や最適化で中心的な役割を持つ。

2.2.1 経路と単純経路

経路は、頂点の列であって連続する頂点対が辺で結ばれているものとして定義される。単純経路は頂点の重複がない経路を指す。重複が許されると同じ部分を何度も行き来する状況が生まれ、長さや特徴づけに違いが出るため、目的に応じて使い分けられる。

2.2.2 閉路とその分類

閉路は、始点と終点が一致し、経路として辿れる辺の並びを持つ構造である。分類では、頂点や辺の重複を許すか、最短性を要求するかなどで区別する。単純閉路は頂点を繰り返さない閉路であり、循環の最小単位として扱われる場面が多い。閉路の存在は木構造との違いを明確にする指標になる。

2.2.3 木と森林

木は連結で閉路を持たない無向グラフとして特徴づけられる。閉路がないことにより、任意の2頂点の間に経路が一意に定まりやすい。森林は木の非交和（連結成分がすべて木）として理解できる。これらの構造は、縮約や探索の枠組みで繰り返し現れ、最小全域木の基礎にもなる。

2.3 部分グラフと誘導部分グラフ

部分グラフは元のグラフから頂点や辺を選び出して得られる構造である。誘導部分グラフは選択の規則が厳密で、近傍関係が保存されるため性質の比較に適する。

2.3.1 部分グラフの概念

部分グラフは、頂点集合の部分集合と、それに対応して選ばれる辺集合から構成される。つまり、元の辺から一部を取り除き、残す辺が選んだ頂点同士を結んでいることが条件となる。辺を任意に削れるため、性質は必ずしも元と同じにならない。

2.3.2 誘導部分グラフと保存される性質

誘導部分グラフは、頂点集合を部分集合 \(U\subseteq V\) に制限したとき、元のグラフで \(U\) 内の頂点どうしを結んでいた辺をすべて保持して得るものをいう。したがって、誘導部分グラフでは「頂点対の隣接関係」がそのまま反映される。結果として、隣接を基準に定義される性質（閉路の存在など）が保持される場合が多く、検証しやすい。

3 特殊な無向グラフのクラス

特定の条件を満たす無向グラフは、性質が体系化されており、理論やアルゴリズムで頻繁に登場する。ここでは完全グラフ、二部グラフ、正則グラフ、平面グラフを扱う。

3.1 完全グラフと二部グラフ

完全グラフと二部グラフは、最も基本的な分類の一つとして理解されることが多い。どちらも近傍構造が明確であり、彩色や極大性の議論に向く。

3.1.1 完全グラフの特徴づけ

完全グラフとは、異なる2頂点間にすべての辺が存在するグラフである。頂点数を \(n\) とすると辺数は \(\binom{n}{2}\) となり、各頂点の次数は \(n-1\) で一定になる。彩色の観点では、互いに隣接する頂点同士が多いため、必要色数が頂点数に対応しやすい。

3.1.2 二部グラフとその分類

二部グラフは、頂点集合を2つの部分集合に分け、それぞれの部分集合の内部には辺を持たず、異なる部分集合間のみで辺が張られるグラフである。分割の一部が空でないことを前提に語られる場合もある。二部性は閉路の長さ（奇数閉路の有無）と結びついて判定されることがあり、構造解析の起点として利用される。

3.2 正則グラフ

正則グラフは、各頂点の次数が同一であるという対称性を持つ。次数の均一性があるため、平均的な振る舞いが読み取りやすく、理論的にも計算機実験的にも扱われる。

3.2.1 k正則グラフ

\(k\) 正則グラフとは、すべての頂点の次数が \(k\) である無向グラフのことである。辺数は \(E=\frac{kV}{2}\) に従うため、頂点数と次数が整合する必要がある。次数が大きいほど局所的に接続が密になり、探索やスペクトル的性質の議論でも重要になる。

3.2.2 疑似乱数的性質との関係

ある種の正則グラフは、統計的にランダムに近い振る舞いを示すことがある。例えば頂点間の結合の偏りが小さい、特定の部分構造の出現頻度がランダムモデルの近くにある、などが観測される場合がある。こうした性質は「疑似乱数」的と呼ばれ、通信網や拡張性の議論、テスト用構造の生成などで参照される。

3.3 平面グラフと外周

平面グラフは、辺が交差しないように平面上へ描けるグラフである。外周（フェース）を含む概念は、地理的配置という直感と結びつき、理論を幾何的に扱う道を開く。

3.3.1 平面性の基本

平面グラフは、頂点を点として、辺を曲線として描いたときに、辺同士が交差しない配置が存在するグラフである。ここで「交差しない」は、交点が新しい頂点として扱われないことを意味する。平面性の判定は一般に容易ではないが、構造制約を与える基本的な概念として重要である。

3.3.2 外周と面の概念

平面上の埋め込み（描画）では、辺によって平面が領域に分割される。これらの領域を外周（面）と呼ぶ。有限領域の集合だけでなく、外側の無限領域も外周として扱う流儀がある。外周数と頂点数・辺数の間には関係式が成り立ち、平面性の性質を数え上げで検討する際に用いられる。

4 無向グラフの解析とアルゴリズム

探索、最短経路、木構造の構成、彩色、性質判定といったタスクは、無向グラフを対象に標準的なアルゴリズムが整備されている。以下では代表的手法の考え方と計算量の目安を整理する。

4.1 探索アルゴリズム

探索は到達可能な頂点を系統的に調べる基礎操作である。無向グラフでは、連結成分の抽出や距離の計算の前処理としても用いられる。

4.1.1 幅優先探索（BFS）

幅優先探索は、始点からの距離が小さい頂点から順に訪問する手続きである。キュー（待ち行列）を用いて、現在の層で処理すべき頂点を保持し、次の層へと進む。グラフが無重みである場合、BFSは最短距離に基づく探索順序を実現するため、到達の早期発見や距離計算に向く。

4.1.2 深さ優先探索（DFS）

深さ優先探索は、分岐先へできる限り深く進んでから戻る手続きである。再帰またはスタックを用いて実装されることが多い。DFSは到達可能性の列挙に加えて、探索木の構築や、後続で扱う閉路検出などの枠組みへ自然につながる特徴がある。

4.2 最短経路と距離計算

最短経路問題は、頂点間を結ぶ経路の中で最小の長さを求める課題として現れる。無向・無重みではBFSが基盤となり、重み付き拡張では別手法が使われる。

4.2.1 BFSによる最短距離

辺がすべて同一コスト（無重み）であるとき、BFSは始点から各頂点までの最短距離を同時に求めることができる。探索の層構造が、距離の増加と一致するためである。さらに、前駆情報を保持すれば、実際の経路を復元することも可能になる。

4.2.2 アルゴリズムの計算量

隣接リスト表現でのBFSは、各頂点を高々1回訪問し、辺を高々1度（無向では対称に見て2度）調べるため、時間計算量はおおむね \(O(V+E)\) となる。隣接行列では、各頂点から全候補を走査する必要があり、探索のコストが \(O(V^2)\) に近づくことがある。

4.3 木構造の処理

木構造は閉路を持たないため、最適化でも探索でも扱いやすい。最小全域木は、重み付き無向グラフで全頂点をつなぐ最安の部分構造を得る目的で導入される。

4.3.1 最小全域木（MST）

最小全域木（MST）は、連結な重み付き無向グラフに対し、すべての頂点を含み、辺数が \(V-1\) で連結かつ閉路を持たない部分グラフで、総重みを最小化するものを指す。存在は連結性に依存する。MSTは配線や路網設計などのモデル化で頻用され、木としての単純さが運用上の利点になることがある。

4.3.2 クラスカル法とプリム法

クラスカル法は、辺を重みの小さい順に選び、閉路ができる場合は採用しないという貪欲法である。採否の判断には連結性（同一成分かどうか）を効率よく判定する仕組みが必要で、典型的には集合管理を用いる。プリム法は、ある起点から始め、現在の集合から外へ伸ばす最小重みの辺を順に追加する。どちらもMSTを構成することが証明されており、グラフの性質や実装要件に応じて選択される。

4.4 彩色と独立集合

彩色は、隣接する頂点同士が同じ色を持たないように割り当てる問題である。独立集合は、互いに隣接しない頂点の集合として定義され、彩色と深い関係を持つ。

4.4.1 グラフ彩色問題

グラフ彩色問題は、最小の色数（クロマティック数）を求める、または特定の色数で塗れるかを判定する課題として定式化される。一般問題は計算困難である一方、二部グラフなど特定クラスでは容易に解ける場合がある。彩色は時間割、周波数割当、資源衝突の回避などの応用に結びつく。

4.4.2 独立集合とクリークの関係

独立集合は、集合内の任意の2頂点が辺で結ばれていない集合である。これに対しクリークは、集合内の任意の2頂点が互いに隣接している集合である。補グラフを考えると、独立集合とクリークは役割が入れ替わる関係にあり、両者は同種の最適化として見通せることがある。彩色は「色ごとに独立集合として頂点を分割する」形で捉えると理解が進む。

4.5 性質の判定

性質の判定では、特定の構造（例えば二部性、閉路、カット）の有無を効率よく調べる。これらは設計上の制約検証としても利用される。

4.5.1 二部性判定

二部性判定は、頂点を2集合に分け、各辺が異なる集合間にだけ現れるようにできるかを確認する問題である。無向グラフでは、探索木に基づく頂点の割り当て（層や色分け）で判定できる。奇数長の閉路が存在する場合には二部性が成立しないため、閉路検出と併せて理解されることが多い。

4.5.2 閉路・カットの検出

閉路検出は、経路により同じ頂点へ戻る循環構造の存在を確認する課題である。DFSの探索辺や訪問状態を用いると効率的に調べられる。カット（切断）は、少数の辺や頂点を取り除くことで連結性がどれだけ分解されるかを表す概念であり、最小カットや橋（bridge）などへ拡張される。これらの検出は、冗長性の評価やボトルネック抽出の基礎になる。