Network Graphs In the 18^{th} century in the town of Königsberg, Germany, a favorite pastime was walking along the Pregel River and strolling over the town's seven bridges (Fig. 1). During this period a natural question arose: Is it possible to take a walk and cross each bridge only once? Before reading further, can you determine the answer? This question was solved by the Swiss mathematician Leonard Euler. His solution was the beginning of network theory. Figure 1. Euler represented the four land areas of Königsberg (A, B, C, and D in Figure 2) as four points and the seven bridges as seven lines joining these points. For example, the island of Kneiphoff (A) can be reached by five bridges, and in the diagram in Figure 2 there are five lines to point A. The three lines from point D represent three bridges, etc. This kind of diagram is called a network graph, or more simply, a network. Notice that Euler was concerned not with the size and shape of the bridges and land regions but rather with how the bridges were connected. Figure 2. A network is a collection of points, called vertices, and a collection of lines, called arcs, connecting these points. A network is traversable if you can trace each arc exactly once by beginning at some point and not lifting your pencil from the paper. The problem of crossing each bridge exactly once reduces to one of traversing the network representing these bridges. Euler made the remarkable discovery that whether a network is traversable depends on the number of odd vertices. In the Königsberg network, there are an odd number of arcs at point A, so A is called an odd vertex. If the number of arcs meeting at a point is even, the point is called an even vertex. Euler found that the only traversable networks are those that have either no odd vertices or exactly two odd vertices. Since the Königsberg network has four odd vertices, it is not traversable. Therefore, it is not possible to take a walk over the bridges of Königsberg and cross each bridge only once. Try working the following Examples A-D before looking at the solutions. Example A Which of the following networks are traversable? Solution Network 1 has two odd vertices, so it is traversable. Network 2 has no odd vertices, so it is traversable. Networks 3 and 4 have four and six odd vertices, respectively, so they are not traversable. We now know how to determine if a network is traversable. But is it possible to predict where you ought to begin in order to trace the network exactly once, and where you will end up? The following example considers this problem. Example B Each of these networks has two odd vertices and is traversable. Show a beginning point and an ending point for each network. Form a conjecture about the beginning and ending points of networks with exactly two odd vertices. Solution Conjecture: One odd vertex will be the starting point, and the other odd vertex will be the ending point. Consider the conjecture in Example B. As a network is traversed, two arcs are used each time we pass through a vertex point: one in arriving at the point and one in leaving. The only way there can be an odd vertex in a traversable network is if that vertex is a beginning point or an ending point. Next consider a network with no odd vertices. Example C The following networks have no odd vertices (all vertices are even). Find at least two different beginning points for traversing each network. Form a conjecture about traversing networks with no odd vertices. Solution Conjecture: In traversing a network with all even vertices, the beginning point may be any vertex, and the ending point will be the same vertex. The conjecture in Example C seems reasonable. Since the arcs occur in pairs at each vertex, beginning at a vertex will always require returning to that vertex. The facts illustrated in Examples A through C are summarized in the following statements.
Four-Color Problem For over 100 years mathematicians believed, but could not prove, that four colors were sufficient to color any map in a plane. The only requirement for map coloring is that two regions sharing a common boundary have different colors. If two regions meet at only one point, they do not share a common boundary. No one had been able to draw a map that required more than four colors, but it could not be proved that four colors are all that is needed. Example D Using the conditions stated in the previous paragraph, determine the minimum number of different colors needed to color each map. Solution Map 1 requires four colors, and map 2 requires three colors. In 1976, two University of Illinois mathematicians, Kenneth Appel and Wolfgang Haken, announced they had proved that four colors are all that is necessary to color any map. This result was exciting to mathematicians, and the proof attracted much attention because it was long and made extensive use of computers. The problem was solved by representing map regions as points and boundaries as arcs connecting these points. Using this network approach, Appel and Haken were able to reduce the problem to an examination of 1936 basic map forms. Appel and Haken fed their map forms into the computer, and after 1200 hours the computer determined that each map can be colored with four or fewer colors. Problem-Solving Application Network theory has a wide range of applications including determining routes, designing electric circuits, and planning schedules. The solution to the following problem illustrates one use of networks. Problem A tour guide is planning a tour of a museum. To minimize congestion at doorways, the guide would like to have the tour pass through each door of the museum exactly once. For what type of floor plans is this possible? Understanding the Problem The tour may begin at any point inside or outside the museum and end at any point. Show that a tour such as the one described above can be conducted for the floor diagram shown here. Question 1: Can the tour be started either outside or inside with this floor plan? Devising a Plan One approach is to draw floor diagrams with different numbers of rooms and doors and try to plan tours. By counting the numbers of rooms, doors, and doors per room, you may discover a pattern. Another approach is to describe the floor plan by a network and then determine if the network is traversable. Question 2: Can such a tour be conducted for the following floor plan? Carrying Out the Plan The network below illustrates the preceding floor plan. Each room is represented by a vertex point. Notice that a vertex (point P) is needed to represent the region outside the floor plan. Question 3: Is this network traversable? How does the use of networks suggest a general solution to the original problem? Looking Back Suppose that in addition to requiring that each door be passed through only once, we require that the tour begin and end in the same room. Question 4: For what type of floor plans is this possible? Answers to Questions 1-4 1. 2. No. Network Graphs Exercises Each of the networks in exercises 1 and 2 has two odd vertices and is traversable. Show a beginning point and an ending point for each. What is always true about the beginning and ending points of networks with exactly two odd vertices?
Which of the networks in exercises 3 and 4 are traversable? Trace each traversable network on a separate piece of paper. Mark a path with arrows, and indicate the beginning and ending points.
The vertices and edges of polyhedra are three-dimensional networks. Use these polyhedra in exercises 5 and 6.
Draw a network for the floor plan in 9 and 10. Is it possible to plan a walk in which each door is passed through exactly once?
For each of the floor plans in 11 and 12 determine if it is possible to plan a walk in which you pass through each door exactly once and begin and end on the outside of the house.
Determine the minimum number of colors required to color each map in 14 and 15 if regions with a common boundary (other than a single point) must be different colors. (Note: The interiors of the circles are to be colored.)
When maps are colored, it is desirable to use different colors for regions with a common boundary. Use this condition in 16 and 17.
Determine if the grids in 19 through 21 are traversable networks. If a network is traversable, mark a beginning point and an ending point. If it is not, explain why.
Counting the outside of the network as one region, as required in part a, results in a relationship that is similar to a famous relationship between the numbers of vertices, faces, and edges of polyhedra. What is this relationship? Figure A below is made up of four polygons that are connected by common nonoverlapping sides. Figure B shows that a continuous arc can be drawn that intersects every side of each polygon exactly once. On which of the figures in 23 and 24 can you draw a continuous arc that passes through each side of each polygon exactly once? (There is no requirement that the arc begin on the interior of a polygon; however, the arc must not intersect a vertex of the figure.) Make a conjecture about the conditions under which a continuous arc can be drawn for such polygons.
Answers to Odd-numbered Network Graphs Exercises 1. Networks with exactly two odd vertices are always traversable. Either odd vertex can be the beginning point, and the other will be the endpoint. 3.
a. Not traversable. 5. Octahedron. 7. Yes, it is traversable. 9. Yes 11. a. No b. Yes 13. Every network has an even number of odd vertices (0, 2, 4, …). 15. a. 3 17. 4 19. Isometric grids are traversable because all vertices are even, and any vertex may be a beginning point. 21. Hexagonal grids are not traversable because there are more than two odd vertices. 23. Figures a and b. There must be exactly 0, 1, or 2 regions with an odd number of sides. 25. a. The beginning point can be either of the two odd vertices; the endpoint will be the other odd vertex. 27. a. Not traversable. |