このページは下書きです。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 法と共に用いられることが多い。