平面图与图着色
平面图与图着色
可平面图(Planar Graph) 如果图G能够被画在一个平面上且图中的任 意两条边都不相交，则图G被称为可平面 图
可平面图(Planar Graph) • 如果图G能够被画在一个平面上且图中的任 意两条边都不相交，则图G被称为可平面 图
Regions ·Exterior region 。Boundary of region
Regions • Exterior region • Boundary of region
The Euler Identity 。Theorem9.1 -If G is a connected plane graph of order n, size m and having r regions,then n-m+r =2
The Euler Identity • Theorem 9.1 – If G is a connected plane graph of order n, size m and having r regions, then n-m+r =2
Theorem 9.2 If G is a planar graph of order n>=3 and size m,then m <3n-6. 。Corollary9.3 Every planar graph contains a vertex of degree 5 or less. 。Corollary9.4 -K is nonplanar
Theorem 9.2 • If G is a planar graph of order n>=3 and size m, then m <= 3n-6. • Corollary 9.3 – Every planar graph contains a vertex of degree 5 or less. • Corollary 9.4 – K5 is nonplanar
Theorem 9.5 The graph K3.3 is nonplanar
Theorem 9.5 • The graph K3,3 is nonplanar
Kuratowski's theorem A graph G is planar if and only if G does not contain K5,K3.3,or a subdivision of K5 or K3.3 as a subgraph. -A graph G'is called a subdivision of a graph G if one or more vertices of degree 2 are inserted into one or more edges of G
Kuratowski’s theorem • A graph G is planar if and only if G does not contain K5 , K3,3 , or a subdivision of K5 or K3,3 as a subgraph. – A graph G’ is called a subdivision of a graph G if one or more vertices of degree 2 are inserted into one or more edges of G
Graph Coloring Dated back to 1852.Francis Guthrie ·→De Morgan→ Hamilton→Sylvester→Kempe→Heawood >Birkhoff→Heesch→Shimamoto→Appel Haken IBM 370-168 (June 1976)
Graph Coloring • Dated back to 1852, Francis Guthrie • De Morgan Hamilton Sylvester Kempe Heawood Birkhoff Heesch Shimamoto Appel & Haken & IBM 370-168 (June 1976)
Vertex Coloring Assignment of colors to the vertices of G, one color to each vertex,such that adjacent vertices are colored differently. Chromatic number,x(G) k-colorable;k-coloring;k-chromatic
Vertex Coloring • Assignment of colors to the vertices of G, one color to each vertex, such that adjacent vertices are colored differently. • Chromatic number, χ(G) • k-colorable; k-coloring; k-chromatic
The Four Color Theorem The chromatic number of every planar graph is at most 4
The Four Color Theorem • The chromatic number of every planar graph is at most 4