グラフアルゴリズム

概要

graph search・状態グラフ・推移閉包の後に方向別grid scanを置き、探索と局所的な状態伝播を続けて学ぶ。二部構造・連結性・最短路・有向構造・関数グラフ・全域木・lowlinkで標準的なgraph toolkitを揃える。Euler trailの次数条件と偶奇部分グラフの後に、二部matching・max-flow/min-cutへの標準的な帰着を学ぶ。続いてgraph core・cycle spaceを扱い、単調path縮約・near-tree kernel化・有向walk周期へ進む。lower-bound flow・min-cost flow・weighted bipartite matchingは発展的なflowとして後半に置き、planar duality・path matching contraction・一般重み付きmatchingで締めくくる。

グラフモデルと構造

対象を頂点・辺・木・有向遷移として構造化する。

考え方

関係を頂点と辺へ写したら、向き、重み、状態に必要な情報を確認する。探索・連結性・最短路・有向構造の基本を揃え、経路の存在から流量・matching・閉路の線形構造へ広げる。

成立条件と計算量

V頂点E辺の明示的な構築だけでもO(V+E)が必要。暗黙の状態グラフでは元入力より状態数が大きくなるため、遷移生成の総数を見積もる。各節で必要な構造を確認し、graphという形式だけから算法を決めない。

章の構成

項目は各章の読書順に並べています。親子関係は順序と独立しているため、階層を字下げで表さず、子Unitには「概念上の親」を示します。導入項目は関連手法の見取り図で、発展的なUnitは対象色を目安に後から戻って学べます。

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

導入対象の目安: 緑色(800–1199)。状態と遷移を頂点と辺で表し、距離・連結性・向きの違いを整理する入口。

対象色の読み方は本書の読み方を参照してください。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-chapter-graph

習得する技能

  • 対象を頂点と辺に対応させ、利用するグラフ性質を示せる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

対象を頂点と辺へ写して到達可能性を扱えるようにし、連結性・最短路・木・フローへ進む土台を作る。

このUnitでは扱わないもの

  • なし

根拠