《Discrete Mathematics II教学-华南理工》Part 2-TopicsInGraphTheory.pptVIP

Series reduction A series reduction consists of deleting the vertex v ? V(G) and replacing the edges (v,v1) and (v,v2) by the edge (v1,v2) The new graph G’ has one vertex and one edge less than G and is said to be obtained from G by series reduction Homeomorphic graphs Two graphs G and G’ are said to be homeomorphic if G’ is obtained from G by a sequence of series reductions. By convention, G is said to be obtainable from itself by a series reduction, i.e. G is homeomorphic to itself. Homeomorphic graphs Define a relation R on graphs: GRG’ if G and G’ are homeomorphic. R is an equivalence relation on the set of all graphs. 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 The Petersen graph ,shown in Figure (a), is noplanar. The subgraph H of the Petersen shown in Figure (b) obtained by deleting 3 and the three edges that have 3 as an endpoint,is homeomorphic to K3,3. Hence, the Petersen graph is nonplanar. 6 4 5 7 8 1 2 9 10 6 4 7 2 9 10 (a)The Petersen graph (b)The subgraph H of the Petersen graph (c)K3,3 Example Five Color Theorem Any planar graph can be colored using no more than five colors. Proof: A fact: any planar graph has at least one vertex of degree less than 5. v1 v5 v4 v3 v2 v 五色定理证明 对结点数n归纳。假定n个结点的平面图可5着色。当G有n个结点时，必有一个结点v其度数6. 不妨设 dev(v)=5, 其邻接点是v1,…,v5. 至少有两个结点不相邻，否则G包含K5, 是非平面图。设v1,v3不相邻，将v1,v3”拉至v”与v合并，其结点数n, 故可5 着色。现在将v1,v3”从中拉出”，v1,v3着色不变，此时v1,v2,…,v5着4种颜色，故v可着第五种颜色。 v1 v5 v4 v3 v2 v Chromatic Polynomials ?(G) is the smallest number of colors needed to produce a proper coloring of G. Computing the total number of different coloring of a graph. If G is a graph and n ? 0 is an integer, let PG(n) be the number of ways to color G using n or fewer colors, PG(n) is polynomial in n. PG: a function called the chromatic polynomial. 8.6 Coloring Graphs Ex. x colors for L4. 1st vertex: colored with any of x colors; 2nd vertex: colored with any o