道路 (图论) 编辑
在图论中，一个图中一条道路是一个顶点序列，使得从它的每个顶点有一条边到该序列中下一顶点。一条道路可能是无穷的，但有限道路有一个最先顶点，称为起点，和最后顶点，称为末点。两者都成为这条道路的端点。道路中其它顶点成为内点。一个圈是起点与末点相同的道路。注意到一个圈中起点的选取是任意的。
4
图片 0 图片
评论 0 评论
匿名用户 · [[ show_time(comment.timestamp) ]]
[[ nltobr(comment.content) ]]
相关
在图论中，环是一条只有第一个和最后一个顶点重复的非空道路。一个没有环的图被称作无环图，一个没有有向环的有向图被称做有向无环图。一个无环的连通图被称作树。
在图论和理论计算机科学中，最长路径问题是指在给定的图中找出长度最长的道路。一条不具有任何重复顶点的路径被称为简单路径。无权图中路径的长度就是边的数量，而有权图中路径长度是边权重之和。不同的是，与此相反的最短路问题可以在多项式时间内解决。而最长路径问题是NP困难的，这意味着除非P/NP问题，否则对应于任意的图，没有办法在时间复杂度内解决该问题。更强的困难结果表明这个问题也是近似算法的。但是，有一个线性时间的方法可以用于有向无环图，这对于发现调度问题中的关键路径有重要的作用。
在图论中，环是一条只有第一个和最后一个顶点重复的非空道路。一个没有环的图被称作无环图，一个没有有向环的有向图被称做有向无环图。一个无环的连通图被称作树。