Are there $|M^{*}| - |M|$ augmenting paths with respect to $M$ in $G$ which are vertex disjoint?
up vote
1
down vote
favorite
I am reading a book about Graph Algorithms written by Takao Asano.
In the book, the author says the following proposition is true, without a proof.
Is the follwing proposition true or false?
If true, please tell me the proof.
Let $G$ be a graph.
Let $M^{*}$ be a maximum matching in $G$.
Let $M$ be a matching in $G$.
Then, there exist $|M^{*}| - |M|$ augmenting paths with respect to $M$ in $G$ which are vertex disjoint.
graph-theory algorithms matching-theory
add a comment |
up vote
1
down vote
favorite
I am reading a book about Graph Algorithms written by Takao Asano.
In the book, the author says the following proposition is true, without a proof.
Is the follwing proposition true or false?
If true, please tell me the proof.
Let $G$ be a graph.
Let $M^{*}$ be a maximum matching in $G$.
Let $M$ be a matching in $G$.
Then, there exist $|M^{*}| - |M|$ augmenting paths with respect to $M$ in $G$ which are vertex disjoint.
graph-theory algorithms matching-theory
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I am reading a book about Graph Algorithms written by Takao Asano.
In the book, the author says the following proposition is true, without a proof.
Is the follwing proposition true or false?
If true, please tell me the proof.
Let $G$ be a graph.
Let $M^{*}$ be a maximum matching in $G$.
Let $M$ be a matching in $G$.
Then, there exist $|M^{*}| - |M|$ augmenting paths with respect to $M$ in $G$ which are vertex disjoint.
graph-theory algorithms matching-theory
I am reading a book about Graph Algorithms written by Takao Asano.
In the book, the author says the following proposition is true, without a proof.
Is the follwing proposition true or false?
If true, please tell me the proof.
Let $G$ be a graph.
Let $M^{*}$ be a maximum matching in $G$.
Let $M$ be a matching in $G$.
Then, there exist $|M^{*}| - |M|$ augmenting paths with respect to $M$ in $G$ which are vertex disjoint.
graph-theory algorithms matching-theory
graph-theory algorithms matching-theory
asked 2 days ago
tchappy ha
35019
35019
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
As always, to compare two matchings, just take the symmetric difference $M mathbin{Delta} M^*$. (That is, take all edges in $M$ or $M^*$, but not both.)
The components of the subgraph spanned by $M mathbin{Delta} M^*$ are all paths or cycles, because all vertices have degree at most $2$. (At most, they are incident to one edge of $M$ and one edge of $M^*$.) The edges along such a path or cycle must alternate between edges of $M$ and edges of $M^*$. So we have the following types of components:
Even cycles, and paths with an even number of edges. We ignore these, because they have the same number of edges from both matchings.
Paths with one more edge from $M$ than from $M^*$. These would be augmenting paths for $M^*$, and so they can't actually exist, because $M^*$ is a maximum matching.
Paths with one more edge from $M^*$ than from $M$. These are augmenting paths for $M$, so they are what we want.
We know that there must be $k := |M^*| - |M|$ components of the third type, giving us $k$ vertex-disjoint $M$-augmenting paths. We know this because $M mathbin{Delta} M^*$ has $k$ more edges from $M^*$ than from $M$, and only components of the third type can give us more edges from $M^*$ than from $M$ (one extra edge per component).
Thank you very much, Misha Lavrov for very clear proof!
– tchappy ha
yesterday
I think "2. Paths with one more edge from $M$ than from $M^*$." and "3. Paths with one more edge from $M^*$ than from $M$." are correct. I cannot edit that.
– tchappy ha
yesterday
@tchappyha Thank you for catching that!
– Misha Lavrov
yesterday
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
As always, to compare two matchings, just take the symmetric difference $M mathbin{Delta} M^*$. (That is, take all edges in $M$ or $M^*$, but not both.)
The components of the subgraph spanned by $M mathbin{Delta} M^*$ are all paths or cycles, because all vertices have degree at most $2$. (At most, they are incident to one edge of $M$ and one edge of $M^*$.) The edges along such a path or cycle must alternate between edges of $M$ and edges of $M^*$. So we have the following types of components:
Even cycles, and paths with an even number of edges. We ignore these, because they have the same number of edges from both matchings.
Paths with one more edge from $M$ than from $M^*$. These would be augmenting paths for $M^*$, and so they can't actually exist, because $M^*$ is a maximum matching.
Paths with one more edge from $M^*$ than from $M$. These are augmenting paths for $M$, so they are what we want.
We know that there must be $k := |M^*| - |M|$ components of the third type, giving us $k$ vertex-disjoint $M$-augmenting paths. We know this because $M mathbin{Delta} M^*$ has $k$ more edges from $M^*$ than from $M$, and only components of the third type can give us more edges from $M^*$ than from $M$ (one extra edge per component).
Thank you very much, Misha Lavrov for very clear proof!
– tchappy ha
yesterday
I think "2. Paths with one more edge from $M$ than from $M^*$." and "3. Paths with one more edge from $M^*$ than from $M$." are correct. I cannot edit that.
– tchappy ha
yesterday
@tchappyha Thank you for catching that!
– Misha Lavrov
yesterday
add a comment |
up vote
1
down vote
accepted
As always, to compare two matchings, just take the symmetric difference $M mathbin{Delta} M^*$. (That is, take all edges in $M$ or $M^*$, but not both.)
The components of the subgraph spanned by $M mathbin{Delta} M^*$ are all paths or cycles, because all vertices have degree at most $2$. (At most, they are incident to one edge of $M$ and one edge of $M^*$.) The edges along such a path or cycle must alternate between edges of $M$ and edges of $M^*$. So we have the following types of components:
Even cycles, and paths with an even number of edges. We ignore these, because they have the same number of edges from both matchings.
Paths with one more edge from $M$ than from $M^*$. These would be augmenting paths for $M^*$, and so they can't actually exist, because $M^*$ is a maximum matching.
Paths with one more edge from $M^*$ than from $M$. These are augmenting paths for $M$, so they are what we want.
We know that there must be $k := |M^*| - |M|$ components of the third type, giving us $k$ vertex-disjoint $M$-augmenting paths. We know this because $M mathbin{Delta} M^*$ has $k$ more edges from $M^*$ than from $M$, and only components of the third type can give us more edges from $M^*$ than from $M$ (one extra edge per component).
Thank you very much, Misha Lavrov for very clear proof!
– tchappy ha
yesterday
I think "2. Paths with one more edge from $M$ than from $M^*$." and "3. Paths with one more edge from $M^*$ than from $M$." are correct. I cannot edit that.
– tchappy ha
yesterday
@tchappyha Thank you for catching that!
– Misha Lavrov
yesterday
add a comment |
up vote
1
down vote
accepted
up vote
1
down vote
accepted
As always, to compare two matchings, just take the symmetric difference $M mathbin{Delta} M^*$. (That is, take all edges in $M$ or $M^*$, but not both.)
The components of the subgraph spanned by $M mathbin{Delta} M^*$ are all paths or cycles, because all vertices have degree at most $2$. (At most, they are incident to one edge of $M$ and one edge of $M^*$.) The edges along such a path or cycle must alternate between edges of $M$ and edges of $M^*$. So we have the following types of components:
Even cycles, and paths with an even number of edges. We ignore these, because they have the same number of edges from both matchings.
Paths with one more edge from $M$ than from $M^*$. These would be augmenting paths for $M^*$, and so they can't actually exist, because $M^*$ is a maximum matching.
Paths with one more edge from $M^*$ than from $M$. These are augmenting paths for $M$, so they are what we want.
We know that there must be $k := |M^*| - |M|$ components of the third type, giving us $k$ vertex-disjoint $M$-augmenting paths. We know this because $M mathbin{Delta} M^*$ has $k$ more edges from $M^*$ than from $M$, and only components of the third type can give us more edges from $M^*$ than from $M$ (one extra edge per component).
As always, to compare two matchings, just take the symmetric difference $M mathbin{Delta} M^*$. (That is, take all edges in $M$ or $M^*$, but not both.)
The components of the subgraph spanned by $M mathbin{Delta} M^*$ are all paths or cycles, because all vertices have degree at most $2$. (At most, they are incident to one edge of $M$ and one edge of $M^*$.) The edges along such a path or cycle must alternate between edges of $M$ and edges of $M^*$. So we have the following types of components:
Even cycles, and paths with an even number of edges. We ignore these, because they have the same number of edges from both matchings.
Paths with one more edge from $M$ than from $M^*$. These would be augmenting paths for $M^*$, and so they can't actually exist, because $M^*$ is a maximum matching.
Paths with one more edge from $M^*$ than from $M$. These are augmenting paths for $M$, so they are what we want.
We know that there must be $k := |M^*| - |M|$ components of the third type, giving us $k$ vertex-disjoint $M$-augmenting paths. We know this because $M mathbin{Delta} M^*$ has $k$ more edges from $M^*$ than from $M$, and only components of the third type can give us more edges from $M^*$ than from $M$ (one extra edge per component).
edited yesterday
answered yesterday
Misha Lavrov
41.5k555101
41.5k555101
Thank you very much, Misha Lavrov for very clear proof!
– tchappy ha
yesterday
I think "2. Paths with one more edge from $M$ than from $M^*$." and "3. Paths with one more edge from $M^*$ than from $M$." are correct. I cannot edit that.
– tchappy ha
yesterday
@tchappyha Thank you for catching that!
– Misha Lavrov
yesterday
add a comment |
Thank you very much, Misha Lavrov for very clear proof!
– tchappy ha
yesterday
I think "2. Paths with one more edge from $M$ than from $M^*$." and "3. Paths with one more edge from $M^*$ than from $M$." are correct. I cannot edit that.
– tchappy ha
yesterday
@tchappyha Thank you for catching that!
– Misha Lavrov
yesterday
Thank you very much, Misha Lavrov for very clear proof!
– tchappy ha
yesterday
Thank you very much, Misha Lavrov for very clear proof!
– tchappy ha
yesterday
I think "2. Paths with one more edge from $M$ than from $M^*$." and "3. Paths with one more edge from $M^*$ than from $M$." are correct. I cannot edit that.
– tchappy ha
yesterday
I think "2. Paths with one more edge from $M$ than from $M^*$." and "3. Paths with one more edge from $M^*$ than from $M$." are correct. I cannot edit that.
– tchappy ha
yesterday
@tchappyha Thank you for catching that!
– Misha Lavrov
yesterday
@tchappyha Thank you for catching that!
– Misha Lavrov
yesterday
add a comment |
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%2f2999328%2fare-there-m-m-augmenting-paths-with-respect-to-m-in-g-which-are%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