〔离散数学〕第7章图论–第5节.ppt

补充：二部图 二部图：G=V,E是图，图G的两个结点子集V1，V2，满足V=V1∪V2, V1 ∩V2= Φ，且图G的每一条边e均具有e∈(vi,vj)，其中vi ∈V1, vj ∈V2。 补充：二部图 K3,3 7-5 平面图 在现实生活中，常常要画一些图形，希望边与边之间尽量减少相交的情况，例如印刷线路板的布线，交通道的设计等，近些年来，大规模集成电路的发展，进一步促进了图的平面性的研究。本节将简要地介绍平面图的概念，欧拉公式和平面图的着色。 平面图问题：在一块地上盖有三座房子，并且挖了三口井供房主人使用。 由于土质和气候等关系，这些井中的这一个或那一个常常干枯。因此各座房子的主人有时要到这个井去打水，有时要到那个井去打水，三个井都可能需要去。 不久，这三个房子的主人相互间变成了冤家，于是决定修建各家通往三个井的小道，使得他们在去三个井的途中不会相遇。 请问：你能否帮他们设计整个的小道路线，满足他们的要求？ 对于许多问题，一个图怎样画出来无关紧要，只要与原来的图同构怎样画都可以。 但是有些时候的实际问题要求我们在平面上完成该图，使得不是节点的地方不能有边相交出现。例如单层印刷电路板，集成电路的布线，通讯和交通中的某些问题等，这就是可平面图问题。 制印刷电路板必须把电路除结点外导线不相交的印制在线路板上。 虽然交通立交桥、多层电路板已广泛出现在现实生活中，但可平面图问题仍然是其最基本的问题。 7-5 平面图 平面图 知识点： 平面图,面, 欧拉公式 Kuratowski定理 本章中的图均指无向图 平面图的定义 定义7-5.1 设G＝〈V，E〉是一个无向图，如果能够把G的所有结点和边画在平面上，且使任何两条边除了端点外没有其它的交点，就称G是一个平面图。 非连通图可以对连通分支分别讨论。 注意，有些图形从表面上看有几条边是相交的，但不能就此肯定它不是平面图。 平面图的例 K1(平凡图)，K2，K3，K4都是平面图 判别平面图的直观方法-观察法。 （1）找出长度尽可能大的且边不相交的圈 C＝v1…v2…v3…v4…v1 是G中的任何圈。 （2）找出交叉的边，设P1＝v1v3和P2＝v2v4是G中的任意两条无公共结点的边。交叉出现在边P1和P2上。 对P1和P2的放置有4种方法， （1） P1和P2或者都在圈C内部，或者都在圈C外部时，它们才会相交叉。 （2） P1和P2分别放置在圈的内部或外部，从而避免交叉。 只有避免不了交叉时，这种图才是非平面图。 例K5－e (K5删除任意一条边)是平面图 平面图的例 K3,3-e是平面图吗？ 非平面图的例 完全图K5和完全二部图K3,3都不是平面图 非平面图的例 完全二部图K3,3 非平面图的例 完全二部图K3,3 平面图的简单性质 若图G是平面图，则G的任何子图都是平面图。 若图G是非平面图，则G的任何母图也都是非平面图。 Kn(n≥5)和K3,n(n≥3)都是非平面图。 设G是平面图，则在G中加平行边或环后所得图还是平面图。 平行边与自回路不影响图的平面性，因此研究图的平面性时，不考虑平行边和环。 平面图面、边界、次数的定义 定义7-5.2 面：设G是一个连通平面图，由图中的边所包围的区域，在区域内既不包含图的结点，也不包含图的边，这样的区域称为图G的一个面，记为r。 边界：包围该面的所有边所构成的回路称为这个面的边界。 次数：边界（即回路）的长度称为该面的次数，即回路中边的条数，面r的次数记为deg(r)。 环的次数=1。 内部面：区域面积有限的面称为有限面（或内部面）。 外部面：区域面积无限的面称为无限面（或外部面）。 显然，平面图有且仅有一个无限面。 例 求面的次数 平面图的握手定理 定理7-5.1 一个有限平面图，面的次数之和等于其边数的两倍。 即： 证明：任取e∈E(G)。 ①若e为面ri和rj(i≠j)的公共边界上的边时，在计算ri和rj的次数时，e各提供1。 ②若e只在某一个面的边界上出现时，则在计算该面的次数时，e提供2。 于是每条边在计算总次数时，都提供2，因而 考察下图所示平面图的面、边界和次数。 补充定理 定理 设G是n(n≥3)阶简单连通平面图，则G的每个面的次数大于等于3。 证明：因为G的任意一个面上至少有3个结点，所以G的每个面的次数都大于等于3。 欧拉定理 定理7-5.2 欧拉定理： 设G是连通平面图，则 v-e+r=2（欧拉公式） 其中v是G结点数，e是G边数，r是G的面数。 例1 ： 在下图中验证欧拉公式 v=7，e=11，r=6： 7-11+6=2。 欧拉定理证明v-e+r=2 证明：归纳法 ⑴若G为一个孤立结点，则v＝1，e＝0，r＝1，故v-e+r＝2成