平面图欧拉定理的简单几何阐释
关于定理的描述，可见于《离散数学及其应用》，此处略。 请看下图的例子： 如上图所示，对于任何一个平面图的局部，我们都可以对其进行删除边操作。 减少一个边，总是导致或者减少一个顶点（减少悬挂边时），或者减少一个面（减少非悬挂边时）。直到变成一个线段（$e = 1, f = 1, v = 2$，如上面最后一张图所示）。 所以根据此递推关系，有： $$ e = (v-1) + (f-1)\\ \text
分类： 学科笔记专辑
数据结构：前序+中序序列确定树
pre = ADCBFKHIGJE in = BCDKFHAGIJE pre = A DCBFKH IGJE // 找出根（第一个）和左右（按照 in 行左右两部分含有的字母） in = BCDKFH A GIJE A DCBFKH IGJE // 得到大致结构 // 后面对左右递归如此操作 for DCBFKH BCDKFH D CB FKH BC D KFH D CB KFH for CB B
离散数学（下）期末重点再梳理
呜呜呜呜呜我凉了。 北邮的同学们，卷起来吧。加速！ 关系 关系的性质 如何求关系的补、并、交、逆 解释自反、对称、反对称、连通、传递、等价等的概念 等价关系：如何证明关系等价 偏序关系：如何证明偏序关系 求传递闭包：求传递闭包的 Warshall 算法详解 关系的同构：如何证明关系同构 格 如何画哈赛图：根据关系的描述画出哈斯图 从哈塞图判断是不是格 群论 同态：如何证明同态？ 同构：如何证明群/
离散数学：利用生成函数求解递推关系
生成函数：一种形式幂级数，其每一项可以提供关于这个序列的信息。 普通生成函数 $\sum_{n=0}^{\infty}a_nx^n$ 简单序列的生成函数 $1, 1, \cdots$ 常数列： $$ \sum_{n=0}^{\infty} x^{n}=\frac{1}{1-x} $$ $1, a, a^2, a^3, \cdots$ 序列 $$ \sum_{n=0}^{\infty}(a x)^{
运筹学笔记：排队论基础
目录 基本概念排队系统的组成符号描述顾客到达的分布：泊松分布顾客到达的密集程度（间隔）：负指数分布服务时间的分布：负指数分布泊松过程的三个条件单服务台模型（M/M/1）系统状态概率排队系统的运行指标系统运行指标的计算Little 公式例题基本概念 排队系统的组成 输入过程：顾客按照怎样的规律到达 顾客的数量 单个到达还是批量到达 顾客到达间隔的分布（如泊松分布，负指数分布） 排队规则 损失制：到达
离散数学笔记（数论部分）
div 和 mod 记号 用法： $ 2 = 8 \operatorname{div} 4 = 9 \operatorname{div} 4$ 除法向下取整 $ 0 = 8 \operatorname{mod} 4; 1 = 9 \operatorname{mod} 4 $ 除法余数 $ \equiv $ 记号 $ 17 \equiv 5 (\operatorname{mod} 6) $ 因为 1
求传递闭包的 Warshall 算法详解
过程详情 【例子】关系的矩阵是： $$ \boldsymbol{W}_{0}=\left[\begin{array}{llll} 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array}\right] $$ 求传递闭包。 【分析与解答】 我们看第 1 列：$\pmatrix{0\\1\\1\\0}$。
离散数学：特征值（校验子）解码详解（Syndrome Decoding）
目录 生成矩阵（Generator Matrix）信道编码（Channel coding）校验矩阵（Parity Check Matrix）生成矩阵和校验矩阵的关系特征值解码求陪集首部的特征值解码生成矩阵（Generator Matrix） 这是表示编码函数的矩阵。行数表示信息位数量，列数表示码长。典型阵是以单位矩阵打头的生成矩阵，比如下面： $$ \bold{G}=\left[\begin{ar
离散数学：最大似然译码详解（最大似然解码，Maximum Likelihood Decoding）
【例子】假设编码函数 $e:B^3\to B^6$ 定义为： $$ \begin{array}{l} e(000)=000000 \\ e(001)=001100 \\ e(010)=010011 \\ e(011)=011111 \\ e(100)=100101 \\ e(101)=101001 \\ e(110)=110110 \\ e(111)=111010 \end{array} $$ 求
运筹学：匈牙利法（求解指派问题）详解
感受： 【例子】效率矩阵为 $$ \begin{bmatrix} 12 & 7 & 9 & 7 & 9 \\ 8 & 9 & 6 & 6 & 6 \\ 7 & 17 & 12 & 14 & 9 \\ 15 & 14 & 6 & 6 & 10 \\ 4 & 10 & 7 & 10 & 9 \end{bmatrix} $$ 试求效率最高的解。 （1）系数矩阵简化 对于每行，分别减去其行的最小值。之后对