图论III 几种特殊的图

1、1第二课第二课 几种几种特殊的图特殊的图 2.1 二部图二部图2.2 欧拉图欧拉图2.3 哈密顿图哈密顿图2.4 平面图平面图 22.1 二部图二部图 二部图二部图完全二部图完全二部图3二部图二部图 定义定义 设无向图设无向图 G=, 若能将若能将V 划分成划分成V1 和和 V2 (V1 V2=V, V1 V2=), 使得使得G中的每条边的两个端中的每条边的两个端点都一个属于点都一个属于V1, 另一个属于另一个属于V2, 则称则称G为为二部图二部图, 记为记为, 称称V1和和V2为为互补顶点子集互补顶点子集. 又若又若G是简单图是简单图, 且且V1中每个顶点都与中每个顶点都与V2中每个顶点相邻

2、中每个顶点相邻,则称则称G为为完全二部图完全二部图, 记为记为Kr,s, 其中其中r=|V1|, s=|V2|. 注意注意: n 阶零图为二部图阶零图为二部图. 4二部图二部图( (续续) ) 例例 下述各图是否是二部图下述各图是否是二部图? ? 定理定理 无向图无向图G=是二部图当且仅当是二部图当且仅当G中无奇圈中无奇圈 不是不是52.2 欧拉图欧拉图欧拉路与欧拉回路欧拉路与欧拉回路存在欧拉路和欧拉回路的充分必要条件存在欧拉路和欧拉回路的充分必要条件 6哥尼斯堡七桥问题哥尼斯堡七桥问题 要求找一条路线要求找一条路线,经过每座桥一次且经过每座桥一次且仅一次仅一次7欧拉图欧拉图 欧拉路欧拉路:

3、图中经过每个顶点且恰好经过每条边一次图中经过每个顶点且恰好经过每条边一次的路的路. 欧拉回路欧拉回路: 图中经过每个顶点恰好经过每条边一次图中经过每个顶点恰好经过每条边一次的回路的回路.欧拉图欧拉图: 有欧拉回路的图有欧拉回路的图.半欧拉图半欧拉图: 有欧拉路有欧拉路,但无欧拉回路的图但无欧拉回路的图.几点说明：上述定义对无向图和有向图都适用几点说明：上述定义对无向图和有向图都适用.规定平凡图为欧拉图规定平凡图为欧拉图.欧拉路是迹欧拉路是迹, 欧拉回路是闭迹欧拉回路是闭迹.环不影响图的欧拉性环不影响图的欧拉性. 8欧拉图实例欧拉图实例例例 是否是欧拉图或半欧拉图是否是欧拉图或半欧拉图?欧拉图欧

4、拉图欧拉图欧拉图半欧拉图半欧拉图半欧拉图半欧拉图不是不是不是不是9欧拉图的判别法欧拉图的判别法 定理定理 无向图无向图G为欧拉图当且仅当为欧拉图当且仅当G连通且无奇度顶连通且无奇度顶点点. G是半欧拉图当且仅当是半欧拉图当且仅当G连通且恰有两个奇度顶连通且恰有两个奇度顶点点. 定理定理 有向图有向图D是欧拉图当且仅当是欧拉图当且仅当D连通且每个顶点连通且每个顶点的入度都等于出度的入度都等于出度. D是半欧拉图当且仅当是半欧拉图当且仅当D连通且连通且恰有两个奇度顶点恰有两个奇度顶点, 其中一个入度比出度大其中一个入度比出度大1, 另一个另一个出度比入度大出度比入度大1, 其余顶点的入度等于出度其

5、余顶点的入度等于出度.10实例实例例例1 哥尼斯堡七桥问题哥尼斯堡七桥问题 4个奇度顶点个奇度顶点, 不存在不存在 欧拉路欧拉路, 更不存在更不存在 欧拉回路欧拉回路,例例2 下面两个图都是欧拉图下面两个图都是欧拉图. 从从A点出发点出发, 如何一次成功地走出一条欧拉回路来？如何一次成功地走出一条欧拉回路来？ 112.3 哈密顿图哈密顿图 哈密顿路和哈密顿回路哈密顿路和哈密顿回路存在哈密顿路和哈密顿回路的充分条件与必要条存在哈密顿路和哈密顿回路的充分条件与必要条件件12哈密顿周游世界问题哈密顿周游世界问题每个顶点是一个城市每个顶点是一个城市, , 有有20个城市个城市, , 要求从一个要求从一

6、个城市出发城市出发, , 恰好经过每一个城市一次恰好经过每一个城市一次, , 回到出发回到出发点点. .13哈密顿图的定义哈密顿图的定义哈密顿路哈密顿路: : 经过图中所有顶点一次且仅一次的路经过图中所有顶点一次且仅一次的路. .哈密顿回路哈密顿回路: : 经过图中所有顶点一次且仅一次的回路经过图中所有顶点一次且仅一次的回路. .哈密顿图哈密顿图: : 具有哈密顿回路的图具有哈密顿回路的图. .半哈密顿图半哈密顿图: : 具有哈密顿路而无哈密顿回路的图具有哈密顿路而无哈密顿回路的图. . 几点说明：几点说明：平凡图是哈密顿图平凡图是哈密顿图. .哈密顿路是通路，哈密顿回路是圈哈密顿路是通路，哈

7、密顿回路是圈. .环不影响图的哈密顿性，对环不影响图的哈密顿性，对3 3阶以上图，平行边也不影响图阶以上图，平行边也不影响图的哈密顿性的哈密顿性. .14实例实例例例 是否是哈密顿图是否是哈密顿图,半哈密顿图半哈密顿图?哈密顿图哈密顿图哈密顿图哈密顿图半哈密顿图半哈密顿图*不是不是*15无向哈密顿图的一个必要条件无向哈密顿图的一个必要条件 定理定理 设无向图设无向图G=是哈密顿图是哈密顿图, 则对于任意则对于任意V1 V且且V1, 均有均有 p(G V1) |V1|.证证 设设C为为G中一条哈密顿回路中一条哈密顿回路, 有有p(C V1) |V1|. 又因为又因为C G, 故故 p(G V1)

8、 p(C V1) |V1|. 几点说明几点说明定理中的条件是哈密顿图的必要条件定理中的条件是哈密顿图的必要条件, 但不是充分条件但不是充分条件.可利用该定理判断某些图不是哈密顿图可利用该定理判断某些图不是哈密顿图. 由定理可知由定理可知, Kr,s当当s r时不是哈密顿图时不是哈密顿图. 当当r 2时时, Kr,r是哈密顿图是哈密顿图, 而而Kr,r+1是半哈密顿图是半哈密顿图. 16实例实例例例 设设G为为n阶无向连通简单图阶无向连通简单图, 若若G中有割点或桥中有割点或桥, 则则G不是哈密顿图不是哈密顿图.证证 (1) 设设v为割点为割点, 则则p(G v) 2|v|=1. 根据定理根据定

9、理, G不是哈密顿图不是哈密顿图.(2) 若若G是是K2(K2有桥有桥), 它显然不是哈密顿图它显然不是哈密顿图. 除除K2外外, 其他的有桥连通图均有割点其他的有桥连通图均有割点. 由由(1), 得证得证G不是不是哈密顿图哈密顿图.17无向哈密顿图的一个充分条件无向哈密顿图的一个充分条件 定理定理 设设G是是n阶无向简单图阶无向简单图, 若任意两个不相邻的若任意两个不相邻的顶点的度数之和大于等于顶点的度数之和大于等于n 1, 则则G中存在哈密顿通中存在哈密顿通路路. 当当n 3时时, 若任意两个不相邻的顶点的度数之和若任意两个不相邻的顶点的度数之和大于等于大于等于n, 则则G中存在哈密顿回路

10、中存在哈密顿回路. 由定理由定理, 当当n 3时时, Kn均为哈密顿图均为哈密顿图.定理中的条件是充分条件定理中的条件是充分条件, 但不是必要条件但不是必要条件.例如例如, n( 5)个顶点的路径存在哈密顿路个顶点的路径存在哈密顿路, 但不满但不满足条件足条件. n( 5)个顶点的圈是哈密顿图个顶点的圈是哈密顿图, 不满足条件不满足条件.18判断是否是哈密顿图判断是否是哈密顿图的可行方法的可行方法n观察出一条哈密顿回路观察出一条哈密顿回路 例如例如 右图右图(周游世界问题周游世界问题)中红中红边给出一条哈密顿回路边给出一条哈密顿回路, 故它故它是哈密顿图是哈密顿图. n满足充分条件满足充分条件

11、例如例如 当当n 3时时, Kn中任何两个不同的顶点中任何两个不同的顶点 u,v, 均均有有d(u)+d(v) = 2(n 1) n, 所以所以Kn为哈密顿图为哈密顿图. 19应用实例应用实例例例 某次国际会议某次国际会议8人参加，已知每人至少与他人参加，已知每人至少与他4人人有共同语言，问服务员能否将他们安排在同一有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都能与两边的人交谈？张圆桌就座，使得每个人都能与两边的人交谈？解解 作无向图作无向图G=, 其中其中V=v|v为与会者为与会者， E=(u,v) | u,v V, u与与v有共同语言有共同语言, 且且u v. G为简单图

12、为简单图. 根据条件根据条件, v V, d(v) 4. 于是，于是， u,v V, 有有d(u)+d(v) 8. 由定理可知由定理可知G为哈密顿图为哈密顿图. 服务员在服务员在G中找一条哈密顿回路中找一条哈密顿回路C，按，按C中相邻关中相邻关系安排座位即可系安排座位即可. 202.4 平面图平面图 平面图与平面嵌入平面图与平面嵌入平面图的面平面图的面极大平面图与极小非平面图极大平面图与极小非平面图欧拉公式欧拉公式平面图的对偶图平面图的对偶图地图着色与四色定理地图着色与四色定理 21平面图和平面嵌入平面图和平面嵌入 定义定义 如果能将图如果能将图G除顶点外边不相交地画在平面上除顶点外边不相交地

13、画在平面上, 则称则称G是是平面图平面图. 这个画出的无边相交的图称作这个画出的无边相交的图称作G的的平面嵌入平面嵌入. 没有平面嵌入的图称作没有平面嵌入的图称作非平面图非平面图. 例如例如 下图中下图中(1)(4)是平面图是平面图, (2)是是(1)的平面嵌入，的平面嵌入，(4)是是(3)的平面嵌入的平面嵌入. (5)是非平面图是非平面图.22平面图和平面嵌入平面图和平面嵌入( (续续) )今后称一个图是平面图今后称一个图是平面图, 可以是指定义中的平面图可以是指定义中的平面图, 又可以又可以是指平面嵌入是指平面嵌入, 视当时的情况而定视当时的情况而定. 当讨论的问题与图的画当讨论的问题与图

14、的画法有关时法有关时, 是指平面嵌入是指平面嵌入. K5和和K3,3是非平面图是非平面图设设G G, 若若G为平面图为平面图, 则则G 也是也是 平面图平面图; 若若G 为非平面图为非平面图, 则则G也也 是非平面图是非平面图. Kn(n 5), Kn,m(n,m 3)都是非平面图都是非平面图. 平行边与环不影响图的平面性平行边与环不影响图的平面性. 23平面图的面与次数平面图的面与次数设设G是一个平面嵌入是一个平面嵌入G的面的面: 由由G的边将平面划分成的每一个区域的边将平面划分成的每一个区域无限面无限面(外部面外部面): 面积无限的面面积无限的面, 用用R0表示表示有限面有限面(内部面内部

15、面): 面积有限的面面积有限的面, 用用R1, R2, Rk表示表示 面面Ri的边界的边界: 包围包围Ri的所有边构成的回路（组）的所有边构成的回路（组）面面Ri的次数的次数: Ri边界的长度，用边界的长度，用deg(Ri)表示表示 定理定理 平面图各面的次数之和等于边数的平面图各面的次数之和等于边数的2倍倍.证证 每条边可能在两个面的公共边界上，也可能只在一个面每条边可能在两个面的公共边界上，也可能只在一个面的边界上的边界上. 前者前者, 在每个面的边界上这条边只出现一次在每个面的边界上这条边只出现一次, 计算计算两次两次. 后者后者, 它在这个面的边界上出现它在这个面的边界上出现2次次,

16、也计算两次也计算两次. 24平面图的面与次数平面图的面与次数( (续续) )例例1 右图有右图有4个面个面, deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8. 例例2 左边左边2个图是同一个平面个图是同一个平面图的平面嵌入图的平面嵌入. R1在在(1)中是中是外部面外部面, 在在(2)中是内部面中是内部面; R2在在(1)中是内部面中是内部面, 在在(2)中是中是外部面外部面. 其实其实, 在平面嵌入中在平面嵌入中可把任何面作为外部面可把任何面作为外部面.25极大平面图极大平面图 定义定义 若若G是简单平面图是简单平面图, 并且在任意两个不相邻的顶点之并且

17、在任意两个不相邻的顶点之间加一条新边所得图为非平面图间加一条新边所得图为非平面图, 则称则称G为为极大平面图极大平面图.例如例如, K5, K3,3若删去一条边是极大平面图若删去一条边是极大平面图. K1, K2, K3, K4都是极大平面图都是极大平面图(它们已无不相邻顶点它们已无不相邻顶点).极大平面图必连通极大平面图必连通*. 阶数大于等于阶数大于等于3的极大平面图中不可能有割点和桥的极大平面图中不可能有割点和桥*. 任何任何n(n 4)阶极大平面图阶极大平面图G均有均有 (G) 3. 定理定理 n(n 3)阶简单平面图是极大平面图当且仅当它连通且阶简单平面图是极大平面图当且仅当它连通且

18、每个面的次数都为每个面的次数都为3. 26实例实例例例 是否是极大平面图是否是极大平面图? 不是不是不是不是是是27极小非平面图极小非平面图 定义定义 若若G是非平面图是非平面图, 并且任意删除一条边所得图并且任意删除一条边所得图都是平面图都是平面图, 则称则称G为为极小非平面图极小非平面图.极小非平面图必为简单图极小非平面图必为简单图例如例如, K5, K3,3是极小非平面图是极小非平面图28欧拉公式欧拉公式 定理定理 (欧拉公式欧拉公式) 设设G为为n阶阶m条边条边r个面的连通平面图个面的连通平面图, 则则 n m+r=2. 证证 对边数对边数m做归纳证明做归纳证明. m=0, G为平凡图

19、为平凡图, 结论为真结论为真.设设m=k(k 0)结论为真结论为真, m=k+1时分情况讨论如下时分情况讨论如下: (1) 若若G中有一个中有一个1度顶点度顶点v, 则则G =G-v 连通连通, 有有n-1个顶点个顶点, k条边和条边和r个面个面. 由由归纳假设归纳假设, (n-1)-k+r=2, 即即n-(k+1)+r=2, 得证得证m=k+1时结论成立时结论成立. (2) 否则否则, G中必有圈中必有圈. 删除一个圈上的一条边删除一个圈上的一条边,记作记作G . G 连通连通, 有有n个顶点个顶点,k条边和条边和r-1个面个面. 由由归纳假设归纳假设, n-k+(r-1)=2, 即即n-(

20、k+1)+r=2, 得证得证m=k+1时结论也成立时结论也成立. 29欧拉公式欧拉公式( (续续) )推论推论(欧拉公式的推广欧拉公式的推广) 设设G是有是有 p (p 2) 个连通分支个连通分支的平面图的平面图, 则则 n m + r = p + 1证证 设第设第 i 个连通分支有个连通分支有 ni个顶点个顶点, mi 条边和条边和 ri 个面个面. 对各连通分支用欧拉公式对各连通分支用欧拉公式, ni mi + ri = 2, i = 1, 2, , p求和并注意求和并注意 r + p 1 = r1+rp, 即得即得 n m + r = p + 130平面图的性质平面图的性质定理定理 设设

21、G为为n阶阶m条边的连通简单平面图条边的连通简单平面图, 若若n 3, 则则mn-6 推论推论 K5 和和 K3,3不是平面图不是平面图. K5K3,331同胚与收缩同胚与收缩 消去消去2度顶点度顶点v 如上图从如上图从(1)到到(2)插入插入2度顶点度顶点v 如上图从如上图从(2)到到(1)G1与与G2同胚同胚: G1与与G2同构同构, 或或经过反复插入、或消去经过反复插入、或消去2度顶度顶点后同构点后同构收缩边收缩边e 如下图从如下图从(1)到到(2)32库拉图斯基定理库拉图斯基定理定理定理 G是平面图是平面图G中不含与中不含与K5同胚的子图同胚的子图, 也不也不含与含与K3,3同胚的子图

22、同胚的子图.定理定理 G是平面图是平面图G中无可收缩为中无可收缩为K5的子图的子图, 也无也无可收缩为可收缩为K3,3的子图的子图. 33非平面图证明非平面图证明例例 证明下述证明下述2个图均为非平面图个图均为非平面图. 收缩收缩2条边条边 收缩收缩2条边条边 K3,3取子图取子图K5取子图取子图34平面图的对偶图平面图的对偶图 定义定义 设平面图设平面图G, 有有n个顶点个顶点, m条边和条边和r个面个面, G的的对偶图对偶图G*=如下：如下：在在G的每一个面的每一个面Ri中任取一个点中任取一个点vi*作为作为G*的顶点的顶点, V*= vi*| i=1,2,r .对对G每一条边每一条边ek

23、, 若若ek在在G的面的面Ri与与Rj的公共边界上的公共边界上, 则作边则作边ek*=(vi*,vj*), 且与且与ek相交相交; 若若ek为为G中的桥且在中的桥且在面面Ri的边界上的边界上, 则作环则作环ek*=(vi*,vi*). E*= ek*| k=1,2, ,m . 35平面图的对偶图的实例平面图的对偶图的实例例例 黑色实线为原平面图黑色实线为原平面图, 红色虚线为其对偶图红色虚线为其对偶图 36平面图的对偶图的性质平面图的对偶图的性质性质：性质：对偶图是平面图，而且是平面嵌入对偶图是平面图，而且是平面嵌入.对偶图是连通图对偶图是连通图若边若边e为为G中的环，则中的环，则G*与与e对应的边对应的边e*为桥为桥; 若若e为桥，则为桥，则G*中与中与e对应的边对应的边e*为环为环.同构的平面图的对偶图不一定同构同构的平面图的对偶图不一定同构. 上页两个平面图同构上页两个平面图同构, 它们的对偶图不同构它