引用图:
我正在编写一个程序来测试图形的所有边。当且仅当它们不共享公共(public)节点时，程序才能并行测试图的边。我的问题来自这样一个事实，即我还必须可以选择不以最有效的方式测试边缘。
如果测试上图中平行边的最有效选择，边 AB , DE , 和 CF都可以并行测试第一个周期，然后是AD , BC , 和 EF在第二个。这只留下 BE离开第三个周期。
如果我一次只能处理两条平行边，那么我可以通过多种方式访问这些边，其中一些方式比其他方式更有效。例如:
AB和 CF可以首先访问，然后是 BC和 AD .这留下了BE , DE , 和 EF每次测试一个，总共 5 个周期。这比访问 AB 效率低和 DE首先，BC和 EF第二，AD和 BE第三，用CF作为总共 4 个周期的最终边缘。
是否有一种算法或实践可以用来找到以这种方式访问图的最有效路径？我的图表具有可变大小和连接性，因此即使我愿意，我也无法亲自解决和规划它们。
任何帮助或指导将不胜感激。自从上过图论课以来已经有一段时间了，所以我不记得是否存在这种性质的东西。我目前正在从理论上解决这个问题，还没有开始尝试在这方面实现任何类型的编程。因此，如果我的问题更好地指向其他地方，我会非常乐意将我的问题移至相关的 Stack Exchange 站点。
最佳答案
这个问题是边缘着色:https://en.wikipedia.org/wiki/Edge_coloring
如果您为图表的边缘着色，使得没有两条相邻的边缘具有相同的颜色，那么您可以对每种颜色执行一个循环，平行测试该颜色的所有边缘。
不幸的是，找到具有最少颜色数的着色是 NP-hard。
关于并行访问图形边缘的算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47100940/