56平面图

第五章图论5.6平面图5.6.1平面图的概念例考虑把三座房和三种设施每种都连接起来的问题，如图7-64所示，是否有可能使得这样的连接里不发生交叉？这个问题可以用完全偶图K3,3来建模。原来的问题可以重新叙述为：能否在平面里画出K3,3，使得没有两条边发生交叉？印刷线路板的设计问题定义1图的平面表示：图的一种图形表示（画法），其中边仅在顶点处相交平面图：有平面表示的图例1判断下面的三个图是否为平面性的。（接下页）解：K4是平面性的，因为可以不带交叉地画出它（图7-66所示）；Q3是平面性的（图7-68所示）；在平面里画出K3,3而没有边交叉，任何这样的尝试都注定是失败的。在K3,3的任何平面表示里，顶点v1和v2都必须同时与v4和v5连接。这四条边所形成的封闭曲线把平面分割成两个区域R1和R2，如图7-70a）所示。顶点v3属于R1或R2。当v3属于闭曲线的内部R2时，在v3和v4之间以及在v3和v5之间的边，把R2分割成两个区域R21和R22，如图7-70b）所示。定义在平面图的一个平面表示中，边把平面划分成若干区域面R：内部不含图的边或顶点的、由边所包围的区域面的边界：包围面的最短的回路面的度deg(R)：边界的长度有限面：面积有限的面，无限面：面积无限的面例右面的平面图有3个面，R1和R2是有限面，R3是无限面R1的边界：1231，R2的边界：2342，R3的边界：1245431deg(R1)=3，deg(R2)=3，deg(R3)=6R3的边界不是12431，因为12431所包围的区域含有边，不能构成面R2的边界不是234542，因为234542不是包围R2的最短的回路定义设平图G=(V，E)有r个面，n个顶点，m条边，称用如下的方法构造出来的图G*=(V*，E*)为G的对偶图：(1)在G的任意一个面Ri中取一个点作为G*的一个顶点Vi*，令V*={V1*，V2*，…，Vr*}。(2)对G的任意一条边ek，若ek出现在G的两个不同的面Ri和Rj(ij)的边界中,则构作G*的边={Vi*，Vj*}；若ek仅出现在G的某一个面Ri的边界中,则构作G*的边(环)ek*={Vi*，Vi*}；令E*={e1*，e2*，…，em*}。例在G的无限面内，仅有G*的一个顶点v4*，过v4*有G*的一个环若平面图G=(V，E)有n个顶点，m条边，r个面，则其对偶图G*=(V*，E*)（１）有r个顶点，m条边（２）是平面图（３）是连通图（４）对于G的任意一个面R及R所对应的G*的顶点V*，deg(R)=d(V*)定理平面图的面的度数之和等于其边的数目的两倍。证明：设可平面图G=(V，E)，其对偶图G*=(V*,E*)，则==2|E*|(由握手定理)=2|E|的面是GRdeg(R)**)(*Vvvd5.6.2欧拉公式定理1欧拉公式连通平面图，r=e-v+2。证明：直观描述首先规定G的平面表示。将要这样证明定理：构造一系列子图G1，G2，…，Ge=G，相继地在每个阶段上添加一条边。用下面的归纳定义来这样做。任意地选择一条G的边来获得G1。从Gn-1这样获得Gn：任意地添加一条与Gn-1里顶点相关联的边，若与这条边关联的另一个顶点还不在Gn-1里，则添加这个顶点。这样的构造是可能的，因为G是连通的。在添加e条边之后就获得G。设rn，en和vn分别表示G的平面表示所诱导出的Gn的平面表示的区域数、边数和顶点数。现在通过归纳来进行证明。对G1来说关系r1=e1-v1+2为真。(接下页)现在假定rn=en-vn+2。设｛an+1，bn+1｝是为了获得Gn+1而添加到Gn里的边。有两种情形需要考虑。在第一种情形里，an+1和bn+1都已经在Gn里了。这两个顶点必然是在一个公共区域R的边界上，否则就不可能把边｛an+1，bn+1｝添加到Gn里而没有两条边交叉（并且Gn+1是平面性的。）这条新边的添加把R分割成两个区域。所以，在这种情形里，rn+1=rn+1,en+1=en+1，而且vn+1=vn+1。因此，联系着区域数、边数、顶点数的公式两边都恰好增加一，所以这个公式仍然为真。在图7-73a）里说明这种情形。在第二种情形里，新边的两个顶点之一已不在Gn里。假定an+1在Gn里但是bn+1不在Gn里。添加这条新边不产生任何新的区域，因为bn+1必然是在边界上有an+1的一个区域里。所以，rn+1=rn,，另外en+1=en+1，而且vn+1=vn+1。联系着区域数、边数、顶点数的公式两边都保持相等，所以这个公式仍然为真。在图7-73b）里说明这种情形。已经完成了归纳论证。因此对所有n来说都有rn=en-vn+2。因为原图是在添加了e条边之后所获得的图Gn，所以这个定理为真。(见下页图)例4假设连通图平面性简单图有20个顶点，每个顶点的度都是3。这个平面性图的平面表示把平面分割成多少个区域？解这个图有20个顶点，每个顶点的度都是3，所以v=20。因为这些顶点的度之和3v=3*20=60是等于边数的两倍2e，所以有2e=60，即e=30。所以，根据欧拉公式，区域数是：r=e-v+2=30-20+2=12推论1简单连通平面图,v≥3，则e≤3v-6证明：①deg(R)=2e②简单图中，deg(R)≥3r画在平面里的连通平面性简单图把平面分割成区域，比如说r个区域，每个区域的度数至少为3（简单图）。特别是，注意无界区域的度数至少为3，因为在图中至少有3个顶点。注意个区域的度数之和恰好是图中边数的两倍，因为每条边都在区域的边界上出现两次（或者在两个不同区域里，或者两次在相同的区域里）。因为每个区域都有大于等于3的度数，所以2e=deg(R)≥3r因此(2/3)e≥r利用欧拉公式r=e-v+2，就得到(2/3)e≥e-v+2所以得到v-2≥e/3。这样就证明了e≤3v-6。例5证明K5不是平面图证明：图K5有5个顶点和10条边。不过，对这个图来说，不满足不等式e≤3v-6，因为e=10和3v-6=9。因此，K5不是平面图。推论2简单连通平面图,v≥3，没有长度为3的回路，则e≤2v-4证明：①deg(R)=2e②deg(R)≥4推论2的证明类似于推论1的证明，不同之处在于，在这种情形里，没有长度为3的回路的事实蕴含着区域的度数至少为4。(接下页)画在平面里的连通平面性简单图把平面分割成区域，比如说r个区域，每个区域的度数至少为3（简单图）。又因为没有长度为3的回路，所以每个区域的度数至少为4。每个区域的度数之和恰好是图中边数的两倍，因为每条边都在区域的边界上出现两次。因为每个区域都有大于等于4的度数，所以2e=deg(R)≥4r因此e≥2r利用欧拉公式r=e-v+2，就得到e≥2e-2v+4这样就证明了e≤2v-4。例6证明K3,3不是平面图证明：因为K3,3没有长度为3的回路（因为它是偶图），所以可以使用推论2。K3,3有6个顶点和9条边。因为e=9和2v-4=8，所以推论2证明K3,3不是平面图。5.6.3库拉图斯基定理定义初等细分：在边上插入顶点收缩：合并顶点图同胚：能通过初等细分或（和）收缩转换例(2)是的(1)初等细分，(4)是(3)的收缩定理2库拉图斯基定理图是非平面图同胚于K3,3或K5的子图。证明：显然，一个包含着同胚于K3,3或K5的子图是非平面性的。不过，相反的命题——即每个非平面性图都包含一个同胚于K3,3或K5的子图的子图——的证明是复杂的，因而不在这里给出。例7确定图7-76中所示的图是否为平面性的。解：G有同胚于K5的子图H。H是这样获得的：删除h，j和k以及所有与这些顶点关联的边。H是同胚于K5的，因为从K5（带有顶点a,b,c,g和i）通过一系列初等细分，添加顶点d,e和f就可以获得H。因此，G是非平面性的习题1.假定一个平面性图有k个连通分支、e条边和v个顶点。另外假设这个图的平面表示把平面分割成r个区域。求用e，v，k所表示的r的公式。2.用库拉图斯基定理来确定下面所给的图是否为平面性的。3.证明：若G是一个带有v个顶点和e条边的连通简单图，则G的厚度至少为e/(3v-6)。