グラフ理論の教科書を開くと，いきなり「$G=(V,E)$とする」と書いてあります．しかし，なぜこの抽象化が有用なのでしょうか？ この記事では，グラフという概念が「関係の可視化」として驚くほど広い範囲の問題を統一的に扱えることを見ていきます．

1 すべてはケーニヒスベルクの橋から始まった

1736年，数学者オイラーはケーニヒスベルク（現在のカリーニングラード）の7つの橋を，すべてちょうど1度ずつ渡って元に戻れるか？ という問題を考えました．

オイラーの天才的な洞察は，島や陸地の形は関係ないということでした．重要なのは「どの陸地がどの橋でつながっているか」という接続関係だけです．

このように，「もの」を点（頂点）で，「つながり」を線（辺）で表したものがグラフです．

2 どこにでもグラフがある

グラフの威力は，驚くほど多様な現象が同じ抽象構造に帰着するところにあります．

graph TD
    subgraph "SNS（無向グラフ）"
        U1["Alice"] --- U2["Bob"]
        U2 --- U3["Carol"]
        U1 --- U3
    end
    subgraph "依存関係（有向グラフ）"
        P1["React"] --> P2["react-dom"]
        P1 --> P3["scheduler"]
        P2 --> P3
    end

    style U1 fill:#f5f5f5,stroke:#333,color:#000
    style U2 fill:#f5f5f5,stroke:#333,color:#000
    style U3 fill:#f5f5f5,stroke:#333,color:#000
    style P1 fill:#f5f5f5,stroke:#333,color:#000
    style P2 fill:#f5f5f5,stroke:#333,color:#000
    style P3 fill:#f5f5f5,stroke:#333,color:#000

3 グラフの形式的定義 ― 直感を数学にする

上の例を統一的に扱うために，形式的な定義を与えましょう．

ここで大事なポイントがあります．無向グラフの辺$\{u,v\}$は集合なので$\{u,v\}=\{v,u\}$ですが，有向グラフの弧$(u,v)$は順序対なので$(u,v)\ne (v,u)$です．友人関係は対称的（無向），依存関係は非対称的（有向）ということが，数学的に正確に表現されています．

4 なぜこの抽象化が強力なのか

5 基本的な用語 ― 共通言語を手に入れる

グラフ理論の記事を読む上で必要な基本用語を整理しておきます．

これは「各辺は2つの端点の次数にそれぞれ1ずつ寄与する」という単純な観察から従います．しかし単純な割に強力で，「次数が奇数の頂点は偶数個ある」などの結果がすぐに出ます．

6 まとめ ― グラフは「考え方のOS」

グラフは単なる点と線の絵ではありません．それは関係を抽象化するための共通言語です．ケーニヒスベルクの橋も，SNS の友人ネットワークも，コンパイラの依存解決も，すべて同じ数学的枠組みで扱えるという事実は，グラフ理論が離散数学の中心に位置する理由をよく説明しています．

次の記事では，このグラフの上をどう「歩く」かを考えます．BFS がなぜ最短路を見つけるのか，その背後にある美しい直感を解説します．