Mixing
Spanning trees for complete graph
$begingroup$
Let $K_n = (V, E)$ be a complete undirected graph with $n$ vertices (namely, every two vertices are connected), and let $n$ be an even number. A spanning tree of $G$ is a connected subgraph of $G$ that contains all vertices in $G$ and no cycles. Design a recursive algorithm that given the graph $K_n$, partitions the set of edges $E$ into $n/2$ distinct subsets $E_1,E_2,dots,E_{n/2}$, such that for every subset $E_i$, the subgraph $G_i = (V, E_i$) is a spanning tree of $K_n$.
(Hint: Solve the problem recursively by removing two nodes and their edges in $K_n$. From the output of recursive call, you get $(n − 2)/2$ spanning trees for $K_{n−2}$. Extend those trees to be spanning trees for $K_n$ and then construct a new spanning tree to complete the job. PS: A collection of sets $S_1,dots,S_k$ is a partition of $S$, if each $S_i$ is a subset of $S$, no two subsets have a non-empty intersection, and the union of all the subsets is $S$.)
Even with the hint, I'm struggling to understand how to solve this question. So when you remove two vertices, you get $n/2 - 1$ spanning trees for $K_{n-2}$, and somehow expand this to $n/2$ spanning trees for $K_n$? Any help would be appreciated.
graph-theory recursion trees
edited Jan 24 at 21:55
Zach Langley
9731019
asked Jan 24 at 18:27
Einstein the trollEinstein the troll
144210
$endgroup$
add a comment |
$begingroup$
Let $K_n = (V, E)$ be a complete undirected graph with $n$ vertices (namely, every two vertices are connected), and let $n$ be an even number. A spanning tree of $G$ is a connected subgraph of $G$ that contains all vertices in $G$ and no cycles. Design a recursive algorithm that given the graph $K_n$, partitions the set of edges $E$ into $n/2$ distinct subsets $E_1,E_2,dots,E_{n/2}$, such that for every subset $E_i$, the subgraph $G_i = (V, E_i$) is a spanning tree of $K_n$.
(Hint: Solve the problem recursively by removing two nodes and their edges in $K_n$. From the output of recursive call, you get $(n − 2)/2$ spanning trees for $K_{n−2}$. Extend those trees to be spanning trees for $K_n$ and then construct a new spanning tree to complete the job. PS: A collection of sets $S_1,dots,S_k$ is a partition of $S$, if each $S_i$ is a subset of $S$, no two subsets have a non-empty intersection, and the union of all the subsets is $S$.)
Even with the hint, I'm struggling to understand how to solve this question. So when you remove two vertices, you get $n/2 - 1$ spanning trees for $K_{n-2}$, and somehow expand this to $n/2$ spanning trees for $K_n$? Any help would be appreciated.
graph-theory recursion trees
edited Jan 24 at 21:55
Zach Langley
9731019
asked Jan 24 at 18:27
Einstein the trollEinstein the troll
144210
$endgroup$
add a comment |
$begingroup$
Let $K_n = (V, E)$ be a complete undirected graph with $n$ vertices (namely, every two vertices are connected), and let $n$ be an even number. A spanning tree of $G$ is a connected subgraph of $G$ that contains all vertices in $G$ and no cycles. Design a recursive algorithm that given the graph $K_n$, partitions the set of edges $E$ into $n/2$ distinct subsets $E_1,E_2,dots,E_{n/2}$, such that for every subset $E_i$, the subgraph $G_i = (V, E_i$) is a spanning tree of $K_n$.
(Hint: Solve the problem recursively by removing two nodes and their edges in $K_n$. From the output of recursive call, you get $(n − 2)/2$ spanning trees for $K_{n−2}$. Extend those trees to be spanning trees for $K_n$ and then construct a new spanning tree to complete the job. PS: A collection of sets $S_1,dots,S_k$ is a partition of $S$, if each $S_i$ is a subset of $S$, no two subsets have a non-empty intersection, and the union of all the subsets is $S$.)
Even with the hint, I'm struggling to understand how to solve this question. So when you remove two vertices, you get $n/2 - 1$ spanning trees for $K_{n-2}$, and somehow expand this to $n/2$ spanning trees for $K_n$? Any help would be appreciated.
graph-theory recursion trees
edited Jan 24 at 21:55
Zach Langley
9731019
asked Jan 24 at 18:27
Einstein the trollEinstein the troll
144210
$endgroup$
Let $K_n = (V, E)$ be a complete undirected graph with $n$ vertices (namely, every two vertices are connected), and let $n$ be an even number. A spanning tree of $G$ is a connected subgraph of $G$ that contains all vertices in $G$ and no cycles. Design a recursive algorithm that given the graph $K_n$, partitions the set of edges $E$ into $n/2$ distinct subsets $E_1,E_2,dots,E_{n/2}$, such that for every subset $E_i$, the subgraph $G_i = (V, E_i$) is a spanning tree of $K_n$.
(Hint: Solve the problem recursively by removing two nodes and their edges in $K_n$. From the output of recursive call, you get $(n − 2)/2$ spanning trees for $K_{n−2}$. Extend those trees to be spanning trees for $K_n$ and then construct a new spanning tree to complete the job. PS: A collection of sets $S_1,dots,S_k$ is a partition of $S$, if each $S_i$ is a subset of $S$, no two subsets have a non-empty intersection, and the union of all the subsets is $S$.)
Even with the hint, I'm struggling to understand how to solve this question. So when you remove two vertices, you get $n/2 - 1$ spanning trees for $K_{n-2}$, and somehow expand this to $n/2$ spanning trees for $K_n$? Any help would be appreciated.
graph-theory recursion trees
graph-theory recursion trees
edited Jan 24 at 21:55
Zach Langley
9731019
asked Jan 24 at 18:27
Einstein the trollEinstein the troll
144210
edited Jan 24 at 21:55
Zach Langley
9731019
asked Jan 24 at 18:27
Einstein the trollEinstein the troll
144210
edited Jan 24 at 21:55
Zach Langley
9731019
edited Jan 24 at 21:55
Zach Langley
9731019
edited Jan 24 at 21:55
Zach Langley
9731019
9731019
asked Jan 24 at 18:27
Einstein the trollEinstein the troll
144210
asked Jan 24 at 18:27
Einstein the trollEinstein the troll
144210
asked Jan 24 at 18:27
Einstein the trollEinstein the troll
144210
144210
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Here is how one step of the construction might look like - going from a tree decomposition of $K_4$ to a tree decomposition of $K_6$.
On the left, we have (in orange and teal) a partition of the edges of a $K_4$ into two spanning trees. The $K_4$ is sitting inside a $K_6$ that we want to decompose. So on the right, we extend the orange and teal trees by two edges each to make them spanning trees of $K_6$, and add a purple tree consisting of the remaining edges.
To go from $K_6$ to $K_8$, you'll extend each of these three trees by two edges each, then add a fourth tree.
For any particular step, it is not too hard to make this work. The important thing is to figure out a pattern to tell you how to go from $n-2$ to $n$ for any even $n$. For this, you should try to do something as symmetric as possible, because symmetric things are easiest to describe.
For example, if we're adding two vertices $x$ and $y$, then there's one "unusual" edge: the edge $xy$. I made this edge part of the new, purple tree in the diagram above, because adding it to just one of the existing trees would break symmetry. You could still do it - it would just be harder to describe what you're doing generally.
From there, think about what we're doing to go from $K_4$ to $K_6$ - or try going from $K_6$ to $K_8$ yourself, if you think you need more to go on - and then generalize.
answered Jan 24 at 19:01
Misha LavrovMisha Lavrov
47.7k657107
$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%2f3086214%2fspanning-trees-for-complete-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$
Here is how one step of the construction might look like - going from a tree decomposition of $K_4$ to a tree decomposition of $K_6$.
On the left, we have (in orange and teal) a partition of the edges of a $K_4$ into two spanning trees. The $K_4$ is sitting inside a $K_6$ that we want to decompose. So on the right, we extend the orange and teal trees by two edges each to make them spanning trees of $K_6$, and add a purple tree consisting of the remaining edges.
To go from $K_6$ to $K_8$, you'll extend each of these three trees by two edges each, then add a fourth tree.
For any particular step, it is not too hard to make this work. The important thing is to figure out a pattern to tell you how to go from $n-2$ to $n$ for any even $n$. For this, you should try to do something as symmetric as possible, because symmetric things are easiest to describe.
For example, if we're adding two vertices $x$ and $y$, then there's one "unusual" edge: the edge $xy$. I made this edge part of the new, purple tree in the diagram above, because adding it to just one of the existing trees would break symmetry. You could still do it - it would just be harder to describe what you're doing generally.
From there, think about what we're doing to go from $K_4$ to $K_6$ - or try going from $K_6$ to $K_8$ yourself, if you think you need more to go on - and then generalize.
answered Jan 24 at 19:01
Misha LavrovMisha Lavrov
47.7k657107
$endgroup$
add a comment |
$begingroup$
Here is how one step of the construction might look like - going from a tree decomposition of $K_4$ to a tree decomposition of $K_6$.
On the left, we have (in orange and teal) a partition of the edges of a $K_4$ into two spanning trees. The $K_4$ is sitting inside a $K_6$ that we want to decompose. So on the right, we extend the orange and teal trees by two edges each to make them spanning trees of $K_6$, and add a purple tree consisting of the remaining edges.
To go from $K_6$ to $K_8$, you'll extend each of these three trees by two edges each, then add a fourth tree.
For any particular step, it is not too hard to make this work. The important thing is to figure out a pattern to tell you how to go from $n-2$ to $n$ for any even $n$. For this, you should try to do something as symmetric as possible, because symmetric things are easiest to describe.
For example, if we're adding two vertices $x$ and $y$, then there's one "unusual" edge: the edge $xy$. I made this edge part of the new, purple tree in the diagram above, because adding it to just one of the existing trees would break symmetry. You could still do it - it would just be harder to describe what you're doing generally.
From there, think about what we're doing to go from $K_4$ to $K_6$ - or try going from $K_6$ to $K_8$ yourself, if you think you need more to go on - and then generalize.
answered Jan 24 at 19:01
Misha LavrovMisha Lavrov
47.7k657107
$endgroup$
add a comment |
$begingroup$
Here is how one step of the construction might look like - going from a tree decomposition of $K_4$ to a tree decomposition of $K_6$.
On the left, we have (in orange and teal) a partition of the edges of a $K_4$ into two spanning trees. The $K_4$ is sitting inside a $K_6$ that we want to decompose. So on the right, we extend the orange and teal trees by two edges each to make them spanning trees of $K_6$, and add a purple tree consisting of the remaining edges.
To go from $K_6$ to $K_8$, you'll extend each of these three trees by two edges each, then add a fourth tree.
For any particular step, it is not too hard to make this work. The important thing is to figure out a pattern to tell you how to go from $n-2$ to $n$ for any even $n$. For this, you should try to do something as symmetric as possible, because symmetric things are easiest to describe.
For example, if we're adding two vertices $x$ and $y$, then there's one "unusual" edge: the edge $xy$. I made this edge part of the new, purple tree in the diagram above, because adding it to just one of the existing trees would break symmetry. You could still do it - it would just be harder to describe what you're doing generally.
From there, think about what we're doing to go from $K_4$ to $K_6$ - or try going from $K_6$ to $K_8$ yourself, if you think you need more to go on - and then generalize.
answered Jan 24 at 19:01
Misha LavrovMisha Lavrov
47.7k657107
$endgroup$
Here is how one step of the construction might look like - going from a tree decomposition of $K_4$ to a tree decomposition of $K_6$.
On the left, we have (in orange and teal) a partition of the edges of a $K_4$ into two spanning trees. The $K_4$ is sitting inside a $K_6$ that we want to decompose. So on the right, we extend the orange and teal trees by two edges each to make them spanning trees of $K_6$, and add a purple tree consisting of the remaining edges.
To go from $K_6$ to $K_8$, you'll extend each of these three trees by two edges each, then add a fourth tree.
For any particular step, it is not too hard to make this work. The important thing is to figure out a pattern to tell you how to go from $n-2$ to $n$ for any even $n$. For this, you should try to do something as symmetric as possible, because symmetric things are easiest to describe.
For example, if we're adding two vertices $x$ and $y$, then there's one "unusual" edge: the edge $xy$. I made this edge part of the new, purple tree in the diagram above, because adding it to just one of the existing trees would break symmetry. You could still do it - it would just be harder to describe what you're doing generally.
From there, think about what we're doing to go from $K_4$ to $K_6$ - or try going from $K_6$ to $K_8$ yourself, if you think you need more to go on - and then generalize.
answered Jan 24 at 19:01
Misha LavrovMisha Lavrov
47.7k657107
answered Jan 24 at 19:01
Misha LavrovMisha Lavrov
47.7k657107
answered Jan 24 at 19:01
Misha LavrovMisha Lavrov
47.7k657107
answered Jan 24 at 19:01
Misha LavrovMisha Lavrov
47.7k657107
47.7k657107
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%2f3086214%2fspanning-trees-for-complete-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
