A graph theory problem corresponding to the one-stroke problem is Hamilton problem.
Directory [hidden]
1 the proposition of the problem
A theorem
2. Theorem of 1
2.2 Theorem 2
Three examples
3. 1 seven-bridge problem
3.2 An example of a sum.
4 One stroke problem and Hamilton problem
5 See also
6 reference source
[Editor] Ask questions
One-stroke problem is a generalization of abstract Konigsberg problem, and it is a kind of graph traversal problem. In the Koenigsberg problem, if the area connected by bridges is regarded as a point and each bridge is regarded as an edge, then the question becomes: For a connected graph G(S, e) with four vertices and seven edges, can you find a path that just contains all the edges and has no repetition? Euler extended the problem to: For a given connected graph, how to judge whether there is a path that contains all the edges and has no repetition? This is a stroke problem. In terms of graph theory, it is to judge whether a graph can traverse all edges without repetition. This kind of diagram is now called Euler diagram. The path traversed at this time is called Euler path (circle or chain), and if the path is closed (circle), it is called Euler path [1].
The summary of a problem is the problem of multiple strokes, which is to discuss how many strokes to use to draw a picture that can't be drawn with one stroke.
[Editor] A Theorem
There are two criteria for judging a stroke problem, both of which were put forward and proved by Euler [1].
[Edit] Theorem 1
A finite graph G is a chain or a cycle if and only if G is a connected graph and the number of odd vertices is equal to 0 or 2. A finite connected graph G is cyclic if and only if it has no odd vertices [2].
Proof [2][3]:
Necessity: If a graph can be drawn in one stroke, then for each vertex, the number of edges "entering" this point in the path is equal to the number of edges "leaving" this point: at this time, the degree of this point is even. Or the difference between the two is one: at this time, this point must be one of the starting point or the end point. Note that there must be an end point if there is a starting point, so the number of odd vertices is either 0 or 2.
Adequacy:
If there are no odd vertices in the graph, then randomly select a point and connect a circle C 1. If this circle is the original picture, it's over. If not, then because the original graph is connected, C 1 and other parts of the original graph must have a common vertex s 1. From this point on, repeat the above steps for the rest of the original drawing. Because the original graph is a finite graph, after several steps, the whole graph is divided into some circles. Because two connected circles are circles, the original picture is also a circle.
If there are two odd vertices u and v in the graph, add an extra edge to connect them and get a finite connected graph without odd vertices. From the above, we know that this graph is a circle, so it becomes a chain after removing the newly added edges, with the starting point and ending point being U and V respectively.
[Edit] Theorem 2
If a finite connected graph G has 2k odd vertices, then it can be drawn with k pens, at least it must be drawn with k pens [2].
Prove [2][3]: Divide these 2k odd vertices into K pairs and connect them respectively to get a finite connected graph without odd vertices. From the above, it can be seen that this picture is a circle, so it will become k chains at most after removing the newly added edges, so it can be drawn with k pens. But if the whole graph can be divided into q chains, then according to the theorem 1, each chain has only two odd vertices, so. So it must be written in k strokes.
[Edit] Example
Figure 1: I can't draw strokes.
Figure 2: Although there are more than one "string" according to China people's writing habits, they can be written in one stroke. [Editor] Seven Bridges Problem
The first picture on the right is an abstract model of the seven-bridge problem, which consists of four vertices and seven edges. Note that all four vertices are odd vertices, and according to the theorem 1, one stroke cannot be drawn.
[Editor] A stroke by stroke example.
Fig. 2 is a model obtained by abstracting Chinese character "string". Since only the top and bottom vertices are odd vertices, they can be drawn with one stroke according to the theorem 1.
[Editor] One stroke problem and Hamilton problem
A problem is whether all edges of a graph can be traversed without repetition, and there is no requirement for vertices to be traversed or repeated. Hamilton problem discusses the traversal of vertices: can we traverse all vertices of a graph without repetition? [4] Hamilton's problem was first put forward by Hamilton in 1856, and it has not been completely solved yet [2].
[Edit] See
The problem of the seventh bridge in konigsberg
Hamilton problem
Tree (graph theory)
chinese postman problem
[Edit] Reference source
1.01.1.2 Janet Heine barnett, Early Works on Graph Theory: eulerian path and K? Osberg bridge problem
2.02. 1 Xiong Bin, Zheng, Graph Theory, Chapter 4, 38-46, East China Normal University Press.
Detailed proof of 3.0 3. 1
Otto and hamiltonian graph.