The subject of graph theory and networks is an area of topology that is rapidly moving into mainstream mathematics. It has modern applications in artificial intelligence, data mining, large‐scale communication networks, and industrial scheduling. Few subjects in mathematics can be traced back to such an exact and interesting beginnings as graph theory to the famous Seven Bridges of Konigsberg Problem, solved by the Swiss mathematician Leonhard Euler in 1736.
The town of Konigsberg, Prussia (now Kaliningrad, Russia), rests on the banks of the Pregel River, and as it flows through the town, it divides the town into four distinct regions connected by seven bridges, illustrated in the accompanying drawing. The town flourished in the seventeenth and eighteenth centuries, and the story goes that the people of Konigsberg spent their evenings strolling throughout the city, crossing the seven bridges that spanned the river. The question was asked whether it was possible to start at one of the four land areas, cross each bridge exactly once, and return to the starting point. The mathematician Euler learned of the problem and in a published paper1 demonstrated that in
order for a person to cross each bridge exactly once and return to the starting point, each land mass must be connected by an even number (2, 4, 6, …) of bridges. Since this was not the case for the Konigsberg bridges such a stroll was not possible.
Before showing how Euler solved this problem, we must introduce the concept of a graph.
Some of the main ingredients of a graph are
In the graph illustrated in the definition, we have
Two important concepts in the study of graphs are Euler paths and Euler circuits.
We now state and indicate the proof of Euler's famous 1736 theorem, effectively solving the Konigsberg Bridge Problem.
Figure 5.3 shows a rough diagram of the Pregel River and four adjoining land masses along with the graphical representation drawn by Euler. Note that not all the vertices in the graph are even (in fact none are even), hence there does not exist an Euler Tour in the graph.
The existence of Euler paths or cycles depends on the number of odd nodes: 0, 2, or more than 2.
The following implications are basic to Euler tours and paths.
One characteristic of graph theory is the variety of problems that can be solved using its principles. One such fascinating problem that can be solved using the tools of graphs is the Handshaking Problem.
One of the fascinating aspects of graph theory is that its applications are almost endless. Anything that involves objects and relations between them can be modeled as a graph. The nodes can be cities as vertices and airplane flights as the edges between them. But how do we model the cost of a flight? We simply use a weighted graph that assigns the costs of the flights to the edges. There are algorithms for finding cheapest paths in a network.
In many applications in modern technology, it is useful to assign nonnegative numbers or weights to the edges of a graph.
One class of problems modeled by weighted graphs, which are becoming more and more important in network design. Network design ranges from the design of telephone and Internet landlines to electrical networks, gas lines, water mains, sewage lines, and on and on. The goal is to design networks that operate effectively at minimum cost.
Consider the weighted graph in Figure 5.6 consisting of eight cities, where the numbers on the edges represent distances between cities. A problem might be to design a high‐speed train network connecting the cities and whose total length is minimum. This is a simple task for eight cities, but when designing communication networks connecting thousands of vertices, the problem is far from trivial.
From the perspective of graph theory, the goal is to find the minimum spanning tree in the graph. A tree is a graph that contains no cycles, and a spanning tree is a subtree that includes every vertex of the graph, and a minimum spanning tree is a spanning tree (there may be many) whose sum of its weights is a minimum.
There is a well‐known algorithm for finding the minimum spanning tree in a graph called Kruskal's Algorithm. The idea behind the algorithm is very simple. One starts with only the vertices of the graph, then, one by one, start adding edges, starting with the edge with the smallest weight, then continue by adding edges with increasing weights, provided no cycle is created. If a cycle is formed, bypass that edge and continue on until all vertices are included in the tree. The result will be a minimum spanning tree in the graph.5 Carrying out Kruskal's Algorithm for the eight cities in Figure 5.6, we find its minimum spanning tree that we draw in Figure 5.7. The total length of the minimum spanning tree is 4330 miles. This will give planners an estimate of the total cost of the new rail system.
In graph theory, a planar graph is one that can be drawn in the plane in a way that no two edges cross each other. It is sometimes called the “integrated circuit” graph. For example, the complete6 graph K4 of order four in Figure 5.8a) is a planar graph. At first glance, the graph may not appear planar since two edges cross, but keep in mind graph theory is not Euclidean geometry. Graph theory is the “geometry of connections,” where shapes of edges are not important, only how the vertices are connected. Hence, the graph in Figure 5.8a can be redrawn as Figure 5.8b or Figure 5.8c that show no intersecting edges.
An important concept of planar graphs is that of the faces of graph, which simply are regions bounded by the edges of the graph. The graph in Figure 5.8 has four vertices, six edges, and four faces. The reader may have counted only three faces, but in our present analysis, we count the infinite region outside the graph as a face.
One property common to every connected planar graph is its Euler Characteristic. No matter how different the graphs may appear, they have something in common and that's their Euler Characteristic. This leads us to Euler's Characteristic Theorem. We will see in Section 5.3 how the Euler Characteristic is an important tool for distinguishing topological shapes in three dimension.
Starting with an arbitrary connected, planar graph, the idea behind the proof is to continually triangulate the graph, throwing out “boundary triangles,” until eventually arriving at a triangle graph, and to show at each step of this process the Euler Characteristic is unchanged. Hence, if the final graph has an Euler Characteristic of 2, so does the initial graph.
Although we will not prove the result for an arbitrary connected, planar graph, the general proof can be understood by working through the proof for the planar representation for a cube as drawn in Figure 5.10a. Starting with the graph in Figure 5.10a, we “triangulate” the five internal faces by drawing edges between different vertices. If we now count the number of vertices, edges, and faces in the triangulated graph in Figure 5.10b, we see that the number of vertices is unchanged; the new graph has five additional edges and five new faces, and so the Euler Characteristic v − e + f remains the same.
The next step is to eliminate the triangles that have one or two edges on the boundary, such as four triangles in Figure 5.8b. We leave it to the reader to verify that the removal of these four boundary triangles, either the type in Figure 5.10b with one boundary edge, or the type in Figure 5.10c with two boundary edges, does not change the Euler Characteristic. Continuing this process of eliminating exterior triangles, we eventually arrive at the triangle graph whose Euler Characteristic is two. Therefore, the original graph also has Euler Characteristic of two.▌
For Problems 2–7, determine if the given graph has an Euler Tour and if so find one.
If all nodes of a graph are even except two, then the graph has an Euler path. This means one starts at one of the odd nodes, traverses all the edges of the graph exactly once, and ends at the other odd node. Find the Euler paths in the graphs in Figure 5.18.
Hamiltonian Tour
Another type of path, or more accurately tour, through a graph is the Hamiltonian tour, which is a tour that starts at a given vertex, traverses each vertex (not edge) exactly once, and then returns to the starting vertex. A graph that contains a Hamiltonian tour is called a Hamiltonian graph. Unfortunately, unlike Euler tours, there is no simple test for determining if a graph has a Hamiltonian tour. For Problems, 9–12 find, if there is a Hamiltonian tour in the given graph.
Suppose the vertices of a graph are indistinguishable.
Assuming the vertices of the graph are indistinguishable, draw all possible graphs with four vertices. Hint: There are 11 of them.
In 1859, Irish mathematician William Rowan Hamilton (1805–1865) marketed a puzzle shaped as a regular dodecahedron, a solid with 12 faces where each face having the shape of a regular pentagon, as illustrated in Figure 5.23. The name of a city was assigned to each corner of the dodecahedron. The goal of the puzzle was to start at any city, find a route along the edges of the dodecahedron, visiting each city exactly once and returning to the starting city. Such a path is a Hamiltonian Tour. The planar representation of a dodecahedron is shown in the following figure. Can you find a Hamiltonian Tour through this dodecahedron?
Graphs in Figure 5.24 are planar representations of the five Platonic solids; the tetrahedron, cube, octahedron, dodecahedron, and icosahedron. Tell if each has Euler and Hamiltonian Tours. If so, find one.
A knight's tour on a chessboard in Figure 5.25 is a path on the board that visits each square exactly once, then returns to the starting square. The smallest chessboards for which a tour is possible are 5 × 6 board and 3 × 10 boards. A tour is not possible for 3 × 3 and 4 × 4 boards
Place a chess knight (or a coin) on any one of the squares of the board drawn in Figure 5.26 and find a tour that lands on each square exactly once and returns to the starting square. Such a tour would be a Hamiltonian tour if one interprets the squares of the board as the vertices of a graph.
A regular graph is one where all vertices have the same degree. A k‐regular graph is a regular graph where each vertex has degree k. Figure 5.27 below shows k‐regular graphs with six vertices for k ranging from zero to three. Note that only the 3‐regular graph is connected.
Draw the following regular graphs
The chromatic number of a graph is the smallest number of colors needed to color a graph so that no two adjacent vertices have the same color. Find the chromatic numbers of the graphs in Figure 5.28.
The chromatic number of the plane is the smallest number of colors required to color all the points in the plane so that no two points that are exactly one unit apart have the same color. The chromatic number is unknown but known to require at least five colors.8 It is also known that any unit‐distance graph, no matter how complicated, can be colored with seven colors. The Moser spindle is a unit‐distance graph with 7 vertices and 11 edges all have the same length, and can be colored with four colors. Can you four‐color the Moser spindle unit‐distance graph drawn in Figure 5.29?
There is a wealth of information related to topics introduced in this section just waiting for curious minds. Try aiming your favorite search engine toward applications of graph theory, graph theory in computer science, and largest known graphs.
52.54.103.76