Reshaping life starting from the Junior Class of HKUST

Chapter 96 Four-color conjecture
"Zhiwen, why are you aiming at me? I didn't say I would participate in the ACM World Programming Contest?" Wu Zhe joked about Shen Zhiwen.

Shen Zhiwen didn't answer, and just stared at Wu Zhe.Being stared at by Shen Zhiwen like this, Wu Zhe could only surrender.

"Zhiwen, is this your attitude of asking for help? This is almost catching up with threats." Wu Zhe said with a smile.

While talking and laughing, Wang Chao cursed: "Dug." Then the computer crashed and the screen went black.

"Young Master Wang, what are you doing again? Watching a small movie? You are still young, don't mess with what you have?" Huang Minghai laughed at Wang Chao.

But even though it was a joke, a few people were still very curious.After all, the computer was equipped by Shen Zhiwen, a master, with high configuration, and the protection of his dormitory was written by Shen Zhiwen and Wu Zhe himself, and Wang Chao's computer level was not low.If it's a computer virus and being hacked, it's impossible for Wang Chao to not even respond at all.

"Hey, are you just watching a short movie? I ran the program I wrote, but I didn't expect it to fail just after running it. I still can't find the reason." Wang Chao said with a flushed face.Damn, good or bad I am a genius!Writing a program can shut him down, it's no wonder Wang Chao doesn't blush.

"Zhiwen, come and help me to see, what the hell is this?" Really can't find the reason, so Wang Chao can only look for Shen Zhiwen.

Shen Zhiwen leaned over to have a look, and then checked carefully.Hit the confirm button to run it manually, but the computer is still down.

Checked it inside and out, and found nothing wrong.But as long as the program written by Wang Chao is run, it will crash, but Shen Zhiwen checked the code, the logic is logical, and the coding is no problem.The system did not report an error, but it just couldn't run.This phenomenon is encountered for the first time.

"Wang Chao, don't mess with it now, the school selection exam is about to start. You and Wu Zhe go to the exam first, and Zhiwen and I will help you find out what's going on first?" Huang Minghai looked at the time and said.

"Well, let's go to the exam first." Wang Chao also knows the importance.

Turning around, he greeted Wu Zhe and said, "Let's go, Ah Zhe!"

"Go alone! I won't go." Wu Zhe replied with a smile.

Several people looked at Wu Zhe with puzzled faces, are you not going?what is this?At that time, I spoke at Mizuki University.If Wu Zhe didn't participate, they would have no face to see people from other universities in the future.

Looking at the expressions of the other people, Wu Zhe also knew that he could stop joking.He smiled and said: "Two days ago, the college informed me that I don't need to take the selection exam. I am afraid of delaying Kaixin.com, so I can go directly to the Qiu competition. So Wang Chao, you need to go there alone, take the exam well, I am optimistic about you! "

"MMP!" Wang Chao just wanted to curse now.

Shen Zhiwen and Huang Minghai were relieved when they saw that it was not Wu Zhe who did not participate in the competition.They all started to make fun of Wang Chao.

Wang Chao could only make a middle finger gesture before going out.

After Wu Zhe waited for Wang Chao to go out, he also began to check the program written by Wang Chao. The code was fine.Wu Zhe looked at it slowly, and the logic seemed self-consistent.Wu Zhe frowned and thought about it.

"Huh? This place seems familiar!" Wu Zhe's eyes lit up, and then he looked for Wang Chao's notebook and looked at his modeling ideas, his mind was also running at high speed.

"Zhiwen, don't be too busy. I should know the problem." Wu Zhe said.

"What's the problem?" Shen Zhiwen asked.

"Hehe, Wang Chao's heart is too big. You look at these four indicators. Up-down-order-shock, and then bring in other parameters to make a judgment on the rendering result. What does this judgment look like to you?
"Four-color conjecture?" Shen Zhiwen reacted immediately. "Fuck, what did Wang Chao think. It would be strange if the machine didn't shut down."

"I guess he didn't realize it himself, thinking that the logic is self-consistent. It would be strange if it didn't go down. The amount of calculation is too large, and it may need a supercomputer to complete it." Wu Zhe said with a smile.

"And he not only made a world-wide problem of the four-color problem, he also made a Sitapan conjecture involving graph theory. I don't know whether he is a genius or a fool. Two unproven conjectures can get To use it, and the logic is self-consistent. I will force him to prove it when I come back." Wu Zhe said fiercely.

"Why can't it be used without a proof? Hasn't it been proved that 1+1=2? Don't use it as it is. Besides, hasn't the four-color problem been proved on a computer?" Huang Minghai said beside him.

"It's just that the four-color problem has been counted 100 billion times without error. It's not over if you don't give a proof in mathematical logic in one day." After speaking, Wu Zhe became interested, picked up a pen and scratch paper and started to prove.

------

In 1852, Guthrie, who graduated from the University of London, came to a scientific research unit to do map coloring work, and found that each map could be colored with only four colors.He wondered if this phenomenon could be proved mathematically?It can only be said that they were too full to eat, Guthrie and his younger brother really started to study, and finally got involved with his younger brother's teacher, the famous mathematician De Morgan, but few of them died. Research it out.

Until 1872, Kelly, the most famous mathematician in Britain at that time, formally proposed this problem to the London Mathematical Society, so the four-color conjecture became a concern of the world's mathematics community, and many first-class mathematicians in the world participated in the four-color conjecture. big battle. In 1880, mathematicians used reductio absurdum to prove that if there is a regular five-color map, there will be a "minimal regular five-color map" with the least number of countries, if there is a If the country has less than six neighboring countries, there will be a regular map with fewer countries that is still five-color. In this way, there will be no number of countries with a very small five-color map, and there will be no regular five-color map .In this way, Kemp thought that he had proved the "four-color problem", but later it was found that he was wrong.

1922 年费兰克林证明了每个有至多25个国家的地图都可以用四种颜色着色。1926年雷诺德将这一结果推广到27个国家，然后在1938年费兰克林又创造了31个国家的纪录。1940 年温恩证明了35个国家的情形以后，这方面的研究有所停滞，直到1970年，奥尔和史坦普尔对所有至多包含40个国家的地图证明了四色定理。在哈肯和阿佩尔最终证明四色定理而使所有这类结果都黯然失色以前，这个数字曾经达到了96。

In 1950, the German mathematician Hesch estimated that proving the four-color conjecture would involve about 1 different configurations.Although his estimate turned out to be an exaggeration, it correctly indicated that the four-color problem might only be solved with the help of powerful computing devices capable of processing huge amounts of data.

In 1972, Haken and Appel joined forces. After four years of intense work, they finally verified the four-color color in June 1976 after spending 6 computer hours with three computers and processing more than 1200 configurations. Problem established.But it must be unsatisfactory for mathematicians.

------

Wu Zhe starts with the coloring judgment problem: Suppose a graph g is only allowed to use these m colors to color the nodes of g, can any two adjacent nodes in the graph have different colors Woolen cloth?
Then from the m-coloring optimization problem, find the smallest integer m that can color the graph g.This integer is called the chromatic number of graph g.This is the least coloring problem for a graph to find the value of m.

for(i = 1m= n; i++)
a＾r/(ab)(ac)+b＾r/(bc)(ba)+c＾r/(ca)(cb)
当r=0，1时式子的值为0 当r=2时值为1 当r=3时值为a+b+c
……

V+FE=X§, V is the number of vertices of polyhedron P, F is the number of faces of polyhedron P, E is the number of edges of polyhedron P, and X§ is the Euler characteristic number of polyhedron P.

If P can be homeomorphic to a surface (which can be commonly understood as being able to inflate and be stretched on a spherical surface), then X§=2, if P is homeomorphic to a surface connected with h ring handles, then X§= 2-2h.

...e-ix=cosx-isinx, and then use the method of adding and subtracting the two formulas to get: sinx=(eix-e-ix)/(2i), cosx=(eix+e-ix)/2.
Take x in eix=cosx+isinx as ∏ to get: e^i∏+1=0.
~~~~~~
(End of this chapter)