Breadth First Search Counter Example
Statement:
"Consider an arbitrary graph G=(V,E) and a source vertex s that is in V. For each shortest paths tree rooted at s, there exists an ordering of the vertices in an adjacency list representation of G which results in precisely this shortest-paths tree when BFS is run from s."
I am struggling to come up with a counter-example for this statement that I have taken for face value to be FALSE.
I understand that the ordering matters when it comes to the shortest-paths tree derived from BFS assuming that the order of the vertex's in the adjacency list is the order BFS follows but can't seem to think of a counter-example that violates this statement.
Edit: I am not asking how to find the other shortest-tree paths, but an example that shows that there are OTHER shortest-tree paths that are not found by BFS.
graph-theory
asked Nov 20 '18 at 2:01
John LarkosJohn Larkos
167
add a comment |
Statement:
"Consider an arbitrary graph G=(V,E) and a source vertex s that is in V. For each shortest paths tree rooted at s, there exists an ordering of the vertices in an adjacency list representation of G which results in precisely this shortest-paths tree when BFS is run from s."
I am struggling to come up with a counter-example for this statement that I have taken for face value to be FALSE.
I understand that the ordering matters when it comes to the shortest-paths tree derived from BFS assuming that the order of the vertex's in the adjacency list is the order BFS follows but can't seem to think of a counter-example that violates this statement.
Edit: I am not asking how to find the other shortest-tree paths, but an example that shows that there are OTHER shortest-tree paths that are not found by BFS.
graph-theory
asked Nov 20 '18 at 2:01
John LarkosJohn Larkos
167
Possible duplicate of Finding all the shortest paths between two nodes in unweighted undirected graph
– bishop
Nov 20 '18 at 2:05
add a comment |
Statement:
"Consider an arbitrary graph G=(V,E) and a source vertex s that is in V. For each shortest paths tree rooted at s, there exists an ordering of the vertices in an adjacency list representation of G which results in precisely this shortest-paths tree when BFS is run from s."
I am struggling to come up with a counter-example for this statement that I have taken for face value to be FALSE.
I understand that the ordering matters when it comes to the shortest-paths tree derived from BFS assuming that the order of the vertex's in the adjacency list is the order BFS follows but can't seem to think of a counter-example that violates this statement.
Edit: I am not asking how to find the other shortest-tree paths, but an example that shows that there are OTHER shortest-tree paths that are not found by BFS.
graph-theory
asked Nov 20 '18 at 2:01
John LarkosJohn Larkos
167
Statement:
"Consider an arbitrary graph G=(V,E) and a source vertex s that is in V. For each shortest paths tree rooted at s, there exists an ordering of the vertices in an adjacency list representation of G which results in precisely this shortest-paths tree when BFS is run from s."
I am struggling to come up with a counter-example for this statement that I have taken for face value to be FALSE.
I understand that the ordering matters when it comes to the shortest-paths tree derived from BFS assuming that the order of the vertex's in the adjacency list is the order BFS follows but can't seem to think of a counter-example that violates this statement.
Edit: I am not asking how to find the other shortest-tree paths, but an example that shows that there are OTHER shortest-tree paths that are not found by BFS.
graph-theory
graph-theory
asked Nov 20 '18 at 2:01
John LarkosJohn Larkos
167
asked Nov 20 '18 at 2:01
John LarkosJohn Larkos
167
edited Nov 20 '18 at 2:18
John Larkos
asked Nov 20 '18 at 2:01
John LarkosJohn Larkos
167
asked Nov 20 '18 at 2:01
John LarkosJohn Larkos
167
asked Nov 20 '18 at 2:01
John LarkosJohn Larkos
167
167
Possible duplicate of Finding all the shortest paths between two nodes in unweighted undirected graph
– bishop
Nov 20 '18 at 2:05
add a comment |
Possible duplicate of Finding all the shortest paths between two nodes in unweighted undirected graph
– bishop
Nov 20 '18 at 2:05
Possible duplicate of Finding all the shortest paths between two nodes in unweighted undirected graph
– bishop
Nov 20 '18 at 2:05
Possible duplicate of Finding all the shortest paths between two nodes in unweighted undirected graph
– bishop
Nov 20 '18 at 2:05
add a comment |
1 Answer
1
active
oldest
votes
Confirm your graph is unweighted and undirected ?
answered Nov 22 '18 at 15:37
TheWildHealerTheWildHealer
409217
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
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
},
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%2fstackoverflow.com%2fquestions%2f53385179%2fbreadth-first-search-counter-example%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
Confirm your graph is unweighted and undirected ?
answered Nov 22 '18 at 15:37
TheWildHealerTheWildHealer
409217
add a comment |
Confirm your graph is unweighted and undirected ?
answered Nov 22 '18 at 15:37
TheWildHealerTheWildHealer
409217
add a comment |
Confirm your graph is unweighted and undirected ?
answered Nov 22 '18 at 15:37
TheWildHealerTheWildHealer
409217
Confirm your graph is unweighted and undirected ?
answered Nov 22 '18 at 15:37
TheWildHealerTheWildHealer
409217
answered Nov 22 '18 at 15:37
TheWildHealerTheWildHealer
409217
answered Nov 22 '18 at 15:37
TheWildHealerTheWildHealer
409217
answered Nov 22 '18 at 15:37
TheWildHealerTheWildHealer
409217
409217
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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.
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%2fstackoverflow.com%2fquestions%2f53385179%2fbreadth-first-search-counter-example%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
Possible duplicate of Finding all the shortest paths between two nodes in unweighted undirected graph
– bishop
Nov 20 '18 at 2:05