 |
SOLUTIONS
|
経路，閉路，フロー
グラフの主な問題はナビゲーションである．特に，迷路からの出口を見付けたり，道路網をナビゲーションしたり等の，2つの頂点間の最短経路を求める問題である．最短経路の長さにより，グラフの直径等の大きさ等，自然の大きさの全コレクションが生じる．一つの頂点から別の頂点へナビゲートする代りに，何らかの方法でグラフ全体を走査したい場合は，閉路を探す．オイラー(Eulerian)閉路，ハミルトン(Hamiltonian)閉路，ポストマン閉路はグラフの全辺，または全頂点を走査する経路を提供する．
参照項目参照項目
最短経路
FindShortestPath — ソースからターゲットまでの最短経路を求める
ShortestPathFunction — グラフの最短経路を与える関数を表す
フロー
FindMaximumFlow — 2つの頂点間の最大フローを求める
FindMinimumCostFlow — 最小費用フローを求める
OptimumFlowData — 最適フローデータを表す
距離
GraphDistance — 2つの頂点間の最短経路の長さ
GraphDistanceMatrix — 頂点の全ペア間のグラフ距離の行列
最長，最短経路
VertexEccentricity — 他のすべての頂点への最長最短経路
GraphRadius — 頂点の最小離心率
GraphDiameter — 頂点の最大離心率
GraphCenter — 最小離心率の頂点
GraphPeriphery — 最大離心率の頂点
位相的経路
TopologicalSort —グラフの位相に対応する順に頂点を与える
閉路と順路
FindPostmanTour — 各辺を少なくとも1回ずつ横切る順路を求める
FindEulerianCycle — 各辺を厳密に1回ずつ横切る閉路を求める
FindHamiltonianCycle — 各頂点を厳密に1回ずつ横切る閉路を求める
