数学
#15 ふれてみよう高校数学 離散数学・数論

グラフ理論の基本——頂点と辺が作る関係の数学

グラフとは

「電車の路線図を思い浮かべてください」——駅（点）と路線（線）で表された地図がグラフです。SNSの人間関係図、インターネットのルーター間の接続、道路網——これらすべてが「グラフ」という一つの数学的枠組みで表現できます。

グラフ（graph）とは、頂点（vertex / node）の集合 VV と、頂点の対を結ぶ辺（edge）の集合 EE からなる構造 G=(V,E)G = (V, E) のことです。

グラフは「関係」を表す最も汎用的な数学的構造です——「どの点とどの点がつながっているか」だけを抽象化したもの。

グラフの種類

「グラフにはいくつかの種類がある」——辺の性質や構造によって使い分けます：

種類説明
無向グラフ辺に向きがない（友達関係）
有向グラフ（ダイグラフ）辺に向きがある（フォロー関係）
重み付きグラフ辺に数値（距離・コスト）がある
単純グラフ多重辺・自己ループなし
完全グラフ KnK_n全頂点間に辺がある
二部グラフ頂点を2組に分け、辺は組をまたぐ
木閉路のない連結グラフ

基本概念

次数（degree）

「その頂点にいくつの辺がつながっているか」——頂点 vv の次数 deg⁡(v)\deg(v) は vv に接続する辺の数です。

握手補題：「全員で握手すると、握手された手の総数は握手の回数の2倍になる」——同じことが辺と次数にも言えます：

∑v∈Vdeg⁡(v)=2∣E∣\sum_{v \in V} \deg(v) = 2|E|

理由：各辺は 22 つの頂点の次数に 11 ずつ貢献するため——「1本の辺は両端の頂点にそれぞれ1を加える」。

系：次数が奇数の頂点の個数は必ず偶数——「握手する手の総数は必ず偶数なので、奇数回握手した人の数も必ず偶数」。

経路・道・閉路

  • 歩道（walk）：辺をたどる列（繰り返しあり）
  • 道（trail）：辺を繰り返さない歩道——「同じ道を2度通らない」
  • 路（path）：頂点も辺も繰り返さない歩道——「同じ場所を2度訪れない」
  • 閉路（cycle）：起点に戻る路——「出発点に戻ってくるルート」

深さ優先探索（DFS）アニメーション

グラフの深さ優先探索（DFS）アニメーション：頂点 A から始まり、できるだけ深く進んでから戻る探索を繰り返す。黄色が現在の頂点、緑が訪問済み、暗い色が未訪問。A→B→D（行き止まり）→E→A→C→F→G と進む様子を観察しよう。迷路を壁に沿って進むイメージ。 
var nodes, edges, visited, stack, dfsOrder, step, timer;

nodes = [
{ x: 300, y: 60,  label: 'A' },
{ x: 160, y: 160, label: 'B' },
{ x: 440, y: 160, label: 'C' },
{ x: 80,  y: 270, label: 'D' },
{ x: 240, y: 270, label: 'E' },
{ x: 360, y: 270, label: 'F' },
{ x: 520, y: 270, label: 'G' }
];

edges = [
[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,4],[5,6]
];

function buildAdj() {
var adj = [];
for (var i = 0; i < nodes.length; i++) adj.push([]);
for (var e = 0; e < edges.length; e++) {
  adj[edges[e][0]].push(edges[e][1]);
  adj[edges[e][1]].push(edges[e][0]);
}
return adj;
}

var adj = buildAdj();
visited = [];
dfsOrder = [];
timer = 0;
step = 0;

// precompute DFS order
function dfs(start) {
var stk = [start], vis = [];
for (var i = 0; i < nodes.length; i++) vis.push(false);
var order = [];
while (stk.length > 0) {
  var v = stk.pop();
  if (vis[v]) continue;
  vis[v] = true;
  order.push(v);
  var nbrs = adj[v].slice().reverse();
  for (var ni = 0; ni < nbrs.length; ni++) {
    if (!vis[nbrs[ni]]) stk.push(nbrs[ni]);
  }
}
return order;
}
dfsOrder = dfs(0);

function loop() {
ctx.clearRect(0, 0, W, H);
timer++;

if (timer % 40 === 0) {
  step = (step + 1) % (dfsOrder.length + 3);
  if (step === 0) { /* restart */ }
}

var currentVisited = step;
var visitedSet = {};
for (var vi = 0; vi < Math.min(currentVisited, dfsOrder.length); vi++) {
  visitedSet[dfsOrder[vi]] = vi + 1;
}

// draw edges
for (var ei = 0; ei < edges.length; ei++) {
  var u = edges[ei][0], v = edges[ei][1];
  var bothVisited = visitedSet[u] !== undefined && visitedSet[v] !== undefined;
  ctx.strokeStyle = bothVisited ? '#22c55e55' : '#334155';
  ctx.lineWidth = bothVisited ? 2.5 : 1.5;
  ctx.beginPath();
  ctx.moveTo(nodes[u].x, nodes[u].y);
  ctx.lineTo(nodes[v].x, nodes[v].y);
  ctx.stroke();
}

// draw nodes
for (var ni = 0; ni < nodes.length; ni++) {
  var nd = nodes[ni];
  var vOrder = visitedSet[ni];
  var isCurrent = (currentVisited <= dfsOrder.length && dfsOrder[currentVisited-1] === ni);

  if (isCurrent) {
    ctx.fillStyle = '#fbbf24';
  } else if (vOrder !== undefined) {
    var t2 = (vOrder - 1) / (nodes.length - 1);
    var r2 = Math.round(34 + t2 * 120);
    var g2 = Math.round(211 - t2 * 80);
    var b2 = Math.round(99 - t2 * 40);
    ctx.fillStyle = 'rgb(' + r2 + ',' + g2 + ',' + b2 + ')';
  } else {
    ctx.fillStyle = '#1e293b';
  }

  ctx.beginPath();
  ctx.arc(nd.x, nd.y, 22, 0, Math.PI * 2);
  ctx.fill();
  ctx.strokeStyle = vOrder !== undefined ? '#22c55e' : '#475569';
  ctx.lineWidth = 2;
  ctx.stroke();

  ctx.fillStyle = '#fff';
  ctx.font = 'bold 15px monospace';
  ctx.textAlign = 'center';
  ctx.fillText(nd.label, nd.x, nd.y + 5);

  if (vOrder !== undefined) {
    ctx.fillStyle = '#fbbf24';
    ctx.font = '10px monospace';
    ctx.fillText(vOrder, nd.x + 16, nd.y - 14);
  }
}

// legend
ctx.fillStyle = '#e2e8f0';
ctx.font = '13px monospace';
ctx.textAlign = 'left';
ctx.fillText('DFS 訪問順: ' + dfsOrder.slice(0, currentVisited).map(function(i){return nodes[i].label}).join(' → '), 14, 328);
ctx.fillStyle = '#fbbf24';
ctx.fillText('■ 現在', 14, 346);
ctx.fillStyle = '#22c55e';
ctx.fillText('■ 訪問済み', 80, 346);
ctx.fillStyle = '#475569';
ctx.fillText('■ 未訪問', 180, 346);

requestAnimationFrame(loop);
}
loop();

探索アルゴリズム

深さ優先探索（DFS）

「迷路を解くときに壁に沿って進む」——スタック（または再帰）を使って、できるだけ深く進んでから戻ります：

DFS(G, s):
  visited = {}
  stack = [s]
  while stack not empty:
    v = stack.pop()
    if v not in visited:
      visited.add(v)
      for each neighbor u of v:
        if u not in visited:
          stack.push(u)

計算量：O(V+E)O(V + E)——「全頂点と全辺を一度ずつ見るだけで済む」

幅優先探索（BFS）

「池に石を投げたときの波紋が広がるように」——キューを使って、近い頂点から順に探索します。最短路（辺の重みが等しい場合）を求められます。

計算量：O(V+E)O(V + E)

オイラー路とオイラー閉路

「すべての橋をちょうど一度ずつ渡って散歩できるか？」——18世紀のケーニヒスベルクという街には川に架かる7本の橋があり、これが「全部の橋を1度ずつ渡れるか」という問題を生みました。

オイラー路：グラフのすべての辺をちょうど一度ずつ通る道——「全ての橋を1度ずつ渡る散歩コース」。

定理（オイラー、1736年）：

  • オイラー閉路（出発点に戻る）が存在   ⟺  \iff 連結かつすべての頂点の次数が偶数——「全ての交差点で入った分だけ出られる」
  • オイラー路（起点・終点が異なる）が存在   ⟺  \iff 連結かつ奇数次数の頂点がちょうど2つ

有名な問題「ケーニヒスベルクの橋」（7本の橋をすべて一度ずつ渡れるか？）はオイラーが 1736 年に否定的に解き、グラフ理論の誕生とされます——「答えは NO。なぜなら奇数次数の頂点が4つあるから」。

ハミルトン路

「全ての都市を一度ずつ訪問する旅行ルートを求める」——これがハミルトン路問題です。

ハミルトン路：グラフのすべての頂点をちょうど一度ずつ通る路——「全ての都市を1度ずつ巡る旅程」。

オイラー路と似た問題に見えますが、ハミルトン路の判定は NP 完全問題（多項式時間アルゴリズムが知られていない）です——「解を確認するのは速いが、解を見つけるのは難しい」。

これが有名な「P ≠\neq NP？」問題（100万ドルの懸賞が掛かった難問）との繋がりを持ちます——「コンピュータで効率よく解けるか否かの境界線上にある問題」。

グラフ理論の応用

「グラフ理論は現代のデジタル技術の根幹にある」——毎日使うスマートフォンの地図アプリも、SNSも、グラフ理論で動いています：

応用グラフの意味
ナビゲーション交差点=頂点、道路=辺（重み付き）
SNSユーザー=頂点、繋がり=辺
コンパイラ依存関係グラフ（有向非循環グラフ、DAG）
スケジューリングタスク=頂点、制約=辺
インターネットルーター=頂点、リンク=辺
PageRankWebページのグラフを有向グラフで表現

隣接行列と隣接リスト

「グラフをコンピュータで扱うには、表現方法を選ぶ必要がある」：

隣接行列（Adjacency Matrix）

「大きな○×の表でつながりを表す」——n×nn \times n 行列 AA：Aij=1A_{ij} = 1（辺 (i,j)(i,j) が存在）、00（なし）

  • 辺の存在確認：O(1)O(1)——「表を見るだけで一発でわかる」
  • メモリ：O(n2)O(n^2)（疎なグラフには非効率）——「ほとんどが空欄の巨大な表が必要」

隣接リスト（Adjacency List）

「各頂点のお隣さんリストを持つ」——各頂点の隣接頂点リスト

  • メモリ：O(V+E)O(V + E)——「辺の数だけのメモリで済む」
  • 多くの実用的アルゴリズムはこちらを使用

シリーズのまとめ

このシリーズ「離散数学・数論」では以下を学びました：

回テーマ
1–3等差・等比数列、Σ公式
4–5漸化式、数学的帰納法
6–9約数、GCD、素数、合同式
10–13行列の演算・逆行列・固有値
14–15フィボナッチ・黄金比、グラフ理論

まとめ

  • グラフ G=(V,E)G = (V, E)：頂点と辺の抽象的な構造——「関係を点と線で表す」
  • 握手補題：∑deg⁡(v)=2∣E∣\sum \deg(v) = 2|E|——「辺の本数の2倍が次数の総和」
  • DFS・BFS：グラフ探索の基本アルゴリズム、O(V+E)O(V+E)——「全頂点を効率よく訪問できる」
  • オイラー路：全辺を通る道（次数の偶奇で判定）——「全ての橋を1度ずつ渡れるか」
  • ハミルトン路：全頂点を通る道（NP完全）——「全都市を1度ずつ巡れるか」
  • グラフはネットワーク・AI・コンパイラ・SNS に広く応用——「関係性を扱うあらゆる場面で活躍」

離散数学・数論は「コンピュータ科学の言語」です。整数・素数・行列・グラフ——これらは現代のすべてのデジタル技術の根底にあります。