完全图分割问题

realnumber

2014浙江省数学竞赛第17题的推广http://kuing.orzweb.net/viewthre ... &extra=page%3D1
原题以及解答：假设每个快递最多可以负责4个城市两两之间的直接联络(即6条线路)，那么13个城市任何2个需要保持直接联络的话，最少需要几个快递？

p=4,n=13．13个点记为 \(M,\ A_i,\ B_i,\ C_i,\ D_i\ (i=1,2,3)\)．
那么13个\(K_4\)为\((M,A_1,A_2,A_3),(M,B_1,B_2,B_3),(M,C_1,C_2,C_3),(M,D_1,D_2,D_3)\),
\((A_1,B_1,C_1,D_1),(A_1,B_2,C_2,D_2),(A_1,B_3,C_3,D_3)\),
\((A_2,B_1,C_2,D_3),(A_2,B_2,C_3,D_1),(A_2,B_3,C_1,D_2)\),
\((A_3,B_1,C_3,D_2),(A_3,B_2,C_1,D_3),(A_3,B_3,C_2,D_1)\).

完全图是每对顶点之间都恰连有一条边的简单图．n个端点的完全图有个n端点及\(\frac{n(n-1)}{2}\)条边，以\(K_n\)表示．见维基百科．

方便叙述，先定义一个概念．
分割：某一个 \(K_n\) 的一些子图 \(K_p\)，\(K_p\) 之间无公共边，且 \(K_n\) 中的任意一边必定在某个 \(K_p\) 中，则称 \(K_n\) 被这些 \(K_p\) 分割，并记为 \(K_p\mid K_n\)．不满足定义称 \(K_n\) 不被 \(K_p\) 分割，记为 \( K_p \nmid  K_n \)．

\(K_n\) 被 \(K_p\) 分割的一个必要条件是 \(p(p-1)\mid{n(n-1)}\)，且 \((p-1)\mid{n-1}\)，且 \(n-1\ge p(p-1)\)．

证明：因为 \(K_n\) 有 \(C_n^2\) 条边，要被有 \(C_p^2\) 条边的 \(K_p\) 分割，则有 \(C_p^2\mid C_n^2\),即 \(p(p-1)\mid {n(n-1)}\).
\(K_n\) 中从某一个顶点A出发的边有 \(n-1\) 条，点A还是 \(K_p\) 中某点，\(K_p\) 中与A连接的边有 \(p-1\) 条，如此 \((p-1)\mid {n-1}\)．
接下来证明 \(n-1\ge p(p-1)\)，取定一点M，含有点M的 \(K_p\) 共有 \(\frac{n-1}{p-1}\) 个，接下来另外的 \(K_p\) 所需要的p个点，最多从刚才的含M的每个 \(K_p\) 中分别取一点，因此有\(\frac{n-1}{p-1}\ge p\)，即 \(n-1\ge p(p-1)\)．

因为手工检验，n，p(n>p)取值较小，所以来这里发贴求助程序验证，并未指望完全解决，有部分有趣的结果就不错了．
p=2时，任意 \(n\ge2\) 符合条件，分割显然成立．
p=3时，符合上述条件的依次有n=7，9，13，15(7,9,13成立．15,19,21,25,27,31,33,37,39,....未验证或否定)．
p=4时，同上，n=13，16，25（13，16成立，25未检验）．
p=5时，同上，n=21，25(21成立，25未检验)
p=6时，同上，n=31，36(31成立,36未检验)．
p=7时，同上，n=43，49(n=43检验中，49未检验)．

我的问题是:p=3以及p=7,n=43用程序来搜索下，前者猜测成立，后者很可能无解．


简略地说：p=3,n=15,就是说有１５个点，两两连线，共 \(C_{15}^2=105\) 条线段(记为 \(K_{15}\) )，３个点两两连线，有３条线(记为 \(K_3\) ),１０５÷３＝３５，就是说，１０５条线段能否分割成３５个三角形.(若成立记为\(K_3\mid K_{15}\)).

kastin

你是想证明（或者否定）那个必要条件同时也是充分条件吗？还是仅仅想问`K_3|K_{15}`是否成立?

zhouguang

推荐链接：http://www.ccrwest.org/cover.html
试一下，在网页中输入v=13，k=4，t=2，就可以得到“原题”的答案13。呵呵。

zhouguang

那链接显示：在楼主p<=5的情况中，所提到的未验证都是可验证的。
p=6，n=36和p=7时的那三种情况都没有达到理论下限。
如果楼主n=43的验证中完成了，如果结果小于49，那么可以Contribute一下。呵呵。

zhouguang

那链接显示：在楼主p<=5的情况中，所提到的未验证都是可验证的。
p=6，n=36和p=7时的那三种情况都没有达到理论下限。
如果楼主n=43的验证中完成了，如果结果小于49，那么可以Contribute一下。呵呵。

zhouguang

噢，这回知道E文的重要了吧，呵呵。


以p=3，n=39为例，操作如下图，其实用不到E文的，呵呵。

kastin

kastin 发表于 2014-5-28 13:01
你是想证明（或者否定）那个必要条件同时也是充分条件吗？还是仅仅想问`K_3|K_{15}`是否成立?

`K_3|K_{15}`是成立的。一种构造方法是，让顶点`v_1,v_2,\dots,v_{15}`按照顺时针依次排列成正15边形的顶点位置。取`v_1,v_2,v_4`两两相连，作为第一个`K_3`子图，接下来将这个三角形以正15边形的中心点旋转`\frac{2\pi}{15}`，这就形成第二个`K_3`子图。类似地，将第二个子图继续旋转`\frac{2\pi}{15}`，得到第三个...这样下去就能得到所有的子图，满足子图之间不存在公共边，且子图的并集就是`K_{15}`。也就是说，`K_{15}`是`K_3`可分解的。

下面以`K_7`为例给出上述方法的图示：