下载文档原格式
图论中的平面图与染色问题图论是数学的一个分支，研究的是图的性质和图之间的关系。
在图论中，平面图与染色问题是重要的研究方向。
一、平面图平面图是指可以在平面上画出的图，其中任意两条边都不相交，任意两个顶点之间都只有一条边相连。
平面图可以用来描述许多实际问题，如地图、电路等。
在平面图中，有一个重要的定理，即欧拉定理。
欧拉定理是数学家欧拉在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 社交网络分析社交网络分析中的社区检测问题可以看作是图分割的一个应用。
典型习题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天考完。
