1
$\begingroup$

Assume that G is a connectable undirected graph, what is the best algorithm in terms of complexity, that check if graph G can have an Eulerian cycle by adding edges?

I thought of their two cases

  • G graph with odd number of vertices- then for sure it can have an Eulerian cycle becouse it is possible to transform the graph into a Clique by adding edges then the degree of all the edges is even - therefore the graph have an Eulerian Cycle
  • G is graph with even number of vertices, therefore there is even number of vertices with odd degree and by connecting them in pairs, it is possible to transform the graph into even degree graph, then it for sure have a Eulerian Cycle. there is only one special case when there is a vertex that is connect to all the other vertices then, in such case it will be impossible to force the graph to have Eulerian Cycle

according to this prove i assume that the following algorithm that run in complexity of O(V), can check if graph can have Eulerian Cycle by adding edges

public static boolean hasCycle(ArrayList<Integer>[] graph){
    if(graph.length % 2 == 1)
        return true;

    for(ArrayList<Integer> vertex: graph) {
        // checking if the edge is connect to all the other vertex
        if (vertex.size() == graph.length - 1)
            return false;
    }

    return true;
}

the prove is correct? and what about the algorithm is also correct?

update

according to the answer i conclude that the following algorithm may work

public static boolean canHaveEualerenCycle(ArrayList<Integer>[] graph) {

    if(graph.length % 2 == 1)
        return true;

    Map<Integer, Set<Integer>> copy = new HashMap<>();

    for (int i = 0; i < graph.length; i++) {
        if (graph[i].size() % 2 == 1) {
            copy.put(i, new HashSet<>());
        }
    }

    // reveresing the graph odd vertex only
    for(Map.Entry<Integer, Set<Integer>> entry : copy.entrySet()) {
        entry.getValue().addAll(copy.keySet());
        entry.getValue().remove(entry.getKey());
        entry.getValue().removeAll(graph[entry.getKey()]);
    }


    // try to connect possible match of odd degree vertexes
    while (!copy.isEmpty()) {
        Map.Entry<Integer, Set<Integer>> entry = copy.entrySet().iterator().next();
        Set<Map.Entry<Integer, Set<Integer>>> edges = copy.entrySet();
        int vertexA = entry.getKey();

        if (!entry.getValue().isEmpty()) {
            int vertexB = entry.getValue().iterator().next();

            // vertexB is even degree now it is not an option any more
            for(Integer v : copy.get(vertexB)) {
                copy.get(v).remove(vertexB);
            }

            // vertexA is even degree now it is not an option any more
            for(Integer v : entry.getValue()) {
                copy.get(v).remove(vertexA);
            }

            copy.remove(vertexB);
            copy.remove(vertexA);
        } else {
            return false;
        }


    }

    return true;
}

but i am not sure 100% i didint find a way to prove that i have to connect odd degrees edges, maybe in a very complex graph it is not true.

$\endgroup$
  • $\begingroup$ You are right, my bad, allready edit the questions, i confused due to the fact that "edge" is also reffer to the "end of something" it is simmeler to a "dot". $\endgroup$ – ido kahana Oct 8 '18 at 19:31
  • $\begingroup$ Yep, the new edit clears it up. To help you keep them straight, while an "edge" refers to the end of something, it usually refers to a long "boundary" type of end: you talk about the edge of the water, the edge of a knife (which is different from the point of the knife!), or the edge of a cliff. For graphs, I think we inherit the words "edge" and "vertices" from talking about polyhedra: a cube, for instance, has eight vertices (the corners) and twelve edges (the boundaries between its six faces). $\endgroup$ – Misha Lavrov Oct 8 '18 at 19:46
0
$\begingroup$

Your algorithm is not always correct: for example, it will give a false positive for the graph below.

enter image description here

Here, the leftmost and rightmost vertices have odd degree, but you can't add an edge between them to fix that, because they already have an edge between them. Adding any other edges would bring one of the other vertices to degree $5$, so there's nothing to be done here.

In the case where $G$ has an even number of vertices, I have another suggestion. Rather than thinking about what edges we can add to $G$ to make all degrees even, think about what edges can be removed from the complementary graph $\overline{G}$ to make all of $\overline{G}$'s degrees odd.

Here, we can focus on each of the connected components of $\overline{G}$ separately. Once you do, there is a simple criterion for dealing with each connected component.

$\endgroup$
  • $\begingroup$ the complexity of just making a reverse graph is O(V*V) there is no better approch? $\endgroup$ – ido kahana Oct 9 '18 at 7:35
  • $\begingroup$ There is no reason to construct the adjacency list of $\overline{G}$; you can use the existing adjacency list of $G$. This approach just has the complexity of however you find connected components. $\endgroup$ – Misha Lavrov Oct 9 '18 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.