将图划分为边对的算法

Question

我接到了一项任务，要找到一种算法，将图 G(V,E) 分成成对的相邻边(为图着色，使得每对相邻边都具有相同的颜色)。

我试图通过绘制一些随机图表来解决这个问题，并得出了一些结论:

1. 如果一个顶点连接到 2(4,6,8...) 个度数为 1 的顶点，则这些顶点构成一对边。
2. 如果度数为 1 的顶点直接连接到环，则环的哪条边与单独的边配对都没有关系。

但是，我无法得出任何其他结论，所以我尝试了另一种方法。我考虑过使用 DFS，找到连接点并将图划分为边数为偶数的子图，因为这些子图也应该可以按此规则划分，依此类推，直到我最终只得到 |E(G')| 的子图。 = 2.

我想到的另一件事是创建图形 G'，其中 E(G) = V(G') 和 V(G) = E(G')。这样我就可以得到一个图，我可以在其中通过 DFS 或始终从叶顶点及其相邻顶点开始删除成对的顶点(以前的边)。

最后一种技术最吸引我，但它似乎是最慢的一种。非常感谢任何有关这些方法中哪种方法最好的反馈或提示。

编辑:换句话说，将图表想象成一个城镇的布局。顶点是十字路口，边是道路。我们想对每条道路装饰(扫描、着色)恰好一次，但是我们只能同时装饰两条相连的道路。我希望这有助于澄清。

例如，具有 E={ab,bd,cd,ac,ae,be,bf,fd} 的图 G，一种可能的对组合是 P={{ab,bf},{ac,cd} ,{ae,eb},{bd,df}}。

Answer 1

一种方法是构造一个新图 G，其中:

1. G中的一个顶点对应原图中的一条边
2. G 中的一条边连接 G 中的顶点 a 和 b，其中 a 和 b 表示原始图中的边在原始图中的一个顶点处相交

然后，如果我没有正确理解原来的问题，G 的目标就是找到最大匹配，这可以通过例如 Blossom algorithm 来完成。 .