《几种图的介绍-2nd-zhou》由会员分享，可在线阅读，更多相关《几种图的介绍-2nd-zhou（47页珍藏版）》请在金锄头文库上搜索。
1、10.3二部图及匹配定义：设无向图 。如果存在V的划分 V1,V2，使得Vi中的任何两个结点都不相邻 ，则称G为二部图二部图，V1和V2称为G的互补结点子集互补结点子集 。 二部图没有自圈。与二部图的一条边关联的两个 结点一定分属于两个互补结点子集。一般来说， 二部图的互补结点子集的划分不是唯一的。 1/135Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client P
2、rofile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.二部图一个无向图如果能画成上面的样式，很容易判 定它是二部图。有些图虽然表面上不是上面的 样式，但经过改画就能成为上面的样式，仍可 判定它是一个二部图如图中（a）可改画成图（b），图（c）可改画成 图（d）。可以看出，它们仍是二部图。2/135Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.
3、0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.二部图定理：设G是阶大于1的无向图。G是二部图，当 且仅当G的所有回路长度均为偶数。 证：先证明必要性。设V1和V2是二部图G的互补结 点子集，C是G的长度为m的回路。取v0为C的某一 结点，在C中存在从v0至v0长度为m的路径，设为 v0e1v1vm-1emv0，不妨设 ，则对于一切的i的顶点着色，即找到从结点集V到 色
4、集C=c1，c2，cn上一个映射，使对任意边 vi，vjE均有(vi)(vj)，即对G的每个结点指派 一种颜色，使得相邻结点都有不同的颜色。37/135Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pt
5、y Ltd.图着色定义：对于平面图G着色时，需要的最少颜色数称 为G的着色数，记为(G)。四色定理：对于任何平面图G，有(G)4。38/135Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd
6、.图的着色数将图的着色数从平面图推广到所有图中，判断下图 的着色数。39/135Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.图的着色数40/135Evaluation only.Eva
7、luation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.图的着色数41/135Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Clien
8、t Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.图的着色数总结： 图G只有孤立结点时，即G是平面图， (G)=1. 图G为n阶完全图时，(G)=n. 若图G是n个结点回路时，则当n为偶数 ，(G)=2；当n为奇数，(G)=3。 若图G是二部图时， (G)=2.42/135Evaluation only.Evaluation only. Cre
9、ated with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.求图的着色数设图G=，且vi，vj是G中不相邻两 结点。现引进下面二个符号。 表示G中加上一条连接vi和vj的边所得到 的图。显然 与G+(vi，vj)相同。 表示把vi和vj两结点收缩为一个结点z所 得到的图，
10、即图G中凡是与vi和vj关联的边 都改为与z关联。(G)=min( )，( )。43/135Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.求图的着色数例：求下图G的着色数。注意：已知的最
11、好的求图的着色数的算法（对 图的顶点个数来说）具有指数的最坏情形时间 复杂度。即使是求图的色数的近似值也是很难 的。44/135Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.图着色的应用
12、图着色在与调度和分配有关的问题中有多种应用（ 注意：由于不知道图着色的有效算法，所以并不能 得出调度和分配的有效方法），这里仅给出一个重 要的例子：安排期末考试。安排期末考试问题：如何安排一个大学里的期末考 试，使得没有学生要同时考两门试。图模型：用顶点表示科目，若有学生要考两门 试，则在表示考试科目的两个顶点之间用边连 接。用不同颜色来表示期末考试的不同时间段 ，考试的安排就对应于图的着色问题。45/135Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.
13、0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.图着色的应用例：安排七门考试，假定科目从1到7编号，下列各 对科目的考试都有学生要同时参加：1和2，1和3，1 和4，1和7，2和3，2和4，2和5，2和7，3和4，3和6 ，3和7，4和5，4和6，5和6，5和7，6和7。46/135Evaluation only.Evaluation only. Created with
14、Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.作业 11，12，15，17 Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.
