极大平面图的构造方法与几类特殊图的色数分析的综述报告.docx

该【极大平面图的构造方法与几类特殊图的色数分析的综述报告 】是由【niuww】上传分享，文档一共【2】页，该文档可以免费在线阅读，需要了解更多关于【极大平面图的构造方法与几类特殊图的色数分析的综述报告 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。极大平面图的构造方法与几类特殊图的色数分析的综述报告一、极大平面图的构造方法极大平面图是指在平面上没有更多的点和边可以添加而成为平面图的图形。其构造方法可以使用对偶图的特性来完成。对于一个给定的平面图G,我们可以构造它的对偶图G',具体方法为:将每个面对应一个节点,在两个面共享一条边时,对应的节点之间连边。易证,得到的G'也是一个平面图。这个对偶操作保持了平面图的平面性质,即每个面内部没有相交边,而且每个点的度数仍然满足欧拉公式的条件。可以证明的是,原图G是极大平面图的充分必要条件是它的对偶图G'是最小生成树(MST)。最小生成树,是指G的一个子图,该子图中包含了所有点(或顶点),且边的总权值最小。制作G'时,我们使用G的每条边来代表一个权值,并且构建出最小生成树即可。具体地,极大平面图的构造方法如下:。'。'中找到最小生成树T'。'来确定G的边集,从而得到极大平面图G。二、,它可以用二分图的思想来着色。我们将树上分散的点,分成两部分,比如说黑色点和白色点,那么相邻的黑色点和白色点之间连一条边,这样就构成了一张二分图。根据二分图的特性,我们知道这些点可以用两种颜色来染色,而且不会产生冲突,即树的色数为2。-1条边。显然,完全图是一个极大图,因为再添加一条边就会产生一个三度以上的点。完全图的色数为n,这是因为每个点都要被涂上一种不同于邻居的颜色。。根据Konig定理,偶图的最小点覆盖等于最大匹配。加上定理可以推出每个最小覆盖的点集,至少和最大匹配的边集一样多。因此,对于偶图来说,只需要先获得它的最大匹配,然后用两种颜色来染色,这样就能得到最小色数。,且边不相交的图形,它的色数是有一个上界的,umber<=4。这是因为一个平面图中不可能存在一个7个点构成的圆,因为这样会导致相邻的三个点位于圆上,从而构成奇环图。因此,不存在奇环图,平面图就可以用4种颜色来染色。