Eulerian digraph

E824091

directed graph graph theory concept

An Eulerian digraph is a directed graph in which every vertex has equal in-degree and out-degree, allowing for a closed trail that traverses each edge exactly once.

Try in SPARQL Jump to: Statements Referenced by

Statements (45)

Predicate	Object
instanceOf	directed graph ⓘ graph theory concept ⓘ
contrastsWith	Hamiltonian digraph ⓘ
decisionProblemComplexity	linear time in number of vertices plus edges ⓘ
definedOn	directed multigraphs (possibly with parallel arcs) ⓘ
equivalentTo	directed graph with a closed Eulerian trail ⓘ directed graph with an Eulerian circuit ⓘ
generalizes	Eulerian graph (undirected) NERFINISHED ⓘ
hasAlgorithm	Fleury’s algorithm adapted to directed graphs NERFINISHED ⓘ Hierholzer’s algorithm to find an Eulerian circuit NERFINISHED ⓘ
hasDecisionProblem	testing whether a given digraph is Eulerian ⓘ
hasEdgeTraversal	Eulerian circuit starts and ends at the same vertex ⓘ Eulerian circuit traverses each directed edge exactly once ⓘ
hasGlobalCondition	strong connectivity of non-isolated vertices ⓘ
hasHistoricalOrigin	generalization of Euler’s Königsberg bridges problem to directed graphs ⓘ
hasLocalCondition	balance of flow at each vertex ⓘ
hasNecessaryAndSufficientCondition	strongly connected after removing zero-degree vertices and in-degree(v)=out-degree(v) for all v ⓘ
hasProperty	admits a closed trail using each edge exactly once ⓘ admits an Eulerian circuit ⓘ any Eulerian circuit induces a cyclic ordering of incident edges at each vertex ⓘ any Eulerian digraph is balanced at every vertex ⓘ any strongly connected balanced digraph is Eulerian ⓘ edge set can be partitioned into directed cycles ⓘ every edge lies on some Eulerian trail ⓘ every vertex has equal in-degree and out-degree ⓘ removing edges of an Eulerian circuit leaves a union of Eulerian digraphs (possibly empty) ⓘ
implies	every vertex has even degree in the underlying undirected graph ⓘ existence of a decomposition of edges into directed cycles ⓘ
mayAllow	loops ⓘ
relatedTo	Eulerian circuit ⓘ Eulerian trail ⓘ semi-Eulerian digraph ⓘ
requiresCondition	each vertex with nonzero degree lies in a single strongly connected component of the underlying digraph ⓘ every vertex with nonzero degree belongs to the same weakly connected component ⓘ in-degree(v) = out-degree(v) for every vertex v ⓘ underlying undirected graph is connected when ignoring isolated vertices ⓘ
studiedIn	Eulerian graph theory ⓘ algorithmic graph theory ⓘ
usedFor	designing closed walk tours in directed networks ⓘ modeling conservation laws in flow networks ⓘ
usedIn	DNA sequencing by Eulerian paths ⓘ circuit design ⓘ network routing ⓘ postman problems ⓘ route planning problems ⓘ

Referenced by (1)

Full triples — surface form annotated when it differs from this entity's canonical label.

de Bruijn–van Aardenne–Ehrenfest theorem → concernsProperty → Eulerian digraph ⓘ