二部图与完全二部图讲述.pptVIP

二部图 二部图 完全二部图 * 二部图 定义 设无向图 G=V,E, 若能将V 划分成V1 和 V2 (V1?V2=V, V1?V2=?), 使得G中的每条边的两个端 点都一个属于V1, 另一个属于V2, 则称G为二部图, 记为V1,V2,E, 称V1和V2为互补顶点子集. 又若G是简单图, 且V1中每个顶点都与V2中每个 顶点相邻,则称G为完全二部图, 记为Kr,s, 其中r=|V1|, s=|V2|. 注意: n 阶零图为二部图. * 二部图的判别法 定理 无向图G=V,E是二部图当且仅当G中无奇圈 例 下述各图都是二部图 * 欧拉图 历史上的哥尼斯堡七桥问题是著名的图论问题。 问题是这样的： 18世纪的东普鲁士有个哥尼斯堡城， 在横贯全城的普雷格尔河两岸和两个岛之间架设了7座桥， 它们把河的两岸和两个岛连接起来（如图1）。 每逢假日， 城中居民进行环城游玩， 人们对此提出了一个“遍游”问题， 即能否有这样一种走法， 使得从某地出发通过且只通过每座桥一次后又回到原地呢？ * 我们将图1中的哥尼斯堡城的4块陆地部分分别标以A， B， Ｃ， D， 将陆地设想为图的结点， 而把桥画成相应的连接边， 这样图1可简化成图2。 于是七桥“遍游”问题等价于在图2中， 从某一结点出发找到一条回路， 通过它的每条边一次且仅一次， 并回到原来的结点。 * 定义 1 给定无孤立结点的图G， 若存在一条经过G中每边一次且仅一次的回路， 则该回路为欧拉回路。 具有欧拉回路的图称为欧拉图。 例如， 给出如图3所示的两个图， 容易看出， (a)是欧拉图， 而(b)不是欧拉图。 * 下图中， (a)图的每个结点的度数都为４， 所以它是欧拉图；(b)图不是欧拉图。 但我们继续考察(b)图可以发现， 该图中有一条路v2v3v4v5v2v1v5， 它经过(b)图中的每条边一次且仅一次， 我们把这样的路称为欧拉路。 定理 1 连通图G是欧拉图的充要条件是G的所有结点的度数都是偶数。 * 定义2 通过图G的每条边一次且仅一次的路称为图G的欧拉路。 对于欧拉路有下面的判定方法。 定理2 连通图G具有一条连接结点vi和vj的欧拉路当且仅当vi和vj是G中仅有的两个奇数度结点。 * 我国民间很早就流传一种“一笔画”游戏。 由定理1和定理2知， 有两种情况可以一笔画。 1) 如果图中所有结点是偶数度结点， 则可以任选一点作为始点一笔画完； 2) 如果图中只有两个奇度结点， 则可以选择其中一个奇度结点作为始点也可一笔画完。 * 【例】下图是一幢房子的平面图形， 前门进入一个客厅， 由客厅通向4个房间。 如果要求每扇门只能进出一次， 现在你由前门进去， 能否通过所有的门走遍所有的房间和客厅， 然后从后门走出。 * 解: 将4个房间和一个客厅及前门外和后门外作为结点， 若两结点有边相连就表示该两结点所表示的位置有一扇门相通。 由此得图 (b)。 由于图中有4个结点是奇度结点， 故由定理7.4.2知本题无解。 * 定理3 一个连通有向图具有（有向）欧拉回路的充要条件是图中每个结点的入度等于出度。 一个连通有向图具有有向欧拉路的充要条件是最多除两个结点外的每个结点的入度等于出度， 但在这两个结点中， 一个结点的入度比出度大1， 另一个结点的入度比出度少1。 类似于无向图的结论， 对有向图有以下结果。 * 平面图和平面嵌入 定义 如果能将图G除顶点外边不相交地画在平面上, 则称G是平面图. 这个画出的无边相交的图称作G的平面嵌入. 没有平面嵌入的图称作非平面图. 例如 下图中(1)~(4)是平面图, (2)是(1)的平面嵌入，(4)是(3)的平面嵌入. (5)是非平面图. 平面图和平面嵌入(续) 今后称一个图是平面图, 可以是指定义中的平面图, 又可以是指平面嵌入, 视当时的情况而定. 当讨论的问题与图的画法有关时, 是指平面嵌入. K5和K3,3是非平面图 设G ??G, 若G为平面图, 则G ?也是 平面图; 若G ?为非平面图, 则G也 是非平面图. Kn(n?5), K3,n(n?3)都是非平面图. 平行边与环不影响图的平面性. K5 K3,3 平面图的面与次数 设G是一个平面嵌入 G的面: 由G的边将平面划分成的每一个区域 无限面(外部面): 面积无限的面, 用R0表示 有限面(内部面): 面积有限的面, 用R1, R2,…, Rk表示 面Ri的边界: 包围Ri的所有边构成的回路组 面Ri的次数: Ri边界的长度，用de