Graph Theory Basics
We shall be talking about the Euler Characteristic, which is an important part of graph theory. Now, if you have not heard of this field before, graph theory is simply the studyof networks and their properties. These networks are represented by points and lines (known as nodes and edges) that are connected, as can be seen in this example.
Below is a picture of the Konigsberg Bridge Problem and its graphical depiction. It is arguably the most famous problem in graph theory and led to the field’s creation by Leonhard Euler. I might review this problem in detail in a future post.
All you really should know though is that being aware of these networks and how they work is rather important to computer scientists. A good example of this can be seen through the Traveling Salesman Problem, a problem in which one tries to find the shortest possible route through a group of cities, given the distances between all the cities. Each citycan only be visited exactly once, and the route must return to the city where it started.
NP-Completeness
Ideally, we would like to solve such problems quickly or efficiently through a standard step-by-step method called an algorithm. However, it turns out that creating efficient orfast algorithms for some problems is very hard (and likely impossible). The Travelling Salesman Problem (TSP) is one such hard problem. In fact, TSP belongs to a set of specially hard problems called NP-complete.
Before I explain the NP-Complete set, let me first tell you about a larger set (superset) of problems called NP (Nondeterministic Polynomial). A problem is in the set NP if I give you a solution for the problem (for example, the shortest tour answer for TSP), and you can quickly (efficiently) check if it is a right or wrong answer. For some problems inset NP, you can actually find or solve the best answers quickly (efficiently, a.k.a. polynomial time) in addition to being able to verify the answer. This subset of problems of NP is called P (Polynomial) - a set of problems for which we can write fast algorithms.
However, there is a subset of problems in NP called NP-Complete that is so hard that if you solve any one of those NP-Complete problems efficiently, every problem in the set NP can be solved efficiently. As a result, that entire set NP will collapse into P - P becomes equal to NP. No serious computer scientist expects that to happen.
If you think about it, this makes sense - it takes humans an incredibly long time to create art, but comparatively shorter time to enjoy it. An example of this problem is Beethoven’s music - solving this problem (i.e. composing that music) took an entire lifetime. However, verifying this problem (listening and detecting that you are listening to a very special piece) takes us less than a few minutes. If P were equal to NP, anyone who listened to and appreciated an outstanding piece of music or writing would also be able to as easily create an equally amazing piece of text or music.
P ≠ NP has not been successfully proved thus far, but most mathematicians and computer scientists believe it to be true. It is a major unsolved problem and is one of the seven Clay Millennium Problems - so a million dollars await the person who solves it; this is probably the hardest way to earn a million dollars.
Computer scientists have been cataloging NP-complete problems. Therefore, before beginning to write a program for a hard problem, it is a good idea to check whether that problemis NP-complete. In such cases, a better approach is to use an efficient heuristic algorithm to compute an approximate (good enough) answer to that problem, instead of aiming to find the best answer.
The Euler Characteristic
Now, coming back to my original topic, the Euler Characteristic is a powerful tool in graph theory and topology. Leonhard Euler observed that for certain sphere-like polyhedra (polyhedra are solid figures with flat faces - tetrahedrons, icosahedrons, etc.), the number of vertices v, number of edges e, and number of faces f satisfied the formula:
Euler’s observation, also called Euler’s polyhedron formula, can be adjusted to allow for generalization to any polyhedra. Furthermore, Euler’s original observation is equivalent to a claim about planar graphs: that for a planar graph $v - e + f = 2$ . This formula can be applied to various problems, such as the classification of the Platonic solids or providing another definition of a genus, which is the number of donut holes in a solid (a sphere has genus zero but a torus (shaped like a donut) has genus one).
In the next post, we shall think about Euler and a proof of the Euler characteristic.