第四章平面图与图的着色 4.1平面图 。定义4.1.1 若能把图G画在一个平面上，使任何两条边都 不相交，就称G可嵌入平面，或称G是可平面图 可平面图在平面的一个嵌入称为平面图. 。如果G是可平面图，那么它的任何导出子图也是 可平面图
第四章 平面图与图的着色 4.1 平面图 l 定义 4.1.1 若能把图G画在一个平面上，使任何两条边都 不相交,就称G可嵌入平面，或称G是可平面图. 可平面图在平面的一个嵌入称为平面图. l 如果G是可平面图,那么它的任何导出子图也是 可平面图
平面图 定义4.1.2 设G是一个平面图，由它的若干条边所构成的 一 个区域内如果不含任何结点及边，就称该区域 为G的一个面或域.包围这个域的诸边称为该域 的边界. 为了讨论方便，我们把平面图G外边的无限区域 称为无限域，其他的域都叫做内部域.如果两个 域有共同的边界，就说它们是相邻的，否则是 不相邻的.如果e不是割边，它一定是某两个域的 共同边界
平面图 l 定义 4.1.2 设G是一个平面图,由它的若干条边所构成的一 个区域内如果不含任何结点及边，就称该区域 为G的一个面或域.包围这个域的诸边称为该域 的边界. l 为了讨论方便,我们把平面图G外边的无限区域 称为无限域,其他的域都叫做内部域.如果两个 域有共同的边界，就说它们是相邻的,否则是 不相邻的.如果e不是割边,它一定是某两个域的 共同边界
平面图 。定理4.1.1 设G是平面连通图，则G的域的数目是 d=m-n+2. 证明：G是连通图，有支撑树T,它包含n-1条边， 不产生回路，因此对T来说只有一个无限域.由于 G是平面图，每加入一条余树边，它一定不与其 他边相交，也就是说一定是跨在某个域内部，把 该区域分成两部分.这样，加入G的m-n+1条余树 边，就生成了m-n+2个域
平面图 l 定理 4.1.1 设G是平面连通图,则G的域的数目是 d = m – n + 2. 证明:G是连通图,有支撑树T,它包含n-1条边， 不产生回路,因此对T来说只有一个无限域.由于 G是平面图,每加入一条余树边,它一定不与其 他边相交,也就是说一定是跨在某个域内部,把 该区域分成两部分.这样,加入G的m-n+1条余树 边,就生成了m-n+2个域
平面图 。推论4.1.1 若平面图G有k个连通支，则 n-m+d=k-1. 。推论4.1.2 对一般平面图G,恒有 n-m+d>=2
平面图 l 推论 4.1.1 若平面图G有k个连通支,则 n – m + d = k – 1. l 推论 4.1.2 对一般平面图G,恒有 n – m + d >= 2
平面图 。定理4.1.2 设平面连通图G没有割边，且每个域的边界数至 少是t,则 m<=t*(n-2)/(t-2) 证明：设G有d个区域，每个域的边界树至少是t, 且每条边都与两个不同的域相邻.因此td<=2m. 代入欧拉公式：(2m/t)>=m-n+2, 即，m<=t*(n-2)1(t-2)
平面图 l 定理 4.1.2 设平面连通图G没有割边,且每个域的边界数至 少是t,则 m <= t * (n - 2) / (t – 2) 证明:设G有d个区域,每个域的边界树至少是t, 且每条边都与两个不同的域相邻.因此td<=2m. 代入欧拉公式: (2m / t) >= m - n + 2, 即, m <= t * (n - 2) / (t – 2)