图 (数学)
在离散数学中，图（）是用于表示物体与物体之间存在某种关系的结构。数学抽象后的“物体”称作节点或顶点（），节点间的相关关系则称作边。在描绘一张图的时候，通常用一组点或小圆圈表示节点，其间的边则使用直线或曲线。 图中的边可以是有方向或没有方向的。例如在一张图中，如果节点表示聚会上的人，而边表示两人曾经握手，则该图就是没有方向的，因为甲和乙握过手也意味着乙一定和甲握过手。相反，如果一条从甲到乙的边表示甲欠乙的钱，则该图就是有方向的，因为“曾经…
标签：#离散数学
共 8 篇文章
逆序对
在计算机科学和离散数学中，一个序列的逆序（inversion）对，是失去自然次序的元素对。 定義 逆序 設\ \pi \ 為一個排列，如果\ i 而且 \ \pi(i) > \pi(j) \ ， 這個位置（有称为“序位”）对 \ (i, j) \ ，或者這个元素对 \ \bigl(\pi(i), \pi(j)\bigr) \ ，被稱為是 \ \pi \ 的一個逆序。 逆序集是所有逆序的集合。一個排列 \ \pi \ 的使用基于位置表示法…
图论
图论（），是组合数学分支，和其他数学分支如群论、矩阵论、拓扑学有着密切关系。 图是图论的主要研究对象。图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。 图论起源于著名的柯尼斯堡七桥问题。该问题于1736年被欧拉解决，因此普遍认为欧拉是图论的创始人。 图论的研究对象相当于一维的单纯複形。 历史 一般认为，欧拉于1736年出版…
组合数学
组合数学（），在总體上是一门研究可數或离散对象的科学。它可分为廣義上的和狭義上的兩種層面，若是前者 (廣義的组合数学) ，其相当于离散数学，而后者 (狭义的组合数学) 則是组合计数、图论、代数结构、数理逻辑等的总称，但这只是不同学者在稱謂上的区别。而随着计算机科学日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。 狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题…
离散数学
是离散数学的研究对象之一，它们拥有有趣的数学性质，可以作为现实世界用来解决问题的模型，而且还在计算机算法开发中有着举足轻重的作用。]] 离散数学（）是数学的几个分支的总称，研究基于离散空间而不是连续的数学结构。与連續变化的实数不同，离散数学的研究对象——例如整数、图和数学逻辑中的命题——不是連續变化的，而是拥有不等、分立的值。因此离散数学不包含微积分和分析等「连续数学」的内容。 离散对象经常可以用整数来枚举。更一般地，离散数学被视为处理…
二阶线性递推式
二阶线性递推式是数列递推式的一种，其特征是次数为1，且数列的第n项与第(n-1)项和(n-2)项有关。 即形如 a_{n+2}+pa_{n+1}+qa_n=0 的递推式叫二阶线性递推式。
树同构
树同构(Tree Isomorphism)描述的是图论中，两个树之间的完全等价关系。在图论的观点下，两个同构的树可以被当作同一个图来研究。 定义 树同构的概念源于图同构。图同构的概念为，两个简单图G和H称为是同构的，当且仅当存在一个将G的节点 1,\ldots,n 映射到H的节点1,\ldots,n的一一对应\sigma，使得G中任意两个节点i和j相连接，当且仅当H中对应的两个节点\sigma(i)和\sigma(j)相连接。树同构即在…
离散优化
离散优化是应用数学和计算机科学中优化问题的一个分支。 在此种数学规划中，变量被限制为离散变量，比如整数。与此相对的是连续优化。 离散优化存在两个主要的分支。 组合优化：指关于图，拟阵等数学结构的问题。 整数规划 此两分支也有着很紧密的关系，许多组合优化问题可以以整数规划来模拟，整数规划问题也可有对应的组合优化版本。