All Questions
Tagged with eulerian-path directed-graphs
11
questions
1
vote
1
answer
34
views
Worst Case Solution for directed Chinese Postman Problem
The Problem
Let $G$ be a directed graph with $n$ vertices. How long is a shortest circuit that visits every edge in the worst case? That is how long is the solution to the directed Chinese Postman ...
- 11
-1
votes
1
answer
43
views
What are necessary and sufficient conditions to have a negative cycle in a directed graph with some negative edges? [closed]
Trying to test Johnson’s algorithm with over 100 vertices but it doesn’t work if there is a negative cycle. So I’m trying to write code to construct graphs with some negative weights (about 10% of the ...
- 35
3
votes
1
answer
190
views
How many ways of traversing every arc of a complete digraph exactly once from a given starting vertex are there?
Given a set of $n$ states $V = \{ s_1, s_2, \ldots, s_n \}$, and a complete digraph $G = (V, A)$ where $A = \{ (a,b) \mid (a,b) \in V^2\; \text{and}\; a \neq b \}$, I'm interested in finding cyclic ...
0
votes
1
answer
35
views
Show that this graph is a tree
Suppose we have a directed multigraph (a graph with loops and parallel edges), with vertex set $V=\{v_1,v_2,\cdots,v_n\}$, such that $d^+(v_i)=d^-(v_i)$ for every $i=1,2,\cdots,n$, i.e. indegree of ...
- 12.7k
0
votes
0
answers
36
views
Can a Graph be Proven to be Directional?
Here's a line from my textbook that I'm having trouble understanding:
Let $G$ be a simple graph with $n$ vertices and $m$ edges. If $G$ is
undirected then then $m\leq \frac{n(n-1)}{2}$, and if $G$ is ...
- 77
2
votes
0
answers
37
views
Digraphs with exactly one Eulerian Tour
I’ve been thinking about the following problem from Richard Stanley’s list of bijective proof problems (2009). There, this problem is said to lack a combinatorial solution. The problem is the ...
- 21
1
vote
1
answer
441
views
How can I solve the Rotating Drum problem for 64 segments? (Or at all)
For clarification, I am very bad at maths and the logic usually goes right over my head, however I am studying a reasonably high level of maths because I am a software and game development student.
I ...
2
votes
1
answer
71
views
Upper bounds on the solution to a directed route inspection problem
If for any strongly connected digraph $D$ we define $\lambda(D)$ to be the length of any shortest closed walk traversing every arc in $D$, then does there exist some constant $m\in\mathbb{R}$ such ...
- 10.6k
2
votes
1
answer
2k
views
How to find Eulerian path in the given graph?
I have plotted the following graph (was given by the adjacency matrix):
And I have to find the Eulerian path there and emphase this.
I am concerned because my book says that the further action ...
- 2,672
0
votes
1
answer
5k
views
What are the necessary and sufficient conditions for Euler path in directed graph?
The definition says
"A directed graph has an eulerian path if and only if it is connected and each vertex except 2 have the same in-degree as out-degree, and one of those 2 vertices has out-degree ...
- 291
7
votes
2
answers
4k
views
Does Eulerian cycle in digraph really need strongly connected component?
I read that a directed graph has an Eulerian cycle if and only if every vertex has equal in degree and out degree, and all of its vertices with nonzero degree belong to a single strongly connected ...
