Example of graph with two different MSPs via Prim's Algorithm?
$begingroup$
I was discussing Prim's algorithm and Kruskal's algorithm for finding minimum spanning trees the other day and we began to wonder about the conditions under which multiple MSPs would be possible.
We quickly came up with and proved the (apparently famous) fact that unique edge labeling leads to a unique MSP.
However, we wondered if it was possible to create a graph in which Prim's algorithm would create at least two different MSPs if it started from different vertices with the added condition that at no point must it be forced to make "a choice", i.e. choose between two edges available to it that have the same weight?
We believed no but could neither prove it nor come up with a counterexample.
graph-theory algorithms computer-science
asked Jan 25 at 21:33
Isky MathewsIsky Mathews
903314
$endgroup$
add a comment |
$begingroup$
I was discussing Prim's algorithm and Kruskal's algorithm for finding minimum spanning trees the other day and we began to wonder about the conditions under which multiple MSPs would be possible.
We quickly came up with and proved the (apparently famous) fact that unique edge labeling leads to a unique MSP.
However, we wondered if it was possible to create a graph in which Prim's algorithm would create at least two different MSPs if it started from different vertices with the added condition that at no point must it be forced to make "a choice", i.e. choose between two edges available to it that have the same weight?
We believed no but could neither prove it nor come up with a counterexample.
graph-theory algorithms computer-science
asked Jan 25 at 21:33
Isky MathewsIsky Mathews
903314
$endgroup$
add a comment |
$begingroup$
I was discussing Prim's algorithm and Kruskal's algorithm for finding minimum spanning trees the other day and we began to wonder about the conditions under which multiple MSPs would be possible.
We quickly came up with and proved the (apparently famous) fact that unique edge labeling leads to a unique MSP.
However, we wondered if it was possible to create a graph in which Prim's algorithm would create at least two different MSPs if it started from different vertices with the added condition that at no point must it be forced to make "a choice", i.e. choose between two edges available to it that have the same weight?
We believed no but could neither prove it nor come up with a counterexample.
graph-theory algorithms computer-science
asked Jan 25 at 21:33
Isky MathewsIsky Mathews
903314
$endgroup$
I was discussing Prim's algorithm and Kruskal's algorithm for finding minimum spanning trees the other day and we began to wonder about the conditions under which multiple MSPs would be possible.
We quickly came up with and proved the (apparently famous) fact that unique edge labeling leads to a unique MSP.
However, we wondered if it was possible to create a graph in which Prim's algorithm would create at least two different MSPs if it started from different vertices with the added condition that at no point must it be forced to make "a choice", i.e. choose between two edges available to it that have the same weight?
We believed no but could neither prove it nor come up with a counterexample.
graph-theory algorithms computer-science
graph-theory algorithms computer-science
asked Jan 25 at 21:33
Isky MathewsIsky Mathews
903314
asked Jan 25 at 21:33
Isky MathewsIsky Mathews
903314
asked Jan 25 at 21:33
Isky MathewsIsky Mathews
903314
asked Jan 25 at 21:33
Isky MathewsIsky Mathews
903314
asked Jan 25 at 21:33
Isky MathewsIsky Mathews
903314
903314
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
No: the only way Prim's algorithm can end up finding multiple minimum spanning trees is if it has to break a tie between two edges with equal weight.
To see this, let $G$ be any (connected) weighted graph. Let $G'$ be a modification of $G$ in which we add a small offset $epsilon_i$ to the weight of the $i^{text{th}}$ edge. Each $epsilon_i$ should be much smaller than the difference between any two distinct edge weights, and the $epsilon_i$'s should all be different.
With this construction, $G'$ has a unique minimum spanning tree, since all its edge weights are distinct. Therefore Prim's algorithm can only produce one possible output for $G'$.
Now run Prim's algorithm in parallel on $G$ and $G'$, starting from the same vertex. One of two things must happen:
The spanning tree found by Prim's algorithm is the same for both graphs. If this happens starting at every vertex, this means that Prim's algorithm always finds the same spanning tree for $G$ - since it certainly always finds the same spanning tree for $G'$.
Starting at some vertex, the spanning tree found for $G$ is different from the spanning tree found for $G'$. For this to happen, there must be a step where the $epsilon_i$ adjustments in $G'$ made a difference. Since the adjustments are much smaller than the difference between distinct edge weights, they can only make a difference when, in $G$, we choose between two edges of equal weight.
To put it differently: if you're consistent about how you break ties between edges (which is what the $epsilon_i$'s accomplish) then you get the same spanning tree no matter where you start.
answered Jan 25 at 22:28
Misha LavrovMisha Lavrov
47.6k657107
$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%2f3087646%2fexample-of-graph-with-two-different-msps-via-prims-algorithm%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$
No: the only way Prim's algorithm can end up finding multiple minimum spanning trees is if it has to break a tie between two edges with equal weight.
To see this, let $G$ be any (connected) weighted graph. Let $G'$ be a modification of $G$ in which we add a small offset $epsilon_i$ to the weight of the $i^{text{th}}$ edge. Each $epsilon_i$ should be much smaller than the difference between any two distinct edge weights, and the $epsilon_i$'s should all be different.
With this construction, $G'$ has a unique minimum spanning tree, since all its edge weights are distinct. Therefore Prim's algorithm can only produce one possible output for $G'$.
Now run Prim's algorithm in parallel on $G$ and $G'$, starting from the same vertex. One of two things must happen:
The spanning tree found by Prim's algorithm is the same for both graphs. If this happens starting at every vertex, this means that Prim's algorithm always finds the same spanning tree for $G$ - since it certainly always finds the same spanning tree for $G'$.
Starting at some vertex, the spanning tree found for $G$ is different from the spanning tree found for $G'$. For this to happen, there must be a step where the $epsilon_i$ adjustments in $G'$ made a difference. Since the adjustments are much smaller than the difference between distinct edge weights, they can only make a difference when, in $G$, we choose between two edges of equal weight.
To put it differently: if you're consistent about how you break ties between edges (which is what the $epsilon_i$'s accomplish) then you get the same spanning tree no matter where you start.
answered Jan 25 at 22:28
Misha LavrovMisha Lavrov
47.6k657107
$endgroup$
add a comment |
$begingroup$
No: the only way Prim's algorithm can end up finding multiple minimum spanning trees is if it has to break a tie between two edges with equal weight.
To see this, let $G$ be any (connected) weighted graph. Let $G'$ be a modification of $G$ in which we add a small offset $epsilon_i$ to the weight of the $i^{text{th}}$ edge. Each $epsilon_i$ should be much smaller than the difference between any two distinct edge weights, and the $epsilon_i$'s should all be different.
With this construction, $G'$ has a unique minimum spanning tree, since all its edge weights are distinct. Therefore Prim's algorithm can only produce one possible output for $G'$.
Now run Prim's algorithm in parallel on $G$ and $G'$, starting from the same vertex. One of two things must happen:
The spanning tree found by Prim's algorithm is the same for both graphs. If this happens starting at every vertex, this means that Prim's algorithm always finds the same spanning tree for $G$ - since it certainly always finds the same spanning tree for $G'$.
Starting at some vertex, the spanning tree found for $G$ is different from the spanning tree found for $G'$. For this to happen, there must be a step where the $epsilon_i$ adjustments in $G'$ made a difference. Since the adjustments are much smaller than the difference between distinct edge weights, they can only make a difference when, in $G$, we choose between two edges of equal weight.
To put it differently: if you're consistent about how you break ties between edges (which is what the $epsilon_i$'s accomplish) then you get the same spanning tree no matter where you start.
answered Jan 25 at 22:28
Misha LavrovMisha Lavrov
47.6k657107
$endgroup$
add a comment |
$begingroup$
No: the only way Prim's algorithm can end up finding multiple minimum spanning trees is if it has to break a tie between two edges with equal weight.
To see this, let $G$ be any (connected) weighted graph. Let $G'$ be a modification of $G$ in which we add a small offset $epsilon_i$ to the weight of the $i^{text{th}}$ edge. Each $epsilon_i$ should be much smaller than the difference between any two distinct edge weights, and the $epsilon_i$'s should all be different.
With this construction, $G'$ has a unique minimum spanning tree, since all its edge weights are distinct. Therefore Prim's algorithm can only produce one possible output for $G'$.
Now run Prim's algorithm in parallel on $G$ and $G'$, starting from the same vertex. One of two things must happen:
The spanning tree found by Prim's algorithm is the same for both graphs. If this happens starting at every vertex, this means that Prim's algorithm always finds the same spanning tree for $G$ - since it certainly always finds the same spanning tree for $G'$.
Starting at some vertex, the spanning tree found for $G$ is different from the spanning tree found for $G'$. For this to happen, there must be a step where the $epsilon_i$ adjustments in $G'$ made a difference. Since the adjustments are much smaller than the difference between distinct edge weights, they can only make a difference when, in $G$, we choose between two edges of equal weight.
To put it differently: if you're consistent about how you break ties between edges (which is what the $epsilon_i$'s accomplish) then you get the same spanning tree no matter where you start.
answered Jan 25 at 22:28
Misha LavrovMisha Lavrov
47.6k657107
$endgroup$
No: the only way Prim's algorithm can end up finding multiple minimum spanning trees is if it has to break a tie between two edges with equal weight.
To see this, let $G$ be any (connected) weighted graph. Let $G'$ be a modification of $G$ in which we add a small offset $epsilon_i$ to the weight of the $i^{text{th}}$ edge. Each $epsilon_i$ should be much smaller than the difference between any two distinct edge weights, and the $epsilon_i$'s should all be different.
With this construction, $G'$ has a unique minimum spanning tree, since all its edge weights are distinct. Therefore Prim's algorithm can only produce one possible output for $G'$.
Now run Prim's algorithm in parallel on $G$ and $G'$, starting from the same vertex. One of two things must happen:
The spanning tree found by Prim's algorithm is the same for both graphs. If this happens starting at every vertex, this means that Prim's algorithm always finds the same spanning tree for $G$ - since it certainly always finds the same spanning tree for $G'$.
Starting at some vertex, the spanning tree found for $G$ is different from the spanning tree found for $G'$. For this to happen, there must be a step where the $epsilon_i$ adjustments in $G'$ made a difference. Since the adjustments are much smaller than the difference between distinct edge weights, they can only make a difference when, in $G$, we choose between two edges of equal weight.
To put it differently: if you're consistent about how you break ties between edges (which is what the $epsilon_i$'s accomplish) then you get the same spanning tree no matter where you start.
answered Jan 25 at 22:28
Misha LavrovMisha Lavrov
47.6k657107
edited Jan 26 at 0:16
answered Jan 25 at 22:28
Misha LavrovMisha Lavrov
47.6k657107
answered Jan 25 at 22:28
Misha LavrovMisha Lavrov
47.6k657107
answered Jan 25 at 22:28
Misha LavrovMisha Lavrov
47.6k657107
47.6k657107
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%2f3087646%2fexample-of-graph-with-two-different-msps-via-prims-algorithm%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
