二部图与完全二部图

1、 二部图二部图 二部图二部图完全二部图完全二部图1二部图二部图 定义定义 设无向图设无向图 G=, 若能将若能将V 划分成划分成V1 和和 V2 (V1 V2=V, V1 V2=), 使得使得G中的每条边的两个端中的每条边的两个端点都一个属于点都一个属于V1, 另一个属于另一个属于V2, 则称则称G为为二部图二部图, 记为记为, 称称V1和和V2为为互补顶点子集互补顶点子集. 又若又若G是简单图是简单图, 且且V1中每个顶点都与中每个顶点都与V2中每个中每个顶点相邻顶点相邻,则称则称G为为完全二部图完全二部图, 记为记为Kr,s, 其中其中r=|V1|, s=|V2|. 注意注意: n 阶零图

2、为二部图阶零图为二部图. 2二部图的判别法二部图的判别法 定理定理 无向图无向图G=是二部图当且仅当是二部图当且仅当G中无奇圈中无奇圈 例例 下述各图都是二部图下述各图都是二部图 3 欧拉图欧拉图历史上的哥尼斯堡七桥问题是著名的图论问题。历史上的哥尼斯堡七桥问题是著名的图论问题。 问题是这样的：问题是这样的： 1818世纪的东普鲁士有个哥尼世纪的东普鲁士有个哥尼斯堡城，斯堡城， 在横贯全城的普雷格尔河两岸和两个岛在横贯全城的普雷格尔河两岸和两个岛之间架设了之间架设了7 7座桥，座桥， 它们把河的两岸和两个岛连它们把河的两岸和两个岛连接起来（如图接起来（如图1 1）。）。 每逢假日，每逢假日，

3、城中居民进行城中居民进行环城游玩，环城游玩， 人们对此提出了一个人们对此提出了一个“遍游遍游”问题，问题， 即能否有这样一种走法，即能否有这样一种走法， 使得从某地出发通过且使得从某地出发通过且只通过每座桥一次后又回到原地呢？只通过每座桥一次后又回到原地呢？4 我们将图我们将图1 1中的哥尼斯堡城的中的哥尼斯堡城的4 4块陆地部分块陆地部分分别标以分别标以A A， B B， ， D D， 将陆地设想为将陆地设想为图的结点，图的结点， 而把桥画成相应的连接边，而把桥画成相应的连接边， 这这样图样图1 1可简化成图可简化成图2 2。 于是七桥于是七桥“遍游遍游”问问题等价于在图题等价于在图2 2中

4、，中， 从某一结点出发找到一从某一结点出发找到一条回路，条回路， 通过它的每条边一次且仅一次，通过它的每条边一次且仅一次， 并回到原来的结点。并回到原来的结点。 5 定义定义 1 1 给定无孤立结点的图给定无孤立结点的图G G， 若存在一条经过若存在一条经过G G中每边一次且仅一次的回路，中每边一次且仅一次的回路， 则该回路为欧拉回则该回路为欧拉回路。路。 具有欧拉回路的图称为欧拉图。具有欧拉回路的图称为欧拉图。 例如，例如， 给出如图给出如图3 3所示的两个图，所示的两个图， 容易看出，容易看出， ( (a a) )是欧拉图，是欧拉图， 而而( (b b) )不是欧拉图。不是欧拉图。 6 下

5、图中，下图中， ( (a a) )图的每个结点的度数都为，图的每个结点的度数都为， 所以它所以它是欧拉图；是欧拉图；( (b b) )图不是欧拉图。图不是欧拉图。 但我们继续考察但我们继续考察( (b b) )图可以发现，图可以发现， 该图中有一条该图中有一条路路v v2 2v v3 3v v4 4v v5 5v v2 2v v1 1v v5 5， 它经过它经过( (b b) )图中的每条边一次且仅图中的每条边一次且仅一次，一次， 我们把这样的路称为欧拉路。我们把这样的路称为欧拉路。 定理定理 1 1 连通图连通图G G是欧拉图的充要条件是是欧拉图的充要条件是G G的所的所有结点的度数都是偶数

6、。有结点的度数都是偶数。7n 定义定义2 2 通过图通过图G G的每条边一次且仅一次的的每条边一次且仅一次的路称为图路称为图G G的欧拉路。的欧拉路。 对于欧拉路有下面对于欧拉路有下面的判定方法。的判定方法。 n定理定理2 2 连通图连通图G G具有一条连接结点具有一条连接结点v vi i和和v vj j的的欧拉路当且仅当欧拉路当且仅当v vi i和和v vj j是是G G中仅有的两个奇中仅有的两个奇数度结点。数度结点。 8 我国民间很早就流传一种我国民间很早就流传一种“一笔画一笔画”游戏。游戏。 由定理由定理1 1和定理和定理2 2知，知， 有两种情有两种情况可以一笔画。况可以一笔画。 1)

7、 1) 如果图中所有结点是偶数度结如果图中所有结点是偶数度结点，点， 则可以任选一点作为始点一笔画完；则可以任选一点作为始点一笔画完； 2) 2) 如果图中只有两个奇度结点，如果图中只有两个奇度结点， 则可以选择其中一个奇度结点作为始点则可以选择其中一个奇度结点作为始点也可一笔画完。也可一笔画完。 9n【例例】下图是一幢房子的平面图形，下图是一幢房子的平面图形， 前门进前门进入一个客厅，入一个客厅， 由客厅通向由客厅通向4 4个房间。个房间。 如果要如果要求每扇门只能进出一次，求每扇门只能进出一次， 现在你由前门进去，现在你由前门进去， 能否通过所有的门走遍所有的房间和客厅，能否通过所有的门走

8、遍所有的房间和客厅， 然后从后门走出。然后从后门走出。 10n 解解: : 将将4 4个房间和一个客厅及前门外和后门外个房间和一个客厅及前门外和后门外作为结点，作为结点， 若两结点有边相连就表示该两结若两结点有边相连就表示该两结点所表示的位置有一扇门相通。点所表示的位置有一扇门相通。 由此得图由此得图 ( (b b) )。 由于图中有由于图中有4 4个结点是奇度结点，个结点是奇度结点， 故由故由定理定理7.4.27.4.2知本题无解。知本题无解。 11n 定理定理3 3 一个连通有向图具有（有向）一个连通有向图具有（有向）欧拉回路的充要条件是图中每个结点的欧拉回路的充要条件是图中每个结点的入度

9、等于出度。入度等于出度。 一个连通有向图具有有一个连通有向图具有有向欧拉路的充要条件是最多除两个结点向欧拉路的充要条件是最多除两个结点外的每个结点的入度等于出度，外的每个结点的入度等于出度， 但在这但在这两个结点中，两个结点中， 一个结点的入度比出度大一个结点的入度比出度大1 1， 另一个结点的入度比出度少另一个结点的入度比出度少1 1。 类似于无向图的结论，类似于无向图的结论， 对有向图有以对有向图有以下结果。下结果。 12平面图和平面嵌入平面图和平面嵌入 定义定义 如果能将图如果能将图G除顶点外边不相交地画在平面上除顶点外边不相交地画在平面上, 则称则称G是是平面图平面图. 这个画出的无边

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

11、3,3是非平面图是非平面图设设G G, 若若G为平面图为平面图, 则则G 也是也是 平面图平面图; 若若G 为非平面图为非平面图, 则则G也也 是非平面图是非平面图. Kn(n 5), K3,n(n 3)都是非平面图都是非平面图. 平行边与环不影响图的平面性平行边与环不影响图的平面性. K5K3,3平面图的面与次数平面图的面与次数设设G是一个平面嵌入是一个平面嵌入G的面的面: 由由G的边将平面划分成的每一个区域的边将平面划分成的每一个区域无限面无限面(外部面外部面): 面积无限的面面积无限的面, 用用R0表示表示有限面有限面(内部面内部面): 面积有限的面面积有限的面, 用用R1, R2, R

12、k表示表示 面面Ri的边界的边界: 包围包围Ri的所有边构成的回路组的所有边构成的回路组面面Ri的次数的次数: Ri边界的长度，用边界的长度，用deg(Ri)表示表示 说明说明: 构成一个面的边界的回路组可能是初级回路构成一个面的边界的回路组可能是初级回路, 简单回简单回路路, 也可能是复杂回路也可能是复杂回路, 还可能是非连通的回路之并还可能是非连通的回路之并. 定理定理 平面图各面的次数之和等于边数的平面图各面的次数之和等于边数的2倍倍.平面图的面与次数平面图的面与次数( (续续) )例例1 右图有右图有4个面个面, deg(R1)=1, deg(R2)=3, deg(R3)=2, deg

13、(R0)=8. 请写各面的边界请写各面的边界.例例2 左边左边2个图是同一个平面个图是同一个平面图的平面嵌入图的平面嵌入. R1在在(1)中是中是外部面外部面, 在在(2)中是内部面中是内部面; R2在在(1)中是内部面中是内部面, 在在(2)中是中是外部面外部面. 其实其实, 在平面嵌入中在平面嵌入中可把任何面作为外部面可把任何面作为外部面.欧拉公式欧拉公式 定理定理11 (欧拉公式欧拉公式) 设设G为为n阶阶m条边条边r个面的连通平面图，个面的连通平面图，则则 n m+r=2. 证证 对边数对边数m做归纳证明做归纳证明. m=0, G为平凡图为平凡图, 结论为真结论为真.设设m=k(k 0

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

15、+1)+r=2,得证得证m=k+1时结论也成立时结论也成立. 证毕证毕. n哈密尔顿图哈密尔顿图 与欧拉回路类似的是哈密尔顿回路问题。与欧拉回路类似的是哈密尔顿回路问题。 它是它是1859年哈密尔顿首先提出的一个关于年哈密尔顿首先提出的一个关于12面体的数学游戏：面体的数学游戏： 能否在下页图中找到能否在下页图中找到一个回路，使它含有图中所有结点一次且一个回路，使它含有图中所有结点一次且仅一次？仅一次？ 若把每个结点看成一座城市，连若把每个结点看成一座城市，连接两个结点的边看成是交通线，那么这个接两个结点的边看成是交通线，那么这个问题就变成能否找到一条旅行路线，使得问题就变成能否找到一条旅行路

16、线，使得沿着该旅行路线经过每座城市恰好一次，沿着该旅行路线经过每座城市恰好一次，再回到原来的出发地呢？为此，这个问题再回到原来的出发地呢？为此，这个问题也被称作周游世界问题。也被称作周游世界问题。 18 12 面体游戏示图面体游戏示图 n 对右图对右图 ， 图中粗图中粗线给出了这样的回路。线给出了这样的回路。 定义定义4 4 给定图给定图G G， 若若有一条路通过有一条路通过G G中每个结中每个结点恰好一次，点恰好一次， 则这样的则这样的路称为哈密尔顿路；若路称为哈密尔顿路；若有一个圈，有一个圈， 通过通过G G中每中每个结点恰好一次个结点恰好一次( (起点两起点两次次) )， 这样的圈称为哈

17、这样的圈称为哈密尔顿回路（或哈密尔密尔顿回路（或哈密尔顿圈）。顿圈）。 具有哈密尔顿回路具有哈密尔顿回路的图称为哈密尔顿图。的图称为哈密尔顿图。 19n 尽管哈密尔顿回路与欧拉回路问题在尽管哈密尔顿回路与欧拉回路问题在形式上极为相似，但是到目前为止还不形式上极为相似，但是到目前为止还不知道一个图为哈密尔顿图的充要条件，知道一个图为哈密尔顿图的充要条件，寻找该充要条件仍是图论中尚未解决的寻找该充要条件仍是图论中尚未解决的主要问题之一。下面先给出一个简单而主要问题之一。下面先给出一个简单而有用的必要条件。有用的必要条件。 n 定理定理1 1 设图设图G GV V , ,E E是哈密尔顿图，是哈密尔

18、顿图， 则则对于对于V V的每个非空子集的每个非空子集S S，均有，均有W W（G GS S）| |S S| | 成成立，立，其中其中W W（G GS S）是图）是图G GS S 的连通分支数。的连通分支数。 20。以以该该图图不不是是哈哈密密尔尔顿顿图图故故不不满满足足必必要要条条件件，所所个个连连通通分分支支，而而有有则则如如图图，若若取取, 23,41 SSGvvS21判断哈密尔顿图的充分条件很多，判断哈密尔顿图的充分条件很多， 我们仅介绍一个。我们仅介绍一个。定理定理2 设设GV ,E是有是有n个结点的简单图，个结点的简单图， 1） 如果任一对不相邻结点如果任一对不相邻结点u， vV， 均均有有 deg(u)deg(v) n1， 则在则在G中存在一条哈密尔顿路；中存在一条哈密尔顿路； 2） 如果任一对不相邻结点如果任一对不相邻结点u， vV， 均均有有 deg(u)deg(v) n， 则则G是哈密尔顿图。是哈密尔顿图。22n【例例3 3】某地有个风景点。若每个景点均有某地有个风景点。若每个景点均有两条道路与其他景点相通，问是否可经过每个两条道路与其他景点相通，