Chapter 8c. Planar Graphs & Graph Coloring PDF

CHAPTER 8c. The Mathematics of Graph– Planar Graphs & Graph Coloring Core Idea “Mathematics creates connections and fosters efficiency through visual tools like graphs and algorithms.” learning objective...

CHAPTER 8c. The Mathematics of Graph– Planar Graphs & Graph Coloring Core Idea “Mathematics creates connections and fosters efficiency through visual tools like graphs and algorithms.” learning objectives 1. define a planar graph; 2. draw the planar drawing of a graph; 3. illustrate different colorable graph; 4. find the chromatic number of a graph; and 5. solve problems involving colorable graphs. challenge… Three Utilities Problem (A Puzzle on Planarity) 1 2 3 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? challenge… Three Utilities Problem (A Puzzle on Planarity) 1 2 3 Attempt: challenge… Three Utilities Problem (A Puzzle on Planarity) 1 2 3 Attempt: PLANARITY Planar Graph A planar graph is a graph that can be drawn so that no edges intersect each other except at vertices. Moreover, a graph is planar if it has a planar drawing. Example: planar planar planar ? PLANARITY Planar Graph A planar graph is a graph that can be drawn so that no edges intersect each other except at vertices. Moreover, a graph is planar if it has a planar drawing. Example: Is the graph below planar? planar graph planar drawing/embedding PLANARITY Example: Is the graph below planar? not planar PLANARITY Example: Is the graph below planar? not planar PLANARITY (Example 1, Page 260) Example: Is the graph below planar? planar PLANARITY (Example 1, Page 260) Example: Is the graph below planar? PLANARITY (Example 1, Page 260) Example: Is the graph below planar? PLANARITY (Check your progress 1, Page 260) Example: Show that the graph is planar. planar PLANARITY (Check your progress 1, Page 260) Example: Show that the graph is planar. challenge… Coloring Maps 272.) GRAPH COLORING In graph theory, it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. By planar duality (vertices are faces of a graph), it became coloring the vertices, and in this form, it generalizes to all graphs. GRAPH COLORING Consider Figure 6.21 & 6.22 (Pg 269). Represent each country by a vertex. If two countries are neighbors (share a common boundary) connect the vertices with an edge. Countries that just touch at just a corner point will not be considered neighbors. Figure 6.21 Figure 6.22 GRAPH COLORING The resulting graph will always be planar because the edges only connect neighboring countries. How many colors will be required? Figure 6.23 Figure 6.24 Figure 6.25 GRAPH COLORING Four-Color Theorem Every planar graph is 4-colorable. (Example 1, Page 270) The fictional map below shows the boundaries of countries on 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. GRAPH COLORING Four-Color Theorem Every planar graph is 4-colorable. (Example 1, Page 270) The fictional map below shows the boundaries of countries on 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. GRAPH COLORING Four-Color Theorem Every planar graph is 4-colorable. (Example 1, Page 270) The fictional map below shows the boundaries of countries on 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. GRAPH COLORING Four-Color Theorem Every planar graph is 4-colorable. (Example 1, Page 270)  The four-color theorem guarantees that we need only four colors to color a planar graph. Nonplanar graph may need more than four colors. CHROMATIC NUMBER OF A GRAPH It is the minimum number of colors needed to color a graph so that no edge connects vertices of the same color. In general, there is no efficient method of finding the chromatics number of a graph. CHROMATIC NUMBER OF A GRAPH Is this map 2-colorable? APPLICATIONS OF GRAPH COLORING (Example 3, Page 273) Eight students clubs need to hold meetings on the same day, but some students belong to more than one club. In order to avoid members missing meeting, the meetings need to be scheduled during different time slots, An “x” in the table below indicates that two corresponding clubs share at least one member. Use graph coloring to determine the minimum no. of time slots necessary to ensure that all club members can attend all meetings. APPLICATIONS OF GRAPH COLORING (Example 3, Page 273) APPLICATIONS OF GRAPH COLORING (Solution for Example 3, Page 273) SC Conclusion: CR SG First Time Slot: SC, DC, SN Second Time Slot: SG, CO CD DC Third Time Slot: HS, CD, CR CO HS SN Each color correspond to a time slot. End of Discussion…