趣题:完全图K_n最少可以拆成多少个完全二分图?

   

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


 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
    和你想象的一样,这个答案就是n-1。一个完全图K_n永远不可能被拆分为n-2个或更少的完全二分图。拆成n-1个是很好办的:从K_n中随便取出一个点作为L集,其余n-1个点作为R集,把这n-1条边从图中取出来形成一个完全二分图,然后继续递归地处理K_(n-1);当规模降到K_2时,我们已经得到了n-2个二分图,并且图中就只剩下一条边了,合起来正好是n-1个完全二分图。现在的关键是,如何证明n-1个已经是最少的了?
    这个证明牛B就牛B在,它根本就不是用组合数学的方法证明的。它居然是用线性代数来证明的!这可以说是我见过的最诡异的证明了。假设我们把K_n划分为了m个完全二分图,第i个二分图的左右两个点集分别记作L_i和R_i。给图中的每个顶点设置一个变量,第i个顶点上的数就记作x_i。于是呢,有

    现在,让我们假设m<n-1。考虑下面这个线性方程组:

    这个线性方程组的式子个数比未知量少,因此它一定有一组非零解c_1, c_2, …, c_n。既然每个L_i里面的变量和都为0了,根据前面的那个恒等式,我们得知

    考虑所有c_i的和的平方,展开后有

    但是,一方面,由线性方程组的第一个方程知c_i的总和为0,其平方当然也等于0;另一方面,c_i是非零解,它的平方和是大于0的。矛盾产生。

    题目来源:Proofs from THE BOOK, Chapter 9

17 条评论

  • R

    第一次来大牛blog留言就是SF……

  • iceberg

    坐坐沙发……

  • 燕仰

    本来还想呼唤一下好几天没更新的你~~

  • someone

    楼上是不是M67大牛的。。

  • hetong_007

    还是觉得数学公式用两种方式书写(文本和gif)
    在阅读的时候有些郁闷……

  • raindaynight

    我总觉得第一个有四个西格玛符号的等式是有问题的。左右两边的项数不等。从而我怀疑下面的证明。。。。。。

  • chong

    上图显示了一种把K_5划分为四个完全二分图的方法

    把完全图K_n划分成完全二分图

    这个是什么意思, 我怎么觉得有点歧义?

  • bobbielf2

    呵呵~~好方法~~
    其实图论的不少问题都是用线性方程来解的,比如最大流问题

  • www.d8898.com

    所以,创业是什么?创业就是选择要未来,而不要现在;就是脱离多数人的正常的轨道,去选择一种特别的人生。如果你不想脱离常轨,那你就不要去创业。大家知道,马云高考考了两三年都没考上,最后终于考上了杭州师范学院的外语系,毕业以后当了五年英语老师。这就是常轨。结果他突然有一种冲动—要办企业。于是他和他太太还有另外几个人跑到北京,做了很多小买卖都不成功。后来他们跑到长城上去发誓,说一定要办成世界上最伟大的公司,仅仅过了十几年,他就成功了。他为什么成功了?因为他变得和普通人不一样了,他不再当老师了,不再朝九晚五地在课堂上讲课了,而是求人做生意了。他脱离了所有的常轨,虽死而无憾。结果,他把这件事慢慢做起来了。现在,他的公司已经成为世界上最伟大的公司。这就是他选择脱离正常轨道的结果。

  • fondking

    我只是能看懂,完全无法想象怎么来的

  • wzh

    博主我想知道组合数学的方法,看了书上的不太懂

回复给 www.d8898.com 取消回复

  +  82  =  85