yaksha's blog

Euler Path on directed graphs?!
By yaksha, history, 6 years ago, In English

Hi, I was solving a problem and it required printing euler path on a directed graph Now,I was unaware of the how to do euler path finding on a directed graph, I tried to search on google but no luck..

What exactly are the conditions that are to be fulfilled to KNOW that a euler path exists and also what are ways to print it... I know of "Fleury’s Algorithm" , but as far as I know (and I know little), this algo is for directed graphs only.. Also came to knew about " Hierholzer’s Algorithm" but this also seems to be working on undirected graphs..

The problem that I was attempting -- 508D - Tanya and Password

The editorial of this problem mentions some points regarding finding euler path on directed graphs but it's not very clear and provides no explanation...

Please can some one help me and also possibly provide me with resources where I can study this?!

Have a nice day!

  • Vote: I like it
  • +15
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

For directed graphs the condition is that all vertices are in one strongly connected component (you can reach every vertex from every other) and the in-degree must be euqal to the out-degree for every vertex.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Hi, Sorry but I went to this site to look for help earlier before asking this question, website

    Here it says that the 2 conditions you mentioned are requirement for a Euler Cycle.. In the problem i was attempting , there is only a requirement of Euler path and not cycle in directed graph,please clear my misunderstanding..

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Eulerian Path criterion is the same, except two vertices v, w such that and

      Also

      all vertices are in one strongly connected component

      More precisely, all non-isolated vertices

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 4   Vote: I like it +10 Vote: I do not like it

        I am sorry , I didnt get the exact conditions!.. I get that it is ALLOWED to have at most one vertex with in_deg — out_deg = 1

        and it's also ALLOWED to at most one vertex with out_deg — in_deg = 1

        all other vertices must have in_deg == out_deg,

        but , The last condition "all non isolated vertices must be in a SCC" feels like it's a necessary thing to have if we want Euler cycle, it seems to me that it's not very necessary for a Euler path...

        This graph for example ..

        1 --> 2 --> 3 --> 4

        does not have all the vertices in one SCC but is obviouly a Euler path..

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it +3 Vote: I do not like it

          Digraph must have both 1 and (-1) vertices (Eulerian Path) or none of them (Eulerian Cycle).

          Last condition can be reduced to "all non-isolated vertices belong to a single weakly connected component" (see yeputons' comment below).

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks! and what you pointed out about (1) and (-1) is GREAT , and obviously true because of SUM(in_degree) = SUM(out_degree) in graph,

            Thanks for the help :)

            Can you provide some resources to know more,from where do these conditions come from , perhaps a proof , or some readings, where did you study this from etc.

            → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it 
        all vertices are in one strongly connected component

        I believe there is a simpler constraint: if one removes "directness" of edges, then the graph without isolated vertexes should be connected.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          yeputons, This feels right and is consistent with examples I could come up with.. So you came up with this through intuition or are there any resources I could read up to understand this , there is a lot of confusion regarding this in my head,..

          Thanks for the tip tho , it seems to work!

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Well, the proof I know simply doesn't require strong connectivity. It goes like this: let's take an arbitrary vertex v and start building a cycle from it, on each iteration we go through an edge which we haven't visited yet. At some point, we're unable to do so. Note that it can happen only if we're standing in the vertex v, otherwise the vertex would different number of incoming/outgoing edges. So, we have a cycle. Now pick up another vertex, etc, until all edges of the graph are visited.

            So we ended up with several cycles which cover all edges of the graph exactly once. Note that if we have cycle C1 and C2 which have at least one vertex x in common, we can merge these two cycles into one. Now, as the graph is weakly connected, we can merge all of our cycles together.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              should'nt we start from the one vertex with out_degree = in_degree + 1 (if there is one , if not start from any) .. either this vertex gives the Euler path or NO vertex can give euler path

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                6 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                That's right if we're looking for an Euler path, not Euler tour.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years ago, # ^ |
                    Vote: I like it -8 Vote: I do not like it

                  What's for this case? 3 1 1 2

                  Here it opposes connectivity. So, no eulerian path and Cycle right?

                  → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That is for Euler circuit. Can you please tell the condition for Euler path in directed graph?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Check my submission 77697447, it's a solution the problem referenced above. I've also added a comment for the condition of existence of an Euler path in a directed graph, along with the book reference.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does Fleury's algorithms work in directed graph if we consider the underlying undirected graph while finding bridge?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes , Fluery's algorithm works on both directed and undirected graphs, and yes we do consider given edges as undirected when finding bridge.

    → Reply
»
3 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Simplified Condition : A graph has an Euler circuit if and only if the degree of every vertex is even.

A graph has an Euler path if and only if there are at most two vertices with odd degree.

→ Reply