Chinese postman problem
The Chinese postman problem is a mathematical problem of graph theory. It is also known as route inspection problem. Suppose there is a mailman who needs to deliver mail to a certain neighbourhood. The mailman is unwilling to walk far, so he wants to find the shortest route through the neighbourhood, that meets the following criteria:
- It is a closed circuit (it ends at the same point it starts).
- He needs to go through every street at least once.
If the graph travelled has an Eulerian path, this circuit is the ideal solution.
Alan Goldman of the U.S. National Bureau of Standards first coined the name 'Chinese Postman Problem' for this problem, as it was originally studied by the Chinese mathematician Mei-Ku Kuan or Meigu Guan in 1962.[1]
Chinese Postman Problem Media
- Error creating thumbnail: About to transcode 1 SVG file(s)
Converting Chinese_postman_problem.svg to /var/www/html/w/images/temp/transform_0fd711713520.png ... org.apache.batik.transcoder.TranscoderException: null Enclosed Exception: file:/var/www/html/w/images/temp/svg_68ca0cc5c86fac9e00af1cc9/Chinese_postman_problem.svg:-1 The attribute "in2" of the element <feBlend> is required at org.apache.batik.transcoder.SVGAbstractTranscoder.transcode(SVGAbstractTranscoder.java:228) at org.apache.batik.transcoder.image.ImageTranscoder.transcode(ImageTranscoder.java:92) at org.apache.batik.transcoder.XMLAbstractTranscoder.transcode(XMLAbstractTranscoder.java:142) at org.apache.batik.transcoder.SVGAbstractTranscoder.transcode(SVGAbstractTranscoder.java:158) at org.apache.batik.apps.rasterizer.SVGConverter.transcode(SVGConverter.java:1008) at org.apache.batik.apps.rasterizer.SVGConverter.execute(SVGConverter.java:719) at org.apache.batik.apps.rasterizer.Main.execute(Main.java:956) at org.apache.batik.apps.rasterizer.Main.main(Main.java:1009) Caused by: org.apache.batik.bridge.BridgeException: file:/var/www/html/w/images/temp/svg_68ca0cc5c86fac9e00af1cc9/Chinese_postman_problem.svg:-1 The attribute "in2" of the element <feBlend> is required at org.apache.batik.bridge.AbstractSVGFilterPrimitiveElementBridge.getIn2(AbstractSVGFilterPrimitiveElementBridge.java:103) at org.apache.batik.bridge.SVGFeBlendElementBridge.createFilter(SVGFeBlendElementBridge.java:98) at org.apache.batik.bridge.SVGFilterElementBridge.buildLocalFilterPrimitives(SVGFilterElementBridge.java:237) at org.apache.batik.bridge.SVGFilterElementBridge.buildFilterPrimitives(SVGFilterElementBridge.java:174) at org.apache.batik.bridge.SVGFilterElementBridge.createFilter(SVGFilterElementBridge.java:108) at org.apache.batik.bridge.CSSUtilities.convertFilter(CSSUtilities.java:683) at org.apache.batik.bridge.AbstractGraphicsNodeBridge.buildGraphicsNode(AbstractGraphicsNodeBridge.java:142) at org.apache.batik.bridge.GVTBuilder.build(GVTBuilder.java:145) at org.apache.batik.bridge.SVGMarkerElementBridge.createMarker(SVGMarkerElementBridge.java:83) at org.apache.batik.bridge.PaintServer.convertMarker(PaintServer.java:137) at org.apache.batik.bridge.PaintServer.convertMarkers(PaintServer.java:94) at org.apache.batik.bridge.SVGDecoratedShapeElementBridge.createMarkerPainter(SVGDecoratedShapeElementBridge.java:67) at org.apache.batik.bridge.SVGDecoratedShapeElementBridge.createShapePainter(SVGDecoratedShapeElementBridge.java:86) at org.apache.batik.bridge.SVGShapeElementBridge.buildGraphicsNode(SVGShapeElementBridge.java:91) at org.apache.batik.bridge.GVTBuilder.buildGraphicsNode(GVTBuilder.java:224) at org.apache.batik.bridge.GVTBuilder.buildComposite(GVTBuilder.java:171) at org.apache.batik.bridge.GVTBuilder.buildGraphicsNode(GVTBuilder.java:219) at org.apache.batik.bridge.GVTBuilder.buildComposite(GVTBuilder.java:171) at org.apache.batik.bridge.GVTBuilder.build(GVTBuilder.java:82) at org.apache.batik.transcoder.SVGAbstractTranscoder.transcode(SVGAbstractTranscoder.java:210) ... 7 more ... error (SVGConverter.error.while.rasterizing.file)
A worked example of an undirected Chinese postman problem:*- Each street must be traversed at least once, starting and ending at the post office at A.
- Four vertices with odd degree (orange) are found on its equivalent graph.
- The pairing with the lowest total length is found.
- After corresponding edges are added (red), the length of the Eulerian circuit is found.