経路（グラフ）
けいろ ／ 道 ／ パス ／ 経路 1対1で対応path
名詞 ・話し言葉・書き言葉
定義
グラフで、辺でつながった頂点を順にたどる道筋のうち、同じ頂点を 2 度通らないもの。
In a graph, a route along edges from vertex to vertex that does not visit any vertex twice.
例文
話し言葉 Is there a path from A to F? Follow the edges and see. A から F への経路はあるか。辺をたどって確かめよう。
書き言葉・答案 Find the shortest path from vertex A to vertex F. 頂点 A から頂点 F への最短経路を求めよ。
言い間違えやすいところ
- 同じ頂点を何度通ってもよいものは walk（歩道）と呼び分ける（Levin）。
- Nicholson（2.3 Matrix Multiplication）は、頂点をくり返してよい道も path（長さ r の r-path）と呼び、隣接行列の累乗で数える（Levin の walk に当たる）。