南京大学：《计算机问题求解》课程教学资源（课件讲稿）平面图与图着色

平面图与图着色

平面图与图着色

可平面图(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