![]() | This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
![]() | On 8 October 2022, it was proposed that this article be moved from Route inspection problem to Chinese postman problem. The result of the discussion was moved. |
Is the information here relevance to the "route inspection problem"? It seems a little bit off topic to me. Dysprosia 11:23, 2 Oct 2003 (UTC)
It seems that the drfinition of the rural postman problem should be change to 'find a minimum weight closed route that traverses a given set of edges' (shuroo)
The article says:
but above it, it says "if and only if". Which is it?
It is not about Hamiltonian (going through nodes) but about Eulerian (going through edges) cycles. A non-oriented connected graph G=(V,E) has an Eulerian cycle if and only if all nodes have even degree.
The article says:
1 → 2
2 → 3
3 → 1
Is this a correct way of demonstrating the validity of those equivalences? -- 213.100.56.253 00:46, 24 May 2007 (UTC)
The "Solution" section deals only with eulerian and non-eulerian graphs, stating that if the graph is eulerian, an eulerian path can be found, otherwise another method can give the shortest path possible. However, wouldn't it be more appropriate to make the distinction between semi-eulerian graphs and non-semi-eulerian graphs? Because all semi-eulerian graphs, whether they are also eulerian or not, have eulerian paths. ( Tanynep ( talk) 12:24, 10 May 2009 (UTC))
The standard usage in graph theory is that a path has no repeated vertices or edges. A trail has no repeated vertices, but it may repeat edges. A walk has no repeated vertices or edges.
A closed walk or trail has the same initial and final vertices. An open walk or trail has different initial and final vertices. A closed path is a closed trail that doesn't repeat a vertex except for the initial and final vertices.
A circuit may be several things. It may be a closed path (or the graph of a closed path), which is also usually called a cycle; or it may be a closed trail.
These are graph-theory customs. The customary terminology in electrical engineering, computer science, or social network analysis may differ in various ways.
See almost any graph theory book written by mathematicians (as opposed to engineers, et al.): Bondy and Murty; Diestel; Bollobas; others that I don't remember at the moment. Zaslav ( talk) 05:26, 28 April 2010 (UTC)
"Eulerian trail" is used for the open trail, and "Eulerian path" is also used. "Eulerian tour" and "Eulerian circuit" are used for the closed trail. You seem to be saying "path" is not correct but you insist on using it. Why? See Talk:Eulerian path for more.
An Eulerian trail/path does not repeat edges. The correct statement is that a graph does not have an Eulerian trail/path if it is necessary to repeat edges. I do not understand why you say different. Zaslav ( talk) 16:51, 28 April 2010 (UTC)
Does anyone know anything about Mei-Ko Kwan the person himself? His name is conspicuous by its complete absence anywhere on the Net other than a brief sentence about how he deduced the Chinese Postman algorithm. There aren't even any photos of him, or any information about where he was born/died or where he lived and did his work.
This is especially odd considering he published his algorithm in 1962, which can't have been easy considering that China was probably one of the worst places to be seen to be an intellectual at the time. — Preceding unsigned comment added by Holy triple m ( talk • contribs) 15:30, 21 February 2011 (UTC)
The whole T-paths section is a complete mess. Where are you getting 1/2 |T| "paths" from? What is this. —Preceding unsigned comment added by 24.15.220.182 ( talk) 01:55, 26 April 2011 (UTC)
The text says: "When T is the empty set, a smallest T-join leads to a solution of the postman problem." But Schrijver's book, Corollary 29.1d, gives us a solution of that problem by T=vertices of odd degree. Did I misunderstand something or is there an error in the text? -- Star Flyer ( talk) 20:51, 18 January 2013 (UTC)
I propose that Chinese postman problem be merged into Route inspection problem.
The article implies that the Rural Salesman (not every edge required) is considered NP-complete, however the source on Rural Salesman is behind a paywall and the citation for the assertion doesn't mention the Rural Salesman. It seems un-intuitive that the original would be P while this variant is NP. If this is the case, an explanation added (or at least a source) would be helpful 50.241.129.75 ( talk) 20:40, 8 November 2017 (UTC)
In Special:Diff/1085693210 I removed a huge pile of material describing metaheuristics for variant problems, added by User:ScientistBuilder, almost completely off-topic to the main subject of this article, and five times as long as the on-topic content of the article. This is not the place for describing those problems in such detail. Adding it here totally unbalances the article. — David Eppstein ( talk) 23:12, 1 May 2022 (UTC)
The result of the move request was: moved. ( non-admin closure) Rotideypoc41352 ( talk · contribs) 03:30, 16 October 2022 (UTC)
Route inspection problem → Chinese postman problem – I would like to suggest renaming the article to Chinese Postman Problem. WalkingRadiance ( talk) 19:26, 8 October 2022 (UTC)
![]() | This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||
|
![]() | On 8 October 2022, it was proposed that this article be moved from Route inspection problem to Chinese postman problem. The result of the discussion was moved. |
Is the information here relevance to the "route inspection problem"? It seems a little bit off topic to me. Dysprosia 11:23, 2 Oct 2003 (UTC)
It seems that the drfinition of the rural postman problem should be change to 'find a minimum weight closed route that traverses a given set of edges' (shuroo)
The article says:
but above it, it says "if and only if". Which is it?
It is not about Hamiltonian (going through nodes) but about Eulerian (going through edges) cycles. A non-oriented connected graph G=(V,E) has an Eulerian cycle if and only if all nodes have even degree.
The article says:
1 → 2
2 → 3
3 → 1
Is this a correct way of demonstrating the validity of those equivalences? -- 213.100.56.253 00:46, 24 May 2007 (UTC)
The "Solution" section deals only with eulerian and non-eulerian graphs, stating that if the graph is eulerian, an eulerian path can be found, otherwise another method can give the shortest path possible. However, wouldn't it be more appropriate to make the distinction between semi-eulerian graphs and non-semi-eulerian graphs? Because all semi-eulerian graphs, whether they are also eulerian or not, have eulerian paths. ( Tanynep ( talk) 12:24, 10 May 2009 (UTC))
The standard usage in graph theory is that a path has no repeated vertices or edges. A trail has no repeated vertices, but it may repeat edges. A walk has no repeated vertices or edges.
A closed walk or trail has the same initial and final vertices. An open walk or trail has different initial and final vertices. A closed path is a closed trail that doesn't repeat a vertex except for the initial and final vertices.
A circuit may be several things. It may be a closed path (or the graph of a closed path), which is also usually called a cycle; or it may be a closed trail.
These are graph-theory customs. The customary terminology in electrical engineering, computer science, or social network analysis may differ in various ways.
See almost any graph theory book written by mathematicians (as opposed to engineers, et al.): Bondy and Murty; Diestel; Bollobas; others that I don't remember at the moment. Zaslav ( talk) 05:26, 28 April 2010 (UTC)
"Eulerian trail" is used for the open trail, and "Eulerian path" is also used. "Eulerian tour" and "Eulerian circuit" are used for the closed trail. You seem to be saying "path" is not correct but you insist on using it. Why? See Talk:Eulerian path for more.
An Eulerian trail/path does not repeat edges. The correct statement is that a graph does not have an Eulerian trail/path if it is necessary to repeat edges. I do not understand why you say different. Zaslav ( talk) 16:51, 28 April 2010 (UTC)
Does anyone know anything about Mei-Ko Kwan the person himself? His name is conspicuous by its complete absence anywhere on the Net other than a brief sentence about how he deduced the Chinese Postman algorithm. There aren't even any photos of him, or any information about where he was born/died or where he lived and did his work.
This is especially odd considering he published his algorithm in 1962, which can't have been easy considering that China was probably one of the worst places to be seen to be an intellectual at the time. — Preceding unsigned comment added by Holy triple m ( talk • contribs) 15:30, 21 February 2011 (UTC)
The whole T-paths section is a complete mess. Where are you getting 1/2 |T| "paths" from? What is this. —Preceding unsigned comment added by 24.15.220.182 ( talk) 01:55, 26 April 2011 (UTC)
The text says: "When T is the empty set, a smallest T-join leads to a solution of the postman problem." But Schrijver's book, Corollary 29.1d, gives us a solution of that problem by T=vertices of odd degree. Did I misunderstand something or is there an error in the text? -- Star Flyer ( talk) 20:51, 18 January 2013 (UTC)
I propose that Chinese postman problem be merged into Route inspection problem.
The article implies that the Rural Salesman (not every edge required) is considered NP-complete, however the source on Rural Salesman is behind a paywall and the citation for the assertion doesn't mention the Rural Salesman. It seems un-intuitive that the original would be P while this variant is NP. If this is the case, an explanation added (or at least a source) would be helpful 50.241.129.75 ( talk) 20:40, 8 November 2017 (UTC)
In Special:Diff/1085693210 I removed a huge pile of material describing metaheuristics for variant problems, added by User:ScientistBuilder, almost completely off-topic to the main subject of this article, and five times as long as the on-topic content of the article. This is not the place for describing those problems in such detail. Adding it here totally unbalances the article. — David Eppstein ( talk) 23:12, 1 May 2022 (UTC)
The result of the move request was: moved. ( non-admin closure) Rotideypoc41352 ( talk · contribs) 03:30, 16 October 2022 (UTC)
Route inspection problem → Chinese postman problem – I would like to suggest renaming the article to Chinese Postman Problem. WalkingRadiance ( talk) 19:26, 8 October 2022 (UTC)