Chapter 6.1 Mathematical Systems PDF

CHAPTER 6.1 The Mathematics of Graphs Copyright © Cengage Learning. All rights reserved.  5.1 Section Graphs and Euler Circuits Copyright © Cengage Learning. All rights reserved. Introducti...

CHAPTER 6.1 The Mathematics of Graphs Copyright © Cengage Learning. All rights reserved.  5.1 Section Graphs and Euler Circuits Copyright © Cengage Learning. All rights reserved. Introduction to Graphs 3 Introduction to Graphs Think of all the various connections we experience in our lives—friends are connected on Facebook, cities are connected by roads, computers are connected across the Internet. A branch of mathematics called graph theory illustrates and analyzes connections such as these. For example, the diagram in Figure 5.1 could represent friends that are connected on Facebook. Figure 5.1 4 Introduction to Graphs Each dot represents a person, and a line segment connecting two dots means that those two people are friends on Facebook. This type of diagram is called a graph. 5 Example 1 – Constructing a Graph The following table lists five students at a college. An “X” indicates that the two students participate in the same study group this semester. 6 Example 1 – Constructing a Graph cont’d a. Draw a graph that represents this information where each vertex represents a student and an edge connects two vertices if the corresponding students study together. b. Use your graph to answer the following questions: Which student is involved in the most study groups with the others? Which student has only one study group in common with the others? How many study groups does Laura have in common with the others? 7 Example 1 – Solution a. We draw five vertices (in any configuration we wish) to represent the five students, and connect vertices with edges according to the table. 8 Example 1 – Solution cont’d b. The vertex corresponding to Amber is connected to more edges than the others, so she is involved with more study groups (three) than the others. Kayla is the only student with one study group in common, as her vertex is the only one connected to just one edge. Laura’s vertex is connected to two edges, so she shares two study groups with the others. 9 Introduction to Graphs In general, a graph can include vertices that are not joined to any edges, but all edges must begin and end at vertices. If two or more edges connect the same vertices, they are called multiple edges. If an edge begins and ends at the same vertex, it is called the loop. A graph is called connected if any vertex can be reached from any other vertex by tracing along edges. (Essentially, the graph consists of one “piece.”) A connected graph in which every possible edge is drawn between vertices (without any multiple edges) is called a complete graph. 10 Introduction to Graphs Several examples of graphs are shown below. This graph has five vertices but This is a connected graph that has a no edges. It is not connected. pair of multiple edges. Note that two edges cross in the center, but there is no vertex there. Unless a dot is drawn, the edges are considered to pass over each other without touching. 11 Introduction to Graphs This graph is not connected; it consists of two This is a complete graph with five vertices. different sections. It also contains a loop. 12 Introduction to Graphs Consequently, the three graphs shown below are considered equivalent graphs because the edges form the same connections of vertices in each graph. 13 Example 2 – Equivalent Graphs Determine whether the following two graphs are equivalent. Solution: Despite the fact that the two graphs have different arrangements of vertices and edges, they are equivalent. 14 Example 2 – Solution cont’d To illustrate, we examine the edges of each graph. The first graph contains six edges; we can list them by indicating which two vertices they connect. The edges are AC, AE, BD, BE, CE, and DE. If we do the same for the second graph, we get the same six edges. Because the two graphs represent the same connections among the vertices, they are equivalent. 15 Euler Circuits 16 Euler Circuits To solve the Königsberg bridges problem, we can represent the arrangement of land areas and bridges with a graph. Let each land area be represented by a vertex, and connect two vertices if there is a bridge spanning the corresponding land areas. Then the geographical configuration shown in Figure 5.3 becomes the graph shown in Figure 5.4. Figure 5.4 Figure 5.3 17 Euler Circuits A path in a graph can be thought of as a movement from one vertex to another by traversing edges. We can refer to our movement by vertex letters. For example, in the graph in Figure 5.4, one path would be A–B–A–C. If a path ends at the same vertex at which it started, it is considered a closed path, or circuit. For the graph in Figure 5.5, the path A–D–F–G–E–B–A is a circuit because it begins and ends at the same vertex. Figure 5.5 18 Euler Circuits The path A–D–F–G–E–H is not a circuit, as the path ends at a different vertex than the one it started at. A circuit that uses every edge, but never uses the same edge twice, is called an Euler circuit. (The path may cross through vertices more than once.) The path B–D–F–G–H–E–C–B–A–D–G–E–B in Figure 5.5 is an Euler circuit. It begins and ends at the same vertex and uses each edge exactly once. (Trace the path with your pencil to verify!) The path A–B–C–E–H–G–E–B–D–A is not an Euler circuit. 19 Euler Circuits The path begins and ends at the same vertex but it does not use edges DF, DG, or FG. Euler essentially proved that the graph in Figure 5.4 could not have an Euler circuit. He accomplished this by examining the number of edges that met at each vertex. Figure 5.4 The number of edges that meet at a vertex is called the degree of a vertex. 20 Euler Circuits He made the observation that in order to complete the desired path, every time you approached a vertex you would then need to leave that vertex. If you traveled through that vertex again, you would again need an approaching edge and a departing edge. Thus for an Euler circuit to exist, the degree of every vertex would have to be an even number. 21 Euler Circuits Furthermore, he was able to show that any graph that has even degree at every vertex must have an Euler circuit. Consequently, such graphs are called Eulerian. 22 Example 3 – Identifying Eulerian Graphs Which of the following graphs has an Euler circuit? a. b. Solution: a. Vertices C and D are of odd degree. By the Eulerian Graph Theorem, the graph does not have an Euler circuit. b. All vertices are of even degree. By the Eulerian Graph Theorem, the graph has an Euler circuit. 23 Euler Circuits The Eulerian Graph Theorem guarantees that when all vertices of a graph have an even degree, an Euler circuit exists, but it does not tell us how to find one. Because the graphs we will examine here are relatively small, we will rely on trial and error to find Euler circuits. 24 Example 4 – Find an Euler Circuit Determine whether the graph shown below is Eulerian. If it is, find an Euler circuit. If it is not, explain how you know. Solution: Each vertex is of even degree (2, 4, or 6), so by the Eulerian graph theorem, the graph is Eulerian. There are many possible Euler circuits in this graph. 25 Example 4 – Solution cont’d We do not have a formal method of locating one, but by trial and error, one Euler circuit is B–A–F–B–E–F–G–E–D– G–B–D–C–B. 26 Euler Paths 27 Euler Paths Perhaps the Königsberg bridges problem would have a solution if we did not need to return to the starting point. In this case, what we are looking for in Figure 5.4 is a path (not necessarily a circuit) that uses every edge once and only once. Figure 5.4 We call such a path an Euler path. Euler showed that even with this relaxed condition, the bridge problem still was not solvable. 28 Euler Paths The general result of his argument is given in the following theorem. 29 Example 6 – An Application of Euler Paths A photographer would like to travel across all of the roads shown on the following map. The photographer will rent a car that need not be returned to the same city, so the trip can begin in any city. Is it possible for the photographer to design a trip that traverses all of the roads exactly once? 30 Example 6 – Solution Looking at the map of roads as a graph, we see that a route that includes all of the roads but does not cover any road twice corresponds to an Euler path of the graph. Notice that only two vertices are of odd degree, the cities Alameda and Dover. Thus we know that an Euler path exists, and so it is possible for the photographer to plan a route that travels each road once. Because (abbreviating the cities) A and D are vertices of odd degree, the photographer must start at one of these cities. With a little experimentation, we find that one Euler path is A–B–C–D–B–F–A–G–F–E–D. 31  CHAPTER 6.2 The Mathematics of Graphs Copyright © Cengage Learning. All rights reserved.  5.2 Section Weighted Graphs Copyright © Cengage Learning. All rights reserved. Hamiltonian Circuits 3 Hamiltonian Circuits We have already looked at paths that use every edge of a graph exactly once. In some situations we may be more interested in paths that visit each vertex once, regardless of whether all edges are used or not. 4 Hamiltonian Circuits For instance, consider the following example. A photographer would like to travel across all of the roads shown on the following map. The photographer will rent a car that need not be returned to the same city, so the trip can begin in any city. 5 Hamiltonian Circuits Is it possible for the photographer to design a trip that traverses all of the roads exactly once? If our priority is to visit each city, we could travel along the route A–B–C–D–E–F–G–A (abbreviating the cities). This path visits each vertex once and returns to the starting vertex without visiting any vertex twice. This type of path is called a Hamiltonian circuit. 6 Hamiltonian Circuits Unfortunately we do not have a straightforward criterion to guarantee that a graph is Hamiltonian, but we do have the following helpful theorem. 7 Example 1 – Apply Dirac’s Theorem The following graph shows the available flights of a small airline. An edge between two vertices in the graph means that the airline has direct flights between the two corresponding cities. Apply Dirac’s theorem to verify that the following graph is Hamiltonian. Then find a Hamiltonian circuit. What does the Hamiltonian circuit represent in terms of flights? 8 Example 1 – Solution There are six vertices in the graph, so n = 6, and every vertex has a degree of at least n/2 = 3. By Dirac’s theorem, the graph is Hamiltonian. This means that the graph contains a circuit that visits each vertex once and returns to the starting vertex without visiting any vertex twice. By trial and error, one Hamiltonian circuit is Portland– Boise–Butte–Salt Lake City–Reno–Sacramento–Portland, which represents a sequence of flights that visits each city and returns to the starting city without visiting any city twice. 9 Weighted Graphs 10 Weighted Graphs A weighted graph is a graph in which each edge is associated with a value, called a weight. The value can represent any quantity we desire. In the case of distances between cities, we can label each edge with the number of miles between the corresponding cities, as in Figure 5.9. (Note that the length of an edge Figure 5.9 does not necessarily correlate to its weight.) 11 Weighted Graphs For each Hamiltonian circuit in the weighted graph, the sum of the weights along the edges traversed gives the total distance traveled along that route. We can then compare different routes and find the one that requires the shortest total distance. This is an example of a famous problem called the traveling salesman problem. 12 Example 2 – Find Hamiltonian Circuits in a Weighted Graph The table below lists the distances in miles between six popular cities that a particular airline flies to. Suppose a traveler would like to start in Chicago, visit the other five cities this airline flies to, and return to Chicago. Find three different routes that the traveler could follow, and find the total distance flown for each route. 13 Example 2 – Solution The various options will be simpler to analyze if we first organize the information in a graph. Begin by letting each city be represented by a vertex. Draw an edge between two vertices if there is a flight between the corresponding cities, and label each edge with a weight that represents the number of miles between the two cities. 14 Example 2 – Solution cont’d A route that visits each city just once corresponds to a Hamiltonian circuit. Beginning at Chicago, one such circuit is Chicago–New York–Dallas–Philadelphia–Atlanta– Washington, D.C.– Chicago. By adding the weights of each edge in the circuit, we see that the total number of miles traveled is 713 + 1374 + 1299 + 670 + 544 + 597 = 5197 15 Example 2 – Solution cont’d By trial and error, we can identify two additional routes. One is Chicago–Philadelphia–Dallas–Washington, D.C.– Atlanta–New York–Chicago. The total weight of the circuit is 665 + 1299 + 1185 + 544 + 748 + 713 = 5154 A third route is Chicago–Washington, D.C.–Dallas–New York–Atlanta–Philadelphia–Chicago. The total mileage is 597 + 1185 + 1374 + 748 + 670 + 665 = 5239 16 Algorithms in Complete Graphs 17 Algorithms in Complete Graphs There is no known shortcut for finding the optimal Hamiltonian circuit in a weighted graph. There are, however, two algorithms, the greedy algorithm and the edge-picking algorithm, that can be used to find a pretty good solution. Both of these algorithms apply only to complete graphs— graphs in which every possible edge is drawn between vertices (without any multiple edges). 18 Algorithms in Complete Graphs For instance, the graph in Figure 5.10 is a complete graph with six vertices. The circuits found by the algorithms are not guaranteed to have the smallest total weight possible, but they are often better than you would find by trial and error. Figure 5.10 19 Algorithms in Complete Graphs The greedy algorithm is so called because it has us choose the “cheapest” option at every chance we get. 20 Example 3 – The Greedy Algorithm Use the greedy algorithm to find a Hamiltonian circuit in the weighted graph shown in Figure 5.11. Start at vertex A. Figure 5.11 21 Example 3 – Solution Begin at A. The weights of the At D, the edge with the edges from A are 13, 5, 4, 15, smallest weight is DB. and 8. The smallest is 4. Connect D to B. Connect A to D. 22 Example 3 – Solution cont’d At B, the edge with At F, the edge with the smallest the smallest weight is weight, 7, is FD. However, D has BF. Connect B to F. already been visited. Choose the next smallest weight, edge FE. Connect F to E. 23 Example 3 – Solution cont’d At E, the edge with the All vertices have been smallest weight whose visited, so we are at step 3 vertex has not been visited of the algorithm. We return is C. Connect E to C. to the starting vertex by connecting C to A. 24 Example 3 – Solution cont’d The Hamiltonian circuit is A–D–B–F–E–C–A. The weight of the circuit is 4 + 2 + 5 + 10 + 6 + 15 = 42 25 Algorithms in Complete Graphs 26 Example 4 – The Edge-Picking Algorithm Use the edge-picking algorithm to find a Hamiltonian circuit in Figure 5.11. Figure 5.11 27 Example 4 – Solution We first highlight the edge of The edge of next smallest weight, namely BD smallest weight is AD with weight 2. with weight 4. 28 Example 4 – Solution cont’d The next smallest weight There are two edges of weight is 5, which appears twice, 6 (the next smallest weight), with edges AE and FB. BC and EC. We cannot use BC We can mark both of them. because it would add a third marked edge to vertex B. We mark edge EC. 29 Example 4 – Solution cont’d We are now at step 3 of the algorithm; any edge we mark will either complete a circuit or add a third edge to a vertex. So we mark the final edge to complete the Hamiltonian circuit, edge FC. 30 Example 4 – Solution cont’d Beginning at vertex A, the Hamiltonian circuit is A–D–B–F–C–E–A. (In the reverse direction, an equivalent circuit is A–E–C–F–B–D–A.) The total weight of the circuit is 4 + 2 + 5 + 14 + 6 + 5 = 36 31 Applications of Weighted Graphs 32 Applications of Weighted Graphs In Example 2, we examined distances between cities. This is just one example of a weighted graph; the weight of an edge can be used to represent any quantity we like. For example, a traveler might be more interested in the cost of flights than the time or distance between cities. If we labeled each edge of the graph in Example 2 with the cost of traveling between the two cities, the total weight of a Hamiltonian circuit would be the total travel cost of the trip. 33 Example 5 – An Application of the Greedy and Edge-Picking Algorithms The cost of flying between various European cities is shown in the following table. 34 Example 5 – An Application of the Greedy and Edge-Picking Algorithms cont’d Use both the greedy algorithm and the edge-picking algorithm to find a low-cost route that visits each city just once and starts and ends in London. Which route is more economical? 35 Example 5 – Solution First we draw a weighted graph with vertices representing the cities and each edge labeled with the price of the flight between the corresponding cities. 36 Example 5 – Solution cont’d To use the greedy algorithm, start at London and travel along the edge with the smallest weight, 160, to Paris. The edge of smallest weight leaving Paris is the edge to Madrid. From Madrid, the edge of smallest weight (that we have not already traversed) is the edge to London, of weight 250. However, we cannot use this edge, because it would bring us to a city we have already seen. We can take the next- smallest-weight edge to Rome. We cannot yet return to London, so the next available edge is to Vienna, then to Berlin, and finally back to London. 37 Example 5 – Solution cont’d The total weight of the edges, and thus the total airfare for the trip, is 160 + 215 + 380 + 480 + 375 + 325 = $1935 38 Example 5 – Solution cont’d If we use the edge-picking algorithm, the edges with the smallest weights that we can highlight are London–Paris and Madrid–Paris. The edge of next smallest weight has a weight of 250, but we cannot use this edge because it would complete a circuit. We can take the edge of next smallest weight, 280, from London to Rome. 39 Example 5 – Solution cont’d We cannot take the edge of next smallest weight, 325, because it would add a third edge to the London vertex, but we can take the edge Vienna–Berlin of weight 375. We must skip the edges of weights 380, 415, and 425, but we can take the edge of weight 480, which is the Vienna– Rome edge. There are no more edges we can mark that will meet the requirements of the algorithm, so we mark the last edge to complete the circuit, Berlin–Madrid. 40 Example 5 – Solution cont’d The resulting route is London–Paris–Madrid–Berlin– Vienna–Rome–London, for a total cost of 160 + 215 + 675 + 375 + 480 + 280 = $2185 (We could also travel this route in the reverse order.) 41  CHAPTER 6.3 The Mathematics of Graphs Copyright © Cengage Learning. All rights reserved.  6.3 Section Planarity and Euler’s Formula Copyright © Cengage Learning. All rights reserved. Planarity 3 Planarity Three utility companies each need to run pipes to three houses. Can they do so without crossing over each other’s pipes at any point? The puzzle is illustrated in Figure 5.15. House X House Y House Z Utility A Utility B Utility C Figure 5.15 4 Planarity One way to approach the puzzle is to express the situation in terms of a graph. Each of the houses and utility companies will be represented by a vertex, and we will draw an edge between two vertices if a pipe needs to run from one building to the other. If we were not worried about pipes crossing, we could easily draw a solution, as in Figure 5.16. The Utilities Graph Figure 5.16 5 Planarity To solve the puzzle, we need to draw an equivalent graph in which no edges cross over each other. If this is possible, the graph is called a planar graph. If the graph is drawn in such a way that no edges cross, we say that we have a planar drawing of the graph. 6 Example 1 – Identify a Planar Graph Show that the graph below is planar. 7 Example 1 – Solution As given, the graph has several intersecting edges. However, we can redraw the graph in an equivalent form in which no edges touch except at vertices by redrawing the two red edges shown. 8 Example 1 – Solution cont’d To verify that the second graph is equivalent to the first, we can label the vertices and check that the edges join the same vertices in each graph. Because the given graph is equivalent to a graph whose edges do not intersect, the graph is planar. 9 Planarity To see that the graph in Figure 5.16 representing the puzzle of connecting utilities is not planar, note that the graph is Hamiltonian, and one Hamiltonian circuit is A–X–B–Y–C–Z–A. The Utilities Graph Figure 5.16 10 Planarity If we redraw the graph so that this circuit is drawn in a loop (see Figure 5.17), we then need to add the edges AY, BZ, and CX. Figure 5.17 All three of these edges connect opposite vertices. 11 Planarity We can draw only one of these edges inside the loop; otherwise two edges would cross. This means that the other two edges must be drawn outside the loop, but as you can see in Figure 5.18, those two edges would then have to cross. Figure 5.18 12 Planarity Thus the graph in Figure 5.16, which we will refer to as the Utilities Graph, is not planar, and so the utilities puzzle is not solvable. One strategy we can use to show that a graph is not planar is to find a subgraph, a graph whose edges and vertices come from the given graph, that is not planar. The Utilities Graph Figure 5.16 The Utilities Graph in Figure 5.16 is a common subgraph to watch for. 13 Planarity Another graph that is not planar is the complete graph with five vertices, denoted K5, shown in Figure 5.19. The complete graph K5 Figure 5.19 14 Example 2 – Identify a Nonplanar Graph Show that the following graph is not planar. 15 Example 2 – Solution In the figure below, we have highlighted edges connecting the top six vertices. If we consider the highlighted edges and attached vertices as a subgraph, we can verify that the subgraph is the Utilities Graph. 16 Example 2 – Solution cont’d The graph is slightly distorted compared with the version shown in Figure 5.16, but it is equivalent. The Utilities Graph Figure 5.16 By the preceding theorem, we know that the graph is not planar. 17 Planarity We can expand this strategy by considering contractions of a subgraph. A contraction of a graph is formed by “shrinking” an edge until the two vertices it connects come together and blend into one. If, in the process, the graph is left with any multiple edges, we merge them into one. The process is illustrated below. 18 Example 3 – Contracting a Graph Show that the first graph below can be contracted to the second graph. Solution: 19 Planarity If we consider contractions, it turns out that the Utilities Graph and K5 serve as building blocks for nonplanar graphs. In fact, it was proved in 1930 that any nonplanar graph will always have a subgraph that is the Utilities Graph or K5, or a subgraph that can be contracted to the Utilities Graph or K5. We can then expand our strategy, as given by the following theorem. 20 Example 4 – Identify a Nonplanar Graph Show that the graph below is not planar. Solution: Note that the graph looks similar to K5. In fact, we can contract some edges and make the graph look like K5. 21 Example 4 – Solution cont’d Choose a pair of adjacent outside edges and contract one of them, as shown in the figure below. 22 Example 4 – Solution cont’d If we similarly contract the four edges colored green in the preceding figure, we arrive at the graph of K5. We were able to contract our graph to K5, so by the nonplanar graph theorem, the given graph is not planar. 23 Euler’s Formula 24 Euler’s Formula Euler noticed a connection between various features of planar graphs. In addition to edges and vertices, he looked at faces of a graph. In a planar drawing of a graph, the edges divide the graph into different regions called faces. The region surrounding the graph, or the exterior, is also considered a face, called the infinite face. 25 Euler’s Formula The following relationship, called Euler’s formula, is always true. 26 Example 5 – Verify Euler’s Formula in a Graph Count the number of edges, vertices, and faces in the planar graph below, and then verify Euler’s formula. Solution: There are seven edges, five vertices, and four faces (counting the infinite face) in the graph. Thus v + f = 5 + 4 = 9 and e + 2 = 7 + 2 = 9, so v + f = e + 2, as Euler’s Formula predicts. 27  CHAPTER 6.4 The Mathematics of Graphs Copyright © Cengage Learning. All rights reserved.  6.4 Section Graph Coloring Copyright © Cengage Learning. All rights reserved. Coloring Maps 3 Coloring Maps Here is a map of the contiguous states of the United States. Note that the map has only four colors and that no two states that share a common border have the same color. 4 Coloring Maps There is a connection between coloring maps and graph theory. This connection has many practical applications, from scheduling tasks, to designing computers, to playing Sudoku. Later in this section we will look more closely at some of these applications. 5 Coloring Maps Suppose the map in Figure 5.21 shows the countries, labeled as letters, of a continent. We will assume that no country is split into more than one piece and countries that touch at just a corner point will not be considered neighbors. Figure 5.21 6 Coloring Maps We can represent each country by a vertex, placed anywhere within the boundary of that country. We will then connect two vertices with an edge if the two corresponding countries are neighbors—that is, if they share a common boundary. The result is shown in Figure 5.22. Figure 5.22 7 Coloring Maps If we erase the boundaries of the countries, we are left with the graph in Figure 5.23. The resulting graph will always be a planar graph, because the edges simply connect neighboring countries. FIGURE 5.23 8 Coloring Maps Our map-coloring question then becomes: Can we give each vertex of the graph a color such that no two vertices connected by an edge share the same color? How many different colors will be required? If this can be accomplished using four colors, for instance, we will say that the graph is 4-colorable. The graph in Figure 5.23 is actually 3-colorable; only three colors are necessary. FIGURE 5.23 9 Coloring Maps One possible coloring is given in Figure 5.24. Figure 5.24 10 Coloring Maps A colored map for Figure 5.21 based on the colors of the vertices of the graph is in Figure 5.25. Figure 5.21 Figure 5.25 We can now formally state the four-color theorem. 11 Example 1 – Using a Graph to Color a Map The fictional map below shows the boundaries of countries on a rectangular continent. Represent the map as a graph, and find a coloring of the graph using the fewest possible number of colors. Then color the map according to the graph coloring. 12 Example 1 – Solution First draw a vertex in each country and then connect two vertices with an edge if the corresponding countries are neighbors. 13 Example 1 – Solution cont’d Now try to color the vertices of the resulting graph so that no edge connects two vertices of the same color. We know we will need at least two colors, so one strategy is simply to pick a starting vertex, give it a color, and then assign colors to the connected vertices one by one. Try to reuse the same colors, and use a new color only when there is no other option. For this graph we will need four colors. (The four-color theorem guarantees that we will not need more than that.) 14 Example 1 – Solution cont’d To see why we will need four colors, notice that the one vertex colored green in the following figure connects to a ring of five vertices. Three different colors are required to color the five-vertex ring, and the green vertex connects to all these, so it requires a fourth color. 15 Example 1 – Solution cont’d Now we color each country the same color as the coresponding vertex. 16 The Chromatic Number of a Graph 17 The Chromatic Number of a Graph We mentioned previously that representing a map as a graph always results in a planar graph. The four-color theorem guarantees that we need only four colors to color a planar graph; however, if we wish to color a nonplanar graph, we may need more than four colors. The minimum number of colors needed to color a graph so that no edge connects vertices of the same color is called the chromatic number of the graph. 18 The Chromatic Number of a Graph In general, there is no efficient method of finding the chromatic number of a graph, but we do have a theorem that can tell us whether a graph is 2-colorable. 19 Example 2 – Determine the Chromatic Number of a Graph Find the chromatic number of following Utilities Graph. Solution: Note that the graph contains circuits such as A–Y–C–Z–B–X–A with six vertices and A–Y–B–X–A with four vertices. It seems that any circuit we find, in fact, involves an even number of vertices. 20 Example 2 – Solution cont’d It is difficult to determine whether we have looked at all possible circuits, but our observations suggest that the graph may be 2-colorable. A little trial and error confirms this if we simply color vertices A, B, and C one color and the remaining vertices another. Thus the Utilities Graph has a chromatic number of 2. 21 Applications of Graph Coloring 22 Applications of Graph Coloring Determining the chromatic number of a graph and finding a corresponding coloring of the graph can solve a wide assortment of practical problems. One common application is in scheduling meetings or events. This is best shown by example. 23 Example 3 – A Scheduling Application of Graph Coloring Eight different school clubs want to schedule meetings on the last day of the semester. Some club members, however, belong to more than one of these clubs, so clubs that share members cannot meet at the same time. How many different time slots are required so that all members can attend all meetings? 24 Example 3 – A Scheduling Application of Graph Coloring cont’d Clubs that have a member in common are indicated with an “X” in the table below. 25 Example 3 – Solution We can represent the given information by a graph. Each club is represented by a vertex, and an edge connects two vertices if the corresponding clubs have at least one common member. 26 Example 3 – Solution cont’d Two clubs that are connected by an edge cannot meet simultaneously. If we let a color correspond to a time slot, then we need to find a coloring of the graph that uses the fewest possible number of colors. 27 Example 3 – Solution cont’d The graph is not 2-colorable, because we can find circuits of odd length. However, by trial and error, we can find a 3-coloring. One example is shown below. Thus the chromatic number of the graph is 3, so we need three different time slots. 28 Example 3 – Solution cont’d Each color corresponds to a time slot, so one scheduling is First time slot: ski club, debate club, student newspaper Second time slot: student government, community outreach Third time slot: honor society, campus Democrats, campus Republicans 29  CHAPTER 6.1 Mathematical Systems Copyright © Cengage Learning. All rights reserved.  6.1 Section Modular Arithmetic Copyright © Cengage Learning. All rights reserved. Introduction to Modular Arithmetic 3 Introduction to Modular Arithmetic If we want to determine a time in the future or in the past, it is necessary to consider whether we have passed 12 o’clock. To determine the time 8 hours after 3 o’clock, we add 3 and 8. Because we did not pass 12 o’clock, the time is 11 o’clock (Figure 8.1A). Figure 8.1A 4 Introduction to Modular Arithmetic However, to determine the time 8 hours after 9 o’clock, we must take into consideration that once we have passed 12 o’clock, we begin again with 1. Therefore, 8 hours after 9 o’clock is 5 o’clock, as shown in Figure 8.1B Figure 8.1B 5 Introduction to Modular Arithmetic We will use the symbol to denote addition on a 12-hour clock. Using this notation, and on a 12-hour clock. We can also perform subtraction on a 12-hour clock. If the time now is 10 o’clock, then 7 hours ago the time was 3 o’clock, which is the difference between 10 and 7 (10 – 7 = 3). 6 Introduction to Modular Arithmetic However, if the time now is 3 o’clock, then, using Figure 8.2, we see that 7 hours ago it was 8 o’clock. If we use the symbol to denote subtraction on a 12-hour clock, we can write and Figure 8.2 7 Example 1 – Perform Clock Arithmetic Evaluate each of the following, where and indicate addition and subtraction, respectively, on a 12-hour clock. a. b. b. c. c. d. Solution: Calculate using a 12-hour clock. a. b. c. d. 8 Introduction to Modular Arithmetic A similar example involves day-of-the-week arithmetic. If we associate each day of the week with a number, as shown below, then 6 days after Friday is Thursday and 16 days after Monday is Wednesday. Symbolically, we write and 9 Introduction to Modular Arithmetic Note: We are using the symbol for days-of-the-week arithmetic to differentiate from the symbol for clock arithmetic. 10 Introduction to Modular Arithmetic Situations such as these that repeat in cycles are represented mathematically by using modular arithmetic, or arithmetic modulo n. 11 Example 2 – Determine Whether a Congruence Is True Determine whether the congruence is true. a. 29  8 mod 3 b. 15  4 mod 6 Solution: a. Find Because 7 is an integer, 29  8 mod 3 is a true congruence. b. Find Because is not an integer, 15  4 mod 6 is not a true congruence. 12 Introduction to Modular Arithmetic Now suppose today is Friday. To determine the day of the week 16 days from now, we observe that 14 days from now the day will be Friday, so 16 days from now the day will be Sunday. Note that the remainder when 16 is divided by 7 is 2, or, using modular notation, 16  2 mod 7. The 2 signifies 2 days after Friday, which is Sunday. 13 Example 3 – A Day of the Week July 4, 2017, was a Tuesday. What day of the week is July 4, 2022? Solution: There are 5 years between the two dates. Each year has 365 days except 2020, which has one extra day because it is a leap year. So the total number of days between the two dates is 5  365 + 1 = 1826. 14 Example 3 – Solution cont’d Because 1826 ÷ 7 = 260 remainder 6, 1826  6 mod 7. Any multiple of 7 days past a given day will be the same day of the week. So the day of the week 1826 days after July 4, 2017, will be the same as the day 6 days after July 4, 2017. Thus July 4, 2022, will be a Monday. 15 Arithmetic Operations Modulo n 16 Arithmetic Operations Modulo n Arithmetic modulo n (where n is a natural number) requires us to evaluate a modular expression after using the standard rules of arithmetic. Thus we perform the arithmetic operation and then divide by the modulus. The answer is the remainder. The result of an arithmetic operation mod n is always a whole number less than n. 17 Example 4 – Addition Modulo n Evaluate: (23 + 38) mod 12 Solution: Add 23 + 38 to produce 61. To evaluate 61 mod 12, divide 61 by the modulus, 12. The answer is the remainder. The answer is 1. 18 Example 5 – Subtraction Modulo n Evaluate each of the following. a. (33 – 16) mod 6 b. (14 – 27) mod 5 Solution: a. Subtract The result is positive. Divide the difference by the modulus, 6. The answer is the remainder. (33 – 16) mod 6 = 5 19 Example 5 – Solution cont’d b. Subtract Because the answer is negative, we must find x so that –13  x mod 5. Thus we must find x so that the value of is an integer. Trying the whole number values of x less than 5, the modulus, we find that when x = 2, (14 – 27) mod 5 = 2 20 Arithmetic Operations Modulo n The methods of adding and subtracting in modular arithmetic can be used for clock arithmetic and days-of-the-week arithmetic. 21 Example 6 – Calculating Times Disregarding A.M. or P.M., if it is 5 o’clock now, what time was it 57 hours ago? Solution: The time can be determined by calculating (5 – 57) mod 12. Because 5 – 57 = –52 is a negative number, find a whole number x less than the modulus 12, so that –52  x mod 12. This means to find x so that is an integer. 22 Example 6 – Solution cont’d Evaluating the expression for whole number values of x less than 12, we have, when an integer. Thus (5 – 57) mod 12 = 8. Or (5- 57)mod 12 = -52 mod 12 -52 / 12 r. -4 , 12 – 4 =8 Therefore, if it is 5 o’clock now, 57 hours ago it was 8 o’clock. 23 Arithmetic Operations Modulo n Problems involving multiplication can also be performed modulo n. 24 Example 7 – Multiplication Modulo n Evaluate: (15  23) mod 11 Solution: Find the product 15  23 and then divide by the modulus,11. The answer is the remainder. The answer is 4. 25  CHAPTER 6.2 Mathematical Systems Copyright © Cengage Learning. All rights reserved.  6.2 Section Applications of Modular Arithmetic Copyright © Cengage Learning. All rights reserved. ISBN and UPC 3 ISBN and UPC Every book that is cataloged in the Library of Congress must have an ISBN (International Standard Book Number). This 13-digit number was created to help ensure that orders for books are filled accurately and that books are catalogued correctly. The first three digits of an ISBN are 978 (or 979), followed by 9 digits that are divided into three groups of various lengths. These indicate the country or region, the publisher, and the title of the book. The last digit (the 13th one) is called a check digit. 4 ISBN and UPC If we label the first digit of an ISBN d1, the second digit d2, and so on to the 13th digit d13, then the check digit is given by the following modular formula. It is this check digit that is used to ensure accuracy. 5 ISBN and UPC Suppose, however, that a bookstore clerk sends an order for the American Heritage Dictionary and inadvertently enters the number 978-0-395-28517-4, where the clerk transposed the 8 and 2 in the five numbers that identify the book. Correct ISBN: 978-0-395-82517-4 Incorrect ISBN: 978-0-395-28517-4 The receiving clerk calculates the check digit as 6. 6 ISBN and UPC Because the check digit is 6 and not 4 as it should be, the receiving clerk knows that an incorrect ISBN has been sent. Transposition errors are among the most frequent errors that occur. The ISBN coding system will catch most of them. 7 Example 1 – Determine a Check Digit for an ISBN Determine the ISBN check digit for the book The Equation that Couldn’t Be Solved by Mario Livio. The first 12 digits of the ISBN are 978-0-7432-5820-? Solution: The check digit is 3. 8 ISBN and UPC Another coding scheme that is closely related to the ISBN is the UPC (Universal Product Code). This number is placed on many items and is particularly useful in grocery stores. A check-out clerk passes the product by a scanner, which reads the number from a bar code and records the price on the cash register. If the price of an item changes for a promotional sale, the price is updated in the computer, thereby relieving a clerk of having to reprice each item. 9 ISBN and UPC In addition to pricing items, the UPC gives the store manager accurate information about inventory and the buying habits of the store’s customers. The UPC is a 12-digit number that satisfies a modular equation that is similar to the one for ISBNs. The last digit is the check digit. If we label the 12 digits of the UPC as d1, d2,... , d12, we can write a formula for the UPC check digit d12. 10 Example 2 – Determine the Check Digit of a UPC Find the check digit for the UPC of the Blu-ray Disc release of the film Jurassic World. The first 11 digits are 0-25192-21221-? Solution: The check digit is 5. 11 Credit Card Numbers 12 Credit Card Numbers Companies that issue credit cards also use modular arithmetic to determine whether a credit card number is valid. This is especially important in e-commerce, where credit card information is frequently sent over the Internet. The primary coding method is based on the Luhn algorithm, which uses mod 10 arithmetic. Credit card numbers are normally 13 to 16 digits long. The first one to six digits are used to identify the card issuer. 13 Credit Card Numbers The table below shows some of the identification prefixes used by four popular card issuers. 14 Credit Card Numbers The Luhn algorithm, used to determine whether a credit card number is valid, is calculated as follows: Beginning with the next-to-last digit (the last digit is the check digit) and reading from right to left, double every other digit. If a digit becomes a two-digit number after being doubled, treat the number as two individual digits. Now find the sum of the new list of digits; the final sum must be congruent to 0 mod 10. The Luhn algorithm is demonstrated in the next example. 15 Example 3 – Determine a Valid Credit Card Number Determine whether 5234 8213 3410 1298 is a valid credit card number. Solution: Highlight every other digit, beginning with the next-to-last digit and reading from right to left. Next double each of the highlighted digits. 16 Example 3 – Solution cont’d Finally, add all digits, treating two-digit numbers as two single digits. Because 60  0 mod 10, this is a valid credit card number. 17 Cryptology 18 Cryptology Related to codes on books and grocery items are secret codes. These codes are used to send messages between people, companies, or nations. It is hoped that by devising a code that is difficult to break, the sender can prevent the communication from being read if it is intercepted by an unauthorized person. Cryptology is the study of making and breaking secret codes. 19 Cryptology Before we discuss how messages are coded, we need to define a few terms. Plaintext is a message before it is coded. The line SHE WALKS IN BEAUTY LIKE THE NIGHT from Lord Byron’s poem “She Walks in Beauty” is in plaintext. Ciphertext is the message after it has been written in code. The line ODA SWHGO EJ XAWQPU HEGA PDA JECDP is the same line of the poem in ciphertext. 20 Cryptology The method of changing from plaintext to ciphertext is called encryption. The line from the poem was encrypted by substituting each letter in plaintext with the letter that is 22 letters after that letter in the alphabet. (Continue from the beginning when the end of the alphabet is reached.) This is called a cyclical coding scheme because each letter of the alphabet is shifted the same number of positions. 21 Cryptology The original alphabet and the substitute alphabet are shown below. To decrypt a message means to take the ciphertext message and write it in plaintext. 22 Cryptology If a cryptologist thinks a message has been encrypted using a cyclical substitution code like the one shown previously, the key to the code can be found by taking a word from the message (usually one of the longer words) and continuing the alphabet for each letter of the word. When a recognizable word appears, the key can be determined. 23 Example 4 – Write Messages Using Cyclical Coding Use the cyclical alphabetic encrypting code that shifts each letter 11 positions to a. code CATHERINE THE GREAT. b. decode TGLY ESP EPCCTMWP. Solution: a. The encrypting congruence is c  (p + 11) mod 26. Replace p by the numerical equivalent of each letter of plaintext and determine c. 24 Example 4 – Solution cont’d The results for CATHERINE are shown below. Continuing, the plaintext would be coded as NLESPCTYP ESP RCPLE. 25 Example 4 – Solution cont’d b. Because m = 11, n = 26 – 11 = 15. The ciphertext is decoded by using the congruence p  (c + 15) mod 26. The results for TGLY are shown below. Continuing, the ciphertext would be decoded as IVAN THE TERRIBLE. 26