离散数学中的的染色问题

龙源期刊网

排列组合中的染色问题

作者：林维祥

来源：《学校教育研究》2018年第02期

引言 组合计数问题是组合数学的重要内容，也是竞赛数学不可或缺的重要组成部分，而染色问题是数学竞赛中常见的一类问题，也是与实际生活联系最为直接的内容. 若能顺利解决此类问题则其他排列组合问题也就迎刃而解了.

解决组合计数问题的主要方法有枚举法、利用计数原理及基本公式、递推方法、容斥原理等，其中蕴含着分类讨论、转化和化归、函数与方程等数学思想。在平时遇到的某些计数问题（如染色问题）看似排列组合类应用题， 但又复杂万分，若从元素递增的角度考虑，建立递推数列就能迎刃而解.

例：如图1所示，将一个城市划分为5个行政区域，现给地图着色，要求相邻区域不得使用同一种颜色，有4种不同颜色可供选择，不同的着色方法有多少？

解：（1）先给B、D着相同的颜色，有 种方法，再依次给A、C、E着色，有 种方法，共有 种方法；

（2）先给B、D着不同颜色，有 种方法，再依次给A、C、E着色，有 种方法，共有 种方法。

所以，不同的着色方法共有 + =72（种）。

例题中的图形我们可以将其抽象为图2，即把图形分成如图的五块，则改变图形至图3，即将图形分成n+1块，有

命题1 如图3所示的一个图形被分成n+1块小块，现将其染色，要求相邻的小块不得使用同一种颜色，有四种颜色可供选择，则有

种方法。

分析：如图3中第O块与每个小块都相邻，则其所涂的颜色必与剩余的任何一个小块的颜色不同；因此，当O块涂了四种颜色中的一种后，就只剩下三种颜色可供剩余的小块涂色，根据此分析，我们有如下证明：

证明： 第O小块可以从四种颜色中任意选一种有 种，设n个小块区域 、 、… 的涂法总数为 ，整个图形的涂法总数为 。不难算出 、 ； 、 。

“离散数学”中的等价关系

“离散数学”是计算机专业的重要基础课程和核心课程。通过该课程的教学，不仅要为学生们进一步学习本专业的后续课程提供必备的数学理论基础，更重要的是培养和提高学生的抽象思维能力和逻辑推理能力。与高等数学主要以连续量作为研究对象不同，离散数学主要以离散量作为主要的研究对象，内容包括数理逻辑、集合论、代数结构、图论以及组合数学、数论和离散概率等。由于这些内容在描述形式、研究方法和计算机应用领域等方面均存在着较大差异，且含有大量比较抽象的概念、定理和各种各样的形式化描述，因而学生普遍感到困难重重，学习效果不理想。因此，如何改进教学方法，提高教学效果，使学生们的抽象思维能力和逻辑推理能力真正得到提升，是“离散数学”课程教学过程中必须认真解决的重要课题。

1离散数学课程中的等价关系

1.1离散数学课程中等价关系的概念

定义1 设R为非空集合A上的二元关系。如果R是自反的、对称的和可传递的，则称R为A上的等价关系。

定义2 设R为非空集合A上的等价关系， x∈A，令 [ x ]R={ y | y ∈A ∧

xRy }，

则称 [ x ]R 为x关于R的等价类，简记为[ x ]。

定义3 设R为非空集合A上的等价关系，以R的所有等价类作元素的集合称为A关于R的商集，记为A/R，即A/R={ [ x ]R| x∈A }。

根据定义1，很容易证明矩阵理论中的矩阵合同关系、相似关系都是等价关系；线性空间的同构关系也是一种等价关系。下面主要讨论离散数学中一些常见的等价关系。

1.2离散数学课程中各种具体的等价关系

数理逻辑中，命题公式A和B等值(记为A B)是指由它们构成的等价式A B为永真式。命题公式的等值关系是建立在由所有命题公式构成的集合上的一种等价关系，这种等价关系将所有命题公式按其是否等值划分成若干个等价类，属于同一个等价类中的命题公式彼此等值，因而，只要清楚了等价类中某一个公式的性质，则与该公式同类的公式的性质也就完全清楚了。因此，命题公式的等值关系(等价关系)是获取命题公式性质的基石。

1 A

D

B C

A

B F

C

D E 简单的染色问题

在我们美丽的地球上，有60多亿人口，任何六个人聚在一起，或者有三个人彼此相识，或者有三个人彼此不相识。你相信吗？那就先让我们来作个游戏！规则：正六边形的六个顶点，两游戏者每次可随意．．选用红或蓝色的笔，轮流．．选择其中的两点连线，谁第一个被迫画成一个同色的三角形（红色或白色），他就是失败者．这个游戏是否一定能分出胜负呢？与先下后下是否有关？

抽象数学问题：把六个点（任意三点不共线）的连线染两色，至少会出现一个同色三角形．

证明：任取一点A，那么由点A引出的5条边中，由抽屉原理，至少有三条是同色的，不妨设AB、AC、AD是蓝色的，如图所示．考察BC、BD、CD三条边，若这三条边中有一条是蓝色的，则与A形成一个蓝色三角形；若这三条边都是红色的，则三角形BCD为一个红色三角形．

“任何六个人聚在一起，或者有三个人彼此相识，或者有三个人彼此不相识”这样一个著名的实际问题也就迎刃而解．

1928年，在英国伦敦数学会的一次学术会议上，年仅24岁的年轻数学家弗兰克·普拉东·拉姆赛（Frank

Plumpton Ramsey）证明了一个定理：如果某一集合（如点集）中事物的数量足够多，且每对事物间都存在一定数量的关系（如各种颜色的边）中的一种，那么必定存在一个包含若干数目事物的子集（如三点集），其中每对事物间也存在同样的关系（如同色三角形）．这个定理称为拉姆赛定理，告诉我们：如果平面上的点数足够多，且每对点间的线（边）或染红色或染蓝色，那么必定存在一个包含3个点的子集，他们之间的边同色，即包含一个同色三角形．

如果我们将刚才的六点染色游戏继续下去，染完所有的线段，同色三角形最少出现了几个？这是偶然吗？恭喜你！答对了，2个！在六点（任意三点不共线）染色游戏中，必有两个同色三角形．

证明：方法一：为方便叙述，我们把平面上有n个点，每两点都有连线的图称为n阶完全图，记作nK．由拉姆赛定理知把6K边染红、蓝两色，必出现一个同色三角形，不妨设这个三角形是红色的ABC．现考虑△ABC以外的点D、E、F，由D引出的五条边中，由抽屉原理，至少有三条边是同色的，除了D与A、B、C所连的边是蓝色的情形以外，其余情形均可仿照结前面的证明得到一个同色三角形；同理，E、F引出的边也有同样的结论．于是，只剩下如图情形，即D、E、F与△ABC的三顶点连线均是蓝色．这时，三角形DEF或者是红色三角形，或者与原来的蓝边形成2 一个蓝色三角形．

龙源期刊网

离散数学在计算机学科中的作用

作者：王雪茹

来源：《价值工程》2010年第21期

摘要:离散数学和计算机科学关系密切,是计算机科学与技术的理论基础。作为有利的数学工具,对计算机的发展与计算机科学的研究起着重大的作用。本文阐述了离散数学在计算机学科不同领域中的应用,分析了离散数学与计算机专业其他学科间的关系,突出其在计算机学科中的作用。

Abstract: Discrete mathematics is closely related to computer science; it is the theory basis for

computer science and technology. As favorable mathematical tool, it plays a major role in the

development of computers and computer science research. In this paper, the application of discrete

mathematics in computer science in different areas is described. the relationship among discrete

mathematics and computer science and other disciplines is analyzed, highlighting its role in computer

science.

关键词:离散数学;数据结构;编译原理;数据库原理;人工智能

Key words: discrete mathematics; data structure;compiler theory;database theory;artificial