路径、圈和流

图的一个关键问题是导航. 尤其是找到两个顶点的最短路径,无论是找到迷宫的出口或公路网的导航. 最短路径的长度引起了自然测量的所有收集诸如图的直径. 如果不只是从一个顶点到另一个顶点的导航,您想以某种方式遍历整个图,您在寻找圈,那么欧拉与哈密尔顿圈提供了遍历图的每条边或顶点的路径.

参考资料参考资料

最短路径

FindShortestPath 求从源到目标的最短路径

ShortestPathFunction 表示一个给出图中最短路径的函数

FindMaximumFlow 求两个顶点之间的最大流

FindMinimumCostFlow 求最小代价流

OptimumFlowData 表示最优流数据

距离

GraphDistance 两个顶点间最短路径的长度

GraphDistanceMatrix 所有顶点对间的距离矩阵

最长最短路径

VertexEccentricity 到每个其它顶点的最长最短路径

GraphRadius 最小顶点离心率

GraphDiameter 最大顶点离心率

GraphCenter 具有最小离心率的顶点

GraphPeriphery 具有最大离心率的顶点

拓扑路径

TopologicalSort 给出为了与图拓扑相兼容的顶点

圈和路径

FindPostmanTour 求遍历每条边至少一次的路径

FindEulerianCycle 求一个遍历每条边一次的圈

FindHamiltonianCycle 求一个遍历每个顶点一次的圈

EulerianGraphQ ▪ HamiltonianGraphQ

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