如何构造顶点均为偶数度的连通图的任意2-正则分离

Question

TL；DR

如何构造顶点都是偶数度的连通图的任意2-正则分离？合适的算法，数据结构？伪代码？有实际实施吗？

定义

D1：如果图H的每个顶点都有2次，则图H将被称为2-正则。

D2：图G的分离H是从G通过将其一些顶点拆分为多个顶点，并在颠覆之间任意共享入射边而获得的图(见图1(。

问题：我想用Java编写一个程序，来构造顶点都是偶数度的连通图G的任意2-正则分离H(见图2(。

到目前为止我做了什么

我在谷歌上搜索了伪代码和实际实现，但除了以下定理外，我没有发现任何相关的东西："给定一个顶点都是偶数度的连通图G，G的边集可以划分为循环，其中没有两个共享边"。下面还有一个定理的构造性证明。我真的不确定斜体的句子是否等同于我要找的"任意2-规则分离"。不过在我看来还是一样。如能核实，不胜感激。

证明(简而言之(：选择G的顶点u。通过在每一步遍历任何尚未遍历的边，从u开始生成轨迹T。继续这个轨迹，直到我们到达之前遇到的顶点v(v可能与u是同一个顶点，也可能不是(。v的两次出现之间的轨迹边缘必须形成一个循环。将此循环称为C1。如果C1覆盖了G的所有边，那么我们就完成了。否则，从曲线图G中移除形成C1的边，留下曲线图G1。在G1中拾取某个顶点u'。重复与以前相同的过程。生成一个循环C2。如果C2覆盖了G的所有剩余边，那么我们就完成了。否则，从曲线图G1中移除形成C2的边，留下曲线图G2。我们以这种方式继续，直到我们用完了G的所有边。此时，我们有许多循环C1，C2。。。，在它们之间的Ck包含G的所有边，但它们中没有两个具有共同的边。

由于证明是构造性的，我用Java编写了一个程序，遵循证明的一些步骤(请参见generateCycle(((此外，我从图中删除所有遍历的边。我使用图2中所示的图形作为输入。在正确性(某些输出不正确(、复杂性(选择适当的数据结构、算法(、设计等方面仍有改进的空间。同样，正如我之前所说，我不确定这种方法是否总是构造任意2-正则分离。

Graph.java

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class Graph<V> {
    Set<V> vertices = new HashSet<V>();
    Map<V, Set<V>> edges = new HashMap<V, Set<V>>();
    public void addEdge(V v1, V v2) {
        vertices.add(v1);
        vertices.add(v2);
        Set<V> e1 = edges.get(v1);
        if(e1 == null) {
            e1 = new HashSet<V>();
            edges.put(v1, e1);
        }
        e1.add(v2);
        Set<V> e2 = edges.get(v2);
        if(e2 == null) {
            e2 = new HashSet<V>();
            edges.put(v2, e2);
        }
        e2.add(v1);
    }
    public void removeEdge(V v1, V v2) {
        Set<V> e1 = edges.get(v1);
        e1.remove(v2);
        if(e1.isEmpty()) {
            edges.remove(v1);
            vertices.remove(v1);
        }
        Set<V> e2 = edges.get(v2);
        e2.remove(v1);
        if(e2.isEmpty()) {
            edges.remove(v2);
            vertices.remove(v2);
        }
    }
    public Set<V> getNeighbors(V v) {
        return edges.get(v);
    }
}

Main.java

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
public class Main {
    public static <V> ArrayList<V> generateCycle(Graph<V> graph, V start) {
        V current = start;
        ArrayList<V> trail = new ArrayList<V>();
        ArrayList<V> cycle = new ArrayList<V>();
        boolean metBefore = false;
        while (!metBefore) {
            trail.add(current);
            Set<V> neighbors = graph.getNeighbors(current);
            if (neighbors == null) {
                break;
            }
            V next = neighbors.iterator().next();
            graph.removeEdge(current, next);
            current = next;
            int index; // index of first occurrence
            if ((index = trail.indexOf(current)) != -1) {
                metBefore = true;
                for (int i = index; i < trail.size(); i++) {
                    cycle.add(trail.get(i));
                }
                cycle.add(current);
            }
        }
        return cycle;
    }
    public static void main(String... args) {
        Graph<String> g = new Graph<String>();
        g.addEdge("1", "2"); g.addEdge("2", "1");
        g.addEdge("1", "5"); g.addEdge("5", "1");
        g.addEdge("2", "5"); g.addEdge("5", "2");
        g.addEdge("2", "4"); g.addEdge("4", "2");
        g.addEdge("2", "3"); g.addEdge("3", "2");
        g.addEdge("3", "4"); g.addEdge("4", "3");
        g.addEdge("4", "5"); g.addEdge("5", "4");
        g.addEdge("4", "6"); g.addEdge("6", "4");
        g.addEdge("6", "5"); g.addEdge("5", "6");
        List<String> vertices = new ArrayList<String>();
        vertices.add("1"); vertices.add("2"); vertices.add("3");
        vertices.add("4"); vertices.add("5"); vertices.add("6");
        ArrayList<ArrayList<String>> cycles = new ArrayList<ArrayList<String>>();
        for (String v : vertices) {
            cycles.add(generateCycle(g, v));
        }
        System.out.println(cycles);
    }
}

输出：[[2，3，4，2]，[]，[]，[4，5，6，4]，[]，]]

很明显，循环[1，2，5，1]丢失了，因为我在生成轨迹1->2->3->4->2时删除了边缘1-2。输出不正确。

那么，如何构造G的任意2-正则分离？

Answer 1

如果所有顶点都具有偶数阶，则可以创建Eularian路径(http://en.wikipedia.org/wiki/Eulerian_path(。

在eularian路径中，可以拆分多次访问的每个顶点(即具有两条以上的边(。拆分时，请确保图形保持连接。