Graph with perfect matching
up vote
2
down vote
favorite
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 8 hours ago
Mason
1,4581325
asked 9 hours ago
John doe
111
New contributor
John doe is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
2
down vote
favorite
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 8 hours ago
Mason
1,4581325
asked 9 hours ago
John doe
111
New contributor
John doe is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Can you include the title of the book in the question?
– Mason
9 hours ago
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
9 hours ago
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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 8 hours ago
Mason
1,4581325
asked 9 hours ago
John doe
111
New contributor
John doe is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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 8 hours ago
Mason
1,4581325
asked 9 hours ago
John doe
111
New contributor
John doe is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 8 hours ago
Mason
1,4581325
asked 9 hours ago
John doe
111
New contributor
John doe is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 8 hours ago
Mason
1,4581325
edited 8 hours ago
Mason
1,4581325
edited 8 hours ago
Mason
1,4581325
1,4581325
asked 9 hours ago
John doe
111
New contributor
John doe is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 9 hours ago
John doe
111
asked 9 hours ago
John doe
111
111
New contributor
John doe is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
John doe is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
John doe is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Can you include the title of the book in the question?
– Mason
9 hours ago
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
9 hours ago
add a comment |
Can you include the title of the book in the question?
– Mason
9 hours ago
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
9 hours ago
Can you include the title of the book in the question?
– Mason
9 hours ago
Can you include the title of the book in the question?
– Mason
9 hours ago
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
9 hours ago
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
9 hours ago
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
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 3 hours ago
hbm
937156
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
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 3 hours ago
hbm
937156
add a comment |
up vote
0
down vote
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 3 hours ago
hbm
937156
add a comment |
up vote
0
down vote
up vote
0
down vote
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 3 hours ago
hbm
937156
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 3 hours ago
hbm
937156
answered 3 hours ago
hbm
937156
answered 3 hours ago
hbm
937156
answered 3 hours ago
hbm
937156
937156
add a comment |
add a comment |
John doe is a new contributor. Be nice, and check out our Code of Conduct.
John doe is a new contributor. Be nice, and check out our Code of Conduct.
John doe is a new contributor. Be nice, and check out our Code of Conduct.
John doe is a new contributor. Be nice, and check out our Code of Conduct.
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
9 hours ago
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
9 hours ago