Stack Overflow
Stack Overflow

Questions tagged [euler-path]

For a finite graph, walk every edge exactly once with the start and end node being the same.

References:

Wikipedia
Wolfram

Related tags:
graph-theory not graph
hamiltonian-path
hamiltonian-cycle
transitive-closure

21 questions
69
votes
9 answers

Difference between hamiltonian path and euler path

Can some one tell me the difference between hamiltonian path and euler path. They seem similar!
mousey
  • 11,601
  • 16
  • 52
  • 59
17
votes
5 answers

Looking for algorithm finding euler path

I'm looking for an algorithm to find an Euler path in a graph. I've seen a good one a couple of weeks ago but I can't find it now, I remember there was tagging edges, something with even/odd connections... Do you know a similar, simple and…
user2489034
  • 239
  • 2
  • 3
  • 15
3
votes
2 answers

Is there a counter-example for this algorithm finding the Euler Path in a Eulerian Graph?

The following is the given algorithm for finding a Euler Path in a Eulerian Graph. However, it is said that there is an counter example with less than 10 vertices. The given Eulerian Graph is undirected and every vertex has even degree and it will…
swordgit
  • 115
  • 10
2
votes
1 answer

Route Inspection of Directed Graph in ASP

For the multidirected graph below I am trying to write an program that visits all edges at least once. For instance, in the below graph I am looking for an outcome similar to "edge(1,2), edge(2,3), edge(3,1), edge(1,2), edge(2,4), edge(4,5),…
john_ny
  • 173
  • 8
1
vote
1 answer

Euler Circuit in a Directed Graph

How to check if a directed graph is eulerian? 1) All vertices with nonzero degree belong to a single strongly connected component. 2) In degree is equal to the out degree for every vertex. Source: geeksforgeeks Question: In the given two…
Ashutosh Rana
  • 123
  • 9
1
vote
1 answer

How to generate level for a game

I'm making a game of line. I have some points and some lines connect them. When player first touch at 1 point the point is marked as "Choosed". Then player touch another point, if there a line connect them the line will be disappear and the second…
Kẻ Xấu Xa
  • 11
  • 3
0
votes
0 answers

Blender Export to gITF format loses Rotation transform setting XYZ Euler switches to Quaternion instead

On exporting from Blender to gITF 2.0 format the rotation Transform setting goes to Quaternion WXYZ instead of staying XYX Euler. Let me know if there is way around. Expecting on Export from Blender to giTF format to retain rotation Transform…
user21949649
  • 1
  • 2
0
votes
0 answers

how to convert vertices degree

For a project I am doing I need to simplify a mesh, so all the vertices are going to be either of 2 or 4 degrees (which means that on every vertex only 2 or 4 edges are meeting, but not any other amount) I was wondering if there is a possability to…
Maria
  • 1
  • 1
0
votes
0 answers

Can a Euler cycle be made from a one-vertex graph?

I have the following question that I must prove or disprove: Let =(,)be an undirected connected graph. Let be the minimum amount of edges one needs to add to G so that the resulting graph has an Euler cycle. Then x≤floor(n/2) when n=the number of…
liatkatz
  • 51
  • 5
0
votes
0 answers

Visit all edges in a graph with minimum number of paths

I am trying to find an algorithm or a way to find paths in a directed graph to visit all edges exactly once with minimum number of paths possible. Then, print the results found. For example in this graph, the minimum number of paths to cover all…
Lulu
  • 1
  • 2
0
votes
0 answers

Incorrect output for covering all graph edges

I need to cover all the edges of a graph with the minimum number of paths. I read that the Eulerian path method is needed here. I tried to reproduce it, but it doesn't work correctly. def split_graph(graph, n): stack = [] path = [] …
Lib
  • 29
  • 5
0
votes
0 answers

Reconstruct a string from n continuous substrings of fixed length

I have as input a list of n+2 continuous substrings of length 3. My goal is to find out whether there exists a string of length n such that all its continuous substrings of length 2 are exactly the input list that I have been given. How can I…
julius
  • 1
  • 2
0
votes
0 answers

T(1.2): subscripts must be either integers 1 to (2^63)-1 or logicals

So, these problem appears when I try to run my code in Octave: * T(1.2): subscripts must be either integers 1 to (2^63)-1 or logic I try an euler method to study and here's my code function fxy = fa(x,y) % fa merupakan fungsi persamaan…
439 767_NINDYA KARISSA TK
  • 1
  • 1
0
votes
2 answers

i made Eulerian path algorithm(Euler-path). what's the problem?

I made an Eulerian path algorithm, what's the problem? #include #include #include #include using namespace std; int graph[1000][1000]; // 1…
yoons
  • 15
  • 6
0
votes
1 answer

Implementing Euler Tour in Python

I am trying to implement the following Euler Tour in Python. However, I am stuck on storing the top values. My code implementation is: def rmq(root, level, prev=None): if not root: return True euler.append(root.data) …
Tanmay
  • 23
  • 1
  • 7
1
2