Menu Sidebar
Menu

Combinatorics

Prufer Sequence 普吕弗序列

最近在翻看伯克利的组合数学课, 恰巧看到了这个. 当时对Prufer的认知, 仅限于他能压缩一个标号树(labeled tree), 后来看到Prufer证明Cayley公式: The number of labeled tree with n nodes is n^(n-2). 感觉这个东西还稍微有点用, lol. 要知道什么是Prufer Code, 首先要了接什么是labeled tree. 标号树就是一棵树, 把每个node从1开始标号. 因为是组合数学, 所以问的是, 对于标号n的树, 有几种可能的情况, 这个是Cayley公式. Prufer用Prufer Code证明了这个公式,当然这不是第一次证明. Prufer Code很好理解, 每次拿出编号最小的node, 然后把它的邻居放到序列里, 直到剩下两个点. 逆Prufer Code也好写, 先列1~n个数, 然后拿出(不放回)没有在序列中的最小的数, 和序列首项连起来, 然后删除序列首项, 直到最后剩下两个点, 然后把这2个顶点连起来. Prufer Code最大的应用就是它的唯一性, 即: 唯一的code对唯一的labeled tree. 这也是它被发明出来证明Cayley公式的原因. 所以任意给一个正整数序列, 都能对上一棵树… 其他应用…我还真是不知道…

Ramsey Theorem 拉姆齐定理

– – 首先吐槽一下这个wiki的翻译, 看了一下是一个台湾人翻译的, 虽然语言很标准..但是读着不是很流畅. 我看Ramsey Number是看 Combinatorics Through Guided Discovery 的时候看到的. 里面第二章介绍Double Induction and Ramsey Number 说的非常详细, 而且很简洁. 这本书是免费的, 伯克利也在用, 强烈推荐. 下面介绍Ramsey Number: Ramsey Number可以从两个方面考虑: 一个是实际问题: 请多少的客人吃饭, 能正好让他们有至少m个互相认识或者n个都不认识. 这里有几点需要注意: 所求的值和条件都为至少 m和n是或者的关系 另一个描述是从图论出发: 一个无向完全图中,最少多少个顶点, 有m大小的Clique或者n大小Independent Set. Clique的定义是:一个顶点的集合,其中任意两点都有边. Independent Set的定义是: 一个顶点的集合, 其中任意两点都没有边. 通过定义, 我们可以很清楚的看出, Ramsey Number是对称的, 即: R(m.n) = R(n,m) 证明Ramsey Number是非常复杂的, 借用wiki上的话就是: 想像有队外星人军队在地球降落,要求取得R(5,5)的值,否则便会毁灭地球。在这个情况,我们应该集中所有电脑和数学家尝试去找这个数值。若它们要求的是R(6,6)的值,我们要尝试毁灭这班外星人了 虽然证明一个不容易, 但是通过一个不等式,可以知道其大概的范围: 如果R(m-1,n)和R(m,n-1)不全是偶数: R(m, […]

书脊

倾城与倾国, 佳人难再得