离散数学结构 第17章 平面图及图的着色习题
- 格式:doc
- 大小:120.00 KB
- 文档页数:7
图论中的平面图与染色问题图论是数学的一个分支,研究的是图的性质和图之间的关系。
在图论中,平面图与染色问题是重要的研究方向。
一、平面图平面图是指可以在平面上画出的图,其中任意两条边都不相交,任意两个顶点之间都只有一条边相连。
平面图可以用来描述许多实际问题,如地图、电路等。
在平面图中,有一个重要的定理,即欧拉定理。
欧拉定理是数学家欧拉在1736年提出并证明的,它给出了平面图中顶点数、边数和面数的关系。
根据欧拉定理,对于连通的平面图,满足公式:V - E + F = 2,其中V表示顶点数,E表示边数,F表示面数。
二、染色问题染色问题是图论中的一个经典问题,即给定一个图,如何用有限种颜色对图的各个顶点进行染色,使得相邻的顶点之间的颜色不相同。
这是一种常见的应用问题,如地图着色、课程表安排等。
在染色问题中,有一个重要的定理,即四色定理。
四色定理是染色问题中的一个著名定理,它指出任何平面图都可以用至多四种颜色对其顶点进行染色,使得相邻的顶点颜色不同。
三、平面图与染色问题的关系平面图与染色问题之间有着紧密的联系。
通过合理的染色方案,可以将一个平面图的顶点进行染色,满足相邻顶点颜色不同的要求。
同时,染色问题的解法与平面图的结构和性质也有关系。
在研究平面图与染色问题时,可以通过绘制平面图的平面嵌入图来分析和求解染色问题。
平面嵌入图是平面图在平面上的一种表示形式,可以把平面图的顶点和边绘制在平面上,形成一种更加直观的图形。
在解决染色问题时,可以借助平面嵌入图的结构和特性,通过一定的算法进行染色。
例如,可以利用贪心算法对顶点进行依次染色,确保相邻顶点染不同的颜色。
四、应用举例平面图与染色问题在实际中有广泛的应用。
一个典型的例子是地图着色问题。
在地图上,每个国家或地区可以用一个顶点表示,国家或地区之间的边表示它们的相邻关系。
通过对地图进行染色,可以实现相邻国家或地区的颜色不同,从而更加方便地辨认。
另一个例子是课程表安排问题。
离散数学着色基础知识离散数学是数学的一个重要分支,它关注离散的数学结构和对象。
在离散数学中,图论作为一个重要的研究领域,着色问题受到广泛的关注。
着色问题是指给定一个图的顶点或边,用不同的颜色给它们进行标记的问题。
本文将介绍离散数学中的着色基础知识,包括图的着色、四色定理以及一些常见的着色应用。
1. 图的着色在图的着色问题中,我们通常要求相邻的顶点或边不能使用相同的颜色。
对于给定的图,我们可以用一个函数来为每个顶点或边赋予一个颜色。
这个函数被称为着色函数。
如果对于每个相邻的顶点或边,它们被赋予了不同的颜色,那么这个着色函数就满足着色条件。
图的着色问题可以分为顶点着色和边着色两种情况。
在顶点着色中,我们使用不同的颜色为图中的每个顶点上色;而在边着色中,我们使用不同的颜色为图中的每条边上色。
通常情况下,我们更关注的是顶点着色问题。
2. 四色定理四色定理是图论中的一个著名的定理,它指出任意一个平面图都可以用四种颜色给其顶点进行着色,使得任意相邻的顶点使用不同的颜色。
具体地说,对于任意一个平面图,我们可以用四种颜色对其顶点进行着色,并且一定能够满足着色条件。
这个定理的证明非常复杂,涉及到大量的数学推理和计算。
它的证明分为两个步骤:首先,通过对所有可能的情况进行穷举和排除,证明了五种颜色是充分的;然后,通过反证法证明了四种颜色就足够了。
四色定理在实际应用中具有重要的意义。
它可以用来解决地图着色问题,即给定一幅地图,用尽可能少的颜色对每个行政区域进行着色,使得相邻的行政区域颜色不同。
四色定理的证明为解决这个问题提供了理论支持。
3. 着色的应用着色问题在现实生活中有许多应用。
除了地图着色问题外,还有课程表着色问题、时间表着色问题等等。
在课程表着色问题中,我们需要为学校的每个班级安排一个课程表,并且要求相邻时间段的课程使用不同的颜色。
这个问题可以转化为图的着色问题,其中图的每个顶点代表一个时间段,边代表时间段的相邻关系。
图是离散数学中的重要概念,而平面图和平面图的着色是图论中的两个关键概念。
平面图是指在平面上绘制的图形,使得图中的边不会相交。
平面图的着色是指对平面图中的顶点进行染色,且相邻的顶点不会被染成相同的颜色。
平面图的概念最早由欧拉在1736年提出。
他发现,如果一个图是可以在平面上绘制而不会边相交的,那么这个图是一个平面图。
欧拉还引入了一个重要的公式,即欧拉定理,它描述了平面图中的顶点、边和面的关系:V - E + F = 2,其中V代表顶点数,E代表边数,F代表面数。
对于平面图的着色问题,四色定理是一个非常重要的结果。
四色定理指出,任何一个平面图,在不考虑多重边和自环的情况下,最多只需要使用四种颜色就能够对图的顶点进行染色,使得相邻的顶点不会有相同的颜色。
这个定理在1976年被由英国数学家Tomás Oliveira e Silva使用计算机辅助证明,被认为是图论史上的一大突破。
对于平面图的着色,有一种特殊的染色方法叫做四色标号。
四色标号是指对于任意一个平面图,都可以给图中的每个顶点赋予一个自然数,使得相邻的顶点之间的差值不超过3。
这种染色方法保证了相邻的顶点不会被染成相同的颜色,同时最多只需要使用四种颜色。
平面图的着色不仅在图论中有着重要的应用,同时在现实生活中也有很多实际的应用。
比如,考虑地图上的城市,如果我们希望将城市标记成不同的颜色,以表示它们的关系,那么可以利用平面图的着色来实现。
另外,平面图的着色还有很多其他的实际应用,比如在工程规划中用于规划电路的布线、在计算机科学中用于处理图像等等。
总之,离散数学中的图的平面图与平面图的着色是图论中的两个重要概念。
平面图是指在平面上绘制的图形,使得边不会相交;平面图的着色是指对平面图中的顶点进行染色,且相邻的顶点不会被染成相同的颜色。
四色定理是平面图着色的重要结果,它指出任意一个平面图可以使用最多四种颜色进行着色。
平面图的着色在现实生活中有着广泛的应用,是离散数学中的一个重要研究领域。
离散数学第二版最全课后习题答案详解离散数学是现代数学的一个重要分支,它在计算机科学、信息科学、电气工程等领域都有着广泛的应用。
对于学习离散数学的同学们来说,课后习题的解答是巩固知识、加深理解的重要环节。
本文将为您提供离散数学第二版的最全课后习题答案详解,希望能对您的学习有所帮助。
在开始讲解具体的习题答案之前,让我们先简要回顾一下离散数学的主要内容。
离散数学包括集合论、数理逻辑、图论、代数结构等几个部分。
集合论是离散数学的基础,它研究集合的性质、运算和关系。
在集合论的习题中,常见的问题包括集合的表示、集合的运算(并集、交集、补集等)、集合的包含关系以及集合的基数等。
例如,有这样一道习题:设集合 A ={1, 2, 3},B ={2, 3, 4},求 A ∪ B 和A ∩ B。
答案是:A ∪ B ={1, 2, 3, 4},A ∩ B ={2, 3}。
这是因为并集是包含两个集合中所有元素的集合,而交集是同时属于两个集合的元素组成的集合。
数理逻辑是研究推理和证明的工具,它包括命题逻辑和谓词逻辑。
在数理逻辑的习题中,需要掌握命题的符号化、逻辑公式的等价变换、推理规则的应用等。
比如,给出这样一个命题:“如果今天下雨,那么我就不去公园”,将其符号化。
我们可以设“今天下雨”为 P,“我去公园”为 Q,那么这个命题可以符号化为P → ¬Q。
图论是研究图的性质和应用的分支。
图的概念在计算机网络、交通运输等领域有着重要的应用。
图论的习题常常涉及图的表示、顶点的度、路径、连通性、图的着色等问题。
假设有这样一道题:一个无向图有 10 个顶点,每个顶点的度都为 6,求这个图的边数。
根据顶点度数之和等于边数的两倍这个定理,我们可以计算出边数为 30。
代数结构则包括群、环、域等概念,在这部分的习题中,需要理解和运用代数结构的定义和性质来解决问题。
接下来,我们具体来看一些习题的详细解答。
例 1:设集合 A ={x | x 是小于 10 的正奇数},B ={x | x 是小于 10 的正偶数},求 A B。
离散数学中的图着色与图分割离散数学是数学的一个分支,它研究的是离散的结构和对象。
在离散数学中,图论是一个非常重要的领域。
而图着色与图分割是图论中的两个基本概念。
一、图着色图着色是指给定一个图的每个顶点分配一种颜色,并且要求相邻的顶点不能有相同的颜色。
这个问题可以看作是一种涂色问题,我们希望用最少的颜色来对图的顶点进行着色。
1.1 色数与染色多项式图的色数是指给定一个图所需的最少颜色数。
一个图的色数通常用符号χ(G)表示。
图的染色多项式是对于给定的图G,它与对应的染色问题有关。
1.2 四色问题四色问题是图论中一个经典的问题,它说的是任何平面地图都可以用四种颜色进行着色,使得相邻的地图区域颜色互不相同。
这个问题虽然在1976年得到了解决,但它的证明过程非常复杂,需要运用大量的数学定理和方法。
二、图分割图分割是指将一个图分割成多个不相交的子图。
图分割在图论和组合优化中具有广泛的应用。
2.1 最小割最小割是指可以将图分割成两个不相交的子图,并且两个子图之间的边的权重之和最小。
最小割问题可以通过最大流最小割定理来解决。
2.2 图分割算法图分割算法是指用于将图分割成多个子图的算法。
常用的图分割算法包括谱图分割算法、k-means算法等。
这些算法可以根据图的特点和需求来选择合适的方法。
三、图着色与图分割的应用3.1 地图着色图着色在地图着色中有着广泛的应用。
通过给地图的每个区域进行着色,可以实现不同区域之间的边界清晰,便于观察和分析。
3.2 电路布线在电路布线中,图着色可以用于解决信号线的冲突问题,保证信号线之间不会相互干扰。
3.3 图像分割图分割在图像处理中有着重要的应用。
通过将图像分割成多个子图,可以实现目标检测、边缘提取等算法的实现。
四、总结离散数学中的图着色与图分割是图论中的两个重要概念。
图着色是将图的顶点着色的过程,目标是用尽量少的颜色进行着色。
图分割是将图分割成多个子图的过程,通过选择合适的算法可以得到满足要求的子图。
在离散数学中,图是一种用于描述对象之间关系的数学模型。
它由一组顶点和连接这些顶点的边组成。
图的理论在许多领域中都得到了广泛的应用,如计算机科学、物理学、社会学等。
本文将重点讨论图的平面图和图的染色。
首先,我们来了解一下图的平面图。
一个平面图是指可以画在二维平面上,使得边不相交的图。
换句话说,平面图可以在纸上用线条表示,且不会发生交叉。
简单来说,平面图就是可以被画在一个平面上而不会出现边交叉的图。
平面图的研究起源于欧拉在1736年所提出的著名的“柯尼斯堡七桥问题”。
欧拉通过研究柯尼斯堡的七座桥的布局问题,引入了欧拉定理,该定理指出:一个无向图是平面图,当且仅当它没有割边(割边是指当移除一个边时,图会被分为两个独立的部分)。
欧拉定理揭示了平面图的基本特性,为后来的研究提供了理论基础。
与平面图相关的是图的染色问题。
图的染色问题是指给图的每个顶点分配一个颜色,使得任意两个相邻顶点具有不同的颜色。
这个问题源于地图染色问题,即如何将地图上的区域用不同颜色进行染色,使得任意两个相邻区域颜色不同。
图的染色问题在实际应用中具有重要意义,如频道分配、时间表设计、DNA测序等。
对于一般的图,图的染色是一个NP-完全问题,很难找到有效的算法。
但是对于平面图,有一个非常重要的定理——四色定理。
四色定理指出:任何平面图都可以用四种颜色对顶点进行染色,使得任意两个相邻顶点具有不同的颜色。
四色定理是图论中的一个重要突破,它的证明历经了200多年的努力,在1976年由Kenneth Appel和Wolfgang Haken首次给出了一个检查过程,使用了计算机的辅助。
以“四色定理”为基础,图的染色问题在实际中也有许多应用。
例如,在地图着色中,四色定理告诉我们任何地图只需要用四种颜色就可以在每两个相邻区域之间使用不同的颜色进行染色。
这在地理信息系统中有着广泛的应用。
另一个例子是频道分配,可以使用图的染色算法来确保无线电频段之间没有干扰。
离散数学中的图着色与图分割图着色和图分割是离散数学中重要的概念和应用之一,它们在图论、计算机科学和其他领域中起着关键作用。
本文将介绍图着色和图分割的概念、方法和应用。
一、图着色图着色是指为图的顶点或边分配颜色的过程。
在图着色中,相邻的顶点或边不能具有相同的颜色。
这个问题在实际生活中有着广泛的应用,比如地图着色、课程表的编排等。
1.1 图的色数图的色数是指对图中的顶点进行着色,使得相邻的顶点具有不同的颜色所需的最小颜色数。
显然,图的色数至少为1,即必须至少使用一种颜色来对图进行着色。
对于简单图,其色数常被称为图的固有色数。
1.2 图的着色问题图的着色问题是指寻找一种合理的图着色方案的问题。
在计算复杂性理论中,图的着色问题被证明是一个NP-难问题,即很难找到一个高效的算法来求解。
二、图分割图分割是指将一个图分割成若干个互不相交的子图的过程。
图分割在图像处理、网络分析等领域中有广泛的应用,常用于物体识别、社区检测等任务。
2.1 最小割最小割是图分割中的一个重要概念。
给定一个图和两个顶点集合S和T,最小割是指将图分割成S和T两个子图,并且使得两个子图之间的边的权重之和最小。
最小割算法被广泛应用于图像分割、图像压缩等领域。
2.2 图分割算法图分割算法的目标是找到一个好的分割方案,使得分割后的子图具有一定的性质。
常用的图分割算法包括谱聚类、最大流最小割算法等。
三、图着色与图分割的应用图着色和图分割在实际应用中有着广泛的应用。
3.1 地图着色地图着色是图着色的一个典型应用。
在地图着色中,每个国家代表一个顶点,相邻的国家之间的边代表它们之间的接壤关系。
要求对地图进行着色,使得相邻的国家具有不同的颜色,以便区分它们。
3.2 图像分割图像分割是图分割的一个重要应用。
图像分割可以将图像中不同的对象或者区域分离出来,常用于目标检测、物体识别等任务。
3.3 社交网络分析社交网络分析中的社区检测问题可以看作是图分割的一个应用。
[Δ](G)=8且不含4-圈的平面图的完备染色平面图是图论中的一个重要概念,指的是可以画在平面上而不会使边发生交叉的图。
平面图在实际生活中有着广泛的应用,比如地图、电路板等。
而对于平面图的染色问题,一直以来都是图论研究的重要方向之一。
在这篇文章中,我们将讨论一个关于平面图的染色问题,即【[Δ](G)=8且不含4-圈的平面图的完备染色】。
让我们来解释一下题目中的一些概念。
这里的【[Δ](G)=8】表示图G中的每个顶点的度数都不超过8,即每个顶点的邻接顶点数不超过8。
而不含4-圈则表示图G中不存在长度为4的圈,也就是说,图G中不存在四个顶点构成的环。
完备染色则是染色问题中的一种特殊情况,指的是对于给定的图G,如果能够给图中的每一个顶点染上一个颜色,使得相邻的顶点颜色不同,且使用最少的颜色数,那么这样的染色方式就是完备染色。
接下来,我们将讨论如何对这样的平面图进行完备染色。
我们需要知道一个关于完备染色的定理,即Brooks定理:如果一个简单图G(即没有自环和重边的图)的最大度数不超过3(即[Δ](G)<=3),那么G的完备染色数不超过最大度数+1。
但是对于最大度数大于3的图,Brooks定理并不成立。
所以对于【[Δ](G)=8且不含4-圈的平面图的完备染色】这样的问题,我们需要采用其他的方法进行求解。
一种常见的方法是利用图的特殊结构和特性,来找到一种能够满足完备染色条件的染色方式。
在这里,我们可以考虑利用平面图的特殊性质来进行染色。
平面图有一个重要的性质是它可以被嵌入在平面上,而且不存在交叉的边。
这意味着我们可以通过不同的方法来找到一种满足条件的完备染色方式。
一种方法是通过对平面图的平面嵌入进行染色。
通过适当的平面嵌入方式,我们可以将平面图中的每个顶点映射到平面上的不同区域,然后在每个区域中进行染色。
这样可以保证相邻的顶点被映射到不同的区域,从而满足完备染色的条件。
另一种方法是利用平面图的特殊结构来进行染色。
2017年11月上交的离散数学形考任务一本课程的教学内容分为三个单元,其中第三单元的名称是(A ).选择一项:A. 数理逻辑B. 集合论C. 图论D. 谓词逻辑题目2答案已保存满分10.00标记题目题干本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合,其中第2章关系与函数中的第3个知识点的名称是(D ).选择一项:A. 函数B. 关系的概念及其运算C. 关系的性质与闭包运算D. 几个重要关系题目3答案已保存满分10.00标记题目题干本课程所有教学内容的电视视频讲解集中在VOD点播版块中,VOD点播版块中共有(B)讲.选择一项:A. 18B. 20C. 19D. 17题目4答案已保存满分10.00标记题目题干本课程安排了7次形成性考核作业,第3次形成性考核作业的名称是( C).选择一项:A. 集合恒等式与等价关系的判定B. 图论部分书面作业C. 集合论部分书面作业D. 网上学习问答题目5答案已保存满分10.00标记题目题干课程学习平台左侧第1个版块名称是:(C).选择一项:A. 课程导学B. 课程公告C. 课程信息D. 使用帮助题目6答案已保存满分10.00标记题目题干课程学习平台右侧第5个版块名称是:(D).选择一项:A. 典型例题B. 视频课堂C. VOD点播D. 常见问题题目7答案已保存满分10.00标记题目题干“教学活动资料”版块是课程学习平台右侧的第( A )个版块.选择一项:A. 6B. 7C. 8D. 9题目8答案已保存满分10.00标记题目题干课程学习平台中“课程复习”版块下,放有本课程历年考试试卷的栏目名称是:(D ).选择一项:A. 复习指导B. 视频C. 课件D. 自测请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划,学习计划应该包括:课程性质和目标(参考教学大纲)、学习内容、考核方式,以及自己的学习安排,字数要求在100—500字.完成后在下列文本框中提交.解答:学习计划学习离散数学任务目标:其一是通过学习离散数学,使学生了解和掌握在后续课程中要直接用到的一些数学概念和基本原理,掌握计算机中常用的科学论证方法,为后续课程的学习奠定一个良好的数学基础;其二是在离散数学的学习过程中,培养自学能力、抽象思维能力和逻辑推理能力,解决实际问题的能力,以提高专业理论水平。
§5.6 平面图与图地着色 习题5.61. 假定一个连通平面图有8个顶点,每个顶点地度数都为3。
请问,这个图地平面嵌入将平面分成多少个面?解 根据条件有8=p ,122/83=⨯=q ,从而根据欧拉定理有62=+-=p q f 。
2.设G 是具有k 个连通分图地)(q p ,平面图地一个平面嵌入,其面数为f ,证明:1+=+-k f g p解 下面用数学归纳法证明如下:(1)1=k 时即为欧拉公式,所以成立。
(2)假设m k ≤时公式成立。
(3)当1+=m 时,将图G 看成两个图1G 与2G 地并,其中1G 为一个连通分图, 2G 为其余m 个连通分图地并,根据上面地假设,对图1G 与2G 有:11111+=+-f q p ,1222+=+-m f q p ,将上两式相加得: 1)1()1()()(212121++=-+++-+m f f q q p p注意到图1G 与2G 共用一个外部面,我们即得1+=+-k f g p 。
3.假定一个)(q p ,图是连通地平面二部图,且p ≥3,则q ≤42-p 。
证;由于二部图中每个回路地长度都是偶数。
当p ≥3时,即每个面地围数至少是4。
据定理,2q ≥4f=4(2-p+q) 从而q ≤42-p 。
4.图5.42地4个图是平面图吗?如果是,给出一个平面嵌入;如果不是,找出与5K 或K 3,3同胚地子图。
图5.42 习题4地图解 图(1),(2),(4)改画如下:从而知图(1),(2)是可平面图,图(4)是5阶完全图5K ,从而是非可平面图。
图(3)也是一个非可平面图,可用库拉托斯基定理证明如下:5.一个简单图地交叉数是指在平面里画这个图且不允许任何三条边在同一点交叉时,各边交叉地最少次数。
求以下非平面图地交叉数:3,3K , 5K , 6K , 7K , 4,3K , 4,4K , 5,5K解:3,3K 地交叉次数是15K 地交叉次数是56K 地交叉次数是107K 地交叉次数是184,3K 地交叉次数是84,4K 地交叉次数是115,5K 地交叉次数是166.下面地算法可以用来为简单图点着色。
离散数学中的染色问题在离散数学领域中,染色问题是一类十分具有挑战性的问题,它涉及到对图的结点或边进行染色的方式与规则。
本文将介绍染色问题的基本概念、常见模型以及算法应用等内容。
1. 染色问题简介染色问题是指在给定的图中对结点或边进行染色,使得相邻结点或边之间的颜色不相同。
染色问题在图论和计算机科学等领域具有重要意义,它可以应用于时间表排列、任务分配、频率分配等实际问题。
2. 图的染色模型在染色问题中,最常用的模型是顶点染色和边染色。
2.1 顶点染色顶点染色指的是对图的每个结点进行染色,使得相邻结点的颜色不相同。
常用的顶点染色问题有着名的四色定理,即任何平面图都可以用四种颜色进行染色,使得相邻结点的颜色不同。
四色定理的证明借助了大量计算机运算,并被认为是计算机科学中的重大突破。
2.2 边染色边染色是指对图的每条边进行染色,使得相邻边之间的颜色不相同。
边染色问题的一个经典例子是地图染色问题,即在给定的地图上对相邻地区进行染色,要求相邻地区的颜色不同。
地图染色问题具有广泛的应用,例如电信领域的频率分配,确保相邻基站的频率不相同。
3. 染色算法为了解决染色问题,研究人员开发了多种求解算法,其中一些方法在特定条件下能够找到最优解。
3.1 贪婪算法贪婪算法是一种简单而高效的求解染色问题的方法。
该算法从某个结点开始,逐个给每个结点染色,每次选择一个尚未被使用的颜色并保证其与相邻结点不冲突。
贪婪算法的局限性在于可能得到的染色方案并非最优解,但它的运行时间较短,适用于大规模图的染色问题。
3.2 回溯算法回溯算法是在求解染色问题中常用的深度优先搜索方法。
该算法从某个结点开始,递归地对相邻结点进行染色,并在染色冲突时进行回溯。
回溯算法能够确保找到一种可行的染色方案,但其时间复杂度较高,不适用于大规模图的染色问题。
3.3 混合算法混合算法结合了贪婪算法和回溯算法的优点,既能够获得较好的染色方案,又能够保证较短的运行时间。
典型习题1习题1. 设G是简单平面图,面数r<12,δ(G)≥3。
(1)证明G中存在次数小于等于4的面。
(2)举例说明,当r=12,其它条件不变时,(1)中结论不真。
提示解本题的思路是,用欧拉公式、握手定理、面与次数的概念等,方法是反证法。
(1) 证明:为了使用欧拉公式,不妨设G是连通的(否则可对它的某连通分支讨论)。
由欧拉公式:n-m+r=2其中,n,m,r分别为G的顶点数、边数和面数。
从而有r=2+m-n < 12 (已知条件)解得n > 2+m-12 ①又由于δ(G) ≥3,由握手定理可得2m ≥ 3n ②将①代入②得2m ≥ 3n >3(2+m-12)=3m-30从而得m < 30 ③若不存在次数小于等于4的面,则2m > 5r (定理17.4)再用欧拉公式得2m > 5r = 5(2+m-n) = 10+5m-5n ④由②与④又得2m ≥ 10+5m-10m/3 ⑤由⑤解得m ≥ 30 ⑥③与⑥矛盾,因此必存在次数小于等于4的面。
(2)下图为正十二面体图,它是平面图,面数r=12,δ(G)=3,可是它每个面的次数均为5。
由此说明当r=12时,(1)中结论不真。
习题2. 设G是n(n≥11)阶无向简单图,证明G或必为非平面图。
提示参看补图以及定理17.12。
答案证明:用反证法,假设G与都是平面图。
由鸽巢原理(参看第十四章第1节习题课第3题提示)可知,G与的边数中至少有一个≥K n边数的一半。
不妨设G的边数m ≥由定理17.12有≤ m ≤ 3n-6即n2-13n+24 ≤ 0解此不等式,得到 2 ≤ n ≤ 10这与n≥11 相矛盾。
故G中必为非平面图。
分析其实,当n=9,10时,G和中已经必有非平面图了。
习题3. 证明下图中(1)与(2)均为非平面图。
提示参看库拉图斯基定理和图的同胚。
证明:(1)为了使用库拉图斯基定理,先将顶点标定顺序。
见图①所示。
典型习题1习题1. 设G是简单平面图,面数r<12,δ(G)≥3。
(1)证明G中存在次数小于等于4的面。
(2)举例说明,当r=12,其它条件不变时,(1)中结论不真。
提示解本题的思路是,用欧拉公式、握手定理、面与次数的概念等,方法是反证法。
(1) 证明:为了使用欧拉公式,不妨设G是连通的(否则可对它的某连通分支讨论)。
由欧拉公式:n-m+r=2其中,n,m,r分别为G的顶点数、边数和面数。
从而有r=2+m-n < 12 (已知条件)解得n > 2+m-12 ①又由于δ(G) ≥3,由握手定理可得2m ≥ 3n ②将①代入②得2m ≥ 3n >3(2+m-12)=3m-30从而得m < 30 ③若不存在次数小于等于4的面,则2m > 5r (定理17.4)再用欧拉公式得2m > 5r = 5(2+m-n) = 10+5m-5n ④由②与④又得2m ≥ 10+5m-10m/3 ⑤由⑤解得m ≥ 30 ⑥③与⑥矛盾,因此必存在次数小于等于4的面。
(2)下图为正十二面体图,它是平面图,面数r=12,δ(G)=3,可是它每个面的次数均为5。
由此说明当r=12时,(1)中结论不真。
习题2. 设G是n(n≥11)阶无向简单图,证明G或必为非平面图。
提示参看补图以及定理17.12。
答案证明:用反证法,假设G与都是平面图。
由鸽巢原理(参看第十四章第1节习题课第3题提示)可知,G与的边数中至少有一个≥K n边数的一半。
不妨设G的边数m ≥由定理17.12有≤ m ≤ 3n-6即n2-13n+24 ≤ 0解此不等式,得到 2 ≤ n ≤ 10这与n≥11 相矛盾。
故G中必为非平面图。
分析其实,当n=9,10时,G和中已经必有非平面图了。
习题3. 证明下图中(1)与(2)均为非平面图。
提示参看库拉图斯基定理和图的同胚。
证明:(1)为了使用库拉图斯基定理,先将顶点标定顺序。
见图①所示。
在(1)中取子图如②所示,该图与K3,3同胚,其中2度顶点分别为f和h。
由库拉图斯基定理可知,原图不是平面图。
(2)先将(2)中图顶点标定顺序,见图①所示。
方法一、去掉①中边(a,f),所得如下图②所示。
收缩边(a,b)和(f,g)(绿边所示),得图③。
③为K5,它是由(2)的子图②收缩边而来的,由库拉图斯基定理2可知,原图不是平面图。
方法二、在①中找到子图④,如下图所示,它是K3,3。
由库拉图斯基定理1(或2)可知,原图不是平面图。
习题4. 设G为n(n≥4)阶极大平面图,证明G的对偶图G*是2边-连通的3-正则图。
提示参看极大平面图、平面图G的对偶图、正则图及定理17.7。
证明:(1)由对偶图的性质可知,G*连通。
又因为极大平面图均为简单图,所以G中无环,故G*中无桥,于是G*2边—连通。
(2)由于G的阶数n≥4,由定理17.7可知G的每个面的次数均为3,因而G*为简单平面图,且每个顶点的度数均为3,故G*为3—正则图。
分析证明本题,主要根据平面图G的对偶图的定义及G与G*之间的关系。
习题5. 设G为n阶m条边的简单连通平面图,证明:当n=7,m=15时,G为极大平面图。
提示参看定理17.4、定理17.7以及欧拉公式。
证明:方法一、由定理17.7,只需证明G的每个面的次数均为3。
由于n=7,m=15,所以G不可能为树,因而必含圈。
又因为G为简单图,因而无平行边和环,故G的每个面的次数至少为3。
下面再证每个面的次数不可能超过3。
用反证法证明。
否则,由定理17.4可知2m > 3r ①由欧拉公式知r=2+m-n=10 ②把②代入①得30 > 30,矛盾。
故G的每个面的次数均为3。
方法二、由欧拉公式n-m+r=2 可解出面数r=10。
由G为简单图,且n=7,可知G的每个面的次数至少为3。
可是m=15,由定理17.4可知2m=30=deg(R i),deg(R i)≥3, i=1,2,...10,故可知i,deg(R i)=3。
分析从不同角度考虑,本题可以有多种证法。
答案给出2种证明方法。
习题6. 设G*为平面图G的对偶图,G**是G*的对偶图。
在什么条件下G**与G一定不同构?又在什么条件下G**G。
提示参看对偶图及定理17.17。
解:(1)当G为非连通图时,因为对偶图总是连通的,此时G**与G一定不同构。
(2)在G的对偶图的图形不改变的条件下,G**G当且仅当G连通。
必要性显然,下面只证充分性。
由定理17.17可知,G*的面数r*=n(n为G的阶数)。
这正说明G*的每个面中恰含G的一个顶点,由G*产生对偶图G**时,取R i**中G的顶点作为G**的顶点V i**,G**的边就取G中的边,因而G**G。
由于同构的平面图的对偶图不一定同构,因而本题要求不改变G*的形状及顶点的位置。
否则会出现G**与G不同构的情况。
分析注意:不要误认为G与G**一定同构。
由解题过程(见答案),有下述结论:(1) 当G为非连通图时,因为对偶图总是连通的,此时G**与G一定不同构。
(2) 当G的对偶图G*的图形不改变的条件下,G**G当且仅当G连通。
典型习题21. 求下列二图G1与G2的点色数和边色数。
提示参看点色数、边色数的概念、定理17.21、维津定理及布鲁克斯定理。
答案(1) X(G1)=4,X'(G1)=5。
(2) X(G2)=4,X'(G2)=4。
分析(1) G1为6阶轮图W6,由定理17.21可知,X(G1)=4。
Δ(G1)=5,由维津定理可知,X'(G1)=5或6。
可是能用5种色给G1的边着色,见下图所示。
所以X'(G1) ≤ 5,故有X'(G1)=5。
(2)由于G2中含奇圈(长度的奇数的圈),由定理17.21可知,X(G2)≥3。
Δ(G2)=4,由布鲁克斯定理可知X(G2) ≤ 4,因而X(G2)只可能取3或4。
但可以如下证明,3种色不能给G2顶点着色。
见下图所示:外部面3个顶点必须用3种色着色(红、绿、蓝),另外3个内部面(K3围成),可不增加颜色,但仍必须用3种色。
剩下的中间顶点不能再用红、绿、篮了,所以X(G2)=4。
因为Δ(G2)=4,由维津定理可知X'(G2)=4或5。
可以证明能用4种色给G2边着色,见下图。
所以X'(G2)=4。
2. 证明: 一个地图G是2-面可着色的当且仅当G为欧拉图。
提示参看地图、欧拉图的定义及定理17.22、定理17.25。
答案证明:若地图G为平凡图,结论为真。
下面设G为非平凡图。
因为G为地图,因而G中无桥并是连通的平面图,所以G是2-面可着色的等价于X*(G)=2。
必要性: 由于G为非平凡地图,由已知条件可知G的面色数X*(G)=2。
由定理17.25可知,G的对偶图G*的点色数X(G*)=2。
由定理17.22知,G*为二部图,故G*中无奇长回路。
于是G*的对偶图G**中无奇度顶点(见定理17.17)。
由于对偶图均连通,故G**为欧拉图。
由上个习题课中练习6可知,G G**,故G为欧拉图。
充分性类似可证。
3. G为3-正则的哈密顿图,证明X'(G)=3。
提示参看维津定理、握手定理及正则图的性质。
证明:由维津定理可知,X'(G) ≥ 3=Δ(G)。
下面证明X'(G) ≤ 3。
因为G为3-正则图,由握手定理可知3n = 2m,其中n与m分别为G的阶数和边数。
因而n为偶数。
设C为G中一条哈密顿回路,则C为偶圈。
因而给C上的边着色,只需用2种颜色。
而G中不在C上的边彼此不相邻,因而可用另一种色给它们着色。
于是,X'(G) ≤ 3。
故X'(G) = 3。
4. 证明彼得松图不是哈密顿图。
提示参看维津定理、定理17.21及彼得松图。
证明:(1)由维津定理及彼得松图的特征可证它的边色数X'=4(读者自己证明)。
(2)由于彼得松图是3-正则图,若它是哈密顿图,由上个练习题可知,它的X'=3,这与X'=4矛盾,所以彼得松图不是哈密顿图。
分析曾经证过彼得松图不是哈密顿图。
但证明比较麻烦。
现在用上题的结论证明本题要简单得多。
5. 高校某系某年级学生在某学期共选修6门公共选修课,期末考试前必须先考完这6门课程,设这6门课分别为C i,i=1,2,...,6。
S(C i)为选修C i的学生集合。
已知S(C i)∩S(C6)≠,i=1,2,3,4,5,S(C i)∩S(C i+1)≠,i=1,2,3,4,S(C5)∩S(C1)≠,问这6门课程至少几天能考完?答:至少需要4天考完。
分析(1) 根据已知条件先作无向图G=<V,E>。
其中,V={C1,C2,…,C6}E={(C i,C j)| C i,C j∈V,i≠j,且S(C i)∩S(C j)≠}所作无向图如下图所示:(2) 给G的顶点一种着色,若C i与C j涂相同的颜色,则C i与C j不相邻,即S(C i)∩S(C j)=,说明没有学生既学课程C i又学课程C j,因而C i与C j可同时考试。
类似地,所有涂同色的顶点代表的课程可同时考试。
于是最少的考试天数为X(G)。
G 为6阶轮图W6,由定理17.21可知,χ(G)=4,故至少4天考完。