【Think】完全二分图

  最近一段时间有小伙伴跟小编吐槽题目太简单,可怜小编搜索能力有限,现向超级数学建模平台全体成员征集Think题目,欢迎各位投稿至

  没错,图中的规律就是:每棵树代表一个质数,一个森林(若干个树放一块儿)就表示这些质数的乘积;如果一个森林表示的是 n ,在这个森林下方添加一个公共根,就构成了新的质数——第 n 个质数。例如, 69 就等于 3 乘以 23 ,它们分别是第 2 个质数和第 3×3 个质数。 131 这个例子更能说明问题,因为它就是第 32 个质数。

  这个东西牛就牛在,它建立了一个自然数到森林的一一对应关系(从而也就建立了自然数到有根树的一一对应关系,因为我们可以用添加超级根的方法把森林都视作树)。这种为有根树编号的方法叫做 Matula-Goebel 编号法,参见数列 A127301。

  注意到质因数分解在构造一一对应关系中的妙用。正是因为有唯一分解定理,数的表示方法才是唯一的。于是乎,图论和数论巧妙地结合在了一起,实在令人拍案叫绝。

  一个完全图K_n是指一个有n个顶点的图,其中每两个点之间都有一条边相连。一个完全二分图是指这样一种图,图中的顶点分为两个点集L和R,L里的每个顶点都和R里的所有点相连。上图显示了一种把K_5划分为四个完全二分图的方法(分别用红蓝绿灰四种颜色来表示这四个子图)。你觉得,最少可以把完全图K_n划分成多少个完全二分图?给出一种划分方案,并证明这个数目已经不能再少了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注