経路,閉路,フロー

グラフの主な問題はナビゲーションである.特に,迷路からの出口を見付けたり,道路網をナビゲーションしたり等の,2つの頂点間の最短経路を求める問題である.最短経路の長さにより,グラフの直径等の大きさ等,自然の大きさの全コレクションが生じる.一つの頂点から別の頂点へナビゲートする代りに,何らかの方法でグラフ全体を走査したい場合は,閉路を探す.オイラー(Eulerian)閉路,ハミルトン(Hamiltonian)閉路,ポストマン閉路はグラフの全辺,または全頂点を走査する経路を提供する.

参照項目参照項目

最短経路

FindShortestPath ソースからターゲットまでの最短経路を求める

ShortestPathFunction グラフの最短経路を与える関数を表す

フロー

FindMaximumFlow 2つの頂点間の最大フローを求める

FindMinimumCostFlow 最小費用フローを求める

OptimumFlowData 最適フローデータを表す

距離

GraphDistance 2つの頂点間の最短経路の長さ

GraphDistanceMatrix 頂点の全ペア間のグラフ距離の行列

最長,最短経路

VertexEccentricity 他のすべての頂点への最長最短経路

GraphRadius 頂点の最小離心率

GraphDiameter 頂点の最大離心率

GraphCenter 最小離心率の頂点

GraphPeriphery 最大離心率の頂点

位相的経路

TopologicalSort グラフの位相に対応する順に頂点を与える

閉路と順路

FindPostmanTour 各辺を少なくとも1回ずつ横切る順路を求める

FindEulerianCycle 各辺を厳密に1回ずつ横切る閉路を求める

FindHamiltonianCycle 各頂点を厳密に1回ずつ横切る閉路を求める

EulerianGraphQ ▪ HamiltonianGraphQ

New to Mathematica? Find your learning path »
Have a question? Ask support »