4.1平面图-Read.pptVIP

图 论 第四章 平面图与图的着色 4.1 平面图 1. 某些实际问题中涉及到图的平面性的研究，譬如印刷电路板的设计、大规模集成电路的布局布线等问题。 定义：若能把图G 改画在一个平面上(同构)，使新图G’的任何两条边都不相交，就称G可嵌入平面、是可平面图，称G’是G的一个平面嵌入，G’是一个平面图。 平面图的域(面) 内部域、无限域 一个域的边界 2. 欧拉公式 定理：设G是平面连通图，则G的域的个数为 d=m-n+2 . (域数=边数－结点数+2) 证：因Ｇ为连通图，故有支撑树Ｔ。 　　对于T，仅有一个域(n-1条边)。每新加入Ｇ－T的一条边，域即恰好增加一个。这样的边共m-(n-1)条，故最终得到Ｇ时域数为m-n+2. 推论1　若平面图Ｇ有k个连通分支，则 d=m-n+k+1. 证：将k个连通分支由左到右顺序排列，相邻两分支间加入一条新边相联(共加入k-1边)，则所得新图与原图域数相同。 　应用欧拉公式有 d=(m+k-1)-n+2=m-n+k+1. 　推论2　对平面图Ｇ，有 n-m+d≥2. 证：由推论１立得。 4.2 极大平面图 1. 定义：设G是结点数n≥3的简单平面图，若在任意两个不相邻结点vi,vj之间，加入边(vi,vj)就会破坏图的平面性，则称G为一个极大平面图。 极大平面图的边数和域数在图的现有结点数的限制下已达到了极限，再多一条边即会破坏其平面性。 2. 极大平面图的性质 1）G是连通的 2）G不存在割边 3）G的每个域的边界数都是3。 证:由于简单图不存在自环与重边(边界数为1,2的域)，故域的边界数≥3。若边界数3，则在此域中至少可加一条边，而不会破坏其平面性,矛盾。 4) 3d=2m (d为域数, m为边数) 证：d个域的边界数之和为3d(每域有3条边)。 由于极大平面图没有割边，故每条边均是两个域的边。求边界数总和时每条边均恰好计数了两次，故边界数之和为边数的两倍，即2m，从而 3d=2m 。 定理 极大平面图G的边数和域数完全由结点数决定。具体有 m=3n-6，d=2n-4。 证：对G有3d=2m, 代入欧拉公式d=m-n+2 ，即证。 3. 简单平面图的一个必要条件 定理 若简单图G为一个平面图，则必有： m≤3n-6，d≤2n-4. 证：d个域的边界数之和≥3d(每域至少有3条边)。 求边界数总和时，每条非割边恰好计数了两次，每条割边只计数了一次，故边界数之和不超过边数的两倍，即≤2m，从而 3d≤2m 。代入欧拉公式d=m-n+2 ，即证。 证明一个简单图为非平面的，可通过证明它不满足平面图的必要条件来实现。这可以用Euler公式或以上定理验证。但域数有时难以确定，故常用验证m≤3n-6不成立来证明 。 例1 某个简单平面图边数为12, 结点数为6, 则每个域的边界数为3。 证：域数d=12-6+2=8。 因为简单平面图每个域的边界数至少为3，若至少有一个域的边界数超过3，则 各域的边界数之和3*8=24。 由于求边界数总和时，每条边最多计数两次，故边界数之和不超过边数的两倍，即≤2*12，从而 2424，矛盾。 故每个域的边界数不会超过3，即恰好等于3。 例2 若简单平面图G中不含有K3子图，则边数m≤2n-4。 证明:G不含K3子图(三角形子图)，故不含边界数为3的域，因此每个域的边界数至少为4，从而各域的边界数之和≥4d。 另一方面，由于每条边最多计数两次，故边界数之和不超过边数的两倍，即≤2m，所以 4d≤2m. 将d=m-n+2代入不等式，即可证得 m≤2n-4 . 例3 简单平面图G中存在度数小于6的结点。 证明：若每个点的度数不小于6，则所有结点的度数之和≥6n. 由于所有结点的度数之和为边数的2倍，所以 2m≥6n， 故m≥3n。 这与简单平面图满足的性质m≤3n-6相矛盾，故G中必有度数小于6的结点。 例4 若简单平面图G中的结点数n≤11,则其中一定存在度数5的结点。 证：假设每个结点的度数≥5，则所有结点的度数之和≥5n。 由于所有结点的度数之和为边数的2倍，所以 2m≥5n， 故m≥5n/2。 另一方面，对于简单平面图有m≤3n-6，故5n/2≤3n-6 ，由此可得n≥12，这与题设矛盾。 4.3 非平面图 1. 定义：如果一个