Mixing
Proof on undirected graph/ minimal spanning tree
$begingroup$
I have an undirected simple graph $ G=(V,E)$ with $V= {1,...,n}$ and $ w: E rightarrow mathbb{R} , w(e_{ij}):=i+j$
I want to show, that $ (V,T)=({1,...,n},{ {1,2}, {1,3},....,{1,n}})$ is a minimal spanning tree. How can I do that?
graph-theory trees
asked Jan 13 at 18:37
SvenMathSvenMath
357
$endgroup$
add a comment |
$begingroup$
I have an undirected simple graph $ G=(V,E)$ with $V= {1,...,n}$ and $ w: E rightarrow mathbb{R} , w(e_{ij}):=i+j$
I want to show, that $ (V,T)=({1,...,n},{ {1,2}, {1,3},....,{1,n}})$ is a minimal spanning tree. How can I do that?
graph-theory trees
asked Jan 13 at 18:37
SvenMathSvenMath
357
$endgroup$
1
$begingroup$
Do you have any restrictions on $G$? looks like you need at least al edges ${1,k}$ to be present. Is $G$ is the complete graph?
$endgroup$
– Thomas Lesgourgues
Jan 13 at 18:56
add a comment |
$begingroup$
I have an undirected simple graph $ G=(V,E)$ with $V= {1,...,n}$ and $ w: E rightarrow mathbb{R} , w(e_{ij}):=i+j$
I want to show, that $ (V,T)=({1,...,n},{ {1,2}, {1,3},....,{1,n}})$ is a minimal spanning tree. How can I do that?
graph-theory trees
asked Jan 13 at 18:37
SvenMathSvenMath
357
$endgroup$
I have an undirected simple graph $ G=(V,E)$ with $V= {1,...,n}$ and $ w: E rightarrow mathbb{R} , w(e_{ij}):=i+j$
I want to show, that $ (V,T)=({1,...,n},{ {1,2}, {1,3},....,{1,n}})$ is a minimal spanning tree. How can I do that?
graph-theory trees
graph-theory trees
asked Jan 13 at 18:37
SvenMathSvenMath
357
asked Jan 13 at 18:37
SvenMathSvenMath
357
asked Jan 13 at 18:37
SvenMathSvenMath
357
asked Jan 13 at 18:37
SvenMathSvenMath
357
asked Jan 13 at 18:37
SvenMathSvenMath
357
357
1
$begingroup$
Do you have any restrictions on $G$? looks like you need at least al edges ${1,k}$ to be present. Is $G$ is the complete graph?
$endgroup$
– Thomas Lesgourgues
Jan 13 at 18:56
add a comment |
1
$begingroup$
Do you have any restrictions on $G$? looks like you need at least al edges ${1,k}$ to be present. Is $G$ is the complete graph?
$endgroup$
– Thomas Lesgourgues
Jan 13 at 18:56
1
1
$begingroup$
Do you have any restrictions on $G$? looks like you need at least al edges ${1,k}$ to be present. Is $G$ is the complete graph?
$endgroup$
– Thomas Lesgourgues
Jan 13 at 18:56
$begingroup$
Do you have any restrictions on $G$? looks like you need at least al edges ${1,k}$ to be present. Is $G$ is the complete graph?
$endgroup$
– Thomas Lesgourgues
Jan 13 at 18:56
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Suppose edge $e={i,j}$ with $1<i<j$ belongs to a minimal spanning tree.
Verify that the spanning tree must contain either a path from $1$ to $i$ not involving edge $e$ or a path from $1$ to $j$ not involving edge $e$.
In the first case replace edge $e$ by edge ${1,j}$, in the second case replace it by edge ${1,i}$.
Verify that you still have a spanning tree.
Now you have contradicted the minimality of the original spanning tree.
answered Jan 13 at 18:56
Leen DroogendijkLeen Droogendijk
6,1351716
$endgroup$
$begingroup$
How can e belong to T. In T you can only have edges like 1 to i ?
$endgroup$
– SvenMath
Jan 13 at 19:10
$begingroup$
I define $e$ to be the edge between $i$ and $j$. It need not belong to $T$, because we must prove that any other spanning tree is not minimal.
$endgroup$
– Leen Droogendijk
Jan 13 at 19:25
1
$begingroup$
That's the principle of the proof. Suppose you have a minimal spanning tree $T$. If you have an edges ${i,j}$ that is not ${1,k}$, than you can find another spanning tree (replacing this edges by ${1,j}$ or ${1,i}$ ) with weight smaller that $wt(T)$. This is a contradiction to the minimality of $T$. Therefore a minimal spanning trees includes only edges ${1,k}$. And Then in order to be a spanning tree, it mus includes all ${1,k}, k=1,ldots,n$
$endgroup$
– Thomas Lesgourgues
Jan 13 at 19:25
$begingroup$
Thank you very much:) That was very helpful:)
$endgroup$
– SvenMath
Jan 13 at 19:42
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%2f3072372%2fproof-on-undirected-graph-minimal-spanning-tree%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$
Suppose edge $e={i,j}$ with $1<i<j$ belongs to a minimal spanning tree.
Verify that the spanning tree must contain either a path from $1$ to $i$ not involving edge $e$ or a path from $1$ to $j$ not involving edge $e$.
In the first case replace edge $e$ by edge ${1,j}$, in the second case replace it by edge ${1,i}$.
Verify that you still have a spanning tree.
Now you have contradicted the minimality of the original spanning tree.
answered Jan 13 at 18:56
Leen DroogendijkLeen Droogendijk
6,1351716
$endgroup$
$begingroup$
How can e belong to T. In T you can only have edges like 1 to i ?
$endgroup$
– SvenMath
Jan 13 at 19:10
$begingroup$
I define $e$ to be the edge between $i$ and $j$. It need not belong to $T$, because we must prove that any other spanning tree is not minimal.
$endgroup$
– Leen Droogendijk
Jan 13 at 19:25
1
$begingroup$
That's the principle of the proof. Suppose you have a minimal spanning tree $T$. If you have an edges ${i,j}$ that is not ${1,k}$, than you can find another spanning tree (replacing this edges by ${1,j}$ or ${1,i}$ ) with weight smaller that $wt(T)$. This is a contradiction to the minimality of $T$. Therefore a minimal spanning trees includes only edges ${1,k}$. And Then in order to be a spanning tree, it mus includes all ${1,k}, k=1,ldots,n$
$endgroup$
– Thomas Lesgourgues
Jan 13 at 19:25
$begingroup$
Thank you very much:) That was very helpful:)
$endgroup$
– SvenMath
Jan 13 at 19:42
add a comment |
$begingroup$
Suppose edge $e={i,j}$ with $1<i<j$ belongs to a minimal spanning tree.
Verify that the spanning tree must contain either a path from $1$ to $i$ not involving edge $e$ or a path from $1$ to $j$ not involving edge $e$.
In the first case replace edge $e$ by edge ${1,j}$, in the second case replace it by edge ${1,i}$.
Verify that you still have a spanning tree.
Now you have contradicted the minimality of the original spanning tree.
answered Jan 13 at 18:56
Leen DroogendijkLeen Droogendijk
6,1351716
$endgroup$
$begingroup$
How can e belong to T. In T you can only have edges like 1 to i ?
$endgroup$
– SvenMath
Jan 13 at 19:10
$begingroup$
I define $e$ to be the edge between $i$ and $j$. It need not belong to $T$, because we must prove that any other spanning tree is not minimal.
$endgroup$
– Leen Droogendijk
Jan 13 at 19:25
1
$begingroup$
That's the principle of the proof. Suppose you have a minimal spanning tree $T$. If you have an edges ${i,j}$ that is not ${1,k}$, than you can find another spanning tree (replacing this edges by ${1,j}$ or ${1,i}$ ) with weight smaller that $wt(T)$. This is a contradiction to the minimality of $T$. Therefore a minimal spanning trees includes only edges ${1,k}$. And Then in order to be a spanning tree, it mus includes all ${1,k}, k=1,ldots,n$
$endgroup$
– Thomas Lesgourgues
Jan 13 at 19:25
$begingroup$
Thank you very much:) That was very helpful:)
$endgroup$
– SvenMath
Jan 13 at 19:42
add a comment |
$begingroup$
Suppose edge $e={i,j}$ with $1<i<j$ belongs to a minimal spanning tree.
Verify that the spanning tree must contain either a path from $1$ to $i$ not involving edge $e$ or a path from $1$ to $j$ not involving edge $e$.
In the first case replace edge $e$ by edge ${1,j}$, in the second case replace it by edge ${1,i}$.
Verify that you still have a spanning tree.
Now you have contradicted the minimality of the original spanning tree.
answered Jan 13 at 18:56
Leen DroogendijkLeen Droogendijk
6,1351716
$endgroup$
Suppose edge $e={i,j}$ with $1<i<j$ belongs to a minimal spanning tree.
Verify that the spanning tree must contain either a path from $1$ to $i$ not involving edge $e$ or a path from $1$ to $j$ not involving edge $e$.
In the first case replace edge $e$ by edge ${1,j}$, in the second case replace it by edge ${1,i}$.
Verify that you still have a spanning tree.
Now you have contradicted the minimality of the original spanning tree.
answered Jan 13 at 18:56
Leen DroogendijkLeen Droogendijk
6,1351716
answered Jan 13 at 18:56
Leen DroogendijkLeen Droogendijk
6,1351716
answered Jan 13 at 18:56
Leen DroogendijkLeen Droogendijk
6,1351716
answered Jan 13 at 18:56
Leen DroogendijkLeen Droogendijk
6,1351716
6,1351716
$begingroup$
How can e belong to T. In T you can only have edges like 1 to i ?
$endgroup$
– SvenMath
Jan 13 at 19:10
$begingroup$
I define $e$ to be the edge between $i$ and $j$. It need not belong to $T$, because we must prove that any other spanning tree is not minimal.
$endgroup$
– Leen Droogendijk
Jan 13 at 19:25
1
$begingroup$
That's the principle of the proof. Suppose you have a minimal spanning tree $T$. If you have an edges ${i,j}$ that is not ${1,k}$, than you can find another spanning tree (replacing this edges by ${1,j}$ or ${1,i}$ ) with weight smaller that $wt(T)$. This is a contradiction to the minimality of $T$. Therefore a minimal spanning trees includes only edges ${1,k}$. And Then in order to be a spanning tree, it mus includes all ${1,k}, k=1,ldots,n$
$endgroup$
– Thomas Lesgourgues
Jan 13 at 19:25
$begingroup$
Thank you very much:) That was very helpful:)
$endgroup$
– SvenMath
Jan 13 at 19:42
add a comment |
$begingroup$
How can e belong to T. In T you can only have edges like 1 to i ?
$endgroup$
– SvenMath
Jan 13 at 19:10
$begingroup$
I define $e$ to be the edge between $i$ and $j$. It need not belong to $T$, because we must prove that any other spanning tree is not minimal.
$endgroup$
– Leen Droogendijk
Jan 13 at 19:25
1
$begingroup$
That's the principle of the proof. Suppose you have a minimal spanning tree $T$. If you have an edges ${i,j}$ that is not ${1,k}$, than you can find another spanning tree (replacing this edges by ${1,j}$ or ${1,i}$ ) with weight smaller that $wt(T)$. This is a contradiction to the minimality of $T$. Therefore a minimal spanning trees includes only edges ${1,k}$. And Then in order to be a spanning tree, it mus includes all ${1,k}, k=1,ldots,n$
$endgroup$
– Thomas Lesgourgues
Jan 13 at 19:25
$begingroup$
Thank you very much:) That was very helpful:)
$endgroup$
– SvenMath
Jan 13 at 19:42
$begingroup$
How can e belong to T. In T you can only have edges like 1 to i ?
$endgroup$
– SvenMath
Jan 13 at 19:10
$begingroup$
How can e belong to T. In T you can only have edges like 1 to i ?
$endgroup$
– SvenMath
Jan 13 at 19:10
$begingroup$
I define $e$ to be the edge between $i$ and $j$. It need not belong to $T$, because we must prove that any other spanning tree is not minimal.
$endgroup$
– Leen Droogendijk
Jan 13 at 19:25
$begingroup$
I define $e$ to be the edge between $i$ and $j$. It need not belong to $T$, because we must prove that any other spanning tree is not minimal.
$endgroup$
– Leen Droogendijk
Jan 13 at 19:25
1
1
$begingroup$
That's the principle of the proof. Suppose you have a minimal spanning tree $T$. If you have an edges ${i,j}$ that is not ${1,k}$, than you can find another spanning tree (replacing this edges by ${1,j}$ or ${1,i}$ ) with weight smaller that $wt(T)$. This is a contradiction to the minimality of $T$. Therefore a minimal spanning trees includes only edges ${1,k}$. And Then in order to be a spanning tree, it mus includes all ${1,k}, k=1,ldots,n$
$endgroup$
– Thomas Lesgourgues
Jan 13 at 19:25
$begingroup$
That's the principle of the proof. Suppose you have a minimal spanning tree $T$. If you have an edges ${i,j}$ that is not ${1,k}$, than you can find another spanning tree (replacing this edges by ${1,j}$ or ${1,i}$ ) with weight smaller that $wt(T)$. This is a contradiction to the minimality of $T$. Therefore a minimal spanning trees includes only edges ${1,k}$. And Then in order to be a spanning tree, it mus includes all ${1,k}, k=1,ldots,n$
$endgroup$
– Thomas Lesgourgues
Jan 13 at 19:25
$begingroup$
Thank you very much:) That was very helpful:)
$endgroup$
– SvenMath
Jan 13 at 19:42
$begingroup$
Thank you very much:) That was very helpful:)
$endgroup$
– SvenMath
Jan 13 at 19:42
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%2f3072372%2fproof-on-undirected-graph-minimal-spanning-tree%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
1
$begingroup$
Do you have any restrictions on $G$? looks like you need at least al edges ${1,k}$ to be present. Is $G$ is the complete graph?
$endgroup$
– Thomas Lesgourgues
Jan 13 at 18:56