离散数学学习心得体会

离散数学学习心得体会

我相信很多人听过一个谜题，在你面前有两个神，一个天使一个恶魔，你不知道哪个是天使哪个是恶魔，同时你面前有两条你不知道通往何处的路，一条通往天堂，一条通往地狱。但是我们知道天使只说真话，恶魔只说假话，现在你只能向你面前的某一个神问一个问题，请问怎么能够问出通往天堂的路。

只需要问其中一个神：“另一个神会说哪条路去天堂？”。

假设你问的是天使，因为恶魔会骗人指向去地狱的路，天使只说实话。所以天使会如实的指向地狱的路。

假设你问的是恶魔，天使会指向去天堂的路，但是恶魔只说谎话，所以他会指向去地狱的路。

也就是说无论是你问的是什么神，他们都会指向去地狱的那条路。事件P为真，事件Q为假时，P且Q为假。仔细一想，天使说的话必定为真，恶魔说的话必定为假那我们那我们把他们两个的话取且运算，就必定为假。

我在第一次解决这个问题时有一些惊讶，很多看上去很浅显而又比较简单的知识在应用时，我却没有任何意识，这就是因为我从来没有去理解过这些知识。

从初中开始我们对函数就耳濡目染，学习了编程之后我对函数的理解就是输入一个值进入函数，函数就返回一个值。不过现在对函数的理解变为了映射，函数是从某一个集合映射到另一个集合的关系。在应用时，函数需要理解的概念不多。但是我们对函数必须有一些思考，不能廉价的认为函数就是某个公式然后代入数字计算。我们将函数想象成映射或者是转换。

从数学的角度来说，关系是笛卡儿的子集，就是一个二维表，还可以是一个矩阵，一个有向图

n元关系，多个（>2）集合的笛卡儿的子集，集合的个数叫关系的阶叫做n.类似n个数

可以用集合，图，矩阵来表示二元关系

关于离散数学中的关系，会出现以下几个概念，二元关系，等价关系，整除关系。

第六章“图”和第七章“树及其应川”可以归为“图论”。在刚接触到“图”这一章的时候我是抱着好奇之心去学习的，因为这章都足关于“图”，想了解一下和几何图形的差别，所以觉得善氏几何的我应该能够把它学好。但足不可否认，随着知识的深入，这一章一定会比前面的更难理解，更难学。因此，上课的时候听得格外认真，我才真正了解到它并不足枯燥乏味的，它的用途非常广泛．并几应用于我们整个日常生活中。比如：怎样布线才能使每一部电话互相连通，并几花费最小？从首府到母州州府的最短路线足什么？ , n项任务怎样才能最有效地由 n 个人完成？管道网络中从源点到集汇点的单位时间最大流是多少？一个计算机芯片需要多少层才能使得同一层的路线互不相交？怎样安排一个体育联盟季度赛的口程表使其在最少的周数内完成？一位流动推销员要以怎样的顺序到达每一个城市才能使得旅行时间最短？我们能用4 种颜色来为每张地图的各个区域着色并使得相邻的区域具有不同的颜色吗？这些问题以及其他一些实际问题都涉及“图论”。这里所说的图并不是几何学中的图形，而足客观世界中某些具体事物间联系的一个数学抽象，用顶点代表事物，用 边表示各式物间的二元关系，如果所讨论的事物之问有某种二元关系，我们就把相应的项点练成一条边。这种由顶点及连接这些顶点的边所组成的图就是图论中所研究的图。由于它关系着客观世界的事物，所以对于解决实际问题是相当有效的。哥尼斯堡桥问题（七桥问题），这个共名的数学难题．在经过如此漫民的时间最终还是瑞士数学家欧拉利川图论解决 它并得出没有一种方法使得从这块陆地中的任意一块开始，通过每一座桥恰好一次再回到原点。

树是指没有回路的连通图。它是连通图中最简单的一类图，许多问题对一般连通图未能解决或者没有简单的方法，而对于树，则己圆满解决，几方法较为简单。而几在许多不同领域中有着广泛的应川。例如家谱图就是其中之一。如果将每个人用一个项点来表示，并几在父子之问连一条边，便得到一个树状图。图论中最著名的应该就是图的染色问题。这个问题的研究来源于著名的四色问题。四色问题是图论中也许是全部数学中最出名、最难得一个问题之一。所谓四色猜想就足在平面中任何一张地图，总可以用至多四种颜色给每一个国家染色，使得任何相邻冈家的颜色是不同的。四色问题粗看起来似乎与我们所讨论的图没有什么联系。其实也是可以转化为图论中的问题来讨沦。首先从地图出发来构作一个图，让每一个项点代表地图的一个区域，如果两个区域有一段公共边界线，就在相应的顶点之间连上一条边。由于地图中每一块区域对应图的一个顶点，两个相邻项点对应两个相邻的区域。所以对地图染色使相邻的区域染以不同的颜色相当于对图的每个顶点染以相应的一种颜色，使得相邻的顶点有不同的颜色。总之，图沦是数学科学的一个分支，而四色问题足典型的图论课题。通过对图沦的初步理解和认识，我深深地认识到，图论的概念虽然有其直观、通俗的方面．但是这许多口常生活川语被引入图沦后就都有厂其严格、确切的含义。我们既要学会通过术语的通俗含义更快、更好地理解图沦概念，又要注意保持术语起码的严格。

对于有向树，有当略去其所有的有向边的方向时我们可以得到的无向图如果是树那么它就是有向树。一棵平凡的有向树，如果他的结点中恰有一个是入度为0的其他的入度都是1那么它就是一个根树，也可以叫它外向树。入度为0的结点就是根。出度为0的结点就是叶。出度大于0的就是内点。内点和根统称为分支点。从根到任意一个结点的通路长度就可以反映出它的层数，所有的结点中层数最大的就叫做高，反映到实际的几何图形上也可以看出高的实际意义与深度比较类似。图在家族关系的描述里有如果一个结点到另外一个结点可达那么可以叫它之前的为祖先，后面的是后代，而对于直接相连的有着父亲儿子以及兄弟之间的关系描述。如果再对树的层级进行细分又可以有兄弟的描述。这里有规定了每一个层次上的结点的次序的根树就可以叫它有序树。在根树的实际应用中有着k元树的概念。如果每个分支点最多有k个儿子那么就可以叫它为k元树。如果每个结点都有着k个儿子。那么t就是k元完全树。对于有序的k元完全树，我们又可以叫它为k元有序完全树。特殊的，在k元完全树里取其某个分支点作为根结点以及其全体后代形成的导出子树又可以称为是以那个点为根结点子树。特殊的二元有序树的每个结点可以有左子树与右子树。每个结点最多有两个子树。利用树的性质以及握手定理可以得出k元完全树的公式（k-1）*i=t-1。在这里的证明题目可以有着多种的解法。可以用定义列式，分别对叶以及分支点用归纳法，使用握手定力以及公式。要开拓思路。森林可以生成树，根树可以转化为二元树。根树转化为二元树的重点在于保留父亲与左边第一个儿子的连线，同时还要将兄弟用从左到右的有向边进行连接。转化的要点在于弟弟变成右儿子。在此基础上还有森林转化为二元树的算法。算法是先将森林中的每一棵树都转化为二元树，再将剩下的每一棵二元树作为左边的二元树的根的右子树，直到所有的二元树都连成一颗二元树为止。

然后是树的遍历。树的遍历中有如果对其对根的操作进行分类，有先根次序、中根次序以及后根次序。顾名思义进行调用以及理解。

通过对于这门课的学习，使我理解了数学与计算机之间的很多联系，锻炼我们的思维方式，对待问题要多方面考虑。离散数学也是学习数学科学中所有高级课程的必经之路，这门课将很多东西联系了起来，也使我对于数学有了新的认识。