《Discrete Mathematics II教学-华南理工》Review.pptVIP

Theorem 2: (Kuratowski’s Theorem) A graph is nonplanar if and only if it contains a subgraph homeomorphic to K3,3 or K5. Kuratowski’s Theorem Definition Let G be a planar simple graph. Each region of the graph G is represented by a vertex. Edge connects two vertices if the regions represented by these vertices have a common border. The resulting graph G* is called the dual graph of the graph G. The problem of coloring the regions of a map is equivalent to the problem of coloring the vertices of the dual graph. Dual graph Definition 1: A coloring of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color. Definition 2: The chromatic number of a graph is the least number of colors needed for a coloring of this graph. Coloring of a simple graph and chromatic number Theorem: (The Four Color Theorem) The chromatic number of a planar graph is no greater than four. The Four Color Theorem was originally posed as a conjecture in the 1850s. It was finally proved by the American Mathematicians in 1976. The four color theorem Note: The four color theorem applies only to planar graphs. Nonplanar graphs can have arbitrary large chromatic numbers. The four color theorem What is the chromatic number of Kn? Solution The chromatic number of Kn is n since every two vertices of this graph are adjacent. Example Graph Coloring Theorems A graph is 2-colorable iff there are no odd cycles. Complete graph Kn requires n colors If the maximum degree is dmax , then the graph can be colored with (dmax + 1) colors All planar graphs can be colored with 4 colors Example Junior students at Department of Computer Science in SCUT are required to take 6 major elective course in this semester. Let Ci, i=1,2, …, 6 denote the course number and S(Ci) be the students enrolled in course Ci , suppose that, S(Ci)?S(C6) ? ?, i=1, 2, …, 5， S(Ci)?S(Ci+1) ? ?, i=1, 2, 3, 4，