Confusion about euler path,trail,circuit?
$begingroup$
What's the difference between a euler trail, path,circuit,cycle and a regular trail,path,circuit,cycle since edges cannot repeat for all of them anyway?
And can vertices be repeated in a euler path?
Clarification will be much appreciated.Thanks.
discrete-mathematics graph-theory
asked Jul 20 '17 at 13:37
Sook LimSook Lim
788
$endgroup$
add a comment |
$begingroup$
What's the difference between a euler trail, path,circuit,cycle and a regular trail,path,circuit,cycle since edges cannot repeat for all of them anyway?
And can vertices be repeated in a euler path?
Clarification will be much appreciated.Thanks.
discrete-mathematics graph-theory
asked Jul 20 '17 at 13:37
Sook LimSook Lim
788
$endgroup$
add a comment |
$begingroup$
What's the difference between a euler trail, path,circuit,cycle and a regular trail,path,circuit,cycle since edges cannot repeat for all of them anyway?
And can vertices be repeated in a euler path?
Clarification will be much appreciated.Thanks.
discrete-mathematics graph-theory
asked Jul 20 '17 at 13:37
Sook LimSook Lim
788
$endgroup$
What's the difference between a euler trail, path,circuit,cycle and a regular trail,path,circuit,cycle since edges cannot repeat for all of them anyway?
And can vertices be repeated in a euler path?
Clarification will be much appreciated.Thanks.
discrete-mathematics graph-theory
discrete-mathematics graph-theory
asked Jul 20 '17 at 13:37
Sook LimSook Lim
788
asked Jul 20 '17 at 13:37
Sook LimSook Lim
788
edited Jul 20 '17 at 13:44
Sook Lim
asked Jul 20 '17 at 13:37
Sook LimSook Lim
788
asked Jul 20 '17 at 13:37
Sook LimSook Lim
788
asked Jul 20 '17 at 13:37
Sook LimSook Lim
788
788
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Definitions taken according to Diestel's text Graph Theory:
A path is a nonempty graph $P=(V,E)$ with $V={x_0,x_1,x_2,dots,x_k}$, $E={x_0x_1,x_1x_2,x_2x_3,dots,x_{k-1}x_k}$ where all $x_i$ are distinct. The path's length is the number of edges, $k$.
A cycle is a path of length $kgeq 2$ along with an additional edge included between $x_0$ and $x_k$. The cycle's length is the number of edges (including this new one).
A circuit is essentially a cycle with the slightly different nuance that we are specifically referring to the edge-set as an element of the edge space when viewing this through the lens of linear algebra, not the graph itself.
A walk (also called a trail) is a nonempty alternating sequence of vertices and edges $v_0e_0v_1e_2v_2e_2dots e_{k-1}v_k$ where $e_i$ is an edge between $v_i$ and $v_{i+1}$ for all $i<k$. A walk is closed if $v_0=v_k$.
Note that a walk/trail may repeat vertices and edges while a path may not repeat vertices (and hence cannot repeat edges either) and neither can a cycle (not counting starting and ending vertices). Also note that circuits often refer to the same thing as cycles in common practice as not everyone follows strict naming conventions.
A graph is called Eulerian if it there exists an Eulerian Tour, a closed walk which visits every edge exactly once.
A graph is called semi-eulerian if it has an Eulerian Walk, a walk which visits every edge exactly once, but not such a closed walk.
You will often see people refer to Eulerian cycles, Eulerian circuits, Eulerian paths, and Eulerian trials. Often times, either they have defined these terms differently, or they simply mean Eulerian Tours and Eulerian Walks respectively while using an incorrect word. (That is to say, an "Eulerian Cycle" is not necessarily a "cycle" in that we allow vertices to repeat)
In recap: Euler <insert object here> are like regular <insert object here> except they must use every available edge in the entire graph (and could possibly repeat vertices which is otherwise not allowed depending on strictness of naming conventions followed by that person). It is not strong enough to simply not repeat edges, but rather all edges in the graph must be used.
answered Jul 20 '17 at 15:40
JMoravitzJMoravitz
47.9k33886
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2365032%2fconfusion-about-euler-path-trail-circuit%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Definitions taken according to Diestel's text Graph Theory:
A path is a nonempty graph $P=(V,E)$ with $V={x_0,x_1,x_2,dots,x_k}$, $E={x_0x_1,x_1x_2,x_2x_3,dots,x_{k-1}x_k}$ where all $x_i$ are distinct. The path's length is the number of edges, $k$.
A cycle is a path of length $kgeq 2$ along with an additional edge included between $x_0$ and $x_k$. The cycle's length is the number of edges (including this new one).
A circuit is essentially a cycle with the slightly different nuance that we are specifically referring to the edge-set as an element of the edge space when viewing this through the lens of linear algebra, not the graph itself.
A walk (also called a trail) is a nonempty alternating sequence of vertices and edges $v_0e_0v_1e_2v_2e_2dots e_{k-1}v_k$ where $e_i$ is an edge between $v_i$ and $v_{i+1}$ for all $i<k$. A walk is closed if $v_0=v_k$.
Note that a walk/trail may repeat vertices and edges while a path may not repeat vertices (and hence cannot repeat edges either) and neither can a cycle (not counting starting and ending vertices). Also note that circuits often refer to the same thing as cycles in common practice as not everyone follows strict naming conventions.
A graph is called Eulerian if it there exists an Eulerian Tour, a closed walk which visits every edge exactly once.
A graph is called semi-eulerian if it has an Eulerian Walk, a walk which visits every edge exactly once, but not such a closed walk.
You will often see people refer to Eulerian cycles, Eulerian circuits, Eulerian paths, and Eulerian trials. Often times, either they have defined these terms differently, or they simply mean Eulerian Tours and Eulerian Walks respectively while using an incorrect word. (That is to say, an "Eulerian Cycle" is not necessarily a "cycle" in that we allow vertices to repeat)
In recap: Euler <insert object here> are like regular <insert object here> except they must use every available edge in the entire graph (and could possibly repeat vertices which is otherwise not allowed depending on strictness of naming conventions followed by that person). It is not strong enough to simply not repeat edges, but rather all edges in the graph must be used.
answered Jul 20 '17 at 15:40
JMoravitzJMoravitz
47.9k33886
$endgroup$
add a comment |
$begingroup$
Definitions taken according to Diestel's text Graph Theory:
A path is a nonempty graph $P=(V,E)$ with $V={x_0,x_1,x_2,dots,x_k}$, $E={x_0x_1,x_1x_2,x_2x_3,dots,x_{k-1}x_k}$ where all $x_i$ are distinct. The path's length is the number of edges, $k$.
A cycle is a path of length $kgeq 2$ along with an additional edge included between $x_0$ and $x_k$. The cycle's length is the number of edges (including this new one).
A circuit is essentially a cycle with the slightly different nuance that we are specifically referring to the edge-set as an element of the edge space when viewing this through the lens of linear algebra, not the graph itself.
A walk (also called a trail) is a nonempty alternating sequence of vertices and edges $v_0e_0v_1e_2v_2e_2dots e_{k-1}v_k$ where $e_i$ is an edge between $v_i$ and $v_{i+1}$ for all $i<k$. A walk is closed if $v_0=v_k$.
Note that a walk/trail may repeat vertices and edges while a path may not repeat vertices (and hence cannot repeat edges either) and neither can a cycle (not counting starting and ending vertices). Also note that circuits often refer to the same thing as cycles in common practice as not everyone follows strict naming conventions.
A graph is called Eulerian if it there exists an Eulerian Tour, a closed walk which visits every edge exactly once.
A graph is called semi-eulerian if it has an Eulerian Walk, a walk which visits every edge exactly once, but not such a closed walk.
You will often see people refer to Eulerian cycles, Eulerian circuits, Eulerian paths, and Eulerian trials. Often times, either they have defined these terms differently, or they simply mean Eulerian Tours and Eulerian Walks respectively while using an incorrect word. (That is to say, an "Eulerian Cycle" is not necessarily a "cycle" in that we allow vertices to repeat)
In recap: Euler <insert object here> are like regular <insert object here> except they must use every available edge in the entire graph (and could possibly repeat vertices which is otherwise not allowed depending on strictness of naming conventions followed by that person). It is not strong enough to simply not repeat edges, but rather all edges in the graph must be used.
answered Jul 20 '17 at 15:40
JMoravitzJMoravitz
47.9k33886
$endgroup$
add a comment |
$begingroup$
Definitions taken according to Diestel's text Graph Theory:
A path is a nonempty graph $P=(V,E)$ with $V={x_0,x_1,x_2,dots,x_k}$, $E={x_0x_1,x_1x_2,x_2x_3,dots,x_{k-1}x_k}$ where all $x_i$ are distinct. The path's length is the number of edges, $k$.
A cycle is a path of length $kgeq 2$ along with an additional edge included between $x_0$ and $x_k$. The cycle's length is the number of edges (including this new one).
A circuit is essentially a cycle with the slightly different nuance that we are specifically referring to the edge-set as an element of the edge space when viewing this through the lens of linear algebra, not the graph itself.
A walk (also called a trail) is a nonempty alternating sequence of vertices and edges $v_0e_0v_1e_2v_2e_2dots e_{k-1}v_k$ where $e_i$ is an edge between $v_i$ and $v_{i+1}$ for all $i<k$. A walk is closed if $v_0=v_k$.
Note that a walk/trail may repeat vertices and edges while a path may not repeat vertices (and hence cannot repeat edges either) and neither can a cycle (not counting starting and ending vertices). Also note that circuits often refer to the same thing as cycles in common practice as not everyone follows strict naming conventions.
A graph is called Eulerian if it there exists an Eulerian Tour, a closed walk which visits every edge exactly once.
A graph is called semi-eulerian if it has an Eulerian Walk, a walk which visits every edge exactly once, but not such a closed walk.
You will often see people refer to Eulerian cycles, Eulerian circuits, Eulerian paths, and Eulerian trials. Often times, either they have defined these terms differently, or they simply mean Eulerian Tours and Eulerian Walks respectively while using an incorrect word. (That is to say, an "Eulerian Cycle" is not necessarily a "cycle" in that we allow vertices to repeat)
In recap: Euler <insert object here> are like regular <insert object here> except they must use every available edge in the entire graph (and could possibly repeat vertices which is otherwise not allowed depending on strictness of naming conventions followed by that person). It is not strong enough to simply not repeat edges, but rather all edges in the graph must be used.
answered Jul 20 '17 at 15:40
JMoravitzJMoravitz
47.9k33886
$endgroup$
Definitions taken according to Diestel's text Graph Theory:
A path is a nonempty graph $P=(V,E)$ with $V={x_0,x_1,x_2,dots,x_k}$, $E={x_0x_1,x_1x_2,x_2x_3,dots,x_{k-1}x_k}$ where all $x_i$ are distinct. The path's length is the number of edges, $k$.
A cycle is a path of length $kgeq 2$ along with an additional edge included between $x_0$ and $x_k$. The cycle's length is the number of edges (including this new one).
A circuit is essentially a cycle with the slightly different nuance that we are specifically referring to the edge-set as an element of the edge space when viewing this through the lens of linear algebra, not the graph itself.
A walk (also called a trail) is a nonempty alternating sequence of vertices and edges $v_0e_0v_1e_2v_2e_2dots e_{k-1}v_k$ where $e_i$ is an edge between $v_i$ and $v_{i+1}$ for all $i<k$. A walk is closed if $v_0=v_k$.
Note that a walk/trail may repeat vertices and edges while a path may not repeat vertices (and hence cannot repeat edges either) and neither can a cycle (not counting starting and ending vertices). Also note that circuits often refer to the same thing as cycles in common practice as not everyone follows strict naming conventions.
A graph is called Eulerian if it there exists an Eulerian Tour, a closed walk which visits every edge exactly once.
A graph is called semi-eulerian if it has an Eulerian Walk, a walk which visits every edge exactly once, but not such a closed walk.
You will often see people refer to Eulerian cycles, Eulerian circuits, Eulerian paths, and Eulerian trials. Often times, either they have defined these terms differently, or they simply mean Eulerian Tours and Eulerian Walks respectively while using an incorrect word. (That is to say, an "Eulerian Cycle" is not necessarily a "cycle" in that we allow vertices to repeat)
In recap: Euler <insert object here> are like regular <insert object here> except they must use every available edge in the entire graph (and could possibly repeat vertices which is otherwise not allowed depending on strictness of naming conventions followed by that person). It is not strong enough to simply not repeat edges, but rather all edges in the graph must be used.
answered Jul 20 '17 at 15:40
JMoravitzJMoravitz
47.9k33886
answered Jul 20 '17 at 15:40
JMoravitzJMoravitz
47.9k33886
answered Jul 20 '17 at 15:40
JMoravitzJMoravitz
47.9k33886
answered Jul 20 '17 at 15:40
JMoravitzJMoravitz
47.9k33886
47.9k33886
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2365032%2fconfusion-about-euler-path-trail-circuit%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
