visual-learning
グラフ理論 インタラクティブ可視化
「頂点と辺のつながり方」が決める構造を、頂点をドラッグ・クリックして体感できる POC 集。 彩色・一筆書き・平面性から、マッチング・中心性・ランダムグラフの相転移までを扱います。
visual-learning シリーズ：情報系アルゴリズム・線形代数・数学を含む全分野は
シリーズ一覧 からたどれます。最短路・MST などのアルゴリズム手順は
情報系アルゴリズム 側にあり、本分野はグラフの構造・性質に焦点を当てます。
構造と不変量
次数
握手補題と次数列
辺を足すと両端の次数が+1。Σ次数=2E、奇数次数の頂点数は偶数。
開く →
平面性平面グラフとオイラーの公式
頂点・辺・面を数え、V−E+F=2 を確認。辺を1本足すと面が1つ増える。
開く →
同型グラフ同型（同じ構造を見抜く）
2つのグラフの頂点を対応づけて同型か判定。次数列など不変量を比較。
開く →
彩色と路
彩色
グラフ彩色（隣接は別色）
頂点クリックで色を変更、競合辺を検出。貪欲彩色と彩色数、平面の四色定理。
開く →
一筆書きオイラー路（一筆書きの条件）
各頂点の次数の偶奇から一筆書き可否を判定。ケーニヒスベルクの橋も。
開く →
ハミルトンハミルトン閉路（全頂点を1回）
頂点クリックで巡回路を作り、ハミルトン閉路か判定。全探索で有無も。
開く →