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