Vertex coloring is the simplest form of labelling a graph. “When used without any qualification, a coloring of a graph is almost always a ‘proper vertex coloring,’ namely a labelling of the graph’s vertices with colors such that no two vertices sharing the same edge have the same color.”
Also, graph coloring with the most (k) colors is called ‘proper’ k-coloring. Coloring with the smallest number of colors that is needed is called chromatic number or sometimes represented as y(G). ” A graph that can be assigned a ‘proper’ k-coloring is k-colorable, and it is k-chromatic if its chromatic number is exactly k.” Vertices are also classified in same color or color classes, independent sets are formed from such classes.
“Nelson asked: What is the smallest number of colors that you’d need to color any such graph, even one formed by linking an infinite number of vertices?”
The Hadwiger-Nelson problem is a problem that deals with the four color theorem and is it really true for infinite amount of vertices. Aubrey De Grey who is behind this says that it is not possible for four but it is for five colors. When he tried around 20,000 vertices it did not work with four. When he tried even just around 1,000 vertices it didn’t work with four either.
In this article it explains to us the real ways that the Four Color Theorem came to be. In 1976, Kenneth Appel and Wolfgang Haken finally succeeded in approving the color theorem but were unable to prove to others how the Four Color Theorem works without suggesting to draw an infinite number of maps to prove it. The truth of the matter was that proving the Four Color Theorem would only be possible with the help of computers. They used the reductio ad absurdum (reduction to absurdity) method. This states that “If we want to prove that something is true, we instead assume that it is false and show that the rest of math goes bad. That is, by assuming falsity, we encounter contradictions to already known truths.” So, Appel and Haken used this idea along with a computer program to work on any map, assuming that there might’ve been a map out there that needed more than four colors. After the computer proved that no map needed more than four colors to complete the four color theorem became the first major mathematical theorem to be proved using a computer. Who knows if this could’ve ever been truly proven without the help of technology?
In July 1879, Alfred Bray Kempe found the proof for the four color conjecture, he submitted the theorem to the American Journal of Mathematics. Soon after, it was published at the end of that year.
In Kempe’s method, he used an argument known as Kempe Chains. If every region on a map is colored but one, then that point left over becomes X. In the end, if X is surrounded by all four colors, then there is a color left for X to become.
A year later, Percy John Heawood was able to prove Kempe wrong by publishing a paper on map coloring theorems. This proved that every map would be five-colored.
Thinking of all the history involved in Coloring theorems is crazy, years ago they started looking into this and everyone rejected peoples solutions, and then came a computer.
While it’s obvious that math is in all video games, between pixel designs and character stats, it’s also used when finding the best way to grab all of those pesky yet useful hidden items around a game map. While reading this link: https://arxiv.org/pdf/1608.06175.pdf, the Traveling Salesman Problem algorithm was found to be the best way to help players attain items that are scattered around games such as Pokemon, Legend of Zelda, and the game that was used in the experiment done in the article, Far Cry 3. Through using the algorithm, the best routes can be found, either based on time or distance, while also taking into account cut-scenes, obstacles such as drop-offs and climbing, and more video-game attributes that may get int the way of finding the fastest paths.
I found this to be really interesting, even if I’m not one for going on item hauls when I play video games. There are many people called “speed players” who are dedicated to cutting every corner to find the fastest ways to play their favorite games. Knowing just how rapid-fire the play, going into the minutes-range rather than finishing games in hours, they most likely use this algorithm to perfect their strategy. For anyone who likes to play on their XBox or Nintendo DS, do your math!
Two examples of interesting TSP Applications I came across:
The people in charge of creating routes for school buses and bus routes in general use the Traveling Salesman problem to drop off their passengers in the most optimal way possible while bringing the bus back to the original location.
Some Airlines like Southwest use TSP to schedule flight paths so that their crews fly to several different locations and come back to their home airport at the end of their shifts. Other airlines have their planes just fly back and forth between airports which results in a much simpler solution to bring the crew back to their home airport, but also is a less optimized use of resources.
According to this article, bees can solve the traveling salesman problem. THAT’S RIGHT! NOW THE BEES ARE GOING TO RULE THE WORLD! HIDE YO KIDS, HIDE YO WIFE CAUSE THE BEES ARE COMING TO STING YOU!!!
On a more serious note: this is actually interesting. Studies show that the flight of a bee becomes more efficient over time, and that they are continually optimizing their routes over time, becoming better navigators with each flight, changing route sequences to improve speed, and becoming adapt to their favorite flights.
Think about how long it took for us to figure out how long it would take for the current fastest supercomputer to brute force-figure out the shortest possible route. Now that was for 100 different locations. Now think about how many flowers there are, and how often bees travel to them. No wonder researchers also say that in the future when your GPS tells you to go left, you may have a bee to thank for that information.
While doing a little research on the Traveling Salesman Problem, I found a short article in a journal about evolutionary computation. In this specific issue, the author discussed how ants are capable of finding the shortest path from a food source to their nest.
The article explains how, at one point, an ant will have to choose between going right or left. They are ants, so obviously they choose randomly. However, this means that about half of the ants will choose correctly. If, for example, one path is on a downward slope and the other on an upward slope, it is probable that more ants will choose to go down.
Keep in mind, as each ant walks towards its’ food source, they are releasing pheromones on the ground. This leaves a trail for the other ants to follow, which is much like the line segments connecting the vertices in a traditional Traveling Salesman Problem. As each ant travels towards the food source, one of them will find the shortest path, given the number of ants per path.
With programs like Concorde TSP Solver we have ways to make the Traveling Salesman Problem irrelevant to our everyday lives. Maps like Google maps can already handle multiple locations and trying to give you the best route. Not to mention you can use any number of alternative map services.
In the larger context however, TSP still lives on as a big problem for mathematicians, to the extent to have considered what it would mean to truly solve the problem in the 2012 movje Traveling Salesman.
Meanwhile, although the problem has been made much easier, truckers delivery drivers still have to deal with the problem from day to day. And given how much it can drive a person crazy we should be thankful we have modern technology to help guide us through the easier version.
That said, if you want to truly kill the TSP then answer P vs. NP and collect your million dollars, here.
I began my google search with the simple “traveling salesman problem”, and after reading a few articles, I found this one to be rather interesting.
In this article, the author Joshi describes solving the TSP by using the top-down approach. This is the same approach we used in class, using the largest parts of the graph to find a solution.
Then, the author mentions trying the same problem, but instead with a bottom-up approach. Joshi calls this the “bottom-up dynamic programming approach”, which begins with the smallest possible subproblems and their solutions, then progresses upward to solve the more complicated subproblem. In the end, the bottom-up approach brought Joshi to an answer sooner than the top-down method.