. Net/sxx/Jingpin/teachers email/paper/5-guojunmo.doc The one here tends to hand in homework.
The next one is the officially published bilingual edition.
Artificial Proof of Zhang Yaodian's Four-color Conjecture; Senior Lecturer in Mathematics at Yuxian Party School, Shanxi Province.
In my spare time of 25 years, I studied the artificial proof of the four-color conjecture. Based on the positive and negative practices of Kemp's chain method and Howood's paradigm, the Hao-Zhang dyeing program and the theory of number combination and bit (intersection) combination of color chains are established, and an inevitable set containing only nine configurations is established, thus making up for the loopholes in Kemp's proof. The full text (in Chinese and English) and the English-Chinese translation of references are posted. Welcome colleagues to criticize and correct me.
Finally, I would like to thank A.lehoyd of Lancaster University, Zhang Zhongfu of Lanzhou Jiaotong University, Lin Cuiqin of Tsinghua University and Professor Wu of Shanghai Normal University for their selfless help.
Attachment: paper
Solving Herwood configuration with "H Z-CP"
Zhang Yaodian (Party School of Yuxian County Committee, Shanxi Province 045 100)
Based on the combination theory of the number and position of color chains, this paper uses H-CP and Z-CP to find a set of inevitable Hewood configurations.
Keywords: H-CP Z-CP
The known Hewood example [1] has two major contributions to solving Hewood configuration. Firstly, H-CP is provided, which enables us to find the configuration combination of aperiodic transformation of Herwood dyeing. Secondly, Example 2 provides the configuration of periodic transformation of Hurwood dyeing, which enables us to find Z-CP and solve the correct dyeing of this configuration.
For the convenience of the following discussion, the simplest model of Herwood configuration in [1] is given first.
As shown in figure 1:
The four colors are represented by A, B, C and D respectively, the area to be dyed V is represented by a small circle, and its five adjacent points are represented by A 1, B 1, B2, C 1 and D 1 respectively. The formed pentagonal region is called double B-clip A-shaped central region. Outside the central area, there are A 1-C 1 chains and A 1-D 1 chains (they are called rings because their two ends are connected with V to distinguish them from open chains), among which there are B 1-D2 chains and B2-. The remaining Hurwood configurations are similar.
In our model, after adding some different color chains, many different standard triangulation diagrams (denoted as G') are formed. When solving with the help of H-CP, it is found that the different number combinations and intersection combinations of color chains directly affect the difference of solutions.
Now, the necessary set of Hurwood configurations is explicitly established.
In the figure below, a small horizontal line is drawn to represent the ring, a thick line is drawn to represent two or more dye exchange chains, and B(D) and so on represent the dye exchange at one point.
As shown in Figure 2: Suppose there are B 1-A2 chains and D 1-C2 chains (or B2-A2 chains) in Figure1.
The solution is to exchange B and D in A 1-C 1 ring to generate a new A-D ring (if it is not born, it belongs to the next configuration), then exchange C and B outside the A-D ring and dye V with C color.
As shown in fig. 3, suppose that there are c 1-D2 chains and D 1-C2 chains in the graph1.
The solution is as follows: b and d in A 1-C 1 ring are exchanged to generate a B-C ring; Exchange D and A outside the B-C ring to generate a new A-C ring (if it fails, it belongs to the next configuration); By exchanging B and D on the A-C ring, V can be dyed into B color.
As shown in Figure 4, suppose there are C 1-D2 chains and B2-A2 chains in Figure1.
The solution is as follows: b and d in A 1-C 1 ring are exchanged to generate a B-C ring; Exchange d and external B-C rings to generate B-D rings; Swap A and C in the B-D ring to generate a new B-C ring (if it is not born, it belongs to the next configuration); By exchanging D and A in B-C rings, V can be dyed with D color.
As shown in Figure 5: Let the B 1-D2 chain in Figure 4 intersect with the A 1-D 1 ring, then B 1-A3 and C 1-A3 are generated.
The solution is as follows: b and d in A 1-C 1 ring are exchanged to generate a B-C ring; Exchange d and external B-C rings to generate B-D rings; Exchange a and c in B-D ring to generate A-D ring; Exchange C and B outside the A-D ring to generate a new B-D ring (if it is not born, it belongs to the next configuration); By exchanging A and C outside the B-D ring, V can be dyed with one color.
As shown in Figure 6: Let the C 1-D2 chain in Figure 5 intersect with A 1-C 1 ring. For simplicity, all the D color points of the C1-C 1-D2 chain outside the ring of A1are dyed with B color, as shown in Figure B (circled).
The solution is as follows: b and d in A 1-C 1 ring are exchanged to generate a B-C ring; Exchange d and external B-C rings to generate B-D rings; Exchange a and c in B-D ring to generate A-D ring; Exchange c and b outside the A-D ring to generate an A-C ring; Exchange B and D outside the A-C ring to generate a new A-D ring (if unborn, it belongs to the next configuration); By exchanging C and B on the A-D ring, V can be dyed into C color.
As shown in Figure 7: Let the chain B 1-D2 in Figure 6 intersect with the chain B 1-A3. For the sake of simplicity, all the A color points of the B 1-A3 chain inside the B 1-D2 chain are colored C, as shown in Figure C (circled).
The solution is as follows: b and d in A 1-C 1 ring are exchanged to generate a B-C ring; Exchange d and external B-C rings to generate B-D rings; Exchange a and c in B-D ring to generate A-D ring; Exchange c and b outside the A-D ring to generate an A-C ring; Exchange b and d outside the A-C ring to generate a B-C ring; Exchange D and A in B-C ring to generate a new A-C ring (if it is not born, it belongs to the next configuration); By exchanging B and D on the A-C ring, V can be dyed into B color.
As shown in fig. 8, it is assumed that the B 1-D2 chain and the C 1-D2 chain intersect in the A1-c/ring in fig. 7.
The solution is as follows: b and d in A 1-C 1 ring are exchanged to generate a B-C ring; Exchange d and external B-C rings to generate B-D rings; Exchange a and c in B-D ring to generate A-D ring; Exchange c and b outside the A-D ring to generate an A-C ring; Exchange b and d outside the A-C ring to generate a B-C ring; Exchange d and a in b-c ring to generate b-d ring; Exchange a and c outside the B-D ring to generate a new B-C ring (if it is not born, it belongs to the next configuration); By exchanging D and A in B-C rings, V can be dyed with D color.
Fig. 9: Let B2-A2 chain intersect with A 1-D 1 ring in fig. 8.
The solution is as follows: b and d in A 1-C 1 ring are exchanged to generate a B-C ring; Exchange d and external B-C rings to generate B-D rings; Exchange a and c in B-D ring to generate A-D ring; Exchange c and b outside the A-D ring to generate an A-C ring; Exchange b and d outside the A-C ring to generate a B-C ring; Exchange d and a in b-c ring to generate b-d ring; Exchange a and c outside the B-D ring to generate an A-D ring; Exchange c and b in A-D ring to generate a new B-D ring; (If not born, it belongs to the next configuration). By exchanging A and C on the B-D ring, V can be dyed with one color.
As shown in the figure 10: This is the 10 double symmetric configuration of Heywood. That is, in fig. 3, let c 1-D2 chain intersect with a 1-c 1 ring, and d 1-C2 chain intersect with a 1-d 1 ring. ; Let the dyed C-B chain and D-B chain intersect symmetrically. This Herwood configuration is the topological transformation form of Example 2 in [1].
For figure 10, if the solution method in figure 2-9 is followed, a Hurwood configuration with four transformation periods will be generated, and the solution cannot be obtained. However, these four continuously transformed Hurwood configurations have the same coloring characteristics, that is, they all contain A-B rings, so the following special Z-CP is produced:
If the first (or third) graph is known, C and D outside the A-B ring are interchanged to generate a new A-C, A-D (or B-C, B-D) ring, and then B(D), B(C)[ or A(D), A(C)] are interchanged, so the solution is as shown in Figure/kloc-.
If the second (or fourth) graph is known, the C and D outside the A-B ring are interchanged to generate a new B-C (or A-D) chain, and then the A(D)[ or A (C)] on one side of the B-C (or A-D) chain is interchanged to reduce the chromatic number of the five vertices of the Pentagon to 3. The solutions are shown in figures 10(2) and 10(4).
The completeness of the necessary set of Figure 2- 10 is proved theoretically.
There are ***C42(=6) different color chains composed of any two of the four colors A, B, C and D in the four-dyeing G', which are reflected in the configuration of Heywood, and there are rings A 1-C 1, A1-D/kloc-. Different numbers of these four chains in Hurwood configuration are combined into four groups:
B 1-A2、B 1-D2、B2-C2、B2-A2
B 1-A2、B 1-D2、B2-C2、D 1-C2
C 1-D2、B 1-D2、B2-C2、B2-A2
C 1-D2、B 1-D2、B2-C2、D 1-C2
However, any two of the six color chains are bound to ***C62(= 15) groups at different positions. There are three disjoint combinations:
A-b and c-d, a-c and b-d, a-d and a-C.
There are 12 cross combinations:
A-b and a-c, a-d, b-c, b-d;
A-c and a-d, b-c, c-d;
A-d and b-d, c-d;
B-c and b-d, c-d;
B-d and c-D.
We regard different number combinations (4 groups) and different position combinations (12 groups can intersect) of the above six color chains as two main variables, and one * * * can get 16 different Hurwood configuration combinations; Then, under the constraints of "the simplest structure" and "the same solution", the tests are carried out one by one, which are summarized as follows: Figure 2-4 shows four different quantitative combinations, of which Figure 2 shows the first two combinations; Figure 5-9 shows the increased intersection combinations, in which Figure 9 already contains 12 intersection combinations; The figure 10 embodies the special combination of quantity and intersection.
So far, we have successfully solved the correct coloring problem of Hewood configuration with "H Z-CP", thus making up for the loopholes in Kemp's proof.
References:
[1], holroyd and Miller ... Heawood should give an example of a quarter of mathematics. ( 1992).43 (2),67-7 1
Attach English version.
Solving Heawood configuration by using H Z-CP
Zhang Yudian
China Yuxian Party School, Yuxian 045 100.
Based on the combination theory of quantity and poison of coloring chain, this paper finds an inevitable set of Heawood configuration by using Heawood-clouring process (H-CP) and Zhang Yudian coloring process (Z-CP). And found a new method, named H Z-CP.
Keywords: H-CP Z-CP H Z-CP
introduce
The paper [1] has two main contributions to solving Heawood configuration. One is H-CP, which can be used to find the Heawood configuration set of Heawood- colored aperiodic transformation. In the other case [1], the Heawood configuration of Heawood coloring periodic transformation is given. With it, Z-CP is found and the correct coloring problem of this configuration is solved.
For the convenience of discussion, the simplest wood pile configuration model is given in [1] as follows.
As shown in the figure 1, A, B, C and D represent four colors, a circle indicates the section to be dyed V, and A 1, B 1, B2, C 1 and D 1 represent five points adjacent to V, forming a five. Embedded area. Outside of v are A 1-C 1 chain and A 1-D 1 chain (because the head and tail are looped by v respectively, they are called loop to distinguish them from others). There are also B 1-D2 chains and B 2-C2 chains. A 1, A2 is separated by C2-D2 chain. Another Heawood configuration is similar.
In this model, if another colored chain is added, many different normal triangle cross-sections are formed (that is, G'). When finding the solution of the mapping, it is found that different number combinations and intersection combinations have influence on the difference of the solution.
As follows, the necessary set of Heywood configuration is given in detail.
result
In the following figure, it is defined as: a small horizontal line represents a ring, and a thick line represents a chain, in which two or more colors change. B(D) etc. Indicates that the color of a point has changed.
As shown in Figure 2, if there are B 1-A2 chains and D 1-C2 chains in Figure1(or B2-A2 chains):
The solution is: in A 1-C 1 loop, B and D are interchanged to form a new A-D loop (if it cannot be formed, it belongs to another configuration). Then, C and B outside the A-D ring are exchanged, and then V can be dyed with C color.
As shown in figure 3, if there are c 1-D2 chains and D 1-C2 chains in figure1:
The solution is: in A 1-C 1 circuit, B and D are interchanged to form a new B-C circuit, and D and an external B-C circuit are interchanged to form a new A-C circuit (if it cannot be formed, it belongs to another configuration). Then in the A-C cycle, B and D are exchanged, and then V can be dyed into B color.
As shown in Figure 4, if there are C 1-D2 chains and B2-A2 chains in Figure1:
Its solution is: in A 1-C 1 loop, B and D are interchanged to form a new B-C loop, D and an outer B-C loop are interchanged to form a new B-D loop, and A and C are interchanged to form a new B-C loop in the B-D loop. Then in the B-C cycle, D and A are exchanged, and then V can be dyed into D color.
As shown in fig. 5, if the B 1-D2 chain and A 1-D 1 ring intersect in fig. 4, new B 1-A 3 rings and C 1-A 3 rings are formed.
Its solution is: in A 1-C 1 loop, B and D are interchanged to form a new B-C loop, D and an outer B-C loop are interchanged to form a new B-D loop, in which A and C are interchanged to form a new A-D loop, and the outer C and B of A-D loop are interchanged. Then, A and C outside the B-D ring are exchanged, and then V can be dyed with a color.
As shown in fig. 6, if the C 1-D2 chain and the A 1-C 1 ring intersect in fig. 5, for simplicity, D can be colored with B in the C 1-D2 chain outside the A1ring. See b in figure 6.
Its solution is: in A 1-C 1 loop, B and D are interchanged to form a new B-C loop, D and an outer B-C loop are interchanged to form a new B-D loop, in which A and C are interchanged to form a new A-D loop, and the outer C and B of A-D loop are interchanged. Then, in the A-D cycle, C and B are exchanged, and then V can be dyed into C color.
As shown in fig. 7, if the B 1-D2 chain and the B 1-A3 ring intersect in fig. 6, for the sake of simplicity, A can be colored with C in the B 1-A3 chain inside the B 1-D2 chain. See c in fig. 7.
The solution is that in A 1-C 1 loop, B and D are interchanged to form a new B-C loop, D and an external B-C loop are interchanged to form a new B-D loop, and A and C are interchanged to form a new A-D loop in the B-D loop.
As shown in fig. 8, if the B 1-D2 chain and the C 1-D2 chain intersect in the ring a1-c in fig. 7.
The solution is that in A 1-C 1 loop, B and D are interchanged to form a new B-C loop, D and an external B-C loop are interchanged to form a new B-D loop, and A and C are interchanged to form a new A-D loop in the B-D loop. In the B-C loop, D and A are exchanged to form a new B-D loop, and A and C outside the B-D loop are exchanged to form a new B-C loop (if it cannot be formed, it belongs to another configuration). Then in the B-C cycle, D and A are exchanged, and then V can be dyed into D color.
As shown in fig. 8, if the B2-A2 chain and A 1-D2 ring intersect in fig. 8.
The solution is that in A 1-C 1 loop, B and D are interchanged to form a new B-C loop, D and an external B-C loop are interchanged to form a new B-D loop, and A and C are interchanged to form a new A-D loop in the B-D loop. In the B-C loop, D and A are interchanged to form a new B-D loop, A and C outside the B-D loop are interchanged to form a new A-D loop, and in the A-D loop, C and B are interchanged to form a new B-D loop (if it cannot be formed, it belongs to another configuration). Then, in the B-D cycle, A and C are exchanged, and then V can be dyed with one color.
In figure 10, it is a Heawood configuration with decagonal symmetry. That is, in fig. 3, according to the intersection combination method in fig. 6, if the C 1-D2 chain intersects with A 1-C 1 ring, the D 1-C2 chain intersects with A 1-D 1 ring, and the d color point is at. This Heawood configuration is a topology transformation form in Example II [1].
For Figure 10, if the solution in Figure 9 is used, the Heawood configuration with four periodic transformations will be generated, and there will be no result. However, these four sequence transformation Heawood configurations have a common coloring feature, that is, they all contain A-B rings. Then, the following Z-CP is produced.
If the figure 10( 1) or 10(3) is known, firstly, C and D outside the A-B loop are interchanged to form a new A-C loop and A-D loop (or B-C loop and B-D loop). B(C) (or A(D) and ampA(C)) interchange. The chromatic number of pentagonal vertices is reduced to 3. The conclusion is shown in figure 10( 1) and figure 10(3).
If the graph 10(2) or 10(4) is known, firstly, C and D outside the A-B ring are interchanged to form a new B-C (or A-D) chain, and then A(D) (or A(C) on the B-C (or A-D) side. The chromatic number of pentagonal vertices is reduced to 3. The conclusions are shown in figure 10(2) and figure 10(4).
The complete necessary set consisting of Figure 2 to 10 is proved as follows.
In the four-color dyed G', the number of different colored chains formed by two of the four colors A, B, C and D is C42(=6). Reflected in the Haywood structure, there are intersecting A 1-C 1 loops and A 1-D 1 loops, and their starting points and ending points are in the central area. And there are four chains: B65438+ 0-D2, B 1-A2(B2-A2), B2-C2, C1-D2 (D1-C2), which start in the central area and end in A1-C. In Heawood configuration, there are four groups of four different quantity combinations of chains:
B 1-A2、B 1-A2、B2-C2、B2-A2
B 1-A2、B 1-D2、B2-C2、D 1-C2
C 1-D2、B 1-D2、B2-C2、B2-A2
C 1-D2、B 1-D2、B2-C2、D 1-C2
Among the six kinds of chains, there are C62(= 15) combinations of two different situations, among which there are three disjoint combinations:
A-B and C-D, A-C and B-D, A-D and b-c;
There are also 12 cross combinations:
A-B and Atlanta, A-D, British Columbia, B-D;
A-C and A-D, B-C, c-d;
A-D and B-D, c-d;
B-C and B-D, c-d;
B-D and c-D.
Different number combinations (4 groups) and different position combinations (intersecting 12 groups) of the above six chains are two main variables, and a total of 16 different combinations of wood configurations can be found. Then, the restriction conditions of "the simplest structure" and "the same solution" are verified one by one, and the specific conclusion is: Figures 2 to 4 show the combination of four different quantities. Among them, Figure 2 shows the first two groups. Fig. 5 to fig. 9 show that increasing cross combination in turn. Among them, Figure 9 contains 12 cross combinations. Figure 10 shows the specific number combination and cross combination.
At this point, the correct coloring of Heawood configuration has been resolved. The program to solve this problem is called H Z-CP. This conclusion makes up for the loopholes in the evidence of Kengpu.
Bibliography:
[1], holroyd and Miller ... Heawood should give an example of a quarter of mathematics. ( 1992).43 (2),67-7 1