离散数学一些特殊的图

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 中有

3、中有m个顶点个顶点, 所以所以Km, n共有共有mn条边。条边。离散数学一些特殊的图5二部图的判别法二部图的判别法 定理定理 无向图无向图G=是二部图当且仅当是二部图当且仅当G中中 无奇圈无奇圈 。即。即G中的每一条回路都是由偶中的每一条回路都是由偶 数条边组成。数条边组成。证明：当证明：当G(V1,V2)是二部图时，是二部图时，G中的任中的任意一条回路的各边必须往返于意一条回路的各边必须往返于V1,V2之间，之间，因此其回路必由偶数条边组成。因此其回路必由偶数条边组成。离散数学一些特殊的图6例：判断下图是否为二部图。例：判断下图是否为二部图。解：图中的每一条回路都是由偶数条边组成。解：图中的

4、每一条回路都是由偶数条边组成。所以此图为二部图。所以此图为二部图。离散数学一些特殊的图7匹配匹配 设设G = (V, E)是具有互补顶点子集是具有互补顶点子集V1和和V2的二的二分图分图, M E, 若若M中任意两条边都不相邻中任意两条边都不相邻, 则称则称M为为G中的匹配中的匹配(对集对集)。l如果如果M是是G的匹配的匹配, 且且M中再加入任何一条边就中再加入任何一条边就都是不匹配了都是不匹配了, 则称则称M为极大匹配。为极大匹配。最大匹配最大匹配: 边数最多的匹配边数最多的匹配匹配数匹配数: 最大匹配中的边数最大匹配中的边数, 记为记为 1。离散数学一些特殊的图8如在下图中，如果用如在下图

5、中，如果用a1,a2,a3,a4表示表示4位教师，位教师，b1,b2,b3表示三门待开的课程。当某位教师能开某门表示三门待开的课程。当某位教师能开某门课程时，则把它们的对应顶点用边连接起来。如果课程时，则把它们的对应顶点用边连接起来。如果规定一个教师只能担任一门课程，那么匹配规定一个教师只能担任一门课程，那么匹配M就表就表示了一种排课方案。为了使排课方案能最大限度地示了一种排课方案。为了使排课方案能最大限度地作到作到“各尽其能各尽其能”，这就是最大匹配的概念。，这就是最大匹配的概念。 离散数学一些特殊的图9匹配匹配 (续续)设设M为为G中一个匹配中一个匹配ai与与bj被被M匹配匹配: (ai,

6、bj) Mai为为M饱和点饱和点: M中有边与中有边与ai关联关联ai为为M非饱和点非饱和点: M中没有边与中没有边与ai关联关联M为完美匹配为完美匹配: G的每个顶点都是的每个顶点都是M饱和点饱和点 离散数学一些特殊的图10定义定义 设设G=为二部图为二部图, |V1| |V2|, M是是G中最中最大匹配大匹配, 若若V1中顶点全是中顶点全是M饱和点饱和点, 则称则称M为为G中中V1到到V2的完备匹配的完备匹配. 当当|V1|=|V2|时时, 完备匹配变成完美完备匹配变成完美匹配匹配.(1)(2)(3) 图中红边组成各图的一个匹配，图中红边组成各图的一个匹配，(1)为完备的为完备的, 但不是

7、完但不是完美的美的; (2)不是完备的不是完备的, 其实其实(2)中无完备匹配中无完备匹配; (3) 是完美的是完美的.匹配匹配 (续续)例：如图例：如图离散数学一些特殊的图11M1M2例例 求下图的饱和点，并判断哪个图是求下图的饱和点，并判断哪个图是完美匹配？完美匹配？ 解：关于解：关于M1, a,b,e,d是饱和点是饱和点f,c是非饱和点是非饱和点 M1不是完美匹配不是完美匹配 M2是完美匹配，所以是完美匹配，所以M2中中 a,b,c,d,e,f都是饱和点都是饱和点。离散数学一些特殊的图12 设设G= V1,V2,E 是二部图，是二部图，M是是G的一个匹配，的一个匹配，如果对如果对G的任意

8、匹配的任意匹配M，都有，都有|M|M|，则，则M为为G的最大匹配的最大匹配 为了寻求二部图的最大匹配，以下引进交替通为了寻求二部图的最大匹配，以下引进交替通路和增长通路两个概念。路和增长通路两个概念。 定义定义 设设G= V1,V2,E 是二部图，是二部图，M是是G的匹配，的匹配，P是是G中的一条路，如果中的一条路，如果P是由是由G中属于中属于M的边和的边和不属于不属于M的边交替组成，则称的边交替组成，则称P为为G的的M交替通路。交替通路。如果交替通路的始点和终点都是如果交替通路的始点和终点都是M的非饱和点，的非饱和点，则称为则称为G的的M增长通路。增长通路。离散数学一些特殊的图13 例如，在

9、图中匹配例如，在图中匹配M=(a1,b2), (a2,b3), (a3,b5)， 路路 L1：a1b2a2b3a3， L2：a2b3a3b5a4， L3：b1a3b5a4， L4：b1a1b2a2b3a3b5a4 都是都是M的交替通路，其中后两条交替通路的交替通路，其中后两条交替通路L3和和L4的的始点和终点都是始点和终点都是M的非饱和点，所以这两条路是的非饱和点，所以这两条路是M增增长通路。长通路。离散数学一些特殊的图14 设设G= V1,V2,E 是二部图，是二部图，M是是G的一个匹配，的一个匹配，P是是G中的一条中的一条M增长通路。把增长通路。把P中所有属于中所有属于M的边的边从从M中去

10、掉，而把中去掉，而把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

11、的边数比的边数比M的边数多的边数多l，即，即|M|M|+1。离散数学一些特殊的图16 由此可见，利用增长通路可以增加匹配所含的边数。由此可见，利用增长通路可以增加匹配所含的边数。不断地寻求不断地寻求G的增长通路，直到再也找不到新的增长通的增长通路，直到再也找不到新的增长通路，就可得到一个最大匹配。将这个结论写成下列的定路，就可得到一个最大匹配。将这个结论写成下列的定理。理。 定理定理 设设G= V1,V2,E 是二部图，是二部图，M为为G的最大匹配的的最大匹配的充分必要条件是充分必要条件是G中不存在中不存在M增长通路。增长通路。 证明：设证明：设M为为G的最大匹配，下证的最大匹配，下证G中不存

12、在中不存在M可扩路。可扩路。 如果如果G中存在一条中存在一条M可扩路，则可以得到比可扩路，则可以得到比M的边数的边数多多1的匹配，所以的匹配，所以M不是最大匹配，矛盾。所以不是最大匹配，矛盾。所以G中不中不存在存在M可扩路。可扩路。 设设G中不存在中不存在M可扩路，下证可扩路，下证M为为G的最大匹配。的最大匹配。 设设M1是最大匹配，证明是最大匹配，证明|M|=|M1|。 考察属于考察属于M而不属于而不属于M1和属于和属于M1而不属于而不属于M中的边，中的边，由这些边连同它们的端点一起构成由这些边连同它们的端点一起构成G的子图的子图H。离散数学一些特殊的图17 在子图在子图H中，任一顶点至多与

13、中，任一顶点至多与M中的一条边关中的一条边关联且与联且与M1中一条边关联。因而任一顶点的度数是中一条边关联。因而任一顶点的度数是1或或2。故。故H的连通分支是一条路，或者是一个回路。的连通分支是一条路，或者是一个回路。 如果如果H的连通分支是一条路的连通分支是一条路P，则它是，则它是M交替路，交替路，也是也是M1交替路。如果交替路。如果P的两个端点均与的两个端点均与M中的边关中的边关联，则联，则P是是M1可扩路。由假设知，可扩路。由假设知，M1是最大匹配，是最大匹配，所以，不存在所以，不存在M1可扩路，得到矛盾。如果可扩路，得到矛盾。如果P的两个的两个端点均与端点均与M1的边关联，那么的边关联

14、，那么P是一条是一条M可扩路与题可扩路与题设矛盾。故设矛盾。故P只能是一个端点与只能是一个端点与M中的边关联，另中的边关联，另一个端点与一个端点与M1中的边关联，这样中的边关联，这样P中属于中属于M的边数的边数与属于与属于M1的边数相等。的边数相等。 离散数学一些特殊的图18 如果如果H的连通分支是一个回路，回路中的的连通分支是一个回路，回路中的边交替地属于边交替地属于M和和M1，因而属于，因而属于M的边数与的边数与属于属于M1的边数相等。的边数相等。 从上面可以看到，从上面可以看到，H中属于中属于M的边与属的边与属于于M1的边的数目相等。再加上既属于的边的数目相等。再加上既属于M又属又属于于

15、M1的边，可以得出：的边，可以得出：M中的边数与中的边数与M1中的中的边数相等。所以边数相等。所以M是最大匹配。是最大匹配。离散数学一些特殊的图19 有了上面的准备以后，就可以进一步讨有了上面的准备以后，就可以进一步讨论如何在二部图中求最大匹配的问题。论如何在二部图中求最大匹配的问题。 设设G= V1,V2,E 是二部图，通常先作是二部图，通常先作G的的一个匹配一个匹配M，再看，再看V1中有没有中有没有M的非饱和点。的非饱和点。如果没有，那么如果没有，那么M肯定是最大匹配；如果有，肯定是最大匹配；如果有，就从这些点出发找就从这些点出发找M增长通路。由增长通路。由M增长通增长通路作出一个更大的匹

16、配。所以，在路作出一个更大的匹配。所以，在G中求最中求最大匹配的关键是寻找大匹配的关键是寻找M增长通路。增长通路。 离散数学一些特殊的图20寻找增长通路的一个有效方法是标记法，其基本思寻找增长通路的一个有效方法是标记法，其基本思想如下：想如下： 设设G= V1,V2,E 是二部图，在是二部图，在G中作一个匹配中作一个匹配M，用，用(* *)标记标记V1中所有中所有M的非饱和点，然后交替地的非饱和点，然后交替地进行以下和两步：进行以下和两步： 选一个选一个V2的新标记过的顶点，比如说的新标记过的顶点，比如说bi，用，用(bi)标记通过标记通过M中的边与中的边与bi邻接且尚未标记过的邻接且尚未标记

17、过的V1的的所有顶点。对所有顶点。对V2所有新标记过的顶点重复这一过程。所有新标记过的顶点重复这一过程。 选一个选一个V1的新标记过的顶点，比如说的新标记过的顶点，比如说ai，用，用(ai)标记不通过标记不通过M中的边与中的边与ai邻接且尚未标记过的邻接且尚未标记过的V2的所的所有顶点。对有顶点。对V1所有新标记过的顶点重复这一过程。所有新标记过的顶点重复这一过程。 离散数学一些特殊的图21 直至标记到一个直至标记到一个V2中的中的M的非饱和点。从的非饱和点。从该顶点倒向追踪到标记有该顶点倒向追踪到标记有(* *)的顶点，就得到的顶点，就得到了一个了一个M增长通路。把增长通路。把M增长通路中所

18、有属于增长通路中所有属于M的边从的边从M中去掉，而把中去掉，而把M可扩路中所有不属可扩路中所有不属于于M的边添加到的边添加到M中，得到一个新的匹配中，得到一个新的匹配M且其所含边数比匹配且其所含边数比匹配M所含的边数多所含的边数多1。对。对M重复上述过程，重复上述过程，直到，直到G中已不存在增长中已不存在增长通路，此时的匹配就是最大匹配。通路，此时的匹配就是最大匹配。离散数学一些特殊的图22 【例例】如图是二部图，求其最大匹配。如图是二部图，求其最大匹配。a1 a2 a3 a4b1 b2 b3 b4 b5离散数学一些特殊的图23 【例例】如图是二部图，求其最大匹配。如图是二部图，求其最大匹配。

19、离散数学一些特殊的图24 解：取二部图的一个匹配解：取二部图的一个匹配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。 离散数学一些特殊

20、的图25 选选V1的新标记过的顶点的新标记过的顶点a3，因为不存在不通，因为不存在不通过过M的边与的边与a3邻接的邻接的V2的顶点，所以不用的顶点，所以不用(a3)标标记记V2的顶点；用的顶点；用(a5)标记标记b3或或b4，假定用，假定用(a5)标标记记b3。如图所示。如图所示。 b3是是M的非饱和点，标记结束。的非饱和点，标记结束。 从从b3倒向追踪到标记有倒向追踪到标记有(* *)的顶点，就得到的顶点，就得到了了M增长通路：增长通路：a4b2a5b3或或a2b2a5b3，取后者。把，取后者。把M增长通路增长通路a2b2a5b3中的边中的边(a5,b2)从从M中去掉，中去掉，而把而把(a2

21、,b2)和和(a5,b3)添加到添加到M中得到新的匹配中得到新的匹配M=(a3,b1), (a2,b2), (a5,b3)，如图，如图9.61所示。所示。离散数学一些特殊的图26离散数学一些特殊的图27 对匹配对匹配M= (a3,b1), (a2,b2), (a5,b3) 再用标记法：再用标记法： 用用(* *)标记标记V1中所有中所有M的非饱和点的非饱和点a1和和 a4。 选选V1的新标记过的顶点的新标记过的顶点a1，用，用(a1)标记不通过标记不通过M的边与的边与a1邻接且尚未标记过的邻接且尚未标记过的V2的所有顶点的所有顶点b1；再用；再用(a4)标记标记b2。 选选V2的新标记过的顶点

22、的新标记过的顶点b1，用，用(b1)标记通过标记通过M的的边与边与b1邻接且尚未标记过的邻接且尚未标记过的V1的所有顶点的所有顶点a3；再用；再用(b2)标标记记a2。 选选V1的新标记过的顶点的新标记过的顶点a2和和a3，V2中已无可标记中已无可标记的顶点。的顶点。 图中已不存在增长通路，所以图中已不存在增长通路，所以M就是最大匹配。就是最大匹配。离散数学一些特殊的图28 【例例】求下图的最大匹配。求下图的最大匹配。 离散数学一些特殊的图29 解：取二部图图解：取二部图图9.62的一个匹配的一个匹配 M=(a2,b2), (a3,b3), (a5,b5)。用。用(* *)标记标记V1中所有中

23、所有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中，得

24、到新的匹配中，得到新的匹配M= (a1,b2),(a2,b4),(a3,b3), (a5,b5) ，如图，如图9.63所示。所示。 对于匹配对于匹配M= (a1,b2),(a2,b4),(a3,b3), (a5,b5)重复上述过重复上述过程，已找不到程，已找不到M可扩路。所以可扩路。所以M就是最大匹配。就是最大匹配。离散数学一些特殊的图30离散数学一些特殊的图31Hall定理 定理定理(Hall定理定理) 设二部图设二部图G=中，中，|V1| |V2|. G中存中存在从在从V1到到V2的完备匹配当且仅当的完备匹配当且仅当V1中任意中任意k 个顶个顶点至少与点至少与V2中的中的k个顶点相邻个顶点

25、相邻(k=1,2,|V1|).由由Hall定理不难证明定理不难证明, 上一页图上一页图(2)没有完备匹配没有完备匹配. Hall定理中的条件称为定理中的条件称为“相异性条件相异性条件”离散数学一些特殊的图32定理定理 设二部图设二部图G=中中, 如果存在如果存在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|)个顶点个