Mixing
Graph with perfect matching
Let $G = (V, E)$ be a connected graph which has a perfect matching. Devise (and prove its correctness) an $O(|V | + |E|)$ time complexity algorithm that constructs a spanning tree $T$ of $G$ such that $V (T)$ admits a bipartition in two stable sets of maximum cardinality in $T$.
I encountered this problem in a book I have about graphs theory, and I struggled for a couple of hours already. The problem is I do not have a starting point for it. Any kind of help would be appreciated.
graph-theory
edited Nov 16 '18 at 8:23
Mason
1,9641530
asked Nov 16 '18 at 7:47
John doe
82
add a comment |
Let $G = (V, E)$ be a connected graph which has a perfect matching. Devise (and prove its correctness) an $O(|V | + |E|)$ time complexity algorithm that constructs a spanning tree $T$ of $G$ such that $V (T)$ admits a bipartition in two stable sets of maximum cardinality in $T$.
I encountered this problem in a book I have about graphs theory, and I struggled for a couple of hours already. The problem is I do not have a starting point for it. Any kind of help would be appreciated.
graph-theory
edited Nov 16 '18 at 8:23
Mason
1,9641530
asked Nov 16 '18 at 7:47
John doe
82
Can you include the title of the book in the question?
– Mason
Nov 16 '18 at 7:51
It is a book based on this book (written by a local author) "Lovasz L., Combinatorial Problems and Exercises, 2nd edition, North Holland, 1993"
– John doe
Nov 16 '18 at 7:54
add a comment |
Let $G = (V, E)$ be a connected graph which has a perfect matching. Devise (and prove its correctness) an $O(|V | + |E|)$ time complexity algorithm that constructs a spanning tree $T$ of $G$ such that $V (T)$ admits a bipartition in two stable sets of maximum cardinality in $T$.
I encountered this problem in a book I have about graphs theory, and I struggled for a couple of hours already. The problem is I do not have a starting point for it. Any kind of help would be appreciated.
graph-theory
edited Nov 16 '18 at 8:23
Mason
1,9641530
asked Nov 16 '18 at 7:47
John doe
82
Let $G = (V, E)$ be a connected graph which has a perfect matching. Devise (and prove its correctness) an $O(|V | + |E|)$ time complexity algorithm that constructs a spanning tree $T$ of $G$ such that $V (T)$ admits a bipartition in two stable sets of maximum cardinality in $T$.
I encountered this problem in a book I have about graphs theory, and I struggled for a couple of hours already. The problem is I do not have a starting point for it. Any kind of help would be appreciated.
graph-theory
graph-theory
edited Nov 16 '18 at 8:23
Mason
1,9641530
asked Nov 16 '18 at 7:47
John doe
82
edited Nov 16 '18 at 8:23
Mason
1,9641530
asked Nov 16 '18 at 7:47
John doe
82
edited Nov 16 '18 at 8:23
Mason
1,9641530
edited Nov 16 '18 at 8:23
Mason
1,9641530
edited Nov 16 '18 at 8:23
Mason
1,9641530
1,9641530
asked Nov 16 '18 at 7:47
John doe
82
asked Nov 16 '18 at 7:47
John doe
82
asked Nov 16 '18 at 7:47
John doe
82
82
Can you include the title of the book in the question?
– Mason
Nov 16 '18 at 7:51
It is a book based on this book (written by a local author) "Lovasz L., Combinatorial Problems and Exercises, 2nd edition, North Holland, 1993"
– John doe
Nov 16 '18 at 7:54
add a comment |
Can you include the title of the book in the question?
– Mason
Nov 16 '18 at 7:51
It is a book based on this book (written by a local author) "Lovasz L., Combinatorial Problems and Exercises, 2nd edition, North Holland, 1993"
– John doe
Nov 16 '18 at 7:54
Can you include the title of the book in the question?
– Mason
Nov 16 '18 at 7:51
Can you include the title of the book in the question?
– Mason
Nov 16 '18 at 7:51
It is a book based on this book (written by a local author) "Lovasz L., Combinatorial Problems and Exercises, 2nd edition, North Holland, 1993"
– John doe
Nov 16 '18 at 7:54
It is a book based on this book (written by a local author) "Lovasz L., Combinatorial Problems and Exercises, 2nd edition, North Holland, 1993"
– John doe
Nov 16 '18 at 7:54
add a comment |
1 Answer
1
active
oldest
votes
Modify BSF so that whenever a vertex is labeled as visited the matched vertex under the perfect matching is also labeled. The resulting tree will have the desired property.
answered Nov 16 '18 at 13:58
hbm
957156
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%2f3000855%2fgraph-with-perfect-matching%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
Modify BSF so that whenever a vertex is labeled as visited the matched vertex under the perfect matching is also labeled. The resulting tree will have the desired property.
answered Nov 16 '18 at 13:58
hbm
957156
add a comment |
Modify BSF so that whenever a vertex is labeled as visited the matched vertex under the perfect matching is also labeled. The resulting tree will have the desired property.
answered Nov 16 '18 at 13:58
hbm
957156
add a comment |
Modify BSF so that whenever a vertex is labeled as visited the matched vertex under the perfect matching is also labeled. The resulting tree will have the desired property.
answered Nov 16 '18 at 13:58
hbm
957156
Modify BSF so that whenever a vertex is labeled as visited the matched vertex under the perfect matching is also labeled. The resulting tree will have the desired property.
answered Nov 16 '18 at 13:58
hbm
957156
answered Nov 16 '18 at 13:58
hbm
957156
answered Nov 16 '18 at 13:58
hbm
957156
answered Nov 16 '18 at 13:58
hbm
957156
957156
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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%2fmath.stackexchange.com%2fquestions%2f3000855%2fgraph-with-perfect-matching%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
Can you include the title of the book in the question?
– Mason
Nov 16 '18 at 7:51
It is a book based on this book (written by a local author) "Lovasz L., Combinatorial Problems and Exercises, 2nd edition, North Holland, 1993"
– John doe
Nov 16 '18 at 7:54