Eulerian trail
E467732
An Eulerian trail is a path in a graph that traverses every edge exactly once, possibly revisiting vertices.
Observed surface forms (2)
| Surface form | Occurrences |
|---|---|
| Eulerian circuit | 1 |
| Eulerian path | 1 |
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
graph theory concept
ⓘ
trail in a graph ⓘ |
| algorithmicConstruction |
Fleury's algorithm
NERFINISHED
ⓘ
Hierholzer's algorithm NERFINISHED ⓘ |
| allowsEdgeRepetition | false ⓘ |
| allowsVertexRepetition | true ⓘ |
| alsoKnownAs | Eulerian path NERFINISHED ⓘ |
| complexityDecisionProblem | decidable in linear time in the size of the graph ⓘ |
| contrastWith | Hamiltonian path ⓘ |
| definition | a trail in a graph that traverses every edge exactly once ⓘ |
| differenceFromHamiltonianPath | covers edges instead of vertices ⓘ |
| edgeCoverage | uses every edge of the graph ⓘ |
| edgeMultiplicity | each edge appears at most once in the trail ⓘ |
| endVertexConditionUndirected | if graph has two odd-degree vertices, trail ends at the other odd-degree vertex ⓘ |
| existenceConditionDirectedGraph |
one vertex may have out-degree = in-degree + 1 and one vertex may have in-degree = out-degree + 1
ⓘ
underlying undirected graph is connected (ignoring isolated vertices) and in-degree equals out-degree for all vertices except possibly two ⓘ |
| existenceConditionUndirectedGraph | graph has exactly zero or two vertices of odd degree and all non-isolated vertices lie in a single connected component ⓘ |
| field | graph theory ⓘ |
| generalizationOf | Eulerian circuit ⓘ |
| graphType |
can be defined for directed graphs
ⓘ
can be defined for multigraphs ⓘ can be defined for undirected graphs ⓘ |
| hasEulerianCircuitConditionDirected | in-degree equals out-degree for every vertex and all vertices with nonzero degree lie in a single strongly connected component of the underlying graph ⓘ |
| hasEulerianCircuitConditionUndirected | all vertices with nonzero degree have even degree and lie in a single connected component ⓘ |
| implies | graph is connected in the subgraph induced by edges of the trail ⓘ |
| introducedBy | Leonhard Euler NERFINISHED ⓘ |
| mathematicalArea | discrete mathematics ⓘ |
| mayStartAndEndAtDifferentVertices | true ⓘ |
| mayStartAndEndAtSameVertex | true ⓘ |
| namedAfter | Leonhard Euler NERFINISHED ⓘ |
| property | provides necessary and sufficient degree conditions for existence in finite graphs ⓘ |
| relatedProblem | Seven Bridges of Königsberg NERFINISHED ⓘ |
| requiresConnectivityDirected | underlying undirected graph of non-isolated vertices is connected ⓘ |
| requiresConnectivityUndirected | all vertices with nonzero degree belong to a single connected component ⓘ |
| specialCaseOf |
trail in a graph
ⓘ
walk in a graph ⓘ |
| startEndConditionDirected | if in-degree equals out-degree for all vertices, trail can start and end at the same vertex ⓘ |
| startEndConditionUndirected | if all vertices have even degree, trail can start and end at the same vertex ⓘ |
| startVertexConditionUndirected | if graph has two odd-degree vertices, trail starts at one of them ⓘ |
| topicOf | introductory graph theory courses ⓘ |
| traversesEveryEdge | exactly once ⓘ |
| usedIn |
Chinese postman problem
ⓘ
DNA sequencing by Eulerian methods ⓘ circuit board routing ⓘ network routing ⓘ route inspection problem ⓘ |
| vertexCoverage | may not visit every vertex ⓘ |
| vertexMultiplicity | vertices may appear multiple times in the trail ⓘ |
Referenced by (4)
Full triples — surface form annotated when it differs from this entity's canonical label.
this entity surface form:
Eulerian path
this entity surface form:
Eulerian circuit