9512.net
甜梦文库
当前位置:首页 >> 数学 >>

离散数学一些特殊的图ppt教学-精选文档_图文

第8章 一些特殊的图
8.1 二部图

8.2 欧拉图
8.3 哈密顿图 8.4 平面图

1

8.1 二部图

§二部图 §完全二部图 §匹配 §极大匹配 §最大匹配 §匹配数 §完备匹配
2

二部图
定义 设无向图 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|.

(a)

(b)
3

以上两个图都是二部图,其中(b)图是完全二部图。

例 完全二分图Km, n=(V1,V2,E)共有 多少条边?
解 因为V1中每个顶点都与V2 中每个顶点相邻接, 所以V1 中每个顶点关联 |V2| = n 条边; 而V1 中有m个顶点, 所以Km, n共有mn条边。

4

二部图的判别法
定理 无向图G=<V,E>是二部图当且仅当G中 无奇圈 。即G中的每一条回路都是由偶 数条边组成。 证明:当G(V1,V2)是二部图时,G中的任 意一条回路的各边必须往返于V1,V2之间, 因此其回路必由偶数条边组成。

5

例:判断下图是否为二部图。

解:图中的每一条回路都是由偶数条边组成。 所以此图为二部图。


6

匹配
设G = (V, E)是具有互补顶点子集V1和V2的二
分图, M ? E, 若M中任意两条边都不相邻, 则称

M为G中的匹配(对集)。
?

如果M是G的匹配, 且M中再加入任何一条边就

都是不匹配了, 则称M为极大匹配。
最大匹配: 边数最多的匹配 匹配数: 最大匹配中的边数, 记为?1。
7

如 在 下 图 中 , 如 果 用 a1,a2,a3,a4 表 示 4 位 教 师 , b1,b2,b3表示三门待开的课程。当某位教师能开某门 课程时,则把它们的对应顶点用边连接起来。如果 规定一个教师只能担任一门课程,那么匹配M就表 示了一种排课方案。为了使排课方案能最大限度地 作到“各尽其能”,这就是最大匹配的概念。

8

匹配 (续)

设M为G中一个匹配 ai与bj被M匹配: (ai,bj)?M ai为M饱和点: M中有边与ai关联 ai为M非饱和点: M中没有边与ai关联 M为完美匹配: G的每个顶点都是M饱和点

9

匹配 (续)
定义 设G=<V1,V2,E>为二部图, |V1|?|V2|, M是G中最 大匹配, 若V1中顶点全是M饱和点, 则称M为G中V1 到V2的完备匹配. 当|V1|=|V2|时, 完备匹配变成完美 匹配.
例:如图

(1)

(2)

(3)

图中红边组成各图的一个匹配,(1)为完备的, 但不是完 美的; (2)不是完备的, 其实(2)中无完备匹配; (3) 是完美的.

10

例 求下图的饱和点,并判断哪个图是

完美匹配?

M1

M2

解:关于M1, a,b,e,d是饱和点f,c是非饱和点 M1不是完美匹配 M2是完美匹配,所以M2中 a,b,c,d,e,f都是饱和点。
11

设 G=?V1,V2,E? 是二部图, M 是 G 的一个匹配, 如果对G的任意匹配M′,都有|M′|≤|M|,则M为 G的最大匹配 为了寻求二部图的最大匹配,以下引进交替通 路和增长通路两个概念。 P是G中的一条路,如果P是由G中属于M的边和 如果交替通路的始点和终点都是M的非饱和点,

定义 设G=?V1,V2,E?是二部图,M是G的匹配,

不属于M的边交替组成,则称P为G的M交替通路。

则称为G的M增长通路。
12

例如,在图中匹配M={(a1,b2), (a2,b3), (a3,b5)}, 路 L1:a1b2a2b3a3, L2:a2b3a3b5a4, L3:b1a3b5a4, L4:b1a1b2a2b3a3b5a4 都是 M 的交替通路,其中后两条交替通路 L3 和 L4 的 始点和终点都是M的非饱和点,所以这两条路是M增 长通路。

13

Microsoft Office PowerPoint,是微软 公司的演示文稿软件。用户可以在投影仪或 者计算机上进行演示,也可以将演示文稿打 印出来,制作成胶片,以便应用到更广泛的 领域中。利用Microsoft Office PowerPoint不 仅可以创建演示文稿,还可以在互联网上召 开面对面会议、远程会议或在网上给观众展 示演示文稿。 Microsoft Office PowerPoint做出来的东西叫演示文稿,其格 式后缀名为:ppt、pptx;或者也可以保存为: pdf、图片格式等
卡盟 kadianwl 卡盟

设 G=?V1,V2,E? 是二部图, M 是 G 的一个匹配,

P是G中的一条M增长通路。把P中所有属于M的边
从 M 中去掉,而把 P中所有不属于 M 的边添加到 M 中,得到一个新的边集 M′ ,则 M′ 也是一个匹配, 其所含边数比匹配M所含的边数多1。
15

例如在图中,把 M 增长通路 L3 : b1a3b5a4 中属于 M的边(a3,b5) 从M中去掉,而把L3中不属于M的边 (a3,b1) 和 (a4,b5) 添加到 M 中,得到一个新的边集 M′=?(a1,b2),(a2,b3),(a3,b1), (a4,b5)? ,显然 M′ 也是匹 配且M′的边数比M的边数多l,即|M′|=|M|+1。
16

由此可见,利用增长通路可以增加匹配所含的边数。 不断地寻求G的增长通路,直到再也找不到新的增长通 路,就可得到一个最大匹配。将这个结论写成下列的定 理。 定理 设G=?V1,V2,E?是二部图,M为G的最大匹配的 充分必要条件是G中不存在M增长通路。 证明:设M为G的最大匹配,下证G中不存在M可扩路。 如果G中存在一条M可扩路,则可以得到比M的边数 多1的匹配,所以M不是最大匹配,矛盾。所以G中不 存在M可扩路。 设G中不存在M可扩路,下证M为G的最大匹配。 设M1是最大匹配,证明|M|=|M1|。 考察属于M而不属于M1和属于M1而不属于M中的边, 由这些边连同它们的端点一起构成G的子图H。
17

在子图 H 中,任一顶点至多与 M 中的一条边关 联且与 M1 中一条边关联。因而任一顶点的度数是 1 或2。故H的连通分支是一条路,或者是一个回路。 如果H的连通分支是一条路P,则它是M交替路, 也是 M1 交替路。如果 P的两个端点均与 M 中的边关 联,则P是M1可扩路。由假设知,M1是最大匹配, 所以,不存在M1可扩路,得到矛盾。如果 P的两个 端点均与 M1 的边关联,那么 P是一条 M可扩路与题 设矛盾。故 P 只能是一个端点与 M 中的边关联,另 一个端点与 M1 中的边关联,这样 P中属于 M的边数 与属于M1的边数相等。
18

如果H的连通分支是一个回路,回路中的 边交替地属于 M和 M1,因而属于 M的边数与 属于M1的边数相等。 从上面可以看到, H 中属于 M 的边与属 于M1的边的数目相等。再加上既属于M又属 于M1的边,可以得出:M中的边数与M1中的 边数相等。所以M是最大匹配。

19

有了上面的准备以后,就可以进一步讨 论如何在二部图中求最大匹配的问题。 设G=?V1,V2,E?是二部图,通常先作G的 一个匹配 M,再看 V1中有没有 M的非饱和点。 如果没有,那么M肯定是最大匹配;如果有, 就从这些点出发找 M 增长通路。由 M增长通 路作出一个更大的匹配。所以,在 G 中求最 大匹配的关键是寻找M增长通路。
20

寻找增长通路的一个有效方法是标记法,其基本思 想如下: 设 G=?V1,V2,E? 是二部图,在 G 中作一个匹配 M,用(*)标记V1中所有M的非饱和点,然后交替地 进行以下①和②两步:
①选一个V1的新标记过的顶点,比如说ai,用(ai) 标记不通过 M中的边与 ai邻接且尚未标记过的 V2的所 有顶点。对V1所有新标记过的顶点重复这一过程。 ②选一个V2的新标记过的顶点,比如说bi,用 (bi)标记通过M中的边与bi邻接且尚未标记过的V1的 所有顶点。对V2所有新标记过的顶点重复这一过程。

21

直至标记到一个V2中的M的非饱和点。从 该顶点倒向追踪到标记有(*)的顶点,就得到 了一个M增长通路。把M增长通路中所有属于 M的边从M中去掉,而把M可扩路中所有不属 于M的边添加到M中,得到一个新的匹配M′ 且其所含边数比匹配M所含的边数多1。对M′ 重复上述过程,……,直到G中已不存在增长 通路,此时的匹配就是最大匹配。

22

【例】如图是二部图,求其最大匹配。
a1 a2 a3 a4

b1

b2

b3

b4

b5

23

【例】如图是二部图,求其最大匹配。

24

解 : 取 二 部 图 的 一 个 匹 配 M= {(a3,b1), (a5,b2)}。用(*)标记V1中所有M的非饱和点a1, a2, a 4。 ①选V1的新标记过的顶点a1,用(a1)标记不 通过M的边与a1邻接且尚未标记过的V2的顶点b1; 类似地用(a2)标记b2。 ②选V2的新标记过的顶点b1,用(b1)标记通 过M的边与b1邻接且尚未标记过的V1的顶点a3; 类似地用(b2)标记a5。
25

过M的边与a3邻接的V2的顶点,所以不用(a3)标 记 V2 的顶点;用 (a5) 标记 b3 或 b4 ,假定用 (a5) 标 记b3。如图所示。 b3是M的非饱和点,标记结束。 从 b3 倒向追踪到标记有 (*) 的顶点,就得到 了M增长通路:a4b2a5b3或a2b2a5b3,取后者。把 M 增长通路 a2b2a5b3 中的边 (a5,b2) 从 M 中去掉, 而 把 (a2,b2) 和 (a5,b3) 添 加到 M 中 得 到 新 的 匹 配 M′={(a3,b1), (a2,b2), (a5,b3)},如图9.61所示。
26

③选V1的新标记过的顶点a3,因为不存在不通

27

对匹配M′= {(a3,b1), (a2,b2), (a5,b3) }再用标记法: 用(*)标记V1中所有M′的非饱和点a1和 a4。 ①选 V1 的新标记过的顶点 a1 ,用 (a1) 标记不通过 M′ 的边与a1邻接且尚未标记过的V2的所有顶点b1;再用(a4) 标记b2。 ②选 V2 的新标记过的顶点 b1 ,用 (b1) 标记通过 M′ 的 边与b1邻接且尚未标记过的V1的所有顶点a3;再用(b2)标 记 a 2。 ③选 V1的新标记过的顶点 a2和a3,V2中已无可标记 的顶点。 图中已不存在增长通路,所以M′就是最大匹配。
28

【例】求下图的最大匹配。

29

解:取二部图图9.62的一个匹配 M={(a2,b2), (a3,b3), (a5,b5)}。用(*)标记V1中所有M的非饱和点a1, a4。 ①选V1的新标记过的顶点a1,用(a1)标记b2和b3。 ②选 V2 的新标记过的顶点 b2 和 b3,用 (b2) 标记 a2 ,用 (b3)标记a3。 ③选V1的新标记过的顶点a2,用(a2)标记b1, b4和b5。 由于b1和b4都是M的非饱和点,说明找到了 M可扩路。 它们是: a1b2a2b4和 a1b2a2b1。选前者,把边 (a2,b2) 从 M中 去掉,而把 (a1,b2) 和 (a2,b4) 添加到 M 中,得到新的匹配 M′=?(a1,b2),(a2,b4),(a3,b3), (a5,b5)?,如图9.63所示。 对于匹配M′= {(a1,b2),(a2,b4),(a3,b3), (a5,b5)}重复上述过 程,已找不到M′可扩路。所以M′就是最大匹配。
30

31

Hall定理
定 理 (Hall 定 理 ) 设 二 部 图 G=<V1,V2,E> 中 , |V1|?|V2|. G中存 在从V1到V2的完备匹配当且仅当V1中任意k 个顶 点至少与V2 中的k个顶点相邻(k=1,2,…,|V1|). 由Hall定理不难证明, 上一页图(2)没有完备匹配.

Hall定理中的条件称为“相异性条件”
32

定理 设二部图G=<V1,V2,E>中, 如果存在t?1, 使得(1)V1中每 个顶点至少关联 t 条边, (2)而V2中每个顶点至多关联t条 边,则G中存在V1到V2的完备匹配. (充分条件) 证明 如果(1)成立, 则与V1中k (1≤k≤|V1|)个顶点相关联的边 的总数, 至少是kt条。根据(2)这些边至少要与V2中k个顶 点相关联。
这就得出V1中每k (1≤k≤|V1|)个顶点, 至少邻接到到V2中 k个顶点。 定理中的条件称为 t 条件. 满足 t 条件的二部图一定满足相 异性条件.
?

33

因此,当给出一个二分图后。 判断G中存在 从V1到V2的完备匹配方法: 先找出V1中的每个结点的度数,令r= minv∈V1{d(v)}。再找出V2中的每个结点的度数, 令R=maxv∈V2 {d(v)}。若r≥R,则问题有解,取 t 为 r 即可。但这只是充分条件,若不满足,则还 要用充要条件来判断。

34

图9.64中的二部图满足t的条件。其中t=3。因此在 图9.64中存在V1到V2的完备匹配。

35

一个应用实例
例 某课题组要从a, b, c, d, e 5人中派3人分别到上海、广州、 香港去开会. 已知a只想去上海,b只想去广州,c, d, e都 表示想去广州或香港. 问该课题组在满足个人要求的条 件下,共有几种派遣方案? 解 令G=<V1,V2,E>, 其中V1={s, g, x}, V2={a, b, c, d, e}, E={(u,v) | u?V1, v?V2, v想去u}, 其中s, g, x分别表示上海、广州和香港. G如图所示. G 满足相异性条件,因而可给 出派遣方案,共有9种派遣方案 (请给出这9种方案).
36

练习: 1.某单位按编制有7个空缺:p1, p2, …..p7.有10个申请者: a1,

a2, …..a10.他们合格的工作岗位依次为:,
{p1,p5,p6},{p2,p6,p7},{p3,p4},{p1,p5}{p6,p7},{p3},{p2,p3}, {p1,p3},{p1},{p5},如何安排他们的工作,使有工作的人最多。 2.某单位有6个未婚女子L1,L2,…,L6和6个未婚男子g1,g2,…,g6,每 个人都有意中人, L1:{g1,g2,g4},L2:{g3,g5},L3:{g1,g2,g4},L4:{g2,g5,g6},L5:{g5,g6}, L6:{g3,g5,g6};而 g1:{L1,L3,L6},g2:{L2,L4,L6},g3:{L2,L5},g4:{L1,L3},g5:{L2,L6},

g6:{L3,L4,L5},请问如何匹配,使男女双方都有满意的婚姻且结 37 婚的对数最多。



学霸百科 | 新词新语

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图