十几种图的介绍ndzhou

《十几种图的介绍ndzhou》由会员分享，可在线阅读，更多相关《十几种图的介绍ndzhou（47页珍藏版）》请在金锄头文库上搜索。

1、10.3二部图及匹配 定义：设无向图 。如果存在V的划分 V1,V2，使得Vi中的任何两个结点都不相邻 ，则称G为二部图二部图，V1和V2称为G的互补结点子集互补结点子集 。 二部图没有自圈。与二部图的一条边关联的两个 结点一定分属于两个互补结点子集。一般来说， 二部图的互补结点子集的划分不是唯一的。 1/135 二部图 一个无向图如果能画成上面的样式，很容易判 定它是二部图。有些图虽然表面上不是上面的 样式，但经过改画就能成为上面的样式，仍可 判定它是一个二部图 如图中（a）可改画成图（b），图（c）可改画成 图（d）。可以看出，它们仍是二部图。 2/135 二部图 定理：设G是阶大于1的无

2、向图。G是二部图，当 且仅当G的所有回路长度均为偶数。 证：先证明必要性。设V1和V2是二部图G的互补结 点子集，C是G的长度为m的回路。取v0为C的某一 结点，在C中存在从v0至v0长度为m的路径，设为 v0e1v1vm-1emv0，不妨设 ，则对于一切的im ， ，当且仅当i为奇数， 与v0相邻， 故 ，则m-1是奇数，所以m为偶数。 再证充分性。 3/135 二部图 设 是连通的。任取 ，做 且vi 到v0的距离为偶数， ，则 必连接V1中的 一点和V2中的一个点。因为若 或 且e连接 u和v，则当v0到u的测地线p1和v0到v的测地线p2无公共 结点时，p1，p2和e构成长度为奇数的回

3、路，与题设矛 盾。当p1和p2有公共结点时，设最后一个公共点为v ，v将p1分为p1和p1，将p2分为p2和p2，且p1和p2均 为v0到v的测地线，长度相等。因为p1和p2的长度均为 偶数或均为奇数，故p1和p2的长度有相同的奇偶性 ，p1，p2和e构成长度为奇数的回路，与题设矛盾。 若G不是连通的，可以用以上办法证明G的每个分支 是二部图，则G也是二部图。 得证。 4/135 二部图 利用上面定理可以很快地判断出图中的（a ）、（c）是二部图，而（b）则不是二部图 。 例： 5/135 二部图 定义：设V1和V2是简单二部图G的互补结点子 集，如果V1中的每个结点与V2中的每个结点相 邻，

4、则称G为完全二部图。 我们把互补结点子集分别包含m和n个结点的完 全二部图记为km,n。 6/135 二部图 7/135 匹配 8/135 匹配 定义：设无向图 ， 。 (1)如果E不包含自圈，并且E中的任何两条边都不 邻接，则称E为G中的匹配匹配。 (2)如果E是G中的匹配，并且对于G中的一切匹配 E，只要 必有E=E，则称E为G中的极极 大匹配大匹配。 (3)G中的边数最多的匹配称为G中的最大匹配最大匹配。 (4)G中的最大匹配包含的边数称为G的匹配数匹配数。 最大匹配一定是极大匹配，而极大匹配不一定 是最大匹配。在一个无向图中，可以有多个极 大匹配和最大匹配。 9/135 匹配 例： 极

5、大匹配： 最大匹配 ： 匹配数：3 10/135 完美匹配 定义：设V1和V2是二部图G的互补结点子集。如果 G的匹配数等于|V1|，则称G中的最大匹配为V1到V2 的完美匹配完美匹配。 只有|V1|V2|时可能存在从V1到V2的完美匹配。但这 个条件并不是充分条件。 上图不存在V1到V2的完美匹配。 11/135 完美匹配 定理：设V1和V2是二部图G的互补结点子集。存在V1 到V2的完美匹配，当且仅当对于任意 , 其中 当二部图的结点数目比较大时，上述定理用起 来不太方便，下面给出存在完美匹配的一个充分 条件，判断二部图是否存在完美匹配时，可以先 用这个充分条件，如果得不出结论，再用上述定

6、 理。 12/135 完美匹配 定理：设V1和V2是二部图G的互补结点子集，t是 正整数。对于V1中的每个结点，在V2中至少有t个 结点与其邻接。对于V2中的每个结点，在V1中至 多有t个结点与其邻接。则存在V1到V2的完美匹配 。 证： 因为去掉平行边不会影响V1到V2的完美匹 配的存在性，因此不妨假设G是简单图。任 取 ，设 .如果边e与S中的某结点关 联，则必有 中的结点与e关联，所以 。故 ， 则 。根据前一个定理，存在V1到V2的完美 匹配。 13/135 二部图 例：有q个委员会 ，要从每个委员会的委员 中选出该委员会的主任，并限定任何人不得兼任一 个以上委员会的主任。问是否可能按

7、照要求选出主 任？ 思路：把这个问题化为图论的问题。令V1是所有委 员会的集合，V2是参加这些委员会的人的集合，若 某人m是委员会C的委员，则在m和C之间连一条边 。这样就构成了以V1和V2为互补结点子集的二部图 ，可能按照要求选出主任，当且仅当存在V1到V2的 完美匹配。 每个委员会至少有t个委员，每个委员至 多参加t个委员会，这时主任是可以选出的。 14/135 10.4平面图 在生活中，通常有这样一类问题，涉及 到图的平面性的研究，比如大家都知道 的印刷线路板的布线问题。近些年来， 大规模集成电路的发展，进一步促进了 图的平面性的研究。 15/135 平面图 例：一个工厂有3个车间 和3

8、个仓库 。为 了工作需要，车间 与仓库 之间将设专 用 的车道。为避免发生车祸 ，应尽量减少 车道的交叉点，最好是没有交叉点，这 是否可能？ 16/135 平面图 定义：在一个平面上，如果能够画出无向图G的图 解，其中没有任何边的交叉，则称图G是个平面图 ；否则，称G是非平面图。 例：将下列非平面图转化为平面图。 17/135 平面图 18/135 平面图 根据平面图的定义，非循环图显然是平面图。 故，研究图的平面性问题，只需要限制有回路 的一类图即可。判别方法是： （1）对于有回路的图找出一个长度尽可能大 的且边不相交的基本回路。 （2）将图中那些相交于的边，适当放置在已 选定的基本圈内侧或

9、外侧，若能避免除结点之 外边的相交，则该图是平面图；否则，便是非 平面图。 19/135 平面图 设 是能够画于平面上的图解中的无向图 ，并且设 是图中的任何基本循环。此外，设 x=v1v3和x=v2v4是图G中的任意 两条基本路径。在左图中给出了两 种可能的结构。显然，x和x或都在 基本循环的内部，或者都在基本循 环的外部，当且仅当G是个非平面 图。因为这时基本路径x和x是相互 交叉的。 20/135 平面图 例：设有一个电路，它含有两个结点子集V1和V2 ，且有|V1|=|V2|=3。用导线把一个集合中的每一个 结点，都与另外一个集合中的每一个结点连通， 如下图所示。试问，是否有可能这样来

10、接线，使 得导线相互不交叉。对于印刷电路，避免交叉具 有实际意义。 21/135 平面图 解：这个问题等价于判定上图是否是个平面图。可以 看出，给定图中有一个基本循环 ，如下 列左图所示。试考察三条边 ，上 述每条边或是处于循环C的内部，或是处于C的外部 。显然，三条边中至少有两条边同时处于的同一侧， 因此避免不了交叉，如下列右图所示。故给定的图是 非平面图。 22/135 库拉托夫斯基图 上图跟下图图（a）等价，由于已经证明了上图 是非平面图，因此下图（a）也是非平面图。同 样方法 ，知（b）也是非平面图。图（a）和（b ）都称为库拉托夫斯基图。 23/135 库拉托夫斯基图 如上图（a）所

11、示，试往图中的一条边上，插 上一个新的次数为2的结点，把一条边分解成 两条边，则不会改变给定图的平面性。另外， 如图(b)所示，把联系于一个次数为2的结点的 两条边，合并成一条边，也不会改变给定图的 平面性。 （a） （b） 24/135 库拉托夫斯基图 定义：设G1和G2是两个无向图。如果G1和G2是同构 的，或者是通过反复插入和(或)删除次数为2的结点 ，能够把G1和G2转化成同构的图，则称G1和G2在次 数为2的结点内是同构的。 25/135 库拉托夫斯基图 库拉托夫斯基定理 ：设G是一个无向图。图G 中不存在任何与下图的两个图同构的子图，当 且仅当图G是个平面图。 26/135 库拉托

12、夫斯基图 例：判断下图是否是可平面图。 27/135 多边形图 定义：多边形的图的归纳法定义如下： 一个多边形是一个多边形的图。设 是一 个多边形的图，再设 是长度为 的任何基本路经，它不与图G中任一路径交叉，且 有 ，但是对于 来说， 。于 是，由图G和P所构成的图 也是一个 多边形的图，其中 28/135 多边形图 多边形的图是个平面图(或多重边图，因为允许长度 为2的循环存在)，它能够把平面划分成数个区域， 每一个区域都是由一个多边形定界。 29/135 多边形图 定义：由多边形的图定界的每一个区域，都称为图 G的面面。 定义：包含有多边形的图G的所有面的边界的多边 形，称为G的极大基本

13、循环极大基本循环。 例：上页图中的循环 就是该多边形图 的极大基本循环。 给定图G的极大基本循环外侧的无限区域，是另 外一个面，一般称为G的无限面。事实上，如果 把图G的图解画在球面上，则G的无限面与其它 的有限面并没有什么区别。 定义：如果图G的两个面共有一条边，则称这 样的两个面是邻接的面邻接的面。 30/135 多边形图 定理：(欧拉公式)设 是个具有k个面(包括 无限面在内)的(n,m)多边形的图。则 证：对于面的数目k用归纳法证明。面的最少数目( 包括无限面在内)是2。在这种情况下，图G是个多边 形，因而应有n=m。这样，有n-m+k=2。 假设对于具有k-1个面(包括无限面)的图来

14、说，定理 成立。 往证对于具有k个面(包括无限面)的图，定理亦成 立。为此，首先构成具有k=k-1个面的(n,m)图G ，然后附加上一条长度为l1的基本路径，它与 G仅共有两个结点，则 31/135 多边形图 根据归纳假设可知， ，因此应有 得证。 32/135 对偶图 定义：设平面图G有k个面 。对每个面Fi 在其内部指定一个新顶点fi；对Fi和Fj公共的边，指 定一条新边fi,fj与其相交。这些新顶点和新边组成 的图用来表示G*，并称G*为图G的对偶图。 由G求G*的方法：对于G中的任何一个面Fi，给 G*指定一个结点fi，对于面Fi和Fj所共有的一条 边，给G*指定一条边fi,fj。实际

15、上，首先在Fi 内指定每个结点fi，并且用连通fi和fj的一条边， 去交叉Fi和Fj所共有的边，这样就可求得对偶图 G*。 33/135 对偶图 例：给定下图的对偶图。 结论：每一个多边形的 图G，其对偶图G*也必 定是一个多边形的图， 而且G和G*是互为对偶 的。 34/135 自对偶图 定义：如果多边形的图G的对偶G*同构于G，则称G 是自对偶图。 与平面图相关的应用：四色问题。是否可用 四种颜色对任何平面图形的区域染色，使得 任何两个邻接区域，包括无限区域都不会呈 现相同的颜色？ 35/135 图着色 平面图的着色问题，最早起源于地图的着色。在 一张地图中，若相邻国家着以不同的颜色，那么 最少需要多少种颜色呢？1840年，德国数学家麦 比乌斯(A.F.Mbius)在他的讲稿中第一次提出了确 信用四种颜色可以对地图着色的问题(以下简称四 色猜想)。1879年肯普(Kempe)给出了这个猜想的 第一个证明，但到1890年希伍德(Hewood)发现肯 普证明