拡張グラフ

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /tenkei/kakuchou-graph#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /tenkei/kakuchou-graph#noredirect を利用してください。
name
拡張グラフ
short description
拡張グラフとは、もともと与えられたグラフを何らかの方法で拡張したグラフのこと。もともとの頂点の集合 $V$ と時刻の集合 $\lbrace 0, 1, \dots, T - 1 \rbrace$ の直積 $V' = V \times \lbrace 0, 1, \dots, T - 1 \rbrace$ を新しいグラフの頂点集合とすることが多い。たいてい Dijkstra 法と共に用いられることが多い。