5.1
Introduction to Graph Theory

5.1.1 Introduction

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

Sketch of Konigsberg, Prussia (now Kaliningrad, Russia).

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.

Typical graph with vertices labeled a, b, c, d, and e.

Figure 5.1 Typical graph.

5.1.2 Glossary of Important Concepts in Graph Theory

Some of the main ingredients of a graph are

  • The order of a graph G is the number of vertices in the graph, denote by |G|.
  • The degree of a vertex is the number of edges connecting the vertex.
  • A path is a sequence of vertices connected by edges.
  • A cycle is a path starting and ending at the same vertex.
  • A graph is connected if it is possible to traverse from any vertex to any another vertex by a path.
  • A vertex is odd (even) if it has an odd (even) number of edges adjacent to it.

In the graph illustrated in the definition, we have

  • the order is |G| = 5.
  • the degree of vertices a, b, c, d, e is 3, 4, 4, 3, 2.
  • typical paths are acdb and aba.
  • typical cycles are adbeca and cdac.
  • the graph is connected.
  • the vertices b, c, e are even, a, d are odd.

5.1.3 Euler Paths and Circuits

Two important concepts in the study of graphs are Euler paths and Euler circuits.

  • An Euler path is a path that passes through each edge of the graph exactly once and ends at a different vertex.
  • An Euler cycle (or tour) is a cycle that passes through each edge of the graph exactly once and starts and ends at the same vertex.

5.1.4 Return to Konigsberg

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.

Diagram displaying bridges across roads (left) and equivalent graph displaying solid circle markers connected by line and curves (right).

Figure 5.3 Graphical representation.

The existence of Euler paths or cycles depends on the number of odd nodes: 0, 2, or more than 2.

5.1.4.1 Euler Paths and Tours and Odd Nodes

The following implications are basic to Euler tours and paths.

  • zero odd vertices ⇒ graph has an Euler tour.
  • two odd vertices ⇒ graph has an Euler path starting at one odd vertex and ending at the other.
  • more than two odd vertices ⇒ graph does not have an Euler path.

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.

Diagram of handshaking problem displaying solid circles connected by lines indicating odd vertices equals to 0 (a), 2 (b), 4 (c), 2 (d), 4 (e), and 2 (f).

Figure 5.5 Handshaking problem. (a) Odd vertices = 0, (b) odd vertices = 2, (c) odd vertices = 4, (d) odd vertices = 2, (e) odd vertices = 4, and (f) odd vertices = 2.

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.

5.1.5 Weighted Graphs

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.

Map displaying eight cities, namely, Boston, New York, Miami, Dallas, St Louis, Minneapolis, Denver, and San Francisco indicated by solid circle markers with interconnected solid lines indicating distances.

Figure 5.6 Weighted graph of cities and distances.

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.

Map displaying eight cities, namely, Boston, New York, Miami, Dallas, St Louis, Minneapolis, Denver, and San Francisco indicated by solid circle markers connected by solid lines.

Figure 5.7 Minimum spanning tree.

5.1.6 Euler's Characteristic for Planar Graphs

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.

Diagram displaying a square with two lines crossing (a), a square with a diagonal line and a curve (b), and a 3D pyramid (c). All lines and curve are attached to corresponding vertices indicated by solid circle.

Figure 5.8 Equivalent drawings the planar graph K4.

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.

Diagram of Euler characteristic displaying three solid circle markers connected by a line forming a triangle shape.

Figure 5.9 Euler characteristic.

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.

Diagram displaying a cube (a) to faces being triangulated (b) to removal of boundary triangles (c), to a square shape (d), leading to a triangle graph (e).

Figure 5.10 At each step v − e + f is unchanged. (a) Start, (b) triangulate faces, (c) remove boundary triangles, (d) almost done, and (e) done.

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.

Problems

  1. In the drawing in Figure 5.11 showing 10 bridges connecting 5 land masses, determine if it is possible to start and end at any land mass and traverse each bridge exactly once.
    Diagram illustrating ten bridges connecting five land masses.

    Figure 5.11 Find an Euler tour.

    For Problems 2–7, determine if the given graph has an Euler Tour and if so find one.

  2. Diagram displaying pyramid with lines forming six smaller pyramids attached to vertices labeled a, b, c, d, e, f, g, h, i, and j.
    Figure 5.12 Find an Euler tour.
  3. Diagram displaying a hexagon inside a circle having dark circle markers labeled a, b, c, d, e, etc. connected with lines.
    Figure 5.13 Find an Euler tour.
  4. Diagram displaying a rectangular box having dark circle markers on each side labeled a, b, c, d, e, and f connected with lines.
    Figure 5.14 Find an Euler tour.
  5. Diagram displaying two concentric circles with horizontal line at the center having curve lines connecting 4 nodes labeled a, b, c, and d.
    Figure 5.15 Find an Euler tour.
  6. Diagram displaying two concentric triangles with connected nodes on each side labeled a, b, c, d, e, and f.
    Figure 5.16 Find an Euler tour.
  7. Diagram displaying a rectangle with 8 circle markers labeled a, b, c, d, e, f, g, and h; node d connects to e, e connects to b, b connects to g, and g connects to d.
    Figure 5.17 Find an Euler tour.
  8. Euler Paths

    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.

    Diagram displaying a star shape with dark circles on each end (a) a cube with dark circles on each side (b), a star with connected circles forms into a pentagon (c), and a cube with connected dark circles (d).

    Figure 5.18 Find an Euler path.

    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.

  9. Diagram of finding a Hamilton path displaying 8 connected dark circles in an octagon formation labeled a, b, c, d, e, etc.
    Figure 5.19 Find a Hamiltonian path.
  10. Diagram displaying a star shaped figure inside a pentagon with open circle markers connected with lines.
    Figure 5.20 Find a Hamiltonian path.
  11. Diagram displaying a four point star inside a diamond shape with open circle markers connected with lines.
    Figure 5.21 Find a Hamiltonian path.
  12. Diagram displaying a pentagon with dark circle markers on each side labeled a, b, i, j, and f with lines connected to dark circle markers on each side of a star labeled d, c, d, e, h, and g inside the pentagon.
    Figure 5.22 Find a Hamiltonian path.
  13. Graphs of Order 3

    Suppose the vertices of a graph are indistinguishable.

    1. Draw all graphs with three vertices.
    2. Draw all graphs with four vertices and three edges.
  14. All Graphs of Order Four

    Assuming the vertices of the graph are indistinguishable, draw all possible graphs with four vertices. Hint: There are 11 of them.

  15. Hamilton's Famous Puzzle

    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?

    Image described by caption.

    Figure 5.23 Planar representation of the regular dodachedron. (a) Regular dodachedron and (b) planar representation of dodachedron.

  16. Tours of Platonic Solids

    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.

    Planar representations of the Platonic solids, namely, tetrahedron, cube, octahedron, dodecahedron, and icosahedron.

    Figure 5.24 Planar representations of the Platonic solids.

  17. Knight's Tour

    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

    1. Give an argument why a knight's tour is not possible for a 4 × 4 board. Hint: Any tour must pass through the upper left square 1 and the lower right square 16.
    2. Draw a graph of 16 nodes representing a 4 × 4 board, where each vertex is connected by an edge if there is a knight's move between the vertices.
    3. Show that a Hamiltonian tour, which is a cycle that passes through each vertex (not edge) exactly once and returns to the starting vertex, is not possible for the graph you drew in part (b).
    Diagram displaying a knight’s tour on a chessboard labeled 1, 2, 3, etc.

    Figure 5.25 Knight's tour.

  18. More Knight's Tour

    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.

    Diagram displaying squares of a chess board and a chess knight.

    Figure 5.26 Find the knight's tour.

  19. Regular Graphs

    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.

    Diagram of regular graphs, namely, 0-regular graphs displaying dark circles; 1-regular graph displaying 3 sets of connected circles; 2- regular graph displaying 2 triangles with dark circles on each side, etc.

    Figure 5.27 Regular graphs.

    Draw the following regular graphs

    1. 4‐regular graph with 6 vertices
    2. 5‐regular graph with 12 vertices.
    3. 3‐regular graph with 8 vertices. These are called cubic graphs, and there are five of them. Draw as many as you can.
  20. Chromatic Number of a Graph

    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.

    Diagram displaying polygons with dark circles on each side, namely, hexagon with lines connecting the circles (a), a pentagon (b), open hexagon (c), 5 circles connected to a circle in the center (d), etc.

    Figure 5.28 Find the chromatic number.

  21. Moser Spindle

    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?

    Illustration of a moser spindle with 7 nodes.

    Figure 5.29 Moser Spindle.

  22. Internet Research

    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.

Notes

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
52.54.103.76