并行访问图形边缘的算法？

Question

引用图:

我正在编写一个程序来测试图形的所有边。当且仅当它们不共享公共(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 站点。

Answer 1

这个问题是边缘着色:https://en.wikipedia.org/wiki/Edge_coloring

如果您为图表的边缘着色，使得没有两条相邻的边缘具有相同的颜色，那么您可以对每种颜色执行一个循环，平行测试该颜色的所有边缘。

不幸的是，找到具有最少颜色数的着色是 NP-hard。