Algorithm

AbstractThis work is based on one of the most famous problem in mathematics: four color theorem. In the introduction, history and examples of the applications of the four color theorem have been examined. Beside the big history of it, four color theorem has a huge application area e.g. in coloring questions, mobile phones, computer science, scheduling activities, security camera placement, wireless communication networks etc. In this work, an application of four color theorem in a specific area has been examined: location area planning. Therefore this essay tries to answer this following question: ‘What are the applications of four color theorem in location area planning?’Four color theorem is first proposed on October 23, 1852 by Francis Guthrie. Loads of proof attempts made by mathematicians but none of them proved the theorem until the Appel and Haken. Appel and Haken found a computer assisted proof and this proof is still valid. But mathematicians still search a proof without help of the computer. When mathematicians were trying to prove the theorem, graph theory was one of the important methods which they used. In this paper, a proof attempt to the four color theorem made by Kempe using graph theory is examined.To explore the applications of four color theorem, an algorithm for location area planning constructed by Lei Chen and Hai-Lin Liu has been examined in this paper. This algorithm provides the lower location area boundary crossings, therefore it lowers the costs and also improves the quality of service at the same time. Four color theorem has lots of applications in area planning and placement projects. By using the four color theorem, the efficiency can easily be increased and the costs can be reduced. Word Count: 285?Contents1. Introduction 42. Four color theorem 62.1. Graph theory 62.2. Definitions 62.3. Proof attempt to the four color theorem 63. An evolutionary algorithm based on four color theorem for location area planning 124. Conclusion 165. References 17?1. IntroductionThe four color theorem states that any map can be colored using four colors in such a way that regions sharing a common boundary (other than a single point) do not share the same color.  Another name of the problem is Guthrie’s problem after Francis Guthrie, who first realized the theorem in 1852. Francis Guthrie was trying to color the map of countries of England and then he noticed that four colors sufficed. He asked his brother Frederick whether it was true that needed at least four colors to color a map of the counties of England. All of these methods was used by other mathematicians to make progress on the four-color problem. There are six and five color theorems in mathematics and they have official proves. But to reduce the number of colors from five to four is very difficult. This problem was finally proved by Appel and Haken (1977), they constructed a computer-assisted proof that four colors were sufficient. However some mathematicians do not accept it because it includes comprehensive analysis by computer that cannot done by hand. But the proof is still valid because no errors found yet.Today, mathematicians are still looking for a new, computer-free solution for four color theorem, and graph theory is one of the main methods used in these studies. I prepared for Math Olympiads in last 5 years, and one of the topics I exposed while studying was graph theory. I have an interest to this problem therefore I decided to write my extended essay about four color theorem. There is an approach to the solution of the four color theorem with graph theory in this essay.Four color theorem has applications in mathematics and also in the graph theory and graph coloring. Beyond the mathematical issues in connection with this theorem, coloring questions have wider practical applications especially for mobile phones. They make it possible to effectively reduce the number of used broadcasting frequencies, equivalent to the colors. One of the most important real life application of four color theorem is computer science. They are surfing four color theorem at algorithms for proving further theorems me internal coding. One of the other application is scheduling activities without interfering with other events while staying on a time frame. Other important application is security camera placement. It allows minimum amount of cameras to cover maximum amount of space and also it uses in mobile phone masts to prevent frequencies from overlapping while using the minimum number of frequencies. In the following part, an application of four color theorem on planning wireless communication networks is investigated.Applying the Four Color Theorem in a Wireless Cell Tower Placement PlanCell phone companies have to assign separate channels to two transmitters to make sure that there isn’t interference when their ranges overlap. But at the same time, they’d like to limit the number of transmitters while avoiding situations when some zones are not covered by any transmitter. Therefore, to save money, they should assign locations for cell phone towers or transmitters efficiently to minimize the number of towers, yet cover an area thoroughly without the towers interfering with each other. So when we consider a cell tower placement map; if each cell tower broadcast channel is like a color, and channel–colors are limited to four, the task mentioned above is equitable to the four-color problem.Apart from these applications, in specific, this question has been tried to be answered in this paper:Research Question: What are the applications of four color theorem in location area planning??2. Four color theorem2.1. Graph theoryGraph theory is the study of the graphs. A graph consists of some points and some lines between them so graph theory concerns the relationship among lines and points. But no attention is paid to the position of points and the length of the lines. 2.2. DefinitionsGraph: A graph is collection of points and lines connecting some subset of them. The points of graph are known as graph vertices or simply points. Similarly the lines connecting the vertices of a graph are known as graph edges or lines. Plane: A plane is a two-dimensional doubly ruled surface spanned by two linearly independent vectors. Planar Graph: In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. e: number of pointsn: number of verticesv: number of edgesf: number of boundaries2.3. Proof attempt to the four color theoremIn this proof the regions in map will be considered as points.Theorem 1: Let’s take a planar graph with n vertices and v edges that has k_1,k_2,…,k_v grade. So, k_1+k_2+?+k_v= 2e.Proof 1: In sum of k_1+k_2+?+k_v each edge is counted twice, because an edge tie 2 corners together and they are counted in both of them. ?Theorem 2: Let’s take a planar graph with f boundaries such as n_1,n_2,…,n_f respectively. So, n_1+n_2+?+n_f= 2e.Proof 2: A boundary is the line between 2 regions, so in this case between points. If boundaries are calculated, each point calculated twice therefore sum of boundaries equals to 2e. So,  n_1+n_2+?+n_f= 2e.?Theorem 3(Morgan): Given 5 points in the plane. It is not possible to connect each point to each other points with the non-intersecting edges.Proof 3(Morgan): To reach the proof contradiction will be tried. Therefore let’s first accept the opposite of the suggestion. If this is possible, every point will have four degrees. According to the theorem 1, there must be 10 edges. But if the Euler Formula is applied:v-e+f=2=> f=e-v+2=10-5+2=7According to theorem 2: n_1+n_2+?+n_7=2e=20But since no n_i is less than 3:n_1+n_2+?+n_7?3.7=21Contradiction! So the suggestion is correct. ?So there cannot be a map with five adjacent regions.Theorem 4(Cayley): It is enough to solve the problem for maps where more than 3 countries do not intersect at the same point.Proof 4(Cayley):  Let’s take a map which includes at least four countries intersected at one point. Let’s say N to one of these points and d to the degree of this point. The degree of point is bigger than 4. The goal is to minimize the degree of this point, while doing this a new map will be obtained and it will be shown that the new map can also be painted with four colors. A region is carried as you can see in Figure 1. Thus, the new degree of N is d-1 and a new point which has the degree of 3 is created. This process is done exactly 3 times for each point which has a degree of three. Thus, degrees of all the points in the new map are reduced to 3. If the new map can be colored with four colors, the old map can be colored with four colors too. So it is enough to prove the problem for maps that do not intersect with more than three countries. ?Theorem 5(Kempe): Each map has a region which has maximum five neighbors, so in a map all the regions cannot have six or more neighbors.Proof 5(Kempe): It can be said that every region has three edges because each region intersects with exactly three regions. In this proof, the Euler Formula will be used and it will be proved by contradiction. Let’s say that each region has at least six neighbors, so the degree of each corner is at least six. Let’s take the number of corners in the map v, the number of regions f and the number of edges is e. Let’s take a random k edge. Like every edge, k contains two points and two regions, therefore:6v?2e and 3f?2e so v?1/3e and f?2/3eIf we use Euler Formula:1/3e-e+ 2/3e= 2 Contradiction!So, in any map there are at least one country with a neighbor number of 2, 3, 4 or 5. This set is called the ‘Kempe Inevitable Set’. Suppose there is a minimal map with 2 neighboring regions. If this region is connected with one of its neighbors, a map with B-1 region remains. So this new map can be colored with four colors. Now let’s go back to the old map. If the map with B-1 region can be colored with four colors, the actual map can also be colored with four colors. Because the extracted region has only two neighbors and it can be colored with the color of the one of the regions which they are not neighbors. This shows that there is no regions with two neighbors in a minimal map. In the same way, assume that there is a region with three neighbors. Then connect this region with one of its neighbors. The new map should be colored with four colors. Now let’s add it back to the map, this map can also be painted regularly because there is a color left which is different from the color of the three neighbors. So there can be no regions with three neighbors in a minimal map.