ネットワーク・最短経路・最小全域木・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 日演習プランを掲載します。
AI HL Graph Theory は『現実世界の最適化問題を数学で解く』分野。Grade 7 を狙う場合、Graph 基本用語の正確な定義 + Eulerian / Hamiltonian の判定条件 + Dijkstra の table 計算 + Prim / Kruskal の MST 構築 + Voronoi の境界線作成と最近傍法の 5 領域を 30 日で固める必要があります。
Paper 1 で定義問題と手計算（Dijkstra・MST・Voronoi）、Paper 2 で隣接行列の行列演算と Voronoi 境界線の方程式、Paper 3 で Graph Theory 単独問題（TSP の Nearest Neighbour・Chinese Postman・Voronoi 応用）が出題されます。本記事は 8 章 + 8 つの FAQ + 30 日演習プラン + Paper 別出題傾向で構成されています。
AI HL の Graph Theory は 「Graph 基本用語 / Eulerian / Hamiltonian / 最短経路 / MST / Voronoi」の 6 領域で構成されます。SL では Voronoi の基本のみ、HL では Eulerian / Hamiltonian / Dijkstra / MST が追加範囲。
グラフ理論の語彙体系。Walk⊃Trail⊃Path の包含関係、次数（degree）と Handshaking Lemma、有向 / 無向 / 重み付きの分類、隣接行列・隣接リストでの表現を理解する。
Königsberg の橋問題が起源。判定条件は『全頂点の次数が偶数（Circuit）』『奇数次数の頂点が 2 個（Path）』。HL only の追加範囲で、Paper 1 / 3 で頻出。
簡単な判定条件なし（NP 困難）。Travelling Salesman Problem（TSP）の基礎概念。Paper 3 で Nearest Neighbour Algorithm による近似解の手順を踏ませる問題が頻出。
重み付きグラフの最短経路アルゴリズム。table 形式で『各頂点の現在距離、前頂点、確定状態』を反復更新。Paper 1 / 2 で手計算問題が頻出、5-7 頂点規模が標準。
全頂点を結ぶ最小重みの木。Prim は頂点ベース貪欲法（1 頂点から成長）、Kruskal は辺ベース貪欲法（重み昇順 + 閉路チェック）。どちらでも結果の総重みは同じ。
平面上のサイト集合から『各点が最も近いサイトの領域』に分割。境界線は隣接サイト間の垂直二等分線。最近傍法・移動店舗・wifi 基地局・店舗立地分析に応用。
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 では隣接行列のべき乗による経路数計算が頻出します。
グラフ理論の最も基本的な定義。頂点は『点（node）』、辺は『2 点を結ぶ線分』を表す。AI HL では問題文の状況（都市・基地局・配達先など）を頂点と辺に落とし込む力が問われる。
辺に向きがあるかどうかで分類。隣接行列で表すと、無向グラフは対称行列、有向グラフは非対称行列になる。Paper では Twitter / Instagram / 一方通行を題材にした有向グラフが頻出。
Dijkstra（最短経路）・Prim / Kruskal（最小全域木）・TSP（巡回セールスマン）の全てで使う。重みは『距離・時間・コスト・容量』のいずれか、現実問題では複数の重みを比較する設定もある。
Walk は『頂点と辺を交互に通る列』、Trail は『辺を重複しない Walk』、Path は『頂点も辺も重複しない Walk』、Cycle は『始点と終点が同じ Path』。AI HL Paper 1 で定義の違いを問う問題が出題。
次数の総和は辺数の 2 倍（握手補題）。奇数次数の頂点は必ず偶数個存在する。Eulerian Path / Circuit の判定で核心的に使う性質。
グラフをコンピュータで扱うための 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³ を計算し、頂点間の経路数を求めよ』と出題されます。
Eulerian Path / Circuit は 『全ての辺を 1 度ずつ通る経路』。グラフ理論の歴史的起点である Königsberg の橋問題（1736 年、Euler） がこの分野の原点です。
プロイセン王国 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 シラバス）：
始点と終点が同じで、全ての辺を 1 度ずつ通る経路。全頂点の次数が偶数であることが必要十分条件（Euler の定理）。発見的アルゴリズム（Fleury / Hierholzer）で構築可能。
始点と終点が異なる Eulerian。奇数次数の 2 頂点が必ず端点になる。Königsberg の橋問題は 4 頂点全てが奇数次数のため Eulerian Path も Circuit も存在しないことをオイラーが証明（グラフ理論の起源）。
全ての頂点を 1 度ずつ通る閉路。Eulerian と違い、簡単な判定条件は知られていない（NP 困難）。AI HL ではグラフ図から実際に経路を探す問題が出題。Dirac の定理（n ≥ 3 で全頂点の次数 ≥ n/2 なら存在）は HL シラバス外。
Hamiltonian Circuit の中で重みの総和が最小のものを見つける問題。NP 困難で、最適解の総当たり計算は O(n!) と膨大。AI HL Paper 3 では Nearest Neighbour Algorithm（貪欲法による近似解）の手順を踏ませる問題が頻出。
郵便配達員が全ての道路（辺）を最低 1 回通って帰路に戻る最短経路。Eulerian でない場合、奇数次数頂点のペアを最小重みのパスで結んで Eulerian 化する。AI HL Paper 3 の応用問題として出題されることがある。
Eulerian の判定は次数を数えるだけ：全頂点の次数が偶数なら Circuit が存在、奇数次数の頂点が 2 個ならその 2 点を端点とする Path が存在、奇数次数頂点が 4 個以上なら Eulerian 不可能。Paper 1 で 5-10 秒で判定できるよう訓練必須。
Hamiltonian は 『全頂点を 1 度ずつ通る経路』。Eulerian と異なり 簡単な判定条件は知られていません（NP 困難）。AI HL では Travelling Salesman Problem（TSP）の文脈で頻出。
問題：n 都市を全て 1 度ずつ訪問し、出発都市に戻る最短経路を求める。
計算量：総当たりは (n − 1)!/2 通り、5 都市で 12 通り、10 都市で 181,440 通り、20 都市で約 6 × 10¹⁶ 通り。
AI HL での扱い：最適解の総当たりは不可能なので、Nearest Neighbour Algorithm（最近傍法による貪欲法） で近似解を求める手順を Paper 3 で踏ませることが多い。
※ 貪欲法なので最適解ではない場合が多い。始点を変えて複数回試し、最小のものを採用するのが Paper 3 の標準手順。
TSP の現実応用：宅配業者の配送ルート最適化（Amazon・Grab・FoodPanda）、観光地巡りの最短ルート、3D プリンターのヘッド移動経路、半導体製造のドリル経路。マレーシアでは Mont Kiara の宅配最適経路 や KL の観光ルート分析 が AI HL IA の定番テーマです。
Dijkstra は 負の重みを持たない重み付きグラフで、ある始点から各頂点への最短距離を求めるアルゴリズム。AI HL Paper 1 / 2 で table 形式の手計算が頻出。
始点の距離は 0、他は到達不能を意味する ∞。table の 1 行目に記入。前頂点の列は全て『−』で開始。
未確定頂点の中で最小距離を持つ頂点を確定。table の該当行の頂点を ○ で囲み、確定済みであることを示す。
辺 (v*, u) の重みを使って距離を緩和。更新があった列は table で赤色や下線で示す。前頂点も同時に記録（経路復元のため）。
全頂点が S に入った時点で終了。終点から前頂点を辿って最短経路を復元。table の最終行に各頂点の最短距離と前頂点が全て記入されている状態を目指す。
table の各列：『反復回数』『確定済み集合 S』『各頂点の現在距離（A, B, C, ...）』『各頂点の前頂点（経路復元用）』。
※ Paper 1 で減点される 2 大ミス：①「途中行を省略して最終結果だけ書く」、②「前頂点を記録せず経路復元できない」。両方を丁寧に書く訓練が必要。
Dijkstra の限界：負の重みを持つ辺があると正しく動作しません（負の閉路では発散）。負の重み対応には Bellman-Ford アルゴリズムが必要ですが、これは AI HL シラバス外。AI HL では『負の重みなし』を確認してから Dijkstra を適用するのが鉄則。
最小全域木（Minimum Spanning Tree、MST）は『全ての頂点を結び、辺数が最小（= 頂点数 − 1）で総重みが最小の木』。電線・水道・通信網などの最小コスト敷設問題に直結します。
1 つの頂点から木を成長させる。各ステップで『現在の木に隣接する辺』の中から最小重みを選ぶ。木が常に連結を保つため、閉路チェックは不要。隣接行列で実装しやすく、密グラフに向く。
辺を 1 つずつ選ぶ。閉路判定（追加で同じ連結成分が結ばれるか）が必要だが、Paper 1 の手計算ではグラフ図を見れば閉路が見えるため簡単。疎グラフに向く。辺数 = 頂点数 − 1 になった時点で終了。
アルゴリズムによって構築順序や経路は異なるが、最終的な MST の総重みは同じ。AI HL Paper 1 では『MST の総重みを求めよ』と問われ、どちらのアルゴリズムを使ってもよい。
現実問題への応用：都市間道路・電気網・通信網・上下水道網の最小コスト設計。AI HL IA でも頻出のテーマ。マレーシアでは地方自治体の通信網敷設計画への応用が考えられる。
MST の現実応用：マレーシア地方部の電力網敷設（高圧線の最小コスト配置）、5G 基地局間の光ファイバー網、上下水道網の最小コスト設計、災害時の避難所間の通信網構築。AI HL IA では『マレーシアの離島間の通信網最適化』のようなテーマで MST + Dijkstra を組合せると高得点。
Voronoi 図は『平面上のサイト集合から各点が最も近いサイトの領域に分割した図』。SL も HL も範囲で、現実応用が極めて広く、AI HL IA の定番テーマです。
各サイトについて『そのサイトが最も近い点の集合』を 1 つの領域とする平面分割。各境界は隣接サイト間の垂直二等分線の一部。AI HL では 3-5 サイトの図を手描きで作成する問題が頻出。
Paper 2 では座標が与えられて『境界線の方程式を求めよ』と出題。中点を通り、PQ の傾きの負の逆数を傾きとする直線の方程式を立てる。Coordinate Geometry の知識が直接使われる。
Voronoi 図を作れば、任意の点について『どのサイトが最も近いか』が領域から即判別できる。配送拠点の割当・店舗の商圏分析・分類問題（kNN の k=1 版）に応用。
新規出店・基地局増設の最適位置は『現在の Voronoi 図で最大の空円を持つ点』。AI HL Paper 3 で『次の店舗をどこに置くべきか』のような応用問題として出題。マレーシアでは Starbucks や Family Mart の出店戦略への応用が題材になる。
AI HL のテキストブックでよく登場する例題。各サイトのサービス領域の面積、最も需要が高そうな領域、領域の偏りなどを分析する。Paper 1 / Paper 2 で出題範囲。
2 サイト P(x_1, y_1) と Q(x_2, y_2) の境界は PQ の垂直二等分線。
※ 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 HL の 3 つの Paper はそれぞれ 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 の垂直二等分線の知識を直接使う。
隣接行列の入力と行列のべき乗（A^k で長さ k の経路数）、座標による Voronoi 境界線の方程式計算、GDC を使った重み付きグラフのデータ処理、ネットワーク最適化問題（コスト最小化・時間最小化）
GDC で行列演算を活用。TI-Nspire CX II の Matrix 機能で A、A²、A³ を高速計算し、経路数を即答する。Voronoi の境界線方程式は手計算（中点・傾き・直線の方程式）と GDC の Graph 機能を併用。
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 つずつ表に整理』が決定的。
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 を狙う）：
過去問の入手先：IBO 公式の Past Papers は学校経由で配布されるのが正規ルート。マレーシア IB 校（MKIS / GIS / ISKL / Sayfol 等）では Math Department が在校生に提供します。塾経由の入手や非公式の過去問サイトは Copyright 違反のリスクがあるため避ける。南数塾では学校から正規入手した過去問の解答解説 + 採点フィードバックを提供しています。
AI HL Graph Theory の頻出概念・技法を 30-60 秒で復習する Shorts コンテンツ。試験前の最終確認に。
南数塾は AI HL の Graph Theory 章に特化した個別カリキュラムを提供。マレーシア IB 校（MKIS / GIS / ISKL 等）の DP 1-2 生徒の Graph 6 → 7 引き上げ実績があります。
※ 本記事は 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 で必ず確認してください。
お子様の現在の Graph Theory の習熟度（Eulerian / Hamiltonian の判定 / Dijkstra / MST / Voronoi の到達度）を診断し、Year 12-13 の 2 年間で Grade 7 を狙う個別カリキュラムをご提案します。Computer Science / Urban Planning / Logistics 系大学進学を見据えた IA テーマ選定もサポート。無料体験授業 + 三者面談（生徒・保護者・講師）にて。
無料相談に申し込む