《离散数学一些特殊的图ppt教学》由会员分享，可在线阅读，更多相关《离散数学一些特殊的图ppt教学（37页珍藏版）》请在金锄头文库上搜索。
1、1第第8章章 一些特殊的图一些特殊的图 8.1 二部图二部图8.2 欧拉图欧拉图8.3 哈密顿图哈密顿图8.4 平面图平面图 28.1 二部图二部图 二部图二部图完全二部图完全二部图匹配匹配极大匹配极大匹配最大匹配最大匹配匹配数匹配数完备匹配完备匹配 3二部图二部图 定义定义 设无向图设无向图 G=, 若能将若能将V 分成分成V1 和和 V2 (V1 V2=V, V1 V2=), 使得使得G中的每条边的两个端中的每条边的两个端点都一个属于点都一个属于V1, 另一个属于另一个属于V2, 则称则称G为为二部图二部图(二分图二分图), 记为记为, 称称V1和和V2为为互补顶点子集互补顶点子集. 又若
2、又若G是简单图是简单图, 且且V1中每个顶点均与中每个顶点均与V2中每个顶点都相中每个顶点都相邻邻, 则称则称G为为完全二部图完全二部图, 记为记为Kr,s, 其中其中r=|V1|, s=|V2|. (a)(b)以上两个图都是二部图，其中以上两个图都是二部图，其中(b)图是完全二部图。图是完全二部图。4例例 完全二分图完全二分图Km, n=(V1,V2,E)共有共有 多少条边多少条边?解解 因为因为V1中每个顶点都与中每个顶点都与V2 中每个顶点相邻接中每个顶点相邻接,所以所以V1 中每个顶点关联中每个顶点关联 |V2| = n 条边条边; 而而V1 中有中有m个顶点个顶点, 所以所以Km,
3、n共有共有mn条边条边。5二部图的判别法二部图的判别法 定理定理 无向图无向图G=是二部图当且仅当是二部图当且仅当G中中 无奇圈无奇圈 。即。即G中的每一条回路都是由偶中的每一条回路都是由偶 数条边组成。数条边组成。证明：当证明：当G(V1,V2)是二部图时，是二部图时，G中的任中的任意一条回路的各边必须往返于意一条回路的各边必须往返于V1,V2之间，之间，因此其回路必由偶数条边组成。因此其回路必由偶数条边组成。6例：判断下图是否为二部图。例：判断下图是否为二部图。解：图中的每一条回路都是由偶数条边组成。解：图中的每一条回路都是由偶数条边组成。所以此图为二部图。所以此图为二部图。7匹配匹配 设
4、设G = (V, E)是具有互补顶点子集是具有互补顶点子集V1和和V2的二的二分图分图, M E, 若若M中中任意两条边都不相邻任意两条边都不相邻, 则称则称M为为G中的中的匹配匹配(对集对集)。l如果如果M是是G的匹配的匹配, 且且M中再中再加入任何一条边加入任何一条边就就都是都是不不匹配了匹配了, 则称则称M为为极大匹配极大匹配。最大匹配最大匹配: 边数最多的匹配边数最多的匹配匹配数匹配数: 最大匹配中的边数最大匹配中的边数, 记为记为 1。8如如在在下下图图中中，如如果果用用a1,a2,a3,a4表表示示4位位教教师师，b1,b2,b3表表示示三三门门待待开开的的课课程程。当当某某位位教
5、教师师能能开开某某门门课课程程时时，则则把把它它们们的的对对应应顶顶点点用用边边连连接接起起来来。如如果果规规定定一一个个教教师师只只能能担担任任一一门门课课程程，那那么么匹匹配配M就就表表示示了了一一种种排排课课方方案案。为为了了使使排排课课方方案案能能最最大大限限度度地地作到作到“各尽其能各尽其能”，这就是最大匹配的概念。，这就是最大匹配的概念。 9匹配匹配 (续续)设设M为为G中一个匹配中一个匹配ai与与bj被被M匹配匹配: (ai,bj) Mai为为M饱和点饱和点: M中有边与中有边与ai关联关联ai为为M非饱和点非饱和点: M中没有边与中没有边与ai关联关联M为完美匹配为完美匹配:
6、G的每个顶点都是的每个顶点都是M饱和点饱和点 10定义定义 设设G=为二部图为二部图, |V1| |V2|, M是是G中最中最大匹配大匹配, 若若V1中顶点全是中顶点全是M饱和点饱和点, 则称则称M为为G中中V1到到V2的的完备匹配完备匹配. 当当|V1|=|V2|时时, 完备匹配变成完美完备匹配变成完美匹配匹配.(1)(2)(3) 图中红边组成各图的一个匹配，图中红边组成各图的一个匹配，(1)为完备的为完备的, 但不是完但不是完美的美的; (2)不是完备的不是完备的, 其实其实(2)中无完备匹配中无完备匹配; (3) 是完美的是完美的.匹配匹配 (续续)例：如图例：如图11M1M2例例 求下
7、图的饱和点，并判断哪个图是求下图的饱和点，并判断哪个图是完美匹配？完美匹配？ 解：关于解：关于M1, a,b,e,d是饱和点是饱和点f,c是非饱和点是非饱和点 M1不是完美匹配不是完美匹配 M2是完美匹配，所以是完美匹配，所以M2中中 a,b,c,d,e,f都是饱和点都是饱和点。12 设设G= V1,V2,E 是是二二部部图图，M是是G的的一一个个匹匹配配，如如果果对对G的的任任意意匹匹配配M，都都有有|M|M|，则则M为为G的的最大匹配最大匹配 为为了了寻寻求求二二部部图图的的最最大大匹匹配配，以以下下引引进进交交替替通通路和增长通路两个概念。路和增长通路两个概念。 定义定义 设设G= V1
8、,V2,E 是二部图，是二部图，M是是G的匹的匹配，配，P是是G中的一条路，如果中的一条路，如果P是由是由G中属于中属于M的的边和不属于边和不属于M的边交替组成，则称的边交替组成，则称P为为G的的M交替交替通路。如果交替通路的始点和终点都是通路。如果交替通路的始点和终点都是M的非饱的非饱和点，则称为和点，则称为G的的M增长通路。增长通路。13 例如，在图中匹配例如，在图中匹配M=(a1,b2), (a2,b3), (a3,b5)， 路路 L1：a1b2a2b3a3， L2：a2b3a3b5a4， L3：b1a3b5a4， L4：b1a1b2a2b3a3b5a4 都都是是M的的交交替替通通路路，
9、其其中中后后两两条条交交替替通通路路L3和和L4的的始始点点和和终终点点都都是是M的的非非饱饱和和点点，所所以以这这两两条条路路是是M增增长长通路。通路。卡盟卡盟 Microsoft Office PowerPoint，是微软公司的演示文稿软件。用户可以在投影仪或者计算机上进行演示，也可以将演示文稿打印出来，制作成胶片，以便应用到更广泛的领域中。利用Microsoft Office PowerPoint不仅可以创建演示文稿，还可以在互联网上召开面对面会议、远程会议或在网上给观众展示演示文稿。 Microsoft Office PowerPoint做出来的东西叫演示文稿，其格式后缀名为：ppt、
10、pptx；或者也可以保存为：pdf、图片格式等15 设设G= V1,V2,E 是是二二部部图图，M是是G的的一一个个匹匹配配，P是是G中中的的一一条条M增增长长通通路路。把把P中中所所有有属属于于M的的边边从从M中中去去掉掉，而而把把P中中所所有有不不属属于于M的的边边添添加加到到M中中，得得到到一一个个新新的的边边集集M，则则M也也是是一一个个匹匹配配，其所含边数比匹配其所含边数比匹配M所含的边数多所含的边数多1。16 例例如如在在图图中中，把把M增增长长通通路路L3：b1a3b5a4中中属属于于M的的边边(a3,b5) 从从M中中去去掉掉，而而把把L3中中不不属属于于M的的边边(a3,b1
11、)和和(a4,b5) 添添加加到到M中中，得得到到一一个个新新的的边边集集M= (a1,b2),(a2,b3),(a3,b1), (a4,b5) ，显显然然M也也是是匹匹配配且且M的边数比的边数比M的边数多的边数多l，即，即|M|M|+1。17 由此可见，利用增长通路可以增加匹配所含的边数。由此可见，利用增长通路可以增加匹配所含的边数。不断地寻求不断地寻求G的增长通路，直到再也找不到新的增长通的增长通路，直到再也找不到新的增长通路，就可得到一个最大匹配。将这个结论写成下列的定路，就可得到一个最大匹配。将这个结论写成下列的定理。理。 定定理理 设设G= V1,V2,E 是是二二部部图图，M为为G
12、的的最最大大匹匹配配的充分必要条件是的充分必要条件是G中不存在中不存在M增长通路。增长通路。 证明：设证明：设M为为G的最大匹配，下证的最大匹配，下证G中不存在中不存在M可扩路。可扩路。 如果如果G中存在一条中存在一条M可扩路，则可以得到比可扩路，则可以得到比M的边数的边数多多1的匹配，所以的匹配，所以M不是最大匹配，矛盾。所以不是最大匹配，矛盾。所以G中不存中不存在在M可扩路。可扩路。 设设G中不存在中不存在M可扩路，下证可扩路，下证M为为G的最大匹配。的最大匹配。 设设M1是最大匹配，证明是最大匹配，证明|M|=|M1|。 考察属于考察属于M而不属于而不属于M1和属于和属于M1而不属于而不
13、属于M中的边，中的边，由这些边连同它们的端点一起构成由这些边连同它们的端点一起构成G的子图的子图H。18 在在子子图图H中中，任任一一顶顶点点至至多多与与M中中的的一一条条边边关关联联且且与与M1中中一一条条边边关关联联。因因而而任任一一顶顶点点的的度度数数是是1或或2。故故H的连通分支是一条路，或者是一个回路。的连通分支是一条路，或者是一个回路。 如如果果H的的连连通通分分支支是是一一条条路路P，则则它它是是M交交替替路路，也也是是M1交交替替路路。如如果果P的的两两个个端端点点均均与与M中中的的边边关关联联，则则P是是M1可可扩扩路路。由由假假设设知知，M1是是最最大大匹匹配配，所所以以，
14、不不存存在在M1可可扩扩路路，得得到到矛矛盾盾。如如果果P的的两两个个端端点点均均与与M1的的边边关关联联，那那么么P是是一一条条M可可扩扩路路与与题题设设矛矛盾盾。故故P只只能能是是一一个个端端点点与与M中中的的边边关关联联，另另一一个个端端点点与与M1中中的的边边关关联联，这这样样P中中属属于于M的的边边数数与属于与属于M1的边数相等。的边数相等。 19 如如果果H的的连连通通分分支支是是一一个个回回路路，回回路路中中的的边边交交替替地地属属于于M和和M1，因因而而属属于于M的的边边数数与与属于属于M1的边数相等。的边数相等。 从从上上面面可可以以看看到到，H中中属属于于M的的边边与与属属
15、于于M1的的边边的的数数目目相相等等。再再加加上上既既属属于于M又又属属于于M1的的边边，可可以以得得出出：M中中的的边边数数与与M1中中的的边数相等。所以边数相等。所以M是最大匹配。是最大匹配。20 有有了了上上面面的的准准备备以以后后，就就可可以以进进一一步步讨讨论如何在二部图中求最大匹配的问题。论如何在二部图中求最大匹配的问题。 设设G= V1,V2,E 是是二二部部图图，通通常常先先作作G的的一一个个匹匹配配M，再再看看V1中中有有没没有有M的的非非饱饱和和点点。如如果果没没有有，那那么么M肯肯定定是是最最大大匹匹配配；如如果果有有，就就从从这这些些点点出出发发找找M增增长长通通路路。
16、由由M增增长长通通路路作作出出一一个个更更大大的的匹匹配配。所所以以，在在G中求最大匹配的关键是寻找中求最大匹配的关键是寻找M增长通路。增长通路。 21寻寻找找增增长长通通路路的的一一个个有有效效方方法法是是标标记记法法，其其基基本本思思想如下：想如下： 设设G= V1,V2,E 是是二二部部图图，在在G中中作作一一个个匹匹配配M，用用(* *)标标记记V1中中所所有有M的的非非饱饱和和点点，然然后后交交替替地地进行以下进行以下和和两步：两步： 选一个选一个V2的新标记过的顶点，比如说的新标记过的顶点，比如说bi，用，用(bi)标记通过标记通过M中的边与中的边与bi邻接且尚未标记过的邻接且尚未
17、标记过的V1的所的所有顶点。对有顶点。对V2所有新标记过的顶点重复这一过程。所有新标记过的顶点重复这一过程。 选选一一个个V1的的新新标标记记过过的的顶顶点点，比比如如说说ai，用用(ai)标标记记不不通通过过M中中的的边边与与ai邻邻接接且且尚尚未未标标记记过过的的V2的的所所有顶点。对有顶点。对V1所有新标记过的顶点重复这一过程。所有新标记过的顶点重复这一过程。 22 直至标记到一个直至标记到一个V2中的中的M的非饱和点。从的非饱和点。从该顶点倒向追踪到标记有该顶点倒向追踪到标记有(* *)的顶点，就得到的顶点，就得到了一个了一个M增长通路。把增长通路。把M增长通路中所有属于增长通路中所有
18、属于M的边从的边从M中去掉，而把中去掉，而把M可扩路中所有不属可扩路中所有不属于于M的边添加到的边添加到M中，得到一个新的匹配中，得到一个新的匹配M且且其所含边数比匹配其所含边数比匹配M所含的边数多所含的边数多1。对。对M重重复上述过程，复上述过程，直到，直到G中已不存在增长通中已不存在增长通路，此时的匹配就是最大匹配。路，此时的匹配就是最大匹配。23 【例例】如图是二部图，求其最大匹配。如图是二部图，求其最大匹配。a1 a2 a3 a4b1 b2 b3 b4 b524 【例例】如图是二部图，求其最大匹配。如图是二部图，求其最大匹配。25 解解 ： 取取 二二 部部 图图 的的 一一 个个 匹
19、匹 配配 M= (a3,b1), (a5,b2)。用用(* *)标标记记V1中中所所有有M的的非非饱饱和和点点a1, a2, a4。 选选V1的的新新标标记记过过的的顶顶点点a1，用用(a1)标标记记不不通通过过M的的边边与与a1邻邻接接且且尚尚未未标标记记过过的的V2的的顶顶点点b1；类似地用；类似地用(a2)标记标记b2。 选选V2的的新新标标记记过过的的顶顶点点b1，用用(b1)标标记记通通过过M的的边边与与b1邻邻接接且且尚尚未未标标记记过过的的V1的的顶顶点点a3；类似地用类似地用(b2)标记标记a5。 26 选选V1的的新新标标记记过过的的顶顶点点a3，因因为为不不存存在在不不通通
20、过过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
21、), (a5,b3)，如图，如图9.61所示。所示。2728 对匹配对匹配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；再再用用(b
22、2)标标记记a2。 选选V1的的新新标标记记过过的的顶顶点点a2和和a3，V2中中已已无无可可标标记记的顶点。的顶点。 图中已不存在增长通路，所以图中已不存在增长通路，所以M就是最大匹配。就是最大匹配。29 【例例】求下图的最大匹配。求下图的最大匹配。 30 解：解：取二部图图取二部图图9.62的一个匹配的一个匹配 M=(a2,b2), (a3,b3), (a5,b5)。用。用(* *)标记标记V1中所有中所有M的非饱和点的非饱和点a1, a4。 选选V1的新标记过的顶点的新标记过的顶点a1，用，用(a1)标记标记b2和和b3。 选选V2的的新新标标记记过过的的顶顶点点b2和和b3，用用(b2
23、)标标记记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), (a
24、5,b5)重复上述过重复上述过程，已找不到程，已找不到M可扩路。所以可扩路。所以M就是最大匹配。就是最大匹配。3132Hall定理 定定 理理 (Hall定定 理理 ) 设设 二二 部部 图图 G=中中 ，|V1| |V2|. G中存中存在在从从V1到到V2的的完完备备匹匹配配当当且且仅仅当当V1中中任任意意k 个个顶顶点至少与点至少与V2中的中的k个顶点相邻个顶点相邻(k=1,2,|V1|).由由Hall定理不难证明定理不难证明, 上一页图上一页图(2)没有完备匹配没有完备匹配. Hall定理中的条件称为定理中的条件称为“相异性条件相异性条件”33定定理理 设设二二部部图图G=中中, 如如果
25、果存存在在t 1, 使使得得(1)V1中中每每个个顶顶点点至至少少关关联联 t 条条边边, (2)而而V2中中每每个个顶顶点点至至多多关关联联t条边，则条边，则G中存在中存在V1到到V2的完备匹配的完备匹配. (充分条件充分条件)证证明明 如如果果(1)成成立立, 则则与与V1中中k (1k|V1|)个个顶顶点点相相关关联联的的边边的的总总数数, 至至少少是是kt条条。根根据据(2)这这些些边边至至少少要要与与V2中中k个个顶顶点相关联。点相关联。l这这就就得得出出V1中中每每k (1k|V1|)个个顶顶点点, 至至少少邻邻接接到到到到V2中中k个顶点。个顶点。定定理理中中的的条条件件称称为为
26、 t 条条件件. 满满足足 t 条条件件的的二二部部图图一一定定满满足足相相异性条件异性条件.34 因因此此，当当给给出出一一个个二二分分图图后后。 判判断断G中中存存在在从从V1到到V2的完备匹配方法的完备匹配方法:先先 找找 出出 V中中 的的 每每 个个 结结 点点 的的 度度 数数 ， 令令 rminv vV1V1d(v)。再再找找出出V中中的的每每个个结结点点的的度度数数，令令Rmaxv vV2V2 d(v)。若若rR，则则问问题题有有解解，取取t为为r即即可可。但但这这只只是是充充分分条条件件，若若不不满满足足，则则还还要要用充要条件来判断。用充要条件来判断。 35图图9.64中中
27、的的二二部部图图满满足足t的的条条件件。其其中中t=3。因因此此在在图图9.64中存在中存在V1到到V2的完备匹配。的完备匹配。 36一个应用实例 例例 某课题组要从某课题组要从a, b, c, d, e 5人中派人中派3人分别到上海、广州、人分别到上海、广州、香港去开会香港去开会. 已知已知a只想去上海，只想去上海，b只想去广州，只想去广州，c, d, e都都表示想去广州或香港表示想去广州或香港. 问该课题组在满足个人要求的条问该课题组在满足个人要求的条件下，共有几种派遣方案？件下，共有几种派遣方案？ 解解 令令G=, 其中其中V1=s, g, x, V2=a, b, c, d, e, E=
28、(u,v) | u V1, v V2, v想去想去u,其中其中s, g, x分别表示上海、广州和香港分别表示上海、广州和香港. G如图所示如图所示. G 满足相异性条件，因而可给满足相异性条件，因而可给出派遣方案，共有出派遣方案，共有9种派遣方案种派遣方案(请给出这请给出这9种方案种方案). 37练习：练习：1.某单位按编制有某单位按编制有7个空缺：个空缺：p1, p2, .p7.有有10个申请者：个申请者： a1, a2, .a10.他们合格的工作岗位依次为：他们合格的工作岗位依次为：, p1,p5,p6,p2,p6,p7,p3,p4,p1,p5p6,p7,p3,p2,p3, p1,p3,p
29、1,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,请问如何匹配，使男女双方都有满意的婚姻且结婚请问如何匹配，使男女双方都有满意的婚姻且结婚的对数最多。的对数最多。
