One stroke problem (Chinese postman problem)

One stroke and the problem of Chinese postmen

One 、 Quote

One stroke problem ：

• Nodes can be repeated
• You can't walk repeatedly
• It is required to walk all sides once

Olatu (Euler graph)：

• Start at any node , Can be a stroke

• Every node has an even price （ Valence refers to the number of edges that can stretch out from this node ）

  

Semi Euler graph (semi-Eulerian graph):

• Only two nodes are odd valued , Others are even priced

  

• A semi Eulerian graph must start with an odd valence node , To the end of another odd price , Just one stroke .

tip: One stroke problem , Because there must be entry and exit at the passing point , So the path point must be even , Because the starting point and the ending point can only enter or exit , So the starting point and ending point can be odd .

The example analysis

example 1： Determine it as eulatu 、 Semi Euler or not Euler .

a. Semi Euler graph

b.B-A-F-E-B-C-D-E-C

example 2 A connected graph has 5 Nodes , The prices of nodes are 4,6,3,p,2

a. Explain why the graph must not be an Euler graph

b. Explain why a graph must be a semi Eulerian graph

c. Find the number of edges （ use p Express ）

d. Draw a diagram with two nodes , It is required that it is neither Eulerian nor semi Eulerian

[ Failed to transfer the external chain picture , The origin station may have anti-theft chain mechanism , It is suggested to save the pictures and upload them directly (img-K7Pg0HWG-1658797650807)(imgs/image-20220725205109029.png)]

a. See nodes with odd prices , It must not be eulato

b. From the handshake lemma , The number of nodes with odd price must be even , therefore p It must be odd , The graph of two odd valued nodes is a semi Eulerian graph .

c. From the handshake lemma , The total price is twice the number of sides , The number of backward edges is $ \frac {p+15} {2} $

d. If two points are boundless and disconnected, they are not Euler or semi Euler , No matter how even the sides are full Euler or half Euler

notes ： An Euler graph must be a connected graph （d Cited example ）

If you can't draw a stroke , It raises a question （ The Chinese postman problem ）

Post office departure , Walk every way , Go back to the post office

Euler's problem is the sum of all paths . The semi Eulerian graph is complex

According to the definition of semi Eulerian graph , The starting point can only be T perhaps Q, Otherwise, you can't draw a stroke , That means there must be some roads to go again .

terms of settlement ： Complete Euler chart , The problem of Chinese postmen has become the way to make up the least , The problem of making the original graph into a full Euler graph .

The handshake lemma tells us , Add one edge for each , The price of two nodes will definitely rise by one . You can choose to supplement S To T and S To Q To make the graph full Euler .

These two edges are the ones that the postman should walk again , In this way, Chinese postmen can start from the post office and finally return to the post office , Minimum cost .

Why choose these two , Not the others , There is more than one way to make up the edges of all Euler , But choose the one that costs the least , That is to say, we should give T and Q Increase the price , And ensure the shortest global path , How to determine the ？ Exhausting

A more complex example ：

The post office is required to set the point A, It can be found that the number of odd valued nodes is 4（A、E、F、G）, We need to mend the edges to finalize the path of repetition with the least cost , The combination has AE/FG、AF/EG、AG/EF

The costs are calculated as

AE+FG = 26 + 22 =48
AF+EG = 35 + 7 = 42
AG+EF = 19 + 20 = 39

So we decided to mend the edges AG and EF

Consider more complex scenarios ： There are no starting and ending points , In this way, the graph can be treated as a semi Eulerian graph , Just mend one side .

This choice is based on AF Two points as the beginning and end , take EG The edge of two points is used as the complementary edge to repeat , The total cost can be minimized .