AI HL Graph Theory & Voronoi 完全攻略

現サイトの公開情報・公開用データを2026年9月19日に照合した資料です。出典の条件を独立に保証するものではありません。入試・学費・資格・評価方法は、出願・科目選択の前に公式情報でご確認ください。

ホーム›ブログ›IB Math AI HL Graph Theory & Voronoi 完全攻略

IB Math AI HL Graph Theory / 2026 年版

IB Math AI HL Graph Theory & Voronoi Diagrams
完全攻略 2026

ネットワーク・最短経路・最小全域木・Voronoi 図の全範囲

マレーシア IB 校（MKIS / GIS / ISKL / Sayfol / Cempaka 等）に通う AI HL Math の DP 1-2 生徒と保護者のための完全ガイド。AI HL Graph Theory（ネットワーク理論）は Computer Science / Urban Planning / Logistics / Data Science 系の大学進学に直結する分野で、現実世界の問題（KL の MRT ネットワーク、宅配最適経路、wifi 基地局配置、店舗立地分析）にそのまま応用できる『実用数学』の代表格です。本記事では Graph の基本用語（Vertex / Edge / Walk / Path / Trail / Cycle）、有向 / 無向 / 重み付きグラフ、隣接行列、Eulerian / Hamiltonian Path・Circuit（Königsberg の橋問題、TSP）、Dijkstra による最短経路、Prim / Kruskal による最小全域木（MST）、Voronoi Diagrams（境界線・最近傍法・最適配置）まで完全網羅し、Paper 1 / Paper 2 / Paper 3 別の出題傾向と 30 日演習プランを掲載します。

Table of Contents

【目次】

AI HL Graph Theory シラバス全体像
グラフの基本概念（有向 / 無向、重み付き、隣接行列）
Eulerian Path / Circuit（Königsberg の橋問題）
Hamiltonian Path / Circuit（TSP の概念）
最短経路（Dijkstra）の手計算手順
最小全域木（MST）— Prim's / Kruskal's algorithm
Voronoi Diagrams（境界線・最近傍法・応用）
30 日過去問演習プラン

Conclusion First

【結論先出し】

Graph Theory は「現実の最適化問題を数学で解く」分野です。

Grade 7 を狙うなら、次の 5 領域を 30 日で固めます。

① Graph 基本用語の正確な定義
② Eulerian / Hamiltonian の判定条件
③ Dijkstra（最短経路）の table 計算
④ Prim / Kruskal による最小全域木
⑤ Voronoi 図の境界線作成と最近傍法

Paper 1 は定義問題と手計算（Dijkstra・MST・Voronoi）。Paper 2 は隣接行列の演算と Voronoi 境界線の方程式。Paper 3 は Graph 単独問題（巡回セールスマン・Chinese Postman・Voronoi 応用）が出ます。

AI HL Graph Theory Syllabus Overview

【① AI HL Graph Theory シラバス全体像】

AI HL の Graph Theory は 「Graph 基本用語 / Eulerian / Hamiltonian / 最短経路 / MST / Voronoi」の 6 領域で構成されます。SL では Voronoi の基本のみ、HL では Eulerian / Hamiltonian / Dijkstra / MST が追加範囲。

① Graph 基本用語

Vertex / Edge / Walk / Path / Trail / Cycle

グラフ理論の語彙体系。Walk⊃Trail⊃Path の包含関係、次数（degree）と Handshaking Lemma、有向 / 無向 / 重み付きの分類、隣接行列・隣接リストでの表現を理解する。

② Eulerian Path / Circuit（HL only）

全辺を 1 度ずつ通る経路

Königsberg の橋問題が起源。判定条件は『全頂点の次数が偶数（Circuit）』『奇数次数の頂点が 2 個（Path）』。HL only の追加範囲で、Paper 1 / 3 で頻出。

③ Hamiltonian Path / Circuit（HL only）

全頂点を 1 度ずつ通る経路 / TSP

簡単な判定条件なし（NP 困難）。Travelling Salesman Problem（TSP）の基礎概念。Paper 3 で Nearest Neighbour Algorithm による近似解の手順を踏ませる問題が頻出。

④ Dijkstra による最短経路（HL only）

負の重みなし、table 形式の手計算

重み付きグラフの最短経路アルゴリズム。table 形式で『各頂点の現在距離、前頂点、確定状態』を反復更新。Paper 1 / 2 で手計算問題が頻出、5-7 頂点規模が標準。

⑤ 最小全域木（MST、HL only）

Prim's / Kruskal's algorithm

全頂点を結ぶ最小重みの木。Prim は頂点ベース貪欲法（1 頂点から成長）、Kruskal は辺ベース貪欲法（重み昇順 + 閉路チェック）。どちらでも結果の総重みは同じ。

⑥ Voronoi Diagrams（SL + HL）

境界線・最近傍法・最適配置

平面上のサイト集合から『各点が最も近いサイトの領域』に分割。境界線は隣接サイト間の垂直二等分線。最近傍法・移動店舗・wifi 基地局・店舗立地分析に応用。

AI HL only と SL の境界

SL の範囲：Voronoi 図の基本（境界線の作成・最近傍法）、Network の基本概念（頂点・辺・次数）。

HL only の追加範囲：Eulerian / Hamiltonian Path・Circuit、Travelling Salesman Problem、Chinese Postman、Dijkstra の正式な手順、Prim's / Kruskal's algorithm、隣接行列の行列演算（A^k で長さ k の経路数）。

※ AI HL では Calculus や Statistics と異なり、Graph Theory は『現実問題の最適化』に直結する独自の分野。Computer Science / Logistics / Urban Planning 進学を狙う生徒には決定的に重要。

【② グラフの基本概念（有向 / 無向、重み付き、隣接行列）】

Graph Theory の出発点は 6 つの基本概念。Paper 1 では定義の正確な理解、Paper 2 では隣接行列のべき乗による経路数計算が頻出します。

Vertex / Edge（頂点・辺）

公式 / 定義

G = (V, E)、V = 頂点集合、E = 辺集合

例

V = {A, B, C, D}, E = {AB, BC, CD, DA, AC}（4 頂点 5 辺）

グラフ理論の最も基本的な定義。頂点は『点（node）』、辺は『2 点を結ぶ線分』を表す。AI HL では問題文の状況（都市・基地局・配達先など）を頂点と辺に落とし込む力が問われる。

有向グラフ / 無向グラフ

公式 / 定義

無向：(A, B) = (B, A) / 有向：(A, B) ≠ (B, A)

例

無向：友達関係 / 有向：Twitter フォロー、一方通行道路

辺に向きがあるかどうかで分類。隣接行列で表すと、無向グラフは対称行列、有向グラフは非対称行列になる。Paper では Twitter / Instagram / 一方通行を題材にした有向グラフが頻出。

重み付きグラフ（Weighted Graph）

公式 / 定義

各辺 e ∈ E に重み w(e) ∈ R を割り当て

例

都市間距離・所要時間・コスト・データ転送量

Dijkstra（最短経路）・Prim / Kruskal（最小全域木）・TSP（巡回セールスマン）の全てで使う。重みは『距離・時間・コスト・容量』のいずれか、現実問題では複数の重みを比較する設定もある。

Walk / Trail / Path / Cycle

公式 / 定義

Walk⊃Trail⊃Path、Cycle は始点 = 終点の Path

例

Walk：A→B→A→C / Trail：A→B→C→D（辺の重複なし）/ Path：A→B→C（頂点も辺も重複なし）

Walk は『頂点と辺を交互に通る列』、Trail は『辺を重複しない Walk』、Path は『頂点も辺も重複しない Walk』、Cycle は『始点と終点が同じ Path』。AI HL Paper 1 で定義の違いを問う問題が出題。

Degree（次数）と Handshaking Lemma

公式 / 定義

deg(v) = v に接続する辺の数、Σ deg(v) = 2|E|

例

4 頂点で deg = (3, 3, 2, 2) → Σ = 10 = 2 × 5 辺

次数の総和は辺数の 2 倍（握手補題）。奇数次数の頂点は必ず偶数個存在する。Eulerian Path / Circuit の判定で核心的に使う性質。

隣接行列 / 隣接リスト

公式 / 定義

隣接行列：n × n の 0/1 行列、隣接リスト：各頂点の隣接頂点の集合

例

隣接行列 A の i 行 j 列 = 1 ⟺ 頂点 i, j が隣接

グラフをコンピュータで扱うための 2 大表現。隣接行列は密グラフ向け、隣接リストは疎グラフ向け。AI HL では隣接行列のべき乗 A^k で『長さ k の経路数』を計算する応用が頻出。

隣接行列のべき乗の意味：A^k の (i, j) 成分は『頂点 i から頂点 j への長さ k の経路（Walk）の数』を表します。例えば A² の (1, 3) 成分は『2 歩で 1 から 3 に到達する経路の数』。AI HL Paper 2 で『GDC で A、A²、A³ を計算し、頂点間の経路数を求めよ』と出題されます。

→ AI Voronoi 図の直感（Shorts）

Voronoi 図と最近傍法の本質を 60 秒で

Eulerian Path and Circuit

【③ Eulerian Path / Circuit（Königsberg の橋問題）】

Eulerian Path / Circuit は 『全ての辺を 1 度ずつ通る経路』。グラフ理論の歴史的起点である Königsberg の橋問題（1736 年、Euler） がこの分野の原点です。

Königsberg の橋問題

プロイセン王国 Königsberg（現在のロシア Kaliningrad）の Pregel 川にかかる 7 本の橋を 『全て 1 度ずつだけ渡って元の場所に戻る』 ことができるか、という問題。

Euler は街の 4 つの陸地を頂点、7 本の橋を辺とするグラフに置き換え、各頂点の次数を計算（3, 3, 5, 3）。全頂点の次数が奇数のため Eulerian Circuit は存在せず、解答は 『不可能』 と数学的に証明しました。

※ この証明がグラフ理論の起源。1736 年の Euler の論文「Solutio problematis ad geometriam situs pertinentis」が世界最初のグラフ理論論文。

Eulerian / Hamiltonian の 5 大型（HL シラバス）：

Eulerian Circuit（閉路、全辺を 1 度ずつ）

公式 / 定義

存在条件：全頂点の次数が偶数、かつグラフが連結

例

4 頂点で次数 (4, 4, 2, 2) → Eulerian Circuit 存在

始点と終点が同じで、全ての辺を 1 度ずつ通る経路。全頂点の次数が偶数であることが必要十分条件（Euler の定理）。発見的アルゴリズム（Fleury / Hierholzer）で構築可能。

Eulerian Path（開路、全辺を 1 度ずつ）

公式 / 定義

存在条件：奇数次数の頂点がちょうど 2 個、その他は偶数次数

例

次数 (3, 3, 4, 2) → 次数 3 の 2 頂点が端点となる Eulerian Path

始点と終点が異なる Eulerian。奇数次数の 2 頂点が必ず端点になる。Königsberg の橋問題は 4 頂点全てが奇数次数のため Eulerian Path も Circuit も存在しないことをオイラーが証明（グラフ理論の起源）。

Hamiltonian Circuit（閉路、全頂点を 1 度ずつ）

公式 / 定義

簡単な判定条件なし（NP-Complete 問題）

例

5 頂点完全グラフ K_5 → 12 通りの異なる Hamiltonian Circuit

全ての頂点を 1 度ずつ通る閉路。Eulerian と違い、簡単な判定条件は知られていない（NP 困難）。AI HL ではグラフ図から実際に経路を探す問題が出題。Dirac の定理（n ≥ 3 で全頂点の次数 ≥ n/2 なら存在）は HL シラバス外。

Travelling Salesman Problem（TSP）

公式 / 定義

最小重みの Hamiltonian Circuit を求める

例

5 都市の総距離最小の巡回経路

Hamiltonian Circuit の中で重みの総和が最小のものを見つける問題。NP 困難で、最適解の総当たり計算は O(n!) と膨大。AI HL Paper 3 では Nearest Neighbour Algorithm（貪欲法による近似解）の手順を踏ませる問題が頻出。

Chinese Postman Problem（中国人郵便配達問題）

公式 / 定義

Eulerian でないグラフを Eulerian にするための最小重み追加辺

例

奇数次数頂点のペアを最小重み辺で結ぶ

郵便配達員が全ての道路（辺）を最低 1 回通って帰路に戻る最短経路。Eulerian でない場合、奇数次数頂点のペアを最小重みのパスで結んで Eulerian 化する。AI HL Paper 3 の応用問題として出題されることがある。

Eulerian の判定は次数を数えるだけ：全頂点の次数が偶数なら Circuit が存在、奇数次数の頂点が 2 個ならその 2 点を端点とする Path が存在、奇数次数頂点が 4 個以上なら Eulerian 不可能。Paper 1 で 5-10 秒で判定できるよう訓練必須。

Hamiltonian Path and Travelling Salesman Problem

【④ Hamiltonian Path / Circuit と TSP】

Hamiltonian は 『全頂点を 1 度ずつ通る経路』。Eulerian と異なり 簡単な判定条件は知られていません（NP 困難）。AI HL では Travelling Salesman Problem（TSP）の文脈で頻出。

Travelling Salesman Problem（TSP）の定式化

問題：n 都市を全て 1 度ずつ訪問し、出発都市に戻る最短経路を求める。

計算量：総当たりは (n − 1)!/2 通り、5 都市で 12 通り、10 都市で 181,440 通り、20 都市で約 6 × 10¹⁶ 通り。

AI HL での扱い：最適解の総当たりは不可能なので、Nearest Neighbour Algorithm（最近傍法による貪欲法） で近似解を求める手順を Paper 3 で踏ませることが多い。

Nearest Neighbour Algorithm（手順）

始点を選ぶ（任意でよい）
現在地から未訪問の都市のうち最も近い都市を選んで移動
全都市を訪問するまで②を繰り返す
最後に始点に戻る
得られた経路の総重みを計算（近似解）

※ 貪欲法なので最適解ではない場合が多い。始点を変えて複数回試し、最小のものを採用するのが Paper 3 の標準手順。

TSP の現実応用：宅配業者の配送ルート最適化（Amazon・Grab・FoodPanda）、観光地巡りの最短ルート、3D プリンターのヘッド移動経路、半導体製造のドリル経路。マレーシアでは Mont Kiara の宅配最適経路 や KL の観光ルート分析 が AI HL IA の定番テーマです。

Dijkstra's Algorithm

【⑤ 最短経路（Dijkstra）の手計算手順】

Dijkstra は 負の重みを持たない重み付きグラフで、ある始点から各頂点への最短距離を求めるアルゴリズム。AI HL Paper 1 / 2 で table 形式の手計算が頻出。

Step 1：初期化

公式 / 定義

d(始点) = 0、他の全頂点 d(v) = ∞、確定集合 S = ∅

例

始点 A：d(A) = 0、d(B) = d(C) = d(D) = d(E) = ∞

始点の距離は 0、他は到達不能を意味する ∞。table の 1 行目に記入。前頂点の列は全て『−』で開始。

Step 2：最小距離の未確定頂点を選ぶ

公式 / 定義

v* = argmin (v ∉ S) d(v)、S ← S ∪ {v*}

例

初回は d(A) = 0 が最小 → A を確定、S = {A}

未確定頂点の中で最小距離を持つ頂点を確定。table の該当行の頂点を ○ で囲み、確定済みであることを示す。

Step 3：隣接頂点の距離を更新

公式 / 定義

u が v* の隣接：d(u) ← min(d(u), d(v*) + w(v*, u))、前頂点を v* に

例

A の隣接 B, C：d(B) = min(∞, 0 + 4) = 4、d(C) = min(∞, 0 + 2) = 2

辺 (v*, u) の重みを使って距離を緩和。更新があった列は table で赤色や下線で示す。前頂点も同時に記録（経路復元のため）。

Step 4：反復と終了

公式 / 定義

全頂点が確定するまで Step 2-3 を繰り返す

例

5 頂点なら 5 回の反復で完了、各回 table の 1 行を追加

全頂点が S に入った時点で終了。終点から前頂点を辿って最短経路を復元。table の最終行に各頂点の最短距離と前頂点が全て記入されている状態を目指す。

Dijkstra の table の書き方（標準形式）

table の各列：『反復回数』『確定済み集合 S』『各頂点の現在距離（A, B, C, ...）』『各頂点の前頂点（経路復元用）』。

反復ごとに 1 行追加し、最小距離の未確定頂点を確定にマーク（○で囲む）
距離が更新された頂点は赤色や下線で強調
前頂点も同時に記録（更新時に書き換え）
最終行から終点の前頂点を辿って最短経路を復元

※ Paper 1 で減点される 2 大ミス：①「途中行を省略して最終結果だけ書く」、②「前頂点を記録せず経路復元できない」。両方を丁寧に書く訓練が必要。

Dijkstra の限界：負の重みを持つ辺があると正しく動作しません（負の閉路では発散）。負の重み対応には Bellman-Ford アルゴリズムが必要ですが、これは AI HL シラバス外。AI HL では『負の重みなし』を確認してから Dijkstra を適用するのが鉄則。

→ AI Voronoi 図の直感（Shorts）

最近傍法と Voronoi の関係を 60 秒で

Minimum Spanning Tree

【⑥ 最小全域木（MST）— Prim's / Kruskal's algorithm】

最小全域木（Minimum Spanning Tree、MST）は『全ての頂点を結び、辺数が最小（= 頂点数 − 1）で総重みが最小の木』。電線・水道・通信網などの最小コスト敷設問題に直結します。

Prim's Algorithm（頂点ベースの貪欲法）

公式 / 定義

1 頂点から始め、最小重みで隣接する頂点を順に追加

例

A から開始 → AC (2) → CB (3) → BD (5) → DE (4) の順に追加

1 つの頂点から木を成長させる。各ステップで『現在の木に隣接する辺』の中から最小重みを選ぶ。木が常に連結を保つため、閉路チェックは不要。隣接行列で実装しやすく、密グラフに向く。

Kruskal's Algorithm（辺ベースの貪欲法）

公式 / 定義

全辺を重み昇順にソート、閉路を作らない辺を順に追加

例

辺の重み昇順 = (AC:2, CB:3, DE:4, BD:5, AB:4) → AC, CB, DE, BD（AB は閉路なので却下）

辺を 1 つずつ選ぶ。閉路判定（追加で同じ連結成分が結ばれるか）が必要だが、Paper 1 の手計算ではグラフ図を見れば閉路が見えるため簡単。疎グラフに向く。辺数 = 頂点数 − 1 になった時点で終了。

MST の重みは Prim でも Kruskal でも同じ

公式 / 定義

Total Weight = Σ w(e) for e in MST

例

AC + CB + DE + BD = 2 + 3 + 4 + 5 = 14

アルゴリズムによって構築順序や経路は異なるが、最終的な MST の総重みは同じ。AI HL Paper 1 では『MST の総重みを求めよ』と問われ、どちらのアルゴリズムを使ってもよい。

MST の応用：ネットワーク敷設コスト最小化

公式 / 定義

電線・水道・通信網などの最小コスト敷設

例

5 つの村を電線で結ぶ最小コスト = MST の総重み

現実問題への応用：都市間道路・電気網・通信網・上下水道網の最小コスト設計。AI HL IA でも頻出のテーマ。マレーシアでは地方自治体の通信網敷設計画への応用が考えられる。

Prim vs Kruskal — 使い分け早見表

Prim：頂点ベース、密グラフに有利、隣接行列で実装、閉路チェック不要
Kruskal：辺ベース、疎グラフに有利、辺リストで実装、閉路チェック必要
Paper 1 での選択：問題文で『どちらでも可』と明記されることが多く、自分が書きやすい方を選ぶ
総重みは同じ：どちらのアルゴリズムを使っても、最終的な MST の総重みは同一

MST の現実応用：マレーシア地方部の電力網敷設（高圧線の最小コスト配置）、5G 基地局間の光ファイバー網、上下水道網の最小コスト設計、災害時の避難所間の通信網構築。AI HL IA では『マレーシアの離島間の通信網最適化』のようなテーマで MST + Dijkstra を組合せると高得点。

Voronoi Diagrams

【⑦ Voronoi Diagrams（境界線・最近傍法・応用）】

Voronoi 図は『平面上のサイト集合から各点が最も近いサイトの領域に分割した図』。SL も HL も範囲で、現実応用が極めて広く、AI HL IA の定番テーマです。

Voronoi 図の定義

公式 / 定義

サイト集合 S = {p_1, ..., p_n}、領域 V(p_i) = {x : d(x, p_i) ≤ d(x, p_j) for all j}

例

2 サイト P, Q なら境界は PQ の垂直二等分線、平面を 2 領域に分割

各サイトについて『そのサイトが最も近い点の集合』を 1 つの領域とする平面分割。各境界は隣接サイト間の垂直二等分線の一部。AI HL では 3-5 サイトの図を手描きで作成する問題が頻出。

境界線の作成（垂直二等分線）

公式 / 定義

2 点 P(x_1, y_1), Q(x_2, y_2) の境界 = PQ の垂直二等分線

例

P(2, 3), Q(5, 7) の境界：中点 (3.5, 5)、傾き = −(5−2)/(7−3) = −3/4

Paper 2 では座標が与えられて『境界線の方程式を求めよ』と出題。中点を通り、PQ の傾きの負の逆数を傾きとする直線の方程式を立てる。Coordinate Geometry の知識が直接使われる。

最近傍法（Nearest Neighbour Method）

公式 / 定義

未知点 x について最も近いサイト p_i = argmin d(x, p_i) を割り当てる

例

新店舗 X の最寄り Starbucks = X が属する Voronoi 領域のサイト

Voronoi 図を作れば、任意の点について『どのサイトが最も近いか』が領域から即判別できる。配送拠点の割当・店舗の商圏分析・分類問題（kNN の k=1 版）に応用。

応用：移動店舗・wifi 基地局の最適配置

公式 / 定義

新サイトを既存サイトから最大距離の点（Largest Empty Circle）に配置

例

Mont Kiara の 5G 基地局空白地帯 = 既存基地局の Voronoi 頂点

新規出店・基地局増設の最適位置は『現在の Voronoi 図で最大の空円を持つ点』。AI HL Paper 3 で『次の店舗をどこに置くべきか』のような応用問題として出題。マレーシアでは Starbucks や Family Mart の出店戦略への応用が題材になる。

応用：移動店舗のサービス領域分析

公式 / 定義

移動店舗 i のサービス可能領域 = V(p_i)

例

KL 市内 6 つの食品トラックの担当エリア = 各トラックの Voronoi 領域

AI HL のテキストブックでよく登場する例題。各サイトのサービス領域の面積、最も需要が高そうな領域、領域の偏りなどを分析する。Paper 1 / Paper 2 で出題範囲。

Voronoi 境界線の方程式（Paper 2 頻出）

2 サイト P(x_1, y_1) と Q(x_2, y_2) の境界は PQ の垂直二等分線。

中点：M = ((x_1 + x_2)/2, (y_1 + y_2)/2)
PQ の傾き：m_PQ = (y_2 − y_1) / (x_2 − x_1)
境界線の傾き：m_⊥ = − 1 / m_PQ（負の逆数）
境界線の方程式：y − y_M = m_⊥ (x − x_M)

※ Coordinate Geometry の垂直二等分線の知識を直接使う。Paper 2 で『P(2, 3), Q(5, 7) の境界の方程式を求めよ』のような問題が出題。

Voronoi の現実応用 4 大例

①店舗立地分析（Starbucks・Family Mart の commercial area 推定）
②移動店舗のサービス領域（食品トラックの担当エリア）
③wifi / 5G 基地局配置（信号の最近接基地局決定）
④Largest Empty Circle 問題（新規サイトの最適配置）

AI HL IA では Mont Kiara の Starbucks 立地分析 や KL の 5G 基地局空白地帯特定 のテーマで、過去に高得点獲得例があります。

→ AI Voronoi 図の直感（Shorts）

Voronoi 領域の作り方を 60 秒で

Paper Focus and 30-Day Plan

【⑧ Paper 別出題傾向と 30 日演習プラン】

AI HL の 3 つの Paper はそれぞれ Graph Theory の出題内容と戦略が異なります。

Paper 1（With GDC）

120 分 / 110 点GDC 使用可（AI は全 Paper で GDC 可）

Graph Theory 出題

Graph 基本用語（Walk / Path / Trail / Cycle）の定義、Eulerian / Hamiltonian の判定、Dijkstra の手計算 table、Prim / Kruskal の MST 構築、Voronoi 図の手描きと境界線の方程式

戦略

Section A で定義問題と短い計算（10-15 点）、Section B で Dijkstra や MST の本格的な手計算（15-25 点）。table の途中行を省略せず、前頂点の記録を忘れない。Voronoi の境界線は Coordinate Geometry の垂直二等分線の知識を直接使う。

Paper 2（With GDC）

120 分 / 110 点GDC 使用可

Graph Theory 出題

隣接行列の入力と行列のべき乗（A^k で長さ k の経路数）、座標による Voronoi 境界線の方程式計算、GDC を使った重み付きグラフのデータ処理、ネットワーク最適化問題（コスト最小化・時間最小化）

戦略

GDC で行列演算を活用。TI-Nspire CX II の Matrix 機能で A、A²、A³ を高速計算し、経路数を即答する。Voronoi の境界線方程式は手計算（中点・傾き・直線の方程式）と GDC の Graph 機能を併用。

Paper 3（GDC + Problem-Solving）

60 分 / 55 点GDC 使用可

Graph Theory 出題

Graph Theory 単独 1 問が出題されることが多い（TSP の Nearest Neighbour 法、Chinese Postman、複数の Voronoi 図を組合せた最適配置、Dijkstra + MST の組合せ）

戦略

60 分で 2 問は 1 問 30 分の配分。Part a, b で基礎（定義・小規模計算）を確実に取り、Part c, d で TSP 近似解や Voronoi 応用で勝負を分ける。Problem-Solving は『手順を全て書く』『途中結果を 1 つずつ表に整理』が決定的。

Graph Theory の出題比率（過去 5 年データ）

AI HL では Graph Theory が試験全体の 約 15-20% を占めます。Paper 1 で約 15-25 点（110 点中）、Paper 2 で約 15-20 点、Paper 3 で約 25-30 点（55 点中、Graph 単独 1 問が出題されることが多い）。合計 55-75 点が Graph 由来 = 275 点満点中 20-27%。Graph で 70% 取れれば、Calculus + Statistics と合わせて Grade 6-7 が見える計算。

30 日過去問演習プラン（Grade 6 → 7 を狙う）：

Week 1（Day 1-7）

Graph 基本用語と Eulerian / Hamiltonian

Vertex / Edge / Walk / Trail / Path / Cycle の定義を 10 問の択一問題で確認
有向 / 無向 / 重み付きグラフの図と隣接行列の対応 15 問
次数と Handshaking Lemma の応用 10 問
Eulerian Path / Circuit の判定問題 15 問（Königsberg 含む）
Hamiltonian Path / Circuit の手探索問題 10 問
Day 7：Paper 1 の Graph 関連短答 1 セット

Week 2（Day 8-14）

Dijkstra による最短経路集中

Dijkstra の table 手計算 20 問（5-7 頂点）
table の前頂点記録と経路復元 10 問
重み付き有向グラフでの Dijkstra 10 問
Dijkstra と Floyd の違いを定性的に比較（HL の範囲確認）
GDC（TI-Nspire CX II）の Matrix 機能で隣接行列の入力 5 問
Day 14：Paper 1 1 セット（時間計測）+ 解答解説

Week 3（Day 15-21）

MST（Prim / Kruskal）と Voronoi

Prim's algorithm の MST 構築 15 問
Kruskal's algorithm の MST 構築 15 問（閉路判定含む）
Voronoi 図の手描き 15 問（3-5 サイト）
Voronoi 境界線の方程式（垂直二等分線）計算 10 問
最近傍法と Voronoi 領域の判別 10 問
Day 21：Paper 2 1 セット（120 分計測）

Week 4（Day 22-30）

Paper 3 形式 + 総合演習

Paper 3 の Graph 単独問題 6 セット（過去 3 年 May + November）
TSP の Nearest Neighbour Algorithm 5 問
Chinese Postman 問題 3 問（奇数次数頂点のペアリング）
Voronoi 応用（移動店舗・基地局配置）3 問
Day 27-29：Paper 1 + Paper 2 + Paper 3 通し模試 1 セット
Day 30：間違えた問題のみ解き直し + 弱点リスト作成

過去問の入手先：IBO 公式の Past Papers は学校経由で配布されるのが正規ルート。マレーシア IB 校（MKIS / GIS / ISKL / Sayfol 等）では Math Department が在校生に提供します。塾経由の入手や非公式の過去問サイトは Copyright 違反のリスクがあるため避ける。南数塾では学校から正規入手した過去問の解答解説 + 採点フィードバックを提供しています。

Related Shorts

【関連 Shorts（30-60 秒で復習）】

AI HL Graph Theory の頻出概念・技法を 30-60 秒で復習する Shorts コンテンツ。試験前の最終確認に。

AI Voronoi 図の直感

Voronoi 領域の作り方と最近傍法を 60 秒で

Related Guides

【関連記事】

IB Math AA / AI HL / SL 4 区分完全攻略

全体像・選び方・Paper 構成・IA テーマ

IB Math AI HL Matrices 完全攻略

Matrix 演算・固有値・Markov Chain の全範囲

Computer Science IB 進学戦略

CMU / MIT / NUS / 東大情報科学完全比較

工学部 IB 進学戦略

MIT / Caltech / Imperial / NUS / 東工大完全比較

建築・デザイン系 IB 進学戦略

Urban Planning / Architecture / Industrial Design

Diagnosis

【関連診断】

→ IB Math AA vs AI 適性診断クイズ（10 問）

AA HL / AI HL / SL のどれが向いているか 3 分で診断

How Nansu Juku Supports AI HL Graph Theory

【南数塾の AI HL Graph Theory 支援】

南数塾は AI HL の Graph Theory 章に特化した個別カリキュラムを提供。マレーシア IB 校（MKIS / GIS / ISKL 等）の DP 1-2 生徒の Graph 6 → 7 引き上げ実績があります。

✓Graph 基本用語（Walk / Path / Trail / Cycle）の定義訓練
✓Eulerian / Hamiltonian の判定問題の即答訓練
✓Dijkstra の table 計算の手順を個別演習（5-7 頂点規模）
✓Prim's / Kruskal's algorithm の MST 構築 30 問演習
✓Voronoi 図の手描き + 境界線の方程式計算
✓Paper 1（手計算）の table 形式の解答訓練
✓Paper 2（GDC）の隣接行列のべき乗計算習熟
✓Paper 3 の TSP / Chinese Postman / Voronoi 応用 30 回演習
✓IA で Graph Theory を使う高得点テーマの選定 + 執筆指導
✓Computer Science / Urban Planning 系大学出願戦略の共有

※ 本記事は 2026 年 5 月時点の IB Diploma Programme 公式シラバス（First Exam 2021、AI HL）と公開情報を基に整理しています。出題比率や用語の表現は IB Math AI Subject Guide に準拠していますが、最終的な確認は IB Official Formula Booklet と各校の Math Department に行ってください。Grade Boundary や難易度は May / November Session で変動するため、IB Official Statistical Bulletin で必ず確認してください。

AI HL Graph Theory で Grade 7 を
取るための個別相談を承ります

お子様の現在の Graph Theory の習熟度（Eulerian / Hamiltonian の判定 / Dijkstra / MST / Voronoi の到達度）を診断し、Year 12-13 の 2 年間で Grade 7 を狙う個別カリキュラムをご提案します。Computer Science / Urban Planning / Logistics 系大学進学を見据えた IA テーマ選定もサポート。無料体験授業 + 三者面談（生徒・保護者・講師）にて。

入試・進学の相談を申し込む

入塾をご検討の方の受講相談は無料、入塾以外の進路相談は有料です。進路相談（有料）について

移行元の確認：現サイトの元ページ（外部）。元サイトは変更していません。

AI HL Graph Theory & Voronoi 完全攻略

ホーム›ブログ›IB Math AI HL Graph Theory & Voronoi 完全攻略

IB Math AI HL Graph Theory / 2026 年版

IB Math AI HL Graph Theory & Voronoi Diagrams
完全攻略 2026

ネットワーク・最短経路・最小全域木・Voronoi 図の全範囲

Table of Contents

【目次】

AI HL Graph Theory シラバス全体像
グラフの基本概念（有向 / 無向、重み付き、隣接行列）
Eulerian Path / Circuit（Königsberg の橋問題）
Hamiltonian Path / Circuit（TSP の概念）
最短経路（Dijkstra）の手計算手順
最小全域木（MST）— Prim's / Kruskal's algorithm
Voronoi Diagrams（境界線・最近傍法・応用）
30 日過去問演習プラン

Conclusion First

【結論先出し】

Graph Theory は「現実の最適化問題を数学で解く」分野です。

Grade 7 を狙うなら、次の 5 領域を 30 日で固めます。

① Graph 基本用語の正確な定義
② Eulerian / Hamiltonian の判定条件
③ Dijkstra（最短経路）の table 計算
④ Prim / Kruskal による最小全域木
⑤ Voronoi 図の境界線作成と最近傍法

AI HL Graph Theory Syllabus Overview

【① AI HL Graph Theory シラバス全体像】

① Graph 基本用語

Vertex / Edge / Walk / Path / Trail / Cycle

② Eulerian Path / Circuit（HL only）

全辺を 1 度ずつ通る経路

Königsberg の橋問題が起源。判定条件は『全頂点の次数が偶数（Circuit）』『奇数次数の頂点が 2 個（Path）』。HL only の追加範囲で、Paper 1 / 3 で頻出。

③ Hamiltonian Path / Circuit（HL only）

全頂点を 1 度ずつ通る経路 / TSP

簡単な判定条件なし（NP 困難）。Travelling Salesman Problem（TSP）の基礎概念。Paper 3 で Nearest Neighbour Algorithm による近似解の手順を踏ませる問題が頻出。

④ Dijkstra による最短経路（HL only）

負の重みなし、table 形式の手計算

⑤ 最小全域木（MST、HL only）

Prim's / Kruskal's algorithm

⑥ Voronoi Diagrams（SL + HL）

境界線・最近傍法・最適配置

AI HL only と SL の境界

SL の範囲：Voronoi 図の基本（境界線の作成・最近傍法）、Network の基本概念（頂点・辺・次数）。

【② グラフの基本概念（有向 / 無向、重み付き、隣接行列）】

Graph Theory の出発点は 6 つの基本概念。Paper 1 では定義の正確な理解、Paper 2 では隣接行列のべき乗による経路数計算が頻出します。

Vertex / Edge（頂点・辺）

公式 / 定義

G = (V, E)、V = 頂点集合、E = 辺集合

例

V = {A, B, C, D}, E = {AB, BC, CD, DA, AC}（4 頂点 5 辺）

有向グラフ / 無向グラフ

公式 / 定義

無向：(A, B) = (B, A) / 有向：(A, B) ≠ (B, A)

例

無向：友達関係 / 有向：Twitter フォロー、一方通行道路

重み付きグラフ（Weighted Graph）

公式 / 定義

各辺 e ∈ E に重み w(e) ∈ R を割り当て

例

都市間距離・所要時間・コスト・データ転送量

Walk / Trail / Path / Cycle

公式 / 定義

Walk⊃Trail⊃Path、Cycle は始点 = 終点の Path

例

Walk：A→B→A→C / Trail：A→B→C→D（辺の重複なし）/ Path：A→B→C（頂点も辺も重複なし）

Degree（次数）と Handshaking Lemma

公式 / 定義

deg(v) = v に接続する辺の数、Σ deg(v) = 2|E|

例

4 頂点で deg = (3, 3, 2, 2) → Σ = 10 = 2 × 5 辺

次数の総和は辺数の 2 倍（握手補題）。奇数次数の頂点は必ず偶数個存在する。Eulerian Path / Circuit の判定で核心的に使う性質。

隣接行列 / 隣接リスト

公式 / 定義

隣接行列：n × n の 0/1 行列、隣接リスト：各頂点の隣接頂点の集合

例

隣接行列 A の i 行 j 列 = 1 ⟺ 頂点 i, j が隣接

→ AI Voronoi 図の直感（Shorts）

Voronoi 図と最近傍法の本質を 60 秒で

Eulerian Path and Circuit

【③ Eulerian Path / Circuit（Königsberg の橋問題）】

Königsberg の橋問題

※ この証明がグラフ理論の起源。1736 年の Euler の論文「Solutio problematis ad geometriam situs pertinentis」が世界最初のグラフ理論論文。

Eulerian / Hamiltonian の 5 大型（HL シラバス）：

Eulerian Circuit（閉路、全辺を 1 度ずつ）

公式 / 定義

存在条件：全頂点の次数が偶数、かつグラフが連結

例

4 頂点で次数 (4, 4, 2, 2) → Eulerian Circuit 存在

Eulerian Path（開路、全辺を 1 度ずつ）

公式 / 定義

存在条件：奇数次数の頂点がちょうど 2 個、その他は偶数次数

例

次数 (3, 3, 4, 2) → 次数 3 の 2 頂点が端点となる Eulerian Path

Hamiltonian Circuit（閉路、全頂点を 1 度ずつ）

公式 / 定義

簡単な判定条件なし（NP-Complete 問題）

例

5 頂点完全グラフ K_5 → 12 通りの異なる Hamiltonian Circuit

Travelling Salesman Problem（TSP）

公式 / 定義

最小重みの Hamiltonian Circuit を求める

例

5 都市の総距離最小の巡回経路

Chinese Postman Problem（中国人郵便配達問題）

公式 / 定義

Eulerian でないグラフを Eulerian にするための最小重み追加辺

例

奇数次数頂点のペアを最小重み辺で結ぶ

Hamiltonian Path and Travelling Salesman Problem

【④ Hamiltonian Path / Circuit と TSP】

Travelling Salesman Problem（TSP）の定式化

問題：n 都市を全て 1 度ずつ訪問し、出発都市に戻る最短経路を求める。

計算量：総当たりは (n − 1)!/2 通り、5 都市で 12 通り、10 都市で 181,440 通り、20 都市で約 6 × 10¹⁶ 通り。

Nearest Neighbour Algorithm（手順）

始点を選ぶ（任意でよい）
現在地から未訪問の都市のうち最も近い都市を選んで移動
全都市を訪問するまで②を繰り返す
最後に始点に戻る
得られた経路の総重みを計算（近似解）

※ 貪欲法なので最適解ではない場合が多い。始点を変えて複数回試し、最小のものを採用するのが Paper 3 の標準手順。

Dijkstra's Algorithm

【⑤ 最短経路（Dijkstra）の手計算手順】

Step 1：初期化

公式 / 定義

d(始点) = 0、他の全頂点 d(v) = ∞、確定集合 S = ∅

例

始点 A：d(A) = 0、d(B) = d(C) = d(D) = d(E) = ∞

始点の距離は 0、他は到達不能を意味する ∞。table の 1 行目に記入。前頂点の列は全て『−』で開始。

Step 2：最小距離の未確定頂点を選ぶ

公式 / 定義

v* = argmin (v ∉ S) d(v)、S ← S ∪ {v*}

例

初回は d(A) = 0 が最小 → A を確定、S = {A}

未確定頂点の中で最小距離を持つ頂点を確定。table の該当行の頂点を ○ で囲み、確定済みであることを示す。

Step 3：隣接頂点の距離を更新

公式 / 定義

u が v* の隣接：d(u) ← min(d(u), d(v*) + w(v*, u))、前頂点を v* に

例

A の隣接 B, C：d(B) = min(∞, 0 + 4) = 4、d(C) = min(∞, 0 + 2) = 2

辺 (v*, u) の重みを使って距離を緩和。更新があった列は table で赤色や下線で示す。前頂点も同時に記録（経路復元のため）。

Step 4：反復と終了

公式 / 定義

全頂点が確定するまで Step 2-3 を繰り返す

例

5 頂点なら 5 回の反復で完了、各回 table の 1 行を追加

Dijkstra の table の書き方（標準形式）

table の各列：『反復回数』『確定済み集合 S』『各頂点の現在距離（A, B, C, ...）』『各頂点の前頂点（経路復元用）』。

反復ごとに 1 行追加し、最小距離の未確定頂点を確定にマーク（○で囲む）
距離が更新された頂点は赤色や下線で強調
前頂点も同時に記録（更新時に書き換え）
最終行から終点の前頂点を辿って最短経路を復元

→ AI Voronoi 図の直感（Shorts）

最近傍法と Voronoi の関係を 60 秒で

Minimum Spanning Tree

【⑥ 最小全域木（MST）— Prim's / Kruskal's algorithm】

Prim's Algorithm（頂点ベースの貪欲法）

公式 / 定義

1 頂点から始め、最小重みで隣接する頂点を順に追加

例

A から開始 → AC (2) → CB (3) → BD (5) → DE (4) の順に追加

Kruskal's Algorithm（辺ベースの貪欲法）

公式 / 定義

全辺を重み昇順にソート、閉路を作らない辺を順に追加

例

辺の重み昇順 = (AC:2, CB:3, DE:4, BD:5, AB:4) → AC, CB, DE, BD（AB は閉路なので却下）

MST の重みは Prim でも Kruskal でも同じ

公式 / 定義

Total Weight = Σ w(e) for e in MST

例

AC + CB + DE + BD = 2 + 3 + 4 + 5 = 14

MST の応用：ネットワーク敷設コスト最小化

公式 / 定義

電線・水道・通信網などの最小コスト敷設

例

5 つの村を電線で結ぶ最小コスト = MST の総重み

Prim vs Kruskal — 使い分け早見表

Prim：頂点ベース、密グラフに有利、隣接行列で実装、閉路チェック不要
Kruskal：辺ベース、疎グラフに有利、辺リストで実装、閉路チェック必要
Paper 1 での選択：問題文で『どちらでも可』と明記されることが多く、自分が書きやすい方を選ぶ
総重みは同じ：どちらのアルゴリズムを使っても、最終的な MST の総重みは同一

Voronoi Diagrams

【⑦ Voronoi Diagrams（境界線・最近傍法・応用）】

Voronoi 図の定義

公式 / 定義

サイト集合 S = {p_1, ..., p_n}、領域 V(p_i) = {x : d(x, p_i) ≤ d(x, p_j) for all j}

例

2 サイト P, Q なら境界は PQ の垂直二等分線、平面を 2 領域に分割

境界線の作成（垂直二等分線）

公式 / 定義

2 点 P(x_1, y_1), Q(x_2, y_2) の境界 = PQ の垂直二等分線

例

P(2, 3), Q(5, 7) の境界：中点 (3.5, 5)、傾き = −(5−2)/(7−3) = −3/4

最近傍法（Nearest Neighbour Method）

公式 / 定義

未知点 x について最も近いサイト p_i = argmin d(x, p_i) を割り当てる

例

新店舗 X の最寄り Starbucks = X が属する Voronoi 領域のサイト

応用：移動店舗・wifi 基地局の最適配置

公式 / 定義

新サイトを既存サイトから最大距離の点（Largest Empty Circle）に配置

例

Mont Kiara の 5G 基地局空白地帯 = 既存基地局の Voronoi 頂点

応用：移動店舗のサービス領域分析

公式 / 定義

移動店舗 i のサービス可能領域 = V(p_i)

例

KL 市内 6 つの食品トラックの担当エリア = 各トラックの Voronoi 領域

Voronoi 境界線の方程式（Paper 2 頻出）

2 サイト P(x_1, y_1) と Q(x_2, y_2) の境界は PQ の垂直二等分線。

中点：M = ((x_1 + x_2)/2, (y_1 + y_2)/2)
PQ の傾き：m_PQ = (y_2 − y_1) / (x_2 − x_1)
境界線の傾き：m_⊥ = − 1 / m_PQ（負の逆数）
境界線の方程式：y − y_M = m_⊥ (x − x_M)

※ Coordinate Geometry の垂直二等分線の知識を直接使う。Paper 2 で『P(2, 3), Q(5, 7) の境界の方程式を求めよ』のような問題が出題。

Voronoi の現実応用 4 大例

①店舗立地分析（Starbucks・Family Mart の commercial area 推定）
②移動店舗のサービス領域（食品トラックの担当エリア）
③wifi / 5G 基地局配置（信号の最近接基地局決定）
④Largest Empty Circle 問題（新規サイトの最適配置）

AI HL IA では Mont Kiara の Starbucks 立地分析 や KL の 5G 基地局空白地帯特定 のテーマで、過去に高得点獲得例があります。

→ AI Voronoi 図の直感（Shorts）

Voronoi 領域の作り方を 60 秒で

Paper Focus and 30-Day Plan

【⑧ Paper 別出題傾向と 30 日演習プラン】

AI HL の 3 つの Paper はそれぞれ Graph Theory の出題内容と戦略が異なります。

Paper 1（With GDC）

120 分 / 110 点GDC 使用可（AI は全 Paper で GDC 可）

Graph Theory 出題

戦略

Paper 2（With GDC）

120 分 / 110 点GDC 使用可

Graph Theory 出題

戦略

Paper 3（GDC + Problem-Solving）

60 分 / 55 点GDC 使用可

Graph Theory 出題

Graph Theory 単独 1 問が出題されることが多い（TSP の Nearest Neighbour 法、Chinese Postman、複数の Voronoi 図を組合せた最適配置、Dijkstra + MST の組合せ）

戦略

Graph Theory の出題比率（過去 5 年データ）

30 日過去問演習プラン（Grade 6 → 7 を狙う）：

Week 1（Day 1-7）

Graph 基本用語と Eulerian / Hamiltonian

Vertex / Edge / Walk / Trail / Path / Cycle の定義を 10 問の択一問題で確認
有向 / 無向 / 重み付きグラフの図と隣接行列の対応 15 問
次数と Handshaking Lemma の応用 10 問
Eulerian Path / Circuit の判定問題 15 問（Königsberg 含む）
Hamiltonian Path / Circuit の手探索問題 10 問
Day 7：Paper 1 の Graph 関連短答 1 セット

Week 2（Day 8-14）

Dijkstra による最短経路集中

Dijkstra の table 手計算 20 問（5-7 頂点）
table の前頂点記録と経路復元 10 問
重み付き有向グラフでの Dijkstra 10 問
Dijkstra と Floyd の違いを定性的に比較（HL の範囲確認）
GDC（TI-Nspire CX II）の Matrix 機能で隣接行列の入力 5 問
Day 14：Paper 1 1 セット（時間計測）+ 解答解説

Week 3（Day 15-21）

MST（Prim / Kruskal）と Voronoi

Prim's algorithm の MST 構築 15 問
Kruskal's algorithm の MST 構築 15 問（閉路判定含む）
Voronoi 図の手描き 15 問（3-5 サイト）
Voronoi 境界線の方程式（垂直二等分線）計算 10 問
最近傍法と Voronoi 領域の判別 10 問
Day 21：Paper 2 1 セット（120 分計測）

Week 4（Day 22-30）

Paper 3 形式 + 総合演習

Paper 3 の Graph 単独問題 6 セット（過去 3 年 May + November）
TSP の Nearest Neighbour Algorithm 5 問
Chinese Postman 問題 3 問（奇数次数頂点のペアリング）
Voronoi 応用（移動店舗・基地局配置）3 問
Day 27-29：Paper 1 + Paper 2 + Paper 3 通し模試 1 セット
Day 30：間違えた問題のみ解き直し + 弱点リスト作成

Related Shorts

【関連 Shorts（30-60 秒で復習）】

AI HL Graph Theory の頻出概念・技法を 30-60 秒で復習する Shorts コンテンツ。試験前の最終確認に。

AI Voronoi 図の直感

Voronoi 領域の作り方と最近傍法を 60 秒で

Related Guides

【関連記事】

IB Math AA / AI HL / SL 4 区分完全攻略

全体像・選び方・Paper 構成・IA テーマ

IB Math AI HL Matrices 完全攻略

Matrix 演算・固有値・Markov Chain の全範囲

Computer Science IB 進学戦略

CMU / MIT / NUS / 東大情報科学完全比較

工学部 IB 進学戦略

MIT / Caltech / Imperial / NUS / 東工大完全比較

建築・デザイン系 IB 進学戦略

Urban Planning / Architecture / Industrial Design

Diagnosis

【関連診断】

→ IB Math AA vs AI 適性診断クイズ（10 問）

AA HL / AI HL / SL のどれが向いているか 3 分で診断

How Nansu Juku Supports AI HL Graph Theory

【南数塾の AI HL Graph Theory 支援】

✓Graph 基本用語（Walk / Path / Trail / Cycle）の定義訓練
✓Eulerian / Hamiltonian の判定問題の即答訓練
✓Dijkstra の table 計算の手順を個別演習（5-7 頂点規模）
✓Prim's / Kruskal's algorithm の MST 構築 30 問演習
✓Voronoi 図の手描き + 境界線の方程式計算
✓Paper 1（手計算）の table 形式の解答訓練
✓Paper 2（GDC）の隣接行列のべき乗計算習熟
✓Paper 3 の TSP / Chinese Postman / Voronoi 応用 30 回演習
✓IA で Graph Theory を使う高得点テーマの選定 + 執筆指導
✓Computer Science / Urban Planning 系大学出願戦略の共有

AI HL Graph Theory で Grade 7 を
取るための個別相談を承ります

入試・進学の相談を申し込む

入塾をご検討の方の受講相談は無料、入塾以外の進路相談は有料です。進路相談（有料）について

移行元の確認：現サイトの元ページ（外部）。元サイトは変更していません。

AI HL Graph Theory & Voronoi 完全攻略

IB Math AI HL Graph Theory & Voronoi Diagrams 完全攻略 2026

【目次】

【結論先出し】

【① AI HL Graph Theory シラバス全体像】

① Graph 基本用語

② Eulerian Path / Circuit（HL only）

③ Hamiltonian Path / Circuit（HL only）

④ Dijkstra による最短経路（HL only）

⑤ 最小全域木（MST、HL only）

⑥ Voronoi Diagrams（SL + HL）

AI HL only と SL の境界

関連内部記事

【② グラフの基本概念（有向 / 無向、重み付き、隣接行列）】

Vertex / Edge（頂点・辺）

有向グラフ / 無向グラフ

重み付きグラフ（Weighted Graph）

Walk / Trail / Path / Cycle

Degree（次数）と Handshaking Lemma

隣接行列 / 隣接リスト

【③ Eulerian Path / Circuit（Königsberg の橋問題）】

Königsberg の橋問題

Eulerian Circuit（閉路、全辺を 1 度ずつ）

Eulerian Path（開路、全辺を 1 度ずつ）

Hamiltonian Circuit（閉路、全頂点を 1 度ずつ）

Travelling Salesman Problem（TSP）

Chinese Postman Problem（中国人郵便配達問題）

【④ Hamiltonian Path / Circuit と TSP】

Travelling Salesman Problem（TSP）の定式化

Nearest Neighbour Algorithm（手順）

【⑤ 最短経路（Dijkstra）の手計算手順】

Step 1：初期化

Step 2：最小距離の未確定頂点を選ぶ

Step 3：隣接頂点の距離を更新

Step 4：反復と終了

Dijkstra の table の書き方（標準形式）

【⑥ 最小全域木（MST）— Prim's / Kruskal's algorithm】

Prim's Algorithm（頂点ベースの貪欲法）

Kruskal's Algorithm（辺ベースの貪欲法）

MST の重みは Prim でも Kruskal でも同じ

MST の応用：ネットワーク敷設コスト最小化

Prim vs Kruskal — 使い分け早見表

【⑦ Voronoi Diagrams（境界線・最近傍法・応用）】

Voronoi 図の定義

境界線の作成（垂直二等分線）

最近傍法（Nearest Neighbour Method）

応用：移動店舗・wifi 基地局の最適配置

応用：移動店舗のサービス領域分析

Voronoi 境界線の方程式（Paper 2 頻出）

【⑧ Paper 別出題傾向と 30 日演習プラン】

Paper 1（With GDC）

Paper 2（With GDC）

Paper 3（GDC + Problem-Solving）

Graph Theory の出題比率（過去 5 年データ）

Week 1（Day 1-7）

Week 2（Day 8-14）

Week 3（Day 15-21）

Week 4（Day 22-30）

【関連 Shorts（30-60 秒で復習）】

【関連記事】

【関連診断】

【南数塾の AI HL Graph Theory 支援】

AI HL Graph Theory で Grade 7 を取るための個別相談を承ります

AI HL Graph Theory & Voronoi 完全攻略

IB Math AI HL Graph Theory & Voronoi Diagrams 完全攻略 2026

【目次】

【結論先出し】

【① AI HL Graph Theory シラバス全体像】

① Graph 基本用語

② Eulerian Path / Circuit（HL only）

③ Hamiltonian Path / Circuit（HL only）

④ Dijkstra による最短経路（HL only）

⑤ 最小全域木（MST、HL only）

⑥ Voronoi Diagrams（SL + HL）

AI HL only と SL の境界

関連内部記事

【② グラフの基本概念（有向 / 無向、重み付き、隣接行列）】

Vertex / Edge（頂点・辺）

有向グラフ / 無向グラフ

重み付きグラフ（Weighted Graph）

IB Math AI HL Graph Theory & Voronoi Diagrams
完全攻略 2026

AI HL Graph Theory で Grade 7 を
取るための個別相談を承ります

IB Math AI HL Graph Theory & Voronoi Diagrams
完全攻略 2026

AI HL Graph Theory で Grade 7 を
取るための個別相談を承ります