What is a simple path in a directed graph?
$begingroup$
In graph theory, a simple path is a path that contains no repeated vertices. But, in a directed graph, the directions of the arrows must be respected, right? That is A -> B <- C is not a path? However, I have a source which states that would also be a simple path, but, according to the same source, that would not be a directed path. Why would A -> B <- C be considered a simple path, or is the source wrong? So, what is a simple path in a directed graph?
graph-theory definition causal-diagrams
asked Jan 20 at 0:58
nbronbro
2,41653173
$endgroup$
add a comment |
$begingroup$
In graph theory, a simple path is a path that contains no repeated vertices. But, in a directed graph, the directions of the arrows must be respected, right? That is A -> B <- C is not a path? However, I have a source which states that would also be a simple path, but, according to the same source, that would not be a directed path. Why would A -> B <- C be considered a simple path, or is the source wrong? So, what is a simple path in a directed graph?
graph-theory definition causal-diagrams
asked Jan 20 at 0:58
nbronbro
2,41653173
$endgroup$
$begingroup$
"A directed path in a digraph is a sequence of vertices in which there is a (directed) edge pointing from each vertex in the sequence to its successor in the sequence. A simple path is one with no repeated vertices." algs4.cs.princeton.edu/42digraph
$endgroup$
– David G. Stork
Jan 20 at 1:01
$begingroup$
That definition demands that the path respect edge direction. Demands it.
$endgroup$
– David G. Stork
Jan 20 at 1:04
$begingroup$
I think, read in context, the definition demands respecting edge direction. Anyway... that's how I've always understood the term.
$endgroup$
– David G. Stork
Jan 20 at 1:08
add a comment |
$begingroup$
In graph theory, a simple path is a path that contains no repeated vertices. But, in a directed graph, the directions of the arrows must be respected, right? That is A -> B <- C is not a path? However, I have a source which states that would also be a simple path, but, according to the same source, that would not be a directed path. Why would A -> B <- C be considered a simple path, or is the source wrong? So, what is a simple path in a directed graph?
graph-theory definition causal-diagrams
asked Jan 20 at 0:58
nbronbro
2,41653173
$endgroup$
In graph theory, a simple path is a path that contains no repeated vertices. But, in a directed graph, the directions of the arrows must be respected, right? That is A -> B <- C is not a path? However, I have a source which states that would also be a simple path, but, according to the same source, that would not be a directed path. Why would A -> B <- C be considered a simple path, or is the source wrong? So, what is a simple path in a directed graph?
graph-theory definition causal-diagrams
graph-theory definition causal-diagrams
asked Jan 20 at 0:58
nbronbro
2,41653173
asked Jan 20 at 0:58
nbronbro
2,41653173
edited Jan 20 at 1:04
nbro
asked Jan 20 at 0:58
nbronbro
2,41653173
asked Jan 20 at 0:58
nbronbro
2,41653173
asked Jan 20 at 0:58
nbronbro
2,41653173
2,41653173
$begingroup$
"A directed path in a digraph is a sequence of vertices in which there is a (directed) edge pointing from each vertex in the sequence to its successor in the sequence. A simple path is one with no repeated vertices." algs4.cs.princeton.edu/42digraph
$endgroup$
– David G. Stork
Jan 20 at 1:01
$begingroup$
That definition demands that the path respect edge direction. Demands it.
$endgroup$
– David G. Stork
Jan 20 at 1:04
$begingroup$
I think, read in context, the definition demands respecting edge direction. Anyway... that's how I've always understood the term.
$endgroup$
– David G. Stork
Jan 20 at 1:08
add a comment |
$begingroup$
"A directed path in a digraph is a sequence of vertices in which there is a (directed) edge pointing from each vertex in the sequence to its successor in the sequence. A simple path is one with no repeated vertices." algs4.cs.princeton.edu/42digraph
$endgroup$
– David G. Stork
Jan 20 at 1:01
$begingroup$
That definition demands that the path respect edge direction. Demands it.
$endgroup$
– David G. Stork
Jan 20 at 1:04
$begingroup$
I think, read in context, the definition demands respecting edge direction. Anyway... that's how I've always understood the term.
$endgroup$
– David G. Stork
Jan 20 at 1:08
$begingroup$
"A directed path in a digraph is a sequence of vertices in which there is a (directed) edge pointing from each vertex in the sequence to its successor in the sequence. A simple path is one with no repeated vertices." algs4.cs.princeton.edu/42digraph
$endgroup$
– David G. Stork
Jan 20 at 1:01
$begingroup$
"A directed path in a digraph is a sequence of vertices in which there is a (directed) edge pointing from each vertex in the sequence to its successor in the sequence. A simple path is one with no repeated vertices." algs4.cs.princeton.edu/42digraph
$endgroup$
– David G. Stork
Jan 20 at 1:01
$begingroup$
That definition demands that the path respect edge direction. Demands it.
$endgroup$
– David G. Stork
Jan 20 at 1:04
$begingroup$
That definition demands that the path respect edge direction. Demands it.
$endgroup$
– David G. Stork
Jan 20 at 1:04
$begingroup$
I think, read in context, the definition demands respecting edge direction. Anyway... that's how I've always understood the term.
$endgroup$
– David G. Stork
Jan 20 at 1:08
$begingroup$
I think, read in context, the definition demands respecting edge direction. Anyway... that's how I've always understood the term.
$endgroup$
– David G. Stork
Jan 20 at 1:08
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
There is not a quite universal consensus about the terminology here.
However, generally, most people would probably assume that when you have a directed graphs, the paths you're talking about will be directed path unless you're being quite explicit about ignoring the directionality.
I don't think just saying "simple" will be explicit enough to convey that. By that I would understand that the path cannot repeat vertices, but there's no reason such a path cannot be expected to respect the direction of edges -- so it makes plenty of sense to speak about either directed or undirected simple paths, and to implicitly assume the former when your edges happen to have direction.
If you want to speak about an undirected path in a directed graph, for the sake of communication please say "undirected path". If you need to decode something someone else says, you're at the mercy of their terminology. Ask for clarification if it is not clear what they mean.
answered Jan 20 at 1:04
Henning MakholmHenning Makholm
240k17306544
$endgroup$
$begingroup$
Maybe you are familiar with causal inference and causality. If yes, in that context, wouldA -> B <- Cbe considered a simple path? In that contextA -> B <- Cis actually called a "collider". But I have a source which states that is also a simple path. I really don't get why, but, given the context I've just mentioned, maybe it makes sense. I don't know. Do you have any knowledge of causal inference?
$endgroup$
– nbro
Jan 20 at 1:09
$begingroup$
@nbro: I refer you to my answer. "Simple" does not in my experience specify anything about whether the path respects directions or not, so I would not call an undirected path just a "simple path" when I'm talking about a directed graph.
$endgroup$
– Henning Makholm
Jan 20 at 1:11
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%2f3080037%2fwhat-is-a-simple-path-in-a-directed-graph%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$
There is not a quite universal consensus about the terminology here.
However, generally, most people would probably assume that when you have a directed graphs, the paths you're talking about will be directed path unless you're being quite explicit about ignoring the directionality.
I don't think just saying "simple" will be explicit enough to convey that. By that I would understand that the path cannot repeat vertices, but there's no reason such a path cannot be expected to respect the direction of edges -- so it makes plenty of sense to speak about either directed or undirected simple paths, and to implicitly assume the former when your edges happen to have direction.
If you want to speak about an undirected path in a directed graph, for the sake of communication please say "undirected path". If you need to decode something someone else says, you're at the mercy of their terminology. Ask for clarification if it is not clear what they mean.
answered Jan 20 at 1:04
Henning MakholmHenning Makholm
240k17306544
$endgroup$
$begingroup$
Maybe you are familiar with causal inference and causality. If yes, in that context, wouldA -> B <- Cbe considered a simple path? In that contextA -> B <- Cis actually called a "collider". But I have a source which states that is also a simple path. I really don't get why, but, given the context I've just mentioned, maybe it makes sense. I don't know. Do you have any knowledge of causal inference?
$endgroup$
– nbro
Jan 20 at 1:09
$begingroup$
@nbro: I refer you to my answer. "Simple" does not in my experience specify anything about whether the path respects directions or not, so I would not call an undirected path just a "simple path" when I'm talking about a directed graph.
$endgroup$
– Henning Makholm
Jan 20 at 1:11
add a comment |
$begingroup$
There is not a quite universal consensus about the terminology here.
However, generally, most people would probably assume that when you have a directed graphs, the paths you're talking about will be directed path unless you're being quite explicit about ignoring the directionality.
I don't think just saying "simple" will be explicit enough to convey that. By that I would understand that the path cannot repeat vertices, but there's no reason such a path cannot be expected to respect the direction of edges -- so it makes plenty of sense to speak about either directed or undirected simple paths, and to implicitly assume the former when your edges happen to have direction.
If you want to speak about an undirected path in a directed graph, for the sake of communication please say "undirected path". If you need to decode something someone else says, you're at the mercy of their terminology. Ask for clarification if it is not clear what they mean.
answered Jan 20 at 1:04
Henning MakholmHenning Makholm
240k17306544
$endgroup$
$begingroup$
Maybe you are familiar with causal inference and causality. If yes, in that context, wouldA -> B <- Cbe considered a simple path? In that contextA -> B <- Cis actually called a "collider". But I have a source which states that is also a simple path. I really don't get why, but, given the context I've just mentioned, maybe it makes sense. I don't know. Do you have any knowledge of causal inference?
$endgroup$
– nbro
Jan 20 at 1:09
$begingroup$
@nbro: I refer you to my answer. "Simple" does not in my experience specify anything about whether the path respects directions or not, so I would not call an undirected path just a "simple path" when I'm talking about a directed graph.
$endgroup$
– Henning Makholm
Jan 20 at 1:11
add a comment |
$begingroup$
There is not a quite universal consensus about the terminology here.
However, generally, most people would probably assume that when you have a directed graphs, the paths you're talking about will be directed path unless you're being quite explicit about ignoring the directionality.
I don't think just saying "simple" will be explicit enough to convey that. By that I would understand that the path cannot repeat vertices, but there's no reason such a path cannot be expected to respect the direction of edges -- so it makes plenty of sense to speak about either directed or undirected simple paths, and to implicitly assume the former when your edges happen to have direction.
If you want to speak about an undirected path in a directed graph, for the sake of communication please say "undirected path". If you need to decode something someone else says, you're at the mercy of their terminology. Ask for clarification if it is not clear what they mean.
answered Jan 20 at 1:04
Henning MakholmHenning Makholm
240k17306544
$endgroup$
There is not a quite universal consensus about the terminology here.
However, generally, most people would probably assume that when you have a directed graphs, the paths you're talking about will be directed path unless you're being quite explicit about ignoring the directionality.
I don't think just saying "simple" will be explicit enough to convey that. By that I would understand that the path cannot repeat vertices, but there's no reason such a path cannot be expected to respect the direction of edges -- so it makes plenty of sense to speak about either directed or undirected simple paths, and to implicitly assume the former when your edges happen to have direction.
If you want to speak about an undirected path in a directed graph, for the sake of communication please say "undirected path". If you need to decode something someone else says, you're at the mercy of their terminology. Ask for clarification if it is not clear what they mean.
answered Jan 20 at 1:04
Henning MakholmHenning Makholm
240k17306544
answered Jan 20 at 1:04
Henning MakholmHenning Makholm
240k17306544
answered Jan 20 at 1:04
Henning MakholmHenning Makholm
240k17306544
answered Jan 20 at 1:04
Henning MakholmHenning Makholm
240k17306544
240k17306544
$begingroup$
Maybe you are familiar with causal inference and causality. If yes, in that context, wouldA -> B <- Cbe considered a simple path? In that contextA -> B <- Cis actually called a "collider". But I have a source which states that is also a simple path. I really don't get why, but, given the context I've just mentioned, maybe it makes sense. I don't know. Do you have any knowledge of causal inference?
$endgroup$
– nbro
Jan 20 at 1:09
$begingroup$
@nbro: I refer you to my answer. "Simple" does not in my experience specify anything about whether the path respects directions or not, so I would not call an undirected path just a "simple path" when I'm talking about a directed graph.
$endgroup$
– Henning Makholm
Jan 20 at 1:11
add a comment |
$begingroup$
Maybe you are familiar with causal inference and causality. If yes, in that context, wouldA -> B <- Cbe considered a simple path? In that contextA -> B <- Cis actually called a "collider". But I have a source which states that is also a simple path. I really don't get why, but, given the context I've just mentioned, maybe it makes sense. I don't know. Do you have any knowledge of causal inference?
$endgroup$
– nbro
Jan 20 at 1:09
$begingroup$
@nbro: I refer you to my answer. "Simple" does not in my experience specify anything about whether the path respects directions or not, so I would not call an undirected path just a "simple path" when I'm talking about a directed graph.
$endgroup$
– Henning Makholm
Jan 20 at 1:11
$begingroup$
Maybe you are familiar with causal inference and causality. If yes, in that context, would
A -> B <- C be considered a simple path? In that context A -> B <- C is actually called a "collider". But I have a source which states that is also a simple path. I really don't get why, but, given the context I've just mentioned, maybe it makes sense. I don't know. Do you have any knowledge of causal inference?$endgroup$
– nbro
Jan 20 at 1:09
$begingroup$
Maybe you are familiar with causal inference and causality. If yes, in that context, would
A -> B <- C be considered a simple path? In that context A -> B <- C is actually called a "collider". But I have a source which states that is also a simple path. I really don't get why, but, given the context I've just mentioned, maybe it makes sense. I don't know. Do you have any knowledge of causal inference?$endgroup$
– nbro
Jan 20 at 1:09
$begingroup$
@nbro: I refer you to my answer. "Simple" does not in my experience specify anything about whether the path respects directions or not, so I would not call an undirected path just a "simple path" when I'm talking about a directed graph.
$endgroup$
– Henning Makholm
Jan 20 at 1:11
$begingroup$
@nbro: I refer you to my answer. "Simple" does not in my experience specify anything about whether the path respects directions or not, so I would not call an undirected path just a "simple path" when I'm talking about a directed graph.
$endgroup$
– Henning Makholm
Jan 20 at 1:11
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%2f3080037%2fwhat-is-a-simple-path-in-a-directed-graph%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
$begingroup$
"A directed path in a digraph is a sequence of vertices in which there is a (directed) edge pointing from each vertex in the sequence to its successor in the sequence. A simple path is one with no repeated vertices." algs4.cs.princeton.edu/42digraph
$endgroup$
– David G. Stork
Jan 20 at 1:01
$begingroup$
That definition demands that the path respect edge direction. Demands it.
$endgroup$
– David G. Stork
Jan 20 at 1:04
$begingroup$
I think, read in context, the definition demands respecting edge direction. Anyway... that's how I've always understood the term.
$endgroup$
– David G. Stork
Jan 20 at 1:08