2008-11-06 23:57| 
9 Comments | 本文内容遵从 
一个完全图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
第一次来大牛blog留言就是SF……
坐坐沙发……
困
本来还想呼唤一下好几天没更新的你～～
楼上是不是M67大牛的。。
还是觉得数学公式用两种方式书写（文本和gif）
在阅读的时候有些郁闷……
我总觉得第一个有四个西格玛符号的等式是有问题的。左右两边的项数不等。从而我怀疑下面的证明。。。。。。
上图显示了一种把K_5划分为四个完全二分图的方法
把完全图K_n划分成完全二分图
这个是什么意思, 我怎么觉得有点歧义?
[...] 线性代数理论不止一次帮助我们证明了看似与线性代数毫无关系的问题。如果你喜欢这个证明，千万不要错过这个经典的图论问题。 Posted in Brain Storm Tags: 线性代数, 组合数学, 证明, 趣题Trackback: http://www.matrix67.com/blog/archives/1900/trackback 我猜您可能还喜欢： 趣题：完全图K_n最少可以拆成多少个完全二分图？ [...]