Route Inspection Problem
up vote
3
down vote
favorite
The route inspection problem, is to find a shortest closed path that visits every edge of a connected undirected graph.
If $G = (V,E)$ is a tree, then any route inspection tour has $2vert Evert$ egdes in it (counted with multiplicity).
I would like to show that if $G$ is not a tree, then a route inspection tour has at most $2vert Evert - 1$ edges (or maybe even less). I assume this has to do with the fact that $G$ has in this case a cycle, but I cannot find the correct argument.
graph-theory eulerian-path
asked Oct 29 at 15:20
netty
264
add a comment |
up vote
3
down vote
favorite
The route inspection problem, is to find a shortest closed path that visits every edge of a connected undirected graph.
If $G = (V,E)$ is a tree, then any route inspection tour has $2vert Evert$ egdes in it (counted with multiplicity).
I would like to show that if $G$ is not a tree, then a route inspection tour has at most $2vert Evert - 1$ edges (or maybe even less). I assume this has to do with the fact that $G$ has in this case a cycle, but I cannot find the correct argument.
graph-theory eulerian-path
asked Oct 29 at 15:20
netty
264
Sorry about my first post. Being more cautious now, I'll start this off as a comment: how about $K_{3,2}$? In producing the optimal solution as on the Wikipedia article for the CPP, we have to double all edges, as every edge is incident to a vertex of odd degree, but no two odd vertices are actually adjacent, so we really have $2#E$ edges to cover, and this graph has a cycle.
– Sam Streeter
Oct 29 at 16:56
I find a tour with $7$ edges. I admit that I don't find the wikipedia article super clear...
– netty
Oct 29 at 17:07
If the graph has a $k$-cycle, then you can get down to $2|E|-k$ by deciding that the edges in the cycle are going to be used one each, and the rest of the edges covered by tree-shaped excursions from that cycle.
– Henning Makholm
Oct 29 at 17:27
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
The route inspection problem, is to find a shortest closed path that visits every edge of a connected undirected graph.
If $G = (V,E)$ is a tree, then any route inspection tour has $2vert Evert$ egdes in it (counted with multiplicity).
I would like to show that if $G$ is not a tree, then a route inspection tour has at most $2vert Evert - 1$ edges (or maybe even less). I assume this has to do with the fact that $G$ has in this case a cycle, but I cannot find the correct argument.
graph-theory eulerian-path
asked Oct 29 at 15:20
netty
264
The route inspection problem, is to find a shortest closed path that visits every edge of a connected undirected graph.
If $G = (V,E)$ is a tree, then any route inspection tour has $2vert Evert$ egdes in it (counted with multiplicity).
I would like to show that if $G$ is not a tree, then a route inspection tour has at most $2vert Evert - 1$ edges (or maybe even less). I assume this has to do with the fact that $G$ has in this case a cycle, but I cannot find the correct argument.
graph-theory eulerian-path
graph-theory eulerian-path
asked Oct 29 at 15:20
netty
264
asked Oct 29 at 15:20
netty
264
edited Nov 16 at 18:22
asked Oct 29 at 15:20
netty
264
asked Oct 29 at 15:20
netty
264
asked Oct 29 at 15:20
netty
264
264
Sorry about my first post. Being more cautious now, I'll start this off as a comment: how about $K_{3,2}$? In producing the optimal solution as on the Wikipedia article for the CPP, we have to double all edges, as every edge is incident to a vertex of odd degree, but no two odd vertices are actually adjacent, so we really have $2#E$ edges to cover, and this graph has a cycle.
– Sam Streeter
Oct 29 at 16:56
I find a tour with $7$ edges. I admit that I don't find the wikipedia article super clear...
– netty
Oct 29 at 17:07
If the graph has a $k$-cycle, then you can get down to $2|E|-k$ by deciding that the edges in the cycle are going to be used one each, and the rest of the edges covered by tree-shaped excursions from that cycle.
– Henning Makholm
Oct 29 at 17:27
add a comment |
Sorry about my first post. Being more cautious now, I'll start this off as a comment: how about $K_{3,2}$? In producing the optimal solution as on the Wikipedia article for the CPP, we have to double all edges, as every edge is incident to a vertex of odd degree, but no two odd vertices are actually adjacent, so we really have $2#E$ edges to cover, and this graph has a cycle.
– Sam Streeter
Oct 29 at 16:56
I find a tour with $7$ edges. I admit that I don't find the wikipedia article super clear...
– netty
Oct 29 at 17:07
If the graph has a $k$-cycle, then you can get down to $2|E|-k$ by deciding that the edges in the cycle are going to be used one each, and the rest of the edges covered by tree-shaped excursions from that cycle.
– Henning Makholm
Oct 29 at 17:27
Sorry about my first post. Being more cautious now, I'll start this off as a comment: how about $K_{3,2}$? In producing the optimal solution as on the Wikipedia article for the CPP, we have to double all edges, as every edge is incident to a vertex of odd degree, but no two odd vertices are actually adjacent, so we really have $2#E$ edges to cover, and this graph has a cycle.
– Sam Streeter
Oct 29 at 16:56
Sorry about my first post. Being more cautious now, I'll start this off as a comment: how about $K_{3,2}$? In producing the optimal solution as on the Wikipedia article for the CPP, we have to double all edges, as every edge is incident to a vertex of odd degree, but no two odd vertices are actually adjacent, so we really have $2#E$ edges to cover, and this graph has a cycle.
– Sam Streeter
Oct 29 at 16:56
I find a tour with $7$ edges. I admit that I don't find the wikipedia article super clear...
– netty
Oct 29 at 17:07
I find a tour with $7$ edges. I admit that I don't find the wikipedia article super clear...
– netty
Oct 29 at 17:07
If the graph has a $k$-cycle, then you can get down to $2|E|-k$ by deciding that the edges in the cycle are going to be used one each, and the rest of the edges covered by tree-shaped excursions from that cycle.
– Henning Makholm
Oct 29 at 17:27
If the graph has a $k$-cycle, then you can get down to $2|E|-k$ by deciding that the edges in the cycle are going to be used one each, and the rest of the edges covered by tree-shaped excursions from that cycle.
– Henning Makholm
Oct 29 at 17:27
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
I would try to do induction over the number of edges $m$:
For the induction step $m rightarrow (m+1)$, consider something like this:
Let $G$ be any non-tree connected graph on $n$ vertices and $m+1$ edges. Because $G$ is not a tree, we can find an edge $e = {u, v }$ which does not destroy connectivity if we remove it. Now me remove this edge from $G$ and obtain a graph $G*$ with only $m$ edges.
There are now two cases:
1) $G*$ is not a tree. By induction hypothesis there is a postman tour on $G*$ with at most $2m - 1$ edges. Now we consider this tour in $G$. It covers all edges but $e$. Hence we obtain a postman tour for $G$ by simply adding it twice into the postman tour for $G*$. This postman tour for $G$ now has at most $2m - 1 + 2 = 2(m+1) - 1$ edges. (Actually this might not be a true postman tour for $G$ because it might not be the shortest possible. But this still proves that a postman tour for $G$ cannot have more than $2(m+1) - 1$ edges.)
2) $G*$ is a tree. Then we know that there is a postman tour for $G*$ with exactly $2m$ edges. Consider now this postman tour on $G$. It covers any edge but $e$ exactly twice. In particular, written in terms of nodes it looks like this: $ (u, ... , v, ... , u)$. Because all edges between $u$ and $v$ are covered twice, we can remove them once and replace them with the edge $e$. We obtain a postman tour $ (u, v, ... , u)$ with at most $2*m + 1 = 2(m+1) - 1$ edges.
Hope this helps. If you don't get what I am trying to do just ask again, I had quite some trouble explaining the second case.
answered Oct 29 at 17:22
araomis
3439
In 2) I don't understand what "remove them once and replace them with the edge $e$" means. Does it also means that we cannot do better than $2text{Card}(E)-1$ in case of a non tree? Do you see a graph for which this is reached? Thanks for you answer!
– netty
Oct 29 at 17:33
Ok, so what I mean by that is the following: you have a tour $t$ through all edges and therefore through all nodes. So on your tour $t$ you come by the node $u$, then you go on and eventually come by the node $v$ and then continue and eventually get back to $u$. The goal is now to build a new tour $t$ which contains also the edge $e$. To achieve this, you go along the tour $t$, come along $u$ and then along $v$. But now instead of following $t$, you go from $v$ directly back to $u$ using edge $e$. This you define as your new tour. It covers all edges.
– araomis
Oct 29 at 19:37
Actually I didn't find any example where this is reached. I guess you could prove that for a non-tree the upper bound is $2Card(E) - 3$. When you modify the tour in case 2) you actually add one edge but remove at least two others. So the there the length is at most $2*m - 1 = 2(m+1) - 3$.
– araomis
Oct 29 at 19:37
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
I would try to do induction over the number of edges $m$:
For the induction step $m rightarrow (m+1)$, consider something like this:
Let $G$ be any non-tree connected graph on $n$ vertices and $m+1$ edges. Because $G$ is not a tree, we can find an edge $e = {u, v }$ which does not destroy connectivity if we remove it. Now me remove this edge from $G$ and obtain a graph $G*$ with only $m$ edges.
There are now two cases:
1) $G*$ is not a tree. By induction hypothesis there is a postman tour on $G*$ with at most $2m - 1$ edges. Now we consider this tour in $G$. It covers all edges but $e$. Hence we obtain a postman tour for $G$ by simply adding it twice into the postman tour for $G*$. This postman tour for $G$ now has at most $2m - 1 + 2 = 2(m+1) - 1$ edges. (Actually this might not be a true postman tour for $G$ because it might not be the shortest possible. But this still proves that a postman tour for $G$ cannot have more than $2(m+1) - 1$ edges.)
2) $G*$ is a tree. Then we know that there is a postman tour for $G*$ with exactly $2m$ edges. Consider now this postman tour on $G$. It covers any edge but $e$ exactly twice. In particular, written in terms of nodes it looks like this: $ (u, ... , v, ... , u)$. Because all edges between $u$ and $v$ are covered twice, we can remove them once and replace them with the edge $e$. We obtain a postman tour $ (u, v, ... , u)$ with at most $2*m + 1 = 2(m+1) - 1$ edges.
Hope this helps. If you don't get what I am trying to do just ask again, I had quite some trouble explaining the second case.
answered Oct 29 at 17:22
araomis
3439
In 2) I don't understand what "remove them once and replace them with the edge $e$" means. Does it also means that we cannot do better than $2text{Card}(E)-1$ in case of a non tree? Do you see a graph for which this is reached? Thanks for you answer!
– netty
Oct 29 at 17:33
Ok, so what I mean by that is the following: you have a tour $t$ through all edges and therefore through all nodes. So on your tour $t$ you come by the node $u$, then you go on and eventually come by the node $v$ and then continue and eventually get back to $u$. The goal is now to build a new tour $t$ which contains also the edge $e$. To achieve this, you go along the tour $t$, come along $u$ and then along $v$. But now instead of following $t$, you go from $v$ directly back to $u$ using edge $e$. This you define as your new tour. It covers all edges.
– araomis
Oct 29 at 19:37
Actually I didn't find any example where this is reached. I guess you could prove that for a non-tree the upper bound is $2Card(E) - 3$. When you modify the tour in case 2) you actually add one edge but remove at least two others. So the there the length is at most $2*m - 1 = 2(m+1) - 3$.
– araomis
Oct 29 at 19:37
add a comment |
up vote
0
down vote
I would try to do induction over the number of edges $m$:
For the induction step $m rightarrow (m+1)$, consider something like this:
Let $G$ be any non-tree connected graph on $n$ vertices and $m+1$ edges. Because $G$ is not a tree, we can find an edge $e = {u, v }$ which does not destroy connectivity if we remove it. Now me remove this edge from $G$ and obtain a graph $G*$ with only $m$ edges.
There are now two cases:
1) $G*$ is not a tree. By induction hypothesis there is a postman tour on $G*$ with at most $2m - 1$ edges. Now we consider this tour in $G$. It covers all edges but $e$. Hence we obtain a postman tour for $G$ by simply adding it twice into the postman tour for $G*$. This postman tour for $G$ now has at most $2m - 1 + 2 = 2(m+1) - 1$ edges. (Actually this might not be a true postman tour for $G$ because it might not be the shortest possible. But this still proves that a postman tour for $G$ cannot have more than $2(m+1) - 1$ edges.)
2) $G*$ is a tree. Then we know that there is a postman tour for $G*$ with exactly $2m$ edges. Consider now this postman tour on $G$. It covers any edge but $e$ exactly twice. In particular, written in terms of nodes it looks like this: $ (u, ... , v, ... , u)$. Because all edges between $u$ and $v$ are covered twice, we can remove them once and replace them with the edge $e$. We obtain a postman tour $ (u, v, ... , u)$ with at most $2*m + 1 = 2(m+1) - 1$ edges.
Hope this helps. If you don't get what I am trying to do just ask again, I had quite some trouble explaining the second case.
answered Oct 29 at 17:22
araomis
3439
In 2) I don't understand what "remove them once and replace them with the edge $e$" means. Does it also means that we cannot do better than $2text{Card}(E)-1$ in case of a non tree? Do you see a graph for which this is reached? Thanks for you answer!
– netty
Oct 29 at 17:33
Ok, so what I mean by that is the following: you have a tour $t$ through all edges and therefore through all nodes. So on your tour $t$ you come by the node $u$, then you go on and eventually come by the node $v$ and then continue and eventually get back to $u$. The goal is now to build a new tour $t$ which contains also the edge $e$. To achieve this, you go along the tour $t$, come along $u$ and then along $v$. But now instead of following $t$, you go from $v$ directly back to $u$ using edge $e$. This you define as your new tour. It covers all edges.
– araomis
Oct 29 at 19:37
Actually I didn't find any example where this is reached. I guess you could prove that for a non-tree the upper bound is $2Card(E) - 3$. When you modify the tour in case 2) you actually add one edge but remove at least two others. So the there the length is at most $2*m - 1 = 2(m+1) - 3$.
– araomis
Oct 29 at 19:37
add a comment |
up vote
0
down vote
up vote
0
down vote
I would try to do induction over the number of edges $m$:
For the induction step $m rightarrow (m+1)$, consider something like this:
Let $G$ be any non-tree connected graph on $n$ vertices and $m+1$ edges. Because $G$ is not a tree, we can find an edge $e = {u, v }$ which does not destroy connectivity if we remove it. Now me remove this edge from $G$ and obtain a graph $G*$ with only $m$ edges.
There are now two cases:
1) $G*$ is not a tree. By induction hypothesis there is a postman tour on $G*$ with at most $2m - 1$ edges. Now we consider this tour in $G$. It covers all edges but $e$. Hence we obtain a postman tour for $G$ by simply adding it twice into the postman tour for $G*$. This postman tour for $G$ now has at most $2m - 1 + 2 = 2(m+1) - 1$ edges. (Actually this might not be a true postman tour for $G$ because it might not be the shortest possible. But this still proves that a postman tour for $G$ cannot have more than $2(m+1) - 1$ edges.)
2) $G*$ is a tree. Then we know that there is a postman tour for $G*$ with exactly $2m$ edges. Consider now this postman tour on $G$. It covers any edge but $e$ exactly twice. In particular, written in terms of nodes it looks like this: $ (u, ... , v, ... , u)$. Because all edges between $u$ and $v$ are covered twice, we can remove them once and replace them with the edge $e$. We obtain a postman tour $ (u, v, ... , u)$ with at most $2*m + 1 = 2(m+1) - 1$ edges.
Hope this helps. If you don't get what I am trying to do just ask again, I had quite some trouble explaining the second case.
answered Oct 29 at 17:22
araomis
3439
I would try to do induction over the number of edges $m$:
For the induction step $m rightarrow (m+1)$, consider something like this:
Let $G$ be any non-tree connected graph on $n$ vertices and $m+1$ edges. Because $G$ is not a tree, we can find an edge $e = {u, v }$ which does not destroy connectivity if we remove it. Now me remove this edge from $G$ and obtain a graph $G*$ with only $m$ edges.
There are now two cases:
1) $G*$ is not a tree. By induction hypothesis there is a postman tour on $G*$ with at most $2m - 1$ edges. Now we consider this tour in $G$. It covers all edges but $e$. Hence we obtain a postman tour for $G$ by simply adding it twice into the postman tour for $G*$. This postman tour for $G$ now has at most $2m - 1 + 2 = 2(m+1) - 1$ edges. (Actually this might not be a true postman tour for $G$ because it might not be the shortest possible. But this still proves that a postman tour for $G$ cannot have more than $2(m+1) - 1$ edges.)
2) $G*$ is a tree. Then we know that there is a postman tour for $G*$ with exactly $2m$ edges. Consider now this postman tour on $G$. It covers any edge but $e$ exactly twice. In particular, written in terms of nodes it looks like this: $ (u, ... , v, ... , u)$. Because all edges between $u$ and $v$ are covered twice, we can remove them once and replace them with the edge $e$. We obtain a postman tour $ (u, v, ... , u)$ with at most $2*m + 1 = 2(m+1) - 1$ edges.
Hope this helps. If you don't get what I am trying to do just ask again, I had quite some trouble explaining the second case.
answered Oct 29 at 17:22
araomis
3439
answered Oct 29 at 17:22
araomis
3439
answered Oct 29 at 17:22
araomis
3439
answered Oct 29 at 17:22
araomis
3439
3439
In 2) I don't understand what "remove them once and replace them with the edge $e$" means. Does it also means that we cannot do better than $2text{Card}(E)-1$ in case of a non tree? Do you see a graph for which this is reached? Thanks for you answer!
– netty
Oct 29 at 17:33
Ok, so what I mean by that is the following: you have a tour $t$ through all edges and therefore through all nodes. So on your tour $t$ you come by the node $u$, then you go on and eventually come by the node $v$ and then continue and eventually get back to $u$. The goal is now to build a new tour $t$ which contains also the edge $e$. To achieve this, you go along the tour $t$, come along $u$ and then along $v$. But now instead of following $t$, you go from $v$ directly back to $u$ using edge $e$. This you define as your new tour. It covers all edges.
– araomis
Oct 29 at 19:37
Actually I didn't find any example where this is reached. I guess you could prove that for a non-tree the upper bound is $2Card(E) - 3$. When you modify the tour in case 2) you actually add one edge but remove at least two others. So the there the length is at most $2*m - 1 = 2(m+1) - 3$.
– araomis
Oct 29 at 19:37
add a comment |
In 2) I don't understand what "remove them once and replace them with the edge $e$" means. Does it also means that we cannot do better than $2text{Card}(E)-1$ in case of a non tree? Do you see a graph for which this is reached? Thanks for you answer!
– netty
Oct 29 at 17:33
Ok, so what I mean by that is the following: you have a tour $t$ through all edges and therefore through all nodes. So on your tour $t$ you come by the node $u$, then you go on and eventually come by the node $v$ and then continue and eventually get back to $u$. The goal is now to build a new tour $t$ which contains also the edge $e$. To achieve this, you go along the tour $t$, come along $u$ and then along $v$. But now instead of following $t$, you go from $v$ directly back to $u$ using edge $e$. This you define as your new tour. It covers all edges.
– araomis
Oct 29 at 19:37
Actually I didn't find any example where this is reached. I guess you could prove that for a non-tree the upper bound is $2Card(E) - 3$. When you modify the tour in case 2) you actually add one edge but remove at least two others. So the there the length is at most $2*m - 1 = 2(m+1) - 3$.
– araomis
Oct 29 at 19:37
In 2) I don't understand what "remove them once and replace them with the edge $e$" means. Does it also means that we cannot do better than $2text{Card}(E)-1$ in case of a non tree? Do you see a graph for which this is reached? Thanks for you answer!
– netty
Oct 29 at 17:33
In 2) I don't understand what "remove them once and replace them with the edge $e$" means. Does it also means that we cannot do better than $2text{Card}(E)-1$ in case of a non tree? Do you see a graph for which this is reached? Thanks for you answer!
– netty
Oct 29 at 17:33
Ok, so what I mean by that is the following: you have a tour $t$ through all edges and therefore through all nodes. So on your tour $t$ you come by the node $u$, then you go on and eventually come by the node $v$ and then continue and eventually get back to $u$. The goal is now to build a new tour $t$ which contains also the edge $e$. To achieve this, you go along the tour $t$, come along $u$ and then along $v$. But now instead of following $t$, you go from $v$ directly back to $u$ using edge $e$. This you define as your new tour. It covers all edges.
– araomis
Oct 29 at 19:37
Ok, so what I mean by that is the following: you have a tour $t$ through all edges and therefore through all nodes. So on your tour $t$ you come by the node $u$, then you go on and eventually come by the node $v$ and then continue and eventually get back to $u$. The goal is now to build a new tour $t$ which contains also the edge $e$. To achieve this, you go along the tour $t$, come along $u$ and then along $v$. But now instead of following $t$, you go from $v$ directly back to $u$ using edge $e$. This you define as your new tour. It covers all edges.
– araomis
Oct 29 at 19:37
Actually I didn't find any example where this is reached. I guess you could prove that for a non-tree the upper bound is $2Card(E) - 3$. When you modify the tour in case 2) you actually add one edge but remove at least two others. So the there the length is at most $2*m - 1 = 2(m+1) - 3$.
– araomis
Oct 29 at 19:37
Actually I didn't find any example where this is reached. I guess you could prove that for a non-tree the upper bound is $2Card(E) - 3$. When you modify the tour in case 2) you actually add one edge but remove at least two others. So the there the length is at most $2*m - 1 = 2(m+1) - 3$.
– araomis
Oct 29 at 19:37
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%2f2976256%2froute-inspection-problem%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
Sorry about my first post. Being more cautious now, I'll start this off as a comment: how about $K_{3,2}$? In producing the optimal solution as on the Wikipedia article for the CPP, we have to double all edges, as every edge is incident to a vertex of odd degree, but no two odd vertices are actually adjacent, so we really have $2#E$ edges to cover, and this graph has a cycle.
– Sam Streeter
Oct 29 at 16:56
I find a tour with $7$ edges. I admit that I don't find the wikipedia article super clear...
– netty
Oct 29 at 17:07
If the graph has a $k$-cycle, then you can get down to $2|E|-k$ by deciding that the edges in the cycle are going to be used one each, and the rest of the edges covered by tree-shaped excursions from that cycle.
– Henning Makholm
Oct 29 at 17:27