SNSの友達関係、Webページのリンク構造、タンパク質の相互作用、分子の構造。これらに共通するのは「点と線」の関係である。グラフ理論は、この関係性を数学的に扱う道具。現実世界の複雑なネットワークを、シンプルな構造で表現する。
グラフ 頂点 辺 有向グラフ 無向グラフ
グラフとは
グラフ（Graph）
G = (V, E)
V: 頂点（vertex/node）の集合
E: 辺（edge）の集合
頂点と頂点を辺で結んだ構造。
グラフの種類
| 種類 | 特徴 | 例 |
|---|---|---|
| 無向グラフ | 辺に方向がない | 友達関係、道路 |
| 有向グラフ | 辺に方向がある | フォロー関係、リンク |
| 重み付きグラフ | 辺に重み（コスト）がある | 距離、類似度 |
| 二部グラフ | 2グループ間の接続のみ | ユーザーと商品 |
基本用語
| 用語 | 意味 |
|---|---|
| 次数（degree） | 頂点に接続する辺の数 |
| パス（path） | 頂点の連続（同じ頂点を通らない） |
| サイクル（cycle） | 始点と終点が同じパス |
| 連結（connected） | 任意の2頂点間にパスがある |
| 木（tree） | サイクルのない連結グラフ |
グラフの表現
グラフをコンピュータで扱うには、データ構造として表現する必要がある。
| 表現 | 構造 | 特徴 |
|---|---|---|
| 隣接リスト | 各頂点の隣接頂点のリスト | 疎なグラフに効率的 |
| 隣接行列 | n×n行列、接続を0/1で表現 | 密なグラフ、行列演算が可能 |
| 辺リスト | 辺（始点、終点）のリスト | シンプル、辺の追加が容易 |
実務での応用
WEB開発での応用
ルーティング：URLとコントローラのマッピングは有向グラフ。
依存関係：パッケージの依存関係はDAG（有向非巡回グラフ）。
DBスキーマ：テーブル間の関係をER図（グラフ）で表現。
SNS：フォロー/フォロワー関係のモデリング。
AI/MLでの応用
知識グラフ：エンティティと関係をグラフで表現。
GNN：グラフ構造を入力とするニューラルネットワーク。
分子設計：原子を頂点、結合を辺とした分子グラフ。
推薦システム：ユーザー-アイテムの二部グラフ。
深掘りリンク
- Wikipedia: グラフ理論
- 書籍：「グラフ理論入門」R.J.ウィルソン
- 次のステップ：隣接行列、グラフアルゴリズム