s*****1
发帖数: 1 | 1 原题是一个简单的小学奥数题：
There are 10 people in a room. If each person shakes hands with exactly 3
other people, what is the total number of handshakes?
现在不问握手次数 而是问有几种握法 请问有几种？ 不要枚举(打码)解法
注意：现在问的是握法，比如四个人只有一种握法
今天一下被问住了 旽旽旽 | d*****u
发帖数: 17243 | 2 你把题理解错了吧
问的是握手事件发生的次数
10*3/2=15 | s****u
发帖数: 1433 | 3 顺序算不同握法么？AB，AC和AC，AB算一种握法么？ | s*****1
发帖数: 1 | 4 鎴戠煡閬鎴戣浜嗗鏋滀笉闂鏁鑰岄棶鎻℃硶鐨勮瘽鏈夊嚑绉br />
銆鍦daigaku(喙戂┷炢┼箲) 鐨勫ぇ浣滀腑鎻愬埌: 銆br />
: 浣犳妸棰樼悊瑙ｉ
敊浜嗗惂
: 闂殑鏄彙鎵嬩簨浠跺彂鐢熺殑娆℃暟
: 10*3/2=15
| s*****1
发帖数: 1 | 5 算一种
不过这个不重要 到时候除2就好了
: 顺序算不同握法么？AB，AC和AC，AB算一种握法么？
【在 s****u 的大作中提到】
: 顺序算不同握法么？AB，AC和AC，AB算一种握法么？
| g****g
发帖数: 1267 | | s*****1
发帖数: 1 | 7 请问是怎么算的呢
: 420？
【在 g****g 的大作中提到】
: 420？
| k**********4
发帖数: 16092 | 8 120
【在 s*****1 的大作中提到】
: 原题是一个简单的小学奥数题：
: There are 10 people in a room. If each person shakes hands with exactly 3
: other people, what is the total number of handshakes?
: 现在不问握手次数 而是问有几种握法 请问有几种？ 不要枚举(打码)解法
: 注意：现在问的是握法，比如四个人只有一种握法
: 今天一下被问住了 旽旽旽
| B*********L
发帖数: 700 | | g****g
发帖数: 1267 | 10 10*（9*8*7/3*2*1）/2
【在 s*****1 的大作中提到】
: 请问是怎么算的呢
:
:
: 420？
:
| | | c******8
发帖数: 445 | 11 C93 + C83 + ...... + C43 + C33 | s*****1
发帖数: 1 | 12 这可能不对 4个人的情况就不符合了。。。
: 10*（9*8*7/3*2*1）/2
【在 g****g 的大作中提到】
: 10*（9*8*7/3*2*1）/2
| g****g
发帖数: 1267 | 13 或者除以3.太久没用脑子了，不会做了
【在 s*****1 的大作中提到】
: 这可能不对 4个人的情况就不符合了。。。
:
:
: 10*（9*8*7/3*2*1）/2
:
| s*****1
发帖数: 1 | 14 嗯 我一开始也是这么想的 但觉得好像没那么多种
: C93 C83 ...... C43 C33
【在 c******8 的大作中提到】
: C93 + C83 + ...... + C43 + C33
| s*****1
发帖数: 1 | 15 哈哈哈 同
今天被问的苦思冥想了一上午
: 或者除以3.太久没用脑子了，不会做了
【在 g****g 的大作中提到】
: 或者除以3.太久没用脑子了，不会做了
| l****u
发帖数: 980 | 16 就是2楼说的15次。每人握3次手，10个人，30人次握手。每次握手是两个人次，所以30
/2等于15。 | l****u
发帖数: 980 | 17 或者这么理解：每次握手是两个人，这两个人各自算半次握手。所以10个人，每人3次
半个握手：10 x 3 x 0.5 = 15 | s*****1
发帖数: 1 | 18 我知道 这个很简单
现在问的是有多少种握法 不是次数
: 就是2楼说的15次。每人握3次手，10个人，30人次握手。每次握手是两个人次，
所以30
: /2等于15。
【在 l****u 的大作中提到】
: 或者这么理解：每次握手是两个人，这两个人各自算半次握手。所以10个人，每人3次
: 半个握手：10 x 3 x 0.5 = 15
| s*****1
发帖数: 1 | 19 比如四个人要握6次手 但只有一种握法
: 或者这么理解：每次握手是两个人，这两个人各自算半次握手。所以10个人，每
人3次
: 半个握手：10 x 3 x 0.5 = 15
【在 l****u 的大作中提到】
: 或者这么理解：每次握手是两个人，这两个人各自算半次握手。所以10个人，每人3次
: 半个握手：10 x 3 x 0.5 = 15
| l****u
发帖数: 980 | 20 哦，只看英文了，没看中文。太复杂了，自己想吧。
【在 s*****1 的大作中提到】
: 我知道 这个很简单
: 现在问的是有多少种握法 不是次数
:
:
: 就是2楼说的15次。每人握3次手，10个人，30人次握手。每次握手是两个人次，
: 所以30
:
: /2等于15。
:
| | | w********9
发帖数: 8613 | 21 这题谁出的？
是很很很复杂的。
可以把它归类成graph。每个节点3个分叉。
有很多graphs，其中有些对应很多解。
不少图有局部节点置换、局部旋转、局部翻转和它们结合的对称性。
还有的graphs是有分离或近分离的子图。比如4和6个节点的子图，以及从它们转变出来
的连图。
从类似5+5子图（没有完全分离的两个5节点子图作为解)转变出来的一种特殊图是
Petersen graph。对称性特别强。
还有一种是是两个内外套的五边形，是平面性的（planar）。对称性也很强。
尽管可能有很多对称性，解的数目可能是很多很多的。
从4个人握2人的手做起。复杂性是指数的。 | N**********d
发帖数: 2466 | | w********9
发帖数: 8613 | 23
让你算的不是那个小学生的竞赛题目。
这题得有很强数学或者计算机背景的人才能做。如果花很多时间去做。
【在 N**********d 的大作中提到】
: 15
| s*****1
发帖数: 1 | 24 我好朋友教孩子数学题
然后他想到如果这样问该怎么做
就和我讨论 结果发现还挺难的
: 让你算的不是那个小学生的竞赛题目。
: 这题得有很强数学或者计算机背景的人才能做。如果花很多时间去做。
【在 w********9 的大作中提到】
:
: 让你算的不是那个小学生的竞赛题目。
: 这题得有很强数学或者计算机背景的人才能做。如果花很多时间去做。
| B*Q
发帖数: 25729 | 25 这是道瞎编的烂题
首先证明这种握手法可能吧
10个人佬不清楚
5个人似乎不可能 | s*****1
发帖数: 1 | 26 奇数人数当然不可能
不需要你证明
: 这是道瞎编的烂题
: 首先证明这种握手法可能吧
: 10个人佬不清楚
: 5个人似乎不可能
【在 B*Q 的大作中提到】
: 这是道瞎编的烂题
: 首先证明这种握手法可能吧
: 10个人佬不清楚
: 5个人似乎不可能
| w********9
发帖数: 8613 | 27
做对应圈图的【2，2】，【3，2】，【4，2】，【5，2】等等
然后对应立方图的【4，3】和【6，3】
小孩最多只要做到上面的就可以了。
可以从用上面的拼凑或参考上面建立一些【10，3】的。。。
把人编号排序，不需要算一些置换等效/对称的，把问题变成几个子问题，然后用计算
机算。
【在 s*****1 的大作中提到】
: 我好朋友教孩子数学题
: 然后他想到如果这样问该怎么做
: 就和我讨论 结果发现还挺难的
:
:
: 让你算的不是那个小学生的竞赛题目。
:
: 这题得有很强数学或者计算机背景的人才能做。如果花很多时间去做。
:
| S*E
发帖数: 3662 | 28 楼主肯定是理解错题目了。即使把3改成2甚至1也不是非常简单。 | w********9
发帖数: 8613 | 29 【m，n】
mn/2次握手
m和n不可以同时为奇数 | s*****1
发帖数: 1 | 30 嗯。。
是这样
: mn/2次握手
: m和n不可以同时为奇数
【在 w********9 的大作中提到】
: 【m，n】
: mn/2次握手
: m和n不可以同时为奇数
| | | w********9
发帖数: 8613 | 31 【10，1】是五个对
10!/5!/2!/2!/2!/2!/2! | w********9
发帖数: 8613 | 32 [10,2]可以是
1.一个大圈
10！/10/2
2.小圈组合
3+3+4 (2个3人圈，和1个4人圈）
3+7
4+6
5+5
要一个个去算，如果你对排列组合比较熟悉，那就不难。
【m，3】复杂多了。 | s***3
发帖数: 742 | 33 10个人每人要握三次手好像做不到。题目肯定有问题
: 这题谁出的？
: 是很很很复杂的。
: 可以把它归类成graph。每个节点3个分叉。
: 有很多graphs，其中有些对应很多解。
: 不少图有局部节点置换、局部旋转、局部翻转和它们结合的对称性。
: 还有的graphs是有分离或近分离的子图。比如4和6个节点的子图，以及从它们转
变出来
: 的连图。
: 从类似5 5子图（没有完全分离的两个5节点子图作为解)转变出来的一种特殊图是
: Petersen graph。对称性特别强。
: 还有一种是是两个内外套的五边形，是平面性的（planar）。对称性也很强。
【在 w********9 的大作中提到】
: [10,2]可以是
: 1.一个大圈
: 10！/10/2
: 2.小圈组合
: 3+3+4 (2个3人圈，和1个4人圈）
: 3+7
: 4+6
: 5+5
: 要一个个去算，如果你对排列组合比较熟悉，那就不难。
: 【m，3】复杂多了。
| s*****1
发帖数: 1 | 34 能的
最简单的例子就是wewill2009说的一个大环，里面人两两配对
: 10个人每人要握三次手好像做不到。题目肯定有问题
: 变出来
【在 s***3 的大作中提到】
: 10个人每人要握三次手好像做不到。题目肯定有问题
:
:
: 这题谁出的？
:
: 是很很很复杂的。
:
: 可以把它归类成graph。每个节点3个分叉。
:
: 有很多graphs，其中有些对应很多解。
:
: 不少图有局部节点置换、局部旋转、局部翻转和它们结合的对称性。
:
: 还有的graphs是有分离或近分离的子图。比如4和6个节点的子图，以及从它们转
: 变出来
:
: 的连图。
| w********9
发帖数: 8613 | 35
图是
有非常非常非常非常多的解。
比如：
把人编号1-10
最简单的一类解是：
1，2，3，4，5构“外环”
10，9，8，7，6内环
让数目加起来是11的2人都握手
把内环变成五角星也是一类解
每类做1-5对节点的互换可以生成很多解
还有几种其它类。。。
【在 s***3 的大作中提到】
: 10个人每人要握三次手好像做不到。题目肯定有问题
:
:
: 这题谁出的？
:
: 是很很很复杂的。
:
: 可以把它归类成graph。每个节点3个分叉。
:
: 有很多graphs，其中有些对应很多解。
:
: 不少图有局部节点置换、局部旋转、局部翻转和它们结合的对称性。
:
: 还有的graphs是有分离或近分离的子图。比如4和6个节点的子图，以及从它们转
: 变出来
:
: 的连图。
| G**********s
发帖数: 1 | 36 自己发现了自己的错误。此处解法是错的。我马上会在后面发出更正结果。 | T*******x
发帖数: 8565 | 37 这个题有这么难？我觉得题的定义还不是完全清楚。
【在 G**********s 的大作中提到】
: 自己发现了自己的错误。此处解法是错的。我马上会在后面发出更正结果。
| s*****1
发帖数: 1 | 38 非常感谢！ 没想到老兄如此尽心解答了
我稍微花些时间理解一下
: 题目：10个点（分别计为A1~A10），两两间可以有0或1条连线，每点恰有3边（
即每点
: 恰与另3点各有1条连线），问这样的图的数目。
: 包括写本贴（同时纠错），费时约4小时，解法很丑陋且无法推广到任意2N（N
【在 G**********s 的大作中提到】
: 自己发现了自己的错误。此处解法是错的。我马上会在后面发出更正结果。
| R**********s
发帖数: 45 | 39
快睡觉了看到这个题，讨论下个人的想法，对1, 2, 3, 4, 5, 6貌似是对的，后面的没
时间来逐个验证正确性。
假设m个人，要和另外的n个人握手，条件是： m>n并且m和n必须满足(m-1)/n是整数。
如果按题中握手3次，那么人数1,2,3,个人肯定不行。
人数是4：(4-1)/3=1 这个可以
人数是5：(5-1)/3=1+1/3不行, 总是有1个人无法满足握3次手。
人数是6：(6-1)/3=1+2/3不行,总是有2个人无法满足握3次手。
人数是7：(7-1)/3=2 这个可以
所以只有4，7, 10, 13, 16， 以此类推，可以满足都握3次手。
握手次数等于：(m-1)*(m-2)*(m-3)…..(m-n)/n*(n-1)*(n-2)…1
所以4个人有 3*2*1/3*2*1 = 1种握法
7个人有 6*5*4/3*2*1 = 20种握法
10个人有 9*8*7/3*2*1 = 84种握法
以此类推
【在 s*****1 的大作中提到】
: 原题是一个简单的小学奥数题：
: There are 10 people in a room. If each person shakes hands with exactly 3
: other people, what is the total number of handshakes?
: 现在不问握手次数 而是问有几种握法 请问有几种？ 不要枚举(打码)解法
: 注意：现在问的是握法，比如四个人只有一种握法
: 今天一下被问住了 旽旽旽
| s*****1
发帖数: 1 | 40 谢谢分享想法！ 但你这个可能不太对
6个人肯定是可以满足的
而奇数人一定不能满足条件
: 快睡觉了看到这个题，讨论下个人的想法，对1, 2, 3, 4, 5, 6貌似是对
的，后
面的没
: 时间来逐个验证正确性。
: 假设m个人，要和另外的n个人握手，条件是： m
【在 R**********s 的大作中提到】
:
: 快睡觉了看到这个题，讨论下个人的想法，对1, 2, 3, 4, 5, 6貌似是对的，后面的没
: 时间来逐个验证正确性。
: 假设m个人，要和另外的n个人握手，条件是： m>n并且m和n必须满足(m-1)/n是整数。
: 如果按题中握手3次，那么人数1,2,3,个人肯定不行。
: 人数是4：(4-1)/3=1 这个可以
: 人数是5：(5-1)/3=1+1/3不行, 总是有1个人无法满足握3次手。
: 人数是6：(6-1)/3=1+2/3不行,总是有2个人无法满足握3次手。
: 人数是7：(7-1)/3=2 这个可以
: 所以只有4，7, 10, 13, 16， 以此类推，可以满足都握3次手。
| | | R**********s
发帖数: 45 | 41
修改一下：
假设m个人，要和另外的n个人握手，条件是： m>n并且m*n/2必须是整数。
如果按题中握手3次，那么人数1,2,3,个人肯定不行。
人数是4：4*3/2=6 这个可以
人数是5：5*3/2=7+1/2不行, 总是有1个人无法满足握3次手。
人数是6：6*3/2=9 这个可以
所以只有4，6, 8, 10, 以此类推，可以满足都握3次手。
握手次数等于：(m-1)*(m-2)*(m-3)…..(m-n)/n*(n-1)*(n-2)…1
所以4个人有 3*2*1/3*2*1 = 1种握法
6个人有 5*4*3/3*2*1 = 10种握法
10个人有 9*8*7/3*2*1 = 84种握法
我看上面有好几个算法，楼主得穷举一下比较小的几个数，比如4,6, 8之类的，有个基
本的正确数值，才能验证各个算法那个是可能正确的。你算出来4,6,8的正确数值是多
少？
【在 s*****1 的大作中提到】
: 谢谢分享想法！ 但你这个可能不太对
: 6个人肯定是可以满足的
: 而奇数人一定不能满足条件
:
:
: 快睡觉了看到这个题，讨论下个人的想法，对1, 2, 3, 4, 5, 6貌似是对
: 的，后
: 面的没
:
: 时间来逐个验证正确性。
:
: 假设m个人，要和另外的n个人握手，条件是： m
| t**8
发帖数: 4527 | 42 GMAT test
10C2/3 = 45 / 3 = 15
【在 s*****1 的大作中提到】
: 原题是一个简单的小学奥数题：
: There are 10 people in a room. If each person shakes hands with exactly 3
: other people, what is the total number of handshakes?
: 现在不问握手次数 而是问有几种握法 请问有几种？ 不要枚举(打码)解法
: 注意：现在问的是握法，比如四个人只有一种握法
: 今天一下被问住了 旽旽旽
| G**********s
发帖数: 1 | 43 不客气。我才发现我上面解法有错（大方向是对的），马上我会发贴更新解法。
【在 s*****1 的大作中提到】
: 非常感谢！ 没想到老兄如此尽心解答了
: 我稍微花些时间理解一下
:
:
: 题目：10个点（分别计为A1~A10），两两间可以有0或1条连线，每点恰有3边（
: 即每点
:
: 恰与另3点各有1条连线），问这样的图的数目。
:
: 包括写本贴（同时纠错），费时约4小时，解法很丑陋且无法推广到任意2N（N
| G**********s
发帖数: 1 | | w********9
发帖数: 8613 | 45
2)
V1
我第一感觉是有错。
如果考虑只有8个人的情况
（1）的情况是
有8！/4！/4！/2=35个解
而你的是35*6=210个解。
不考虑生成图的对称性必然错。
【在 G**********s 的大作中提到】
: 仍错。错因略。马上更新第三版。
| G**********s
发帖数: 1 | 46 题目：10个点（分别计为V1~V10），两两间可以有0或1条连线，每点恰有3边（即每点
恰与另3点各有1条连线），问这样的图的数目。
解：记为图G(10,3)，要求的这样的图的数目记为N(10,3)；则如果是6点、每点2边则为
G(6,2)，其数目为N(6,2)。需求N(10,3)。
N(3,2)=1
N(4,2)=3
N(5,2)=3*4=12
N(6,2)：分2种情况：
情况1：两个三角形：C(6,3)/2=10
情况2：连通：6!/6/2=60
N(6,2)=10+60=70
【解法2（直接构造）：C(5,2)*(1+C(3,1)*C(2,1))=70】
N(7,2)：分2种情况：
情况1：1个三角形+1个四边形：C(7,3)*N(4,2)=35*3=105
情况2：连通：7!/7/2=360
N(7,2)=105+360=465
【解法2（直接构造）：C(6,2)*(N(4,2)+C(4,1)*(1+C(3,1)*C(2,1)))=465】
N(8,2)：分3种情况：
情况1：2个四边形：C(8,4)/2*N(4,2)^2=35*3^2=315
情况2：1个三角形+1个五边形：C(8,3)*N(5,2)=56*12=672
情况2：连通：8!/8/2=2520
N(8,2)=315+672+2520=3507
【解法2（直接构造）：C(7,2)*(N(5,2)+C(5,1)*(N(4,2)+C(4,1)*(1+C(3,1)*C(2,1)))
)=3507】
【由此已可看出N(n,2)的一般规律了】
前面N(n,2)的求解是对的，后面N(10,3)自查发现有大错，要推倒重来，先删了，汗…… | T********2
发帖数: 1 | 47 问题定义清楚了。解法我觉得没有问题。结果比较复杂，我没有验证。
【在 G**********s 的大作中提到】
: 题目：10个点（分别计为V1~V10），两两间可以有0或1条连线，每点恰有3边（即每点
: 恰与另3点各有1条连线），问这样的图的数目。
: 解：记为图G(10,3)，要求的这样的图的数目记为N(10,3)；则如果是6点、每点2边则为
: G(6,2)，其数目为N(6,2)。需求N(10,3)。
: N(3,2)=1
: N(4,2)=3
: N(5,2)=3*4=12
: N(6,2)：分2种情况：
: 情况1：两个三角形：C(6,3)/2=10
: 情况2：连通：6!/6/2=60
| A******u
发帖数: 1279 | 48
【在 s*****1 的大作中提到】
: 原题是一个简单的小学奥数题：
: There are 10 people in a room. If each person shakes hands with exactly 3
: other people, what is the total number of handshakes?
: 现在不问握手次数 而是问有几种握法 请问有几种？ 不要枚举(打码)解法
: 注意：现在问的是握法，比如四个人只有一种握法
: 今天一下被问住了 旽旽旽
| G**********s
发帖数: 1 | 49 赞！请问是用什么软件生成的？若有相关源程序，能否公之于众？谢谢。
【在 A******u 的大作中提到】
| A******u
发帖数: 1279 | 50 Mathematica command
Table[GraphPlot[GraphData[g, "EdgeRules"]], {g, GraphData["Cubic", 10]}] | | | c******8
发帖数: 445 | 51 这个软件很好啊，不过第三排靠左两个图形是错的？
：Mathematica command
： | R**********s
发帖数: 45 | 52
哇，老哥你太牛了！膜拜膜拜！！
你这个里面是不是每个点都是看做相同的？如果按楼主的问题，不同人的话，是不是还
要加一步，把不同的人放入这些点里面？
如果每个位置都不同的话，那放人很简单。但是好像很多图都是镜像重复的，尤其有好
几个图都是上下左右都是镜像重复的，这样问题好像又变得更复杂了。。。
【在 A******u 的大作中提到】
: Mathematica command
: Table[GraphPlot[GraphData[g, "EdgeRules"]], {g, GraphData["Cubic", 10]}]
| w********9
发帖数: 8613 | 53
错。
6人握手有一种是3-3内外圈含
编号
6！/3!/3!(分3人、3人两组，现选内组后选外）
*
3！*3！/3/2(各分“位”构环，位无别后虑；链接内外；位无别；内外无别；翻转无别）
=60种
还有一种是4人单连圈；中间放两人链，每个再跟外面的链接。后一种链接有2种方式：
外圈邻居在一组，或不在一组。前者是平面型/planar，后者不是。算算。
【在 R**********s 的大作中提到】
:
: 哇，老哥你太牛了！膜拜膜拜！！
: 你这个里面是不是每个点都是看做相同的？如果按楼主的问题，不同人的话，是不是还
: 要加一步，把不同的人放入这些点里面？
: 如果每个位置都不同的话，那放人很简单。但是好像很多图都是镜像重复的，尤其有好
: 几个图都是上下左右都是镜像重复的，这样问题好像又变得更复杂了。。。
| w********9
发帖数: 8613 | 54
【4，2】就是错的
一圈
4！/4/2=3
2组，每组2人，
4！/2！/2！/2
=3
【在 G**********s 的大作中提到】
: 题目：10个点（分别计为V1~V10），两两间可以有0或1条连线，每点恰有3边（即每点
: 恰与另3点各有1条连线），问这样的图的数目。
: 解：记为图G(10,3)，要求的这样的图的数目记为N(10,3)；则如果是6点、每点2边则为
: G(6,2)，其数目为N(6,2)。需求N(10,3)。
: N(3,2)=1
: N(4,2)=3
: N(5,2)=3*4=12
: N(6,2)：分2种情况：
: 情况1：两个三角形：C(6,3)/2=10
: 情况2：连通：6!/6/2=60
| w********9
发帖数: 8613 | 55
是的
种类很多
有的有旋转重复、翻转重复或镜像重复的“减少”
还有节点人的置换增生
这题非常复杂
大家别费脑子了
【在 A******u 的大作中提到】
: Mathematica command
: Table[GraphPlot[GraphData[g, "EdgeRules"]], {g, GraphData["Cubic", 10]}]
| T********2
发帖数: 1 | 56 这个图看着真挺酷。
【在 A******u 的大作中提到】
| T********2
发帖数: 1 | 57 那两个图没错，有三个点离的很近，看起来重合了。
【在 c******8 的大作中提到】
: 这个软件很好啊，不过第三排靠左两个图形是错的？
:
: ：Mathematica command
: ：
| T********2
发帖数: 1 | 58 总共21个。非常好。
【在 A******u 的大作中提到】
| T********2
发帖数: 1 | 59 你说的也有道理。对每个图考虑label的排列方式，每个图都不一样，总体是挺复杂的
。但是能得到21个图，接下来就好办一些。还是要定义清楚什么样的两种labeling算同
一个。
【在 w********9 的大作中提到】
:
: 是的
: 种类很多
: 有的有旋转重复、翻转重复或镜像重复的“减少”
: 还有节点人的置换增生
: 这题非常复杂
: 大家别费脑子了
| T********2
发帖数: 1 | 60 对。是还有点复杂。但是至少问题的定义可以很简单，就是看edge集合，edge定义为无
序对，也就是两个元素的集合。edge集合相等的两个图算同一个。
【在 R**********s 的大作中提到】
:
: 哇，老哥你太牛了！膜拜膜拜！！
: 你这个里面是不是每个点都是看做相同的？如果按楼主的问题，不同人的话，是不是还
: 要加一步，把不同的人放入这些点里面？
: 如果每个位置都不同的话，那放人很简单。但是好像很多图都是镜像重复的，尤其有好
: 几个图都是上下左右都是镜像重复的，这样问题好像又变得更复杂了。。。
| | | T********2
发帖数: 1 | 61 对每个图做一次计算，每个图从10!的label排列中计算，每一次计算得到一个15个edge
的集合，每一个图有10!=3.6M个计算，得到一个集合的集合。这变成了一个编程题。
【在 T********2 的大作中提到】
: 对。是还有点复杂。但是至少问题的定义可以很简单，就是看edge集合，edge定义为无
: 序对，也就是两个元素的集合。edge集合相等的两个图算同一个。
| A****C
发帖数: 1 | 62 就是茴香豆的“茴”字有几种写法。
【在 w********9 的大作中提到】
:
: 是的
: 种类很多
: 有的有旋转重复、翻转重复或镜像重复的“减少”
: 还有节点人的置换增生
: 这题非常复杂
: 大家别费脑子了
| w********9
发帖数: 8613 | 63
这题的复杂性我算是了解很多了。从简单题目做起就知道。
如果能做出简单些的，比如【8，3】或者【10，2】等等，就知道有些什么在里面需要
考虑了。
如果有一定的排列组合（尤其是有点复杂的counting）、群论（对称群和置换群）和图
论知识，那我前面说的东西一般都不会难理解。
【在 T********2 的大作中提到】
: 你说的也有道理。对每个图考虑label的排列方式，每个图都不一样，总体是挺复杂的
: 。但是能得到21个图，接下来就好办一些。还是要定义清楚什么样的两种labeling算同
: 一个。
| s*****1
发帖数: 1 | 64 嗯 我问的时候完全没想到如此复杂
谢谢各位大神解答 我也再自己想想
: 这题的复杂性我算是了解很多了。从简单题目做起就知道。
: 如果能做出简单些的，比如【8，3】或者【10，2】等等，就知道有些什么在里
面需要
: 考虑了。
: 如果有一定的排列组合（尤其是有点复杂的counting）、群论（对称群和置换群
）和图
: 论知识，那我前面说的东西一般都不会难理解。
【在 w********9 的大作中提到】
:
: 这题的复杂性我算是了解很多了。从简单题目做起就知道。
: 如果能做出简单些的，比如【8，3】或者【10，2】等等，就知道有些什么在里面需要
: 考虑了。
: 如果有一定的排列组合（尤其是有点复杂的counting）、群论（对称群和置换群）和图
: 论知识，那我前面说的东西一般都不会难理解。
| T*******x
发帖数: 8565 | 65 这个问题叫cubic graph。是一个很重要的graph。wiki上有介绍。undirected 的情况
好像没有通项公式。tree的情况都没有通项公式，这个比tree复杂。
【在 w********9 的大作中提到】
:
: 这题的复杂性我算是了解很多了。从简单题目做起就知道。
: 如果能做出简单些的，比如【8，3】或者【10，2】等等，就知道有些什么在里面需要
: 考虑了。
: 如果有一定的排列组合（尤其是有点复杂的counting）、群论（对称群和置换群）和图
: 论知识，那我前面说的东西一般都不会难理解。
| T********2
发帖数: 1 | 66 这个问题是10个vertex的cubic graph的问题。Cubic graph就是每个vertex上有3个
edge。考虑undirected graph，每个edge就是一个vertex pair，无序。
还分labeled和unlabeled两种。labeled就是vertex命名为1到10，两个graph相等必须
两个edge set相等。unlabeled是如果两个graph之间可以通过vertex重命名，使得两个
edge set相等，那么这两个graph算同一个unlabeled graph。也就是labeled graph空
间的等价类空间。
这个问题的结论是，10个vertex的unlabeled cubic graph共21种，其中19种是联通的
，2种是不联通的。labeled的情况我觉得在unlabeled的基础上算并不难，我算了一种。
下面主要考虑unlabeled的情况。
首先扫一下外围。n个vertex，cubic graph，那么一共3n/2个edge，所以n必须是偶数
。n=2不行。n=4可以，这是最少vertex的情况。
这个graph如果是不连通的，那么每一个component都是小的cubic graph，这个问题被
降解。所以接下来只考虑连通图。
我看到前面一个人贴的mathematica的计算和结果图，非常向往，想要用python算一下
。解决了一些问题，但是中间还是有一步用了brute force的算法。这步我还在想，看
看有没有更好的算法。因为brute force的算法对这个10vertex还勉强，12个就很慢了
，再往上应该就不行了。
思路是限定命名和连接方式，挤出对称性，使生成的labeled graph的集合越小越好。
然后在这个集合上分类。对称性如果全部挤出的话，那得到的直接就是unlabeled
graph集合。但是我觉得可能不能做到。所以再分类这一步可能不可避免。这一步我用
了brute force的算法。这是需要改进的地方。
限定命名和连接方式，我用了一个假设：最长链长度为10，也就是可以一笔连完。
这个是我观察了前面一个人贴图，我发现联通图中最长链长度都为10。我又看了几个
wiki上著名的cubic graph，都是可以一笔连完的。我觉得这个应该可以在数学上证明。
有了这个假设就挤出了很多对称性。从1到10的vertex，链条连接就有了9条边，接下来
只需要安排剩下的6条边。这一步编程算一下，得到725个图。
也就是说有725个labeled cubic graph，其中每一个都有从1到10的9条边的链条。所以
记录其中一个graph，只需要记录6条边，因为从1到10的9条边是固定的(1,2),(2,3),..
.(9,10).
但是这725个图中，有很多代表相同的unlabeled graph。如何把它们分为等价类，这就
是问题的关键。等价类的定义是，前面已经说了，存在一个permutation，使一个图的
edge set变为另外一个图的edge set，那两图就是同一等价类。但是permutation
group太大，10!=3.6M。目标是要找一个小一点的group，就是permutation group的子
群，使得用这个子群中的permutation，就足以验证725图中的两个属于同一等价类。
但是没找到。是有一些小的群，比如reflection群，但是不足以测试任意两个。
所以这一步我是brute force，用3.6M个permutation来找出725图中一个图的所有等价
类图。下面是19个图，每一个是一个等价类的representation。最右边一列是这个等价
类中有多少个图。
((1, 3), (1, 4), (2, 5), (6, 9), (7, 10), (8, 10)) 4
((1, 3), (1, 4), (2, 6), (5, 9), (7, 10), (8, 10)) 11
((1, 3), (1, 4), (2, 7), (5, 9), (6, 10), (8, 10)) 50
((1, 3), (1, 4), (2, 8), (5, 10), (6, 9), (7, 10)) 16
((1, 3), (1, 4), (2, 8), (5, 10), (6, 10), (7, 9)) 24
((1, 3), (1, 5), (2, 7), (4, 9), (6, 10), (8, 10)) 106
((1, 3), (1, 5), (2, 8), (4, 10), (6, 9), (7, 10)) 66
((1, 3), (1, 5), (2, 8), (4, 10), (6, 10), (7, 9)) 53
((1, 3), (1, 6), (2, 8), (4, 9), (5, 10), (7, 10)) 42
((1, 3), (1, 6), (2, 8), (4, 10), (5, 9), (7, 10)) 126
((1, 3), (1, 6), (2, 8), (4, 10), (5, 10), (7, 9)) 34
((1, 3), (1, 6), (2, 9), (4, 7), (5, 10), (8, 10)) 31
((1, 3), (1, 6), (2, 10), (4, 8), (5, 10), (7, 9)) 20
((1, 4), (1, 6), (2, 8), (3, 9), (5, 10), (7, 10)) 13
((1, 4), (1, 6), (2, 8), (3, 10), (5, 9), (7, 10)) 71
((1, 4), (1, 6), (2, 9), (3, 8), (5, 10), (7, 10)) 14
((1, 4), (1, 7), (2, 10), (3, 8), (5, 9), (6, 10)) 35
((1, 4), (1, 8), (2, 5), (3, 10), (6, 9), (7, 10)) 7
((1, 5), (1, 8), (2, 10), (3, 7), (4, 9), (6, 10)) 2
【在 T*******x 的大作中提到】
: 这个问题叫cubic graph。是一个很重要的graph。wiki上有介绍。undirected 的情况
: 好像没有通项公式。tree的情况都没有通项公式，这个比tree复杂。
| T********2
发帖数: 1 | 67 等价类的算法解决了。
一个长链graph到另一个长链graph的变换，取决于该graph中全部长链，每一个长链对
应一个permutation。一个10 vertex cubic graph中长链数大概几百个吧，这比
permutation group小多了，但是随graph的不同而变化。
用这个算法做等价类的分类快多了。现在的瓶颈不在分类了，在于前面一步产生全部
labeled的长链graph。12个vertex的联通cubic graph有85种，这个算起来还比较快。
14个vertex就很慢了，现在算快一个小时了，还卡在第一步。
6个vertex的联通图有2种，10个里面就包含这个。
8个vertex的联通图有5种，加上不联通的就是6种。
12个vertex的联通图有85种，不连通的可以有8+4,6+6,4+4+4，所以是10种，总共95种。
种。
【在 T********2 的大作中提到】
: 这个问题是10个vertex的cubic graph的问题。Cubic graph就是每个vertex上有3个
: edge。考虑undirected graph，每个edge就是一个vertex pair，无序。
: 还分labeled和unlabeled两种。labeled就是vertex命名为1到10，两个graph相等必须
: 两个edge set相等。unlabeled是如果两个graph之间可以通过vertex重命名，使得两个
: edge set相等，那么这两个graph算同一个unlabeled graph。也就是labeled graph空
: 间的等价类空间。
: 这个问题的结论是，10个vertex的unlabeled cubic graph共21种，其中19种是联通的
: ，2种是不联通的。labeled的情况我觉得在unlabeled的基础上算并不难，我算了一种。
: 下面主要考虑unlabeled的情况。
: 首先扫一下外围。n个vertex，cubic graph，那么一共3n/2个edge，所以n必须是偶数
| T********2
发帖数: 1 | 68 14 vertex的结果出来了。共509种。算了1个半小时，都在第一步，第二步只用一分钟。
种。
【在 T********2 的大作中提到】
: 等价类的算法解决了。
: 一个长链graph到另一个长链graph的变换，取决于该graph中全部长链，每一个长链对
: 应一个permutation。一个10 vertex cubic graph中长链数大概几百个吧，这比
: permutation group小多了，但是随graph的不同而变化。
: 用这个算法做等价类的分类快多了。现在的瓶颈不在分类了，在于前面一步产生全部
: labeled的长链graph。12个vertex的联通cubic graph有85种，这个算起来还比较快。
: 14个vertex就很慢了，现在算快一个小时了，还卡在第一步。
: 6个vertex的联通图有2种，10个里面就包含这个。
: 8个vertex的联通图有5种，加上不联通的就是6种。
: 12个vertex的联通图有85种，不连通的可以有8+4,6+6,4+4+4，所以是10种，总共95种。
| G**********s
发帖数: 1 | 69
……
正确答案是11180820。我的解法大方向100%正确，但太多细节、至今仍有错、没能磨出
正确答案。前后共花了近50个小时，4/25后忙于它事就再没管了；当时的错误答案（见
下）是11619300。下面把这个仍有错（但大方向100%正确）的解法贴出来（也贴到我的
博客）。此解法能配以计算机编程解决，本来打算纯手工得到正确答案后再在重拾当初
的编程能力后再做，在未来几年也应没时间做了。
此题应该有更好的数学工具和相应的更好方法。比如，此题也是求这样的10*10矩阵的
数目：矩阵左上到右下对角线上全为0，其它位置非0即1，且矩阵中任一行或列求和都
为3。所以此题可能有线性代数相关解法。我已经近20年没有碰高数，数分线代等等全
忘光了（其实组合数学、图论亦然，只是此二者不需要多少记忆），虽下载了当年大学
的《线性代数》教材，稍微看了一下，仍没头绪……让行家见笑了。
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
正确答案链接（没有解法）
https://oeis.org/search?q=cubic+graph+labeled&sort=&language=&go=Search
1, 0, 1, 70, 19355, 11180820, 11555272575, 19506631814670, 50262958713792825
, 187747837889699887800, 976273961160363172131825,
6840300875426184026353242750, 62870315446244013091262178375075,
741227949070136911068308523257857500 (list; graph; refs; listen; history;
text; internal format)
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
题目：10个点（分别计为#1~#10），两两间可以有0或1条连线，每点恰有3边（即每点
恰与另3点各有1条连线），问这样的图的数目。
解：记为图G(10,3)，要求的这样的图的数目记为N(10,3)；则如果是6点、每点2边则为
G(6,2)，其数目为N(6,2)。需求N(10,3)。
注意有N(m,k)=N(m,m-1-k) m>K
N(3,2)=N(3,0)=1
N(4,2)=N(4,1)=3【解法2：N(4,2)=4!/4/2=3】
N(5,2)=N(4,2)*4=3*4=12【解法2：N(5,2)=5!/5/2=12】
N(6,2)：分2种情况：
情况1：两个三角形：C(6,3)/2=10
情况2：连通：6!/6/2=60
N(6,2)=10+60=70
【解法2（直接构造）：C(5,2)*(1+C(3,1)*C(2,1))=70】
N(7,2)：分2种情况：
情况1：1个三角形+1个四边形：C(7,3)*N(4,2)=35*3=105
情况2：连通：7!/7/2=360
N(7,2)=105+360=465
【解法2（直接构造）：C(6,2)*(N(4,2)+C(4,1)*(1+C(3,1)*C(2,1)))=465】
N(8,2)：分3种情况：
情况1：2个四边形：C(8,4)/2*N(4,2)^2=35*3^2=315
情况2：1个三角形+1个五边形：C(8,3)*N(5,2)=56*12=672
情况2：连通：8!/8/2=2520
N(8,2)=315+672+2520=3507
【解法2（直接构造）：C(7,2)*(N(5,2)+C(5,1)*(N(4,2)+C(4,1)*(1+C(3,1)*C(2,1)))
)=3507】
【由此已可看出N(n,2)的一般规律了】
---------------------------------------------------
1234四种情况间，因#1~4与#5~10间连线数不同，彼此不可能重复，若有重复只可能是
各自内部
---------------------------------------------------
分情况讨论：期待答案：11180820=84*133105
结论01：记G(4,1333)为4点，其中各点分别在内部连出1、3、3、3边，此为无解。
结论02：G(5,13333且“1”确定)：“1”确定意思是该图与外界二线已确定
考察#1点，与#1有连线的3点，记为#2~4【C(9,3)=84】，考察#2~4这3点和余下6点#5~
10间的连线：因为“偶数点团向外连线数+2*偶数点团内边数=偶数点团内点数*3”，所
以偶数点团#1~4向外连线数必为偶数，#234至多向外有2条连线，所以总数≤6，即连线
数为0、2、4、6。如下讨论，得：84*(70+5400+64980+67875)=11619300
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
（1）连线数=0，则只可能是#1~4构成一个4阶完全图，#5~10为G(6,3)：N(6,3)=N(6,2)
=70
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
（2）连线数=2，则#2~4点中必有2点各向外伸出1线（不可能是一点向外伸出2线），记
为#2、#3【C(3,2)=3】，如下讨论，共有可能：3*(180+1620)=5400
（2-1）若此2线连向#5~10中1点，记为#5【C(6,1)=6】，则#5与#6~10中唯一某点有唯
一连线，记为#6【C(5,1)=5】。此为G(5,13333且“1”确定)。如下，共有：6*5*6=180
下面求N(5,13333且“1”确定)：记#6连的另2点为#78【C(4,2)=6】，则只能#9#10都连
#78再彼此相连，唯一解。所以N(5,13333且“1”确定)=6。
（2-2）若此2线连向#5~10中2点，如下讨论，共有：360+1260=1620
（2-2-1）若该2点有连线。记该2点为#56【C(6,2)=15】，则#56相连。记#5连#2【C(2,
1)=2】，则#6连#3。此是G(6,113333且“11”确定)：若#56连向同一点，余G(4,1333)
，无解；所以#56连向#7~10的不同两点，则有一一对应构造法：先让#7~10两两连线成1
个4阶完全图，再断开此4阶完全图中任一边【C(6,1)=6】把边上两点分别连到#5、#6【
2!=2】，共有：15*2*6*2=360
（2-2-2）否则，该2点无连线。
法1：则有一一映射构造法：先让#5~10这6点先成一个G(6,3)【N(6,3)】，再断开G(6,3
)中任一边【6*3/2=9】，把该边2点与#2、#3相连，都有【2!】个唯一解，且一一对应
。共有：N(6,3)*9*2!=70*9*2=1260
法2：记该2点为#56【C(6,2)=15】，则#56无连线。记#5连#2【C(2,1)=2】，则#6连#3
。则有一一映射构造法：让#5~10这6点先成一个G(6,3)且该G(6,3)中#56间必须有连线
【由下知=42】，再断开#56连线，#5连#2，#6连#3。共有：15*2*42=1260
设G(6,3)中#56有连线的个数为x。据全对称性，6阶完全图共有C(6,2)=15条边，G(6,3)
边数6*3/2=9，15*x=70*9，所以x=70*9/15=42。
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
（3）连线数=4。记#2为#234中唯一连出2线的点【C(3,1)】，则#34相连。按余下6点接
收此4线数目分类讨论，共有：C(3,1)*(180+780+10980+9720)=64980
（3-1）“310000”：记“3”#5【C(6,1)=6】，“1”#6【C(5,1)=5】，则#2连到#6，
由此为G(5,13333且“1”确定)。共有：6*5*N(5,13333且“1”确定)=6*5*6=180【勿需
再验了】
（3-2）“220000”：“22”记为#56【C(6,2)】，记#23【C(2,1)】连#5【C(2,1)】，
则#24连#6。如下讨论，共有：C(6,2)*C(2,1)*C(2,1)*(1+12)=60*13=780
（3-2-1）若#5、#6间有连线，则余下#7~10成4阶完全图，共有：1
（3-2-2）否则，#5、#6间无连线。若#56连向#7~10的同点，则#7~10余下为G(4,1333)
，无解；所以#56连向#7~10的异点，则有一一对应构造法（同2-2-1）：先让#7~10两两
连线成1个4阶完全图，再断开此4阶完全图中任一边【C(6,1)】把边上两点分别连到#5
、#6【2!】，共有：C(6,1)*2!=12
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
（3-3）“211000”：“2”记为#5【C(6,1)】。如下讨论，共有：C(6,1)*(1560+270)=
6*1830=10980
即求G(6,122333)
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▄▄▄▄▄▄▄
（3-3-1）若#2连#5，则34之一连#5，记#3连#5【C(2,1)=2】，#24余下各1线连向#6~10
上相异2点XY（“11”），#5余下1线连#6【C(5,1)=5】。如下讨论，共有：2*5*(24+
132)=1560
（3-3-1-1）若#6也连#24之一，即#6是“1”，记#26相连【C(2,1)=2】。因#46连向#7~
10的不能是同一点，否则G(4,1333)无解，所以#46连向的是#7~10的2个不同点，由此有
一一映射构造法：#7~10先成1个4阶完全图，再断开此4阶完全图中任一边【C(6,1)=6】
把边上两点分别连到#46【2!=2】，共有：2*6*2=24
（3-3-1-2）否则，若#6连向#7~10的两点和#24连向#7~10的两点是同2点，G(4,1133)，
无解。所以#6余下2线和#24连出2线到达的是#7~10点团上不同边。记#6连的#7~10中2点
为#78【C(4,2)=6】。如下讨论，共有：6*(8+14)=132
若#78间有连线，则只可能#78余下2线连向#9#10上不同点【2!】再#9#10相连。共
有：C(4,2)*2!=8
否则，#78间无连线。如下讨论，共有：6+8=14
若#24到达的是#9#10二点【2!=2】，则#7~10成G(4,2)【N(4,2)=3】。共有：2
*3=6
否则，#24必有且仅有一线连#78之一，记#2【C(2,1)=2】到达#7【C(2,1)=2】
，则#4连#9#10之一，记#4连#9【C(2,1)=2】，则只能#10必连#789、#89相连，唯一解
。共有：2*2*2=8
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▄▄▄▄▄▄▄
（3-3-2）否则，即#25无连线，则只能是#34连#5，#5的2线连向“11”（记为#67【C(5
,2)】）。如下讨论，共有：C(5,2)*(12+15)=270
若#567间有连线，则因#8~10的点团内三点必向外各发出至少1线（共3线），而#
567共余5线，所以#567之间至多(5-3)/2=1线。
如果#567间有1线，则#567会向#8~10伸出3线。如下讨论，共有：6+6=12
#56或#57连线，记#56连线【C(2,1)】，则只能#67余下3线向#8~10不同点连线
【C(3,1)】，再#8~10两两相连：C(2,1)*C(3,1)=6。
#67连线，则只能#567余下3线向#8~10不同点连线【3!】，再#8~10两两相连：
3!=6
否则，#567间无连线。若#567连向#8~10中同一点，无解。因#8~10将接收#567共5
线，则#8~10自身将有(3*3-5)/2=2条连线。记#8【C(3,1)】向#9#10连线，则#9#10间无
连线。如下讨论，共有：C(3,1)*(1+4)=15
若#58相连，则有1解：1
若#59【C(2,1)】相连，则有2解：C(2,1)*2=4
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
（3-4）“111100”，即G(222233)：记#2连的#7~10中的2点是#56【C(6,2)=15】，记#3
连#7【C(4,1)=4】、#4连#8【C(3,1)=3】。共有15*4*3*(42+12)=9720
（3-4-1）若#9#10间有连线。则有一一映射构造法：#5~10成G(6,2)，且该G(6,2)中#9#
10间无连线【“？”】，再把#9#10相连。求“？”中值：G(6,2)有两种结构，一是2个
三角形，此时#9#10不能在1个三角形中，满足条件数：C(4,2)=6（另法：C(6,3)/2-C(4
,1)=10-4=6）；二是环形，(6!/6/2)-2!*(5!/5/2)=60-2*12=60-2*12=36。所以“？”=
6+36=42
（3-4-2）#9#10间无连线。则#9#10都向#5678连出3线，且#5678的每点只能至多接受2
线，所以4点中恰有2点都接受#9#10的2线【C(4,2)=6】，另2点只接受#9#10的1线【2!=
2】，该2点再彼此相连，成唯一解。共有：6*2=12
（3-4解法2）记#2连的#7~10中的2点是#56【C(6,2)=15】。如下讨论，共有：15*(192+
144+288)=9360
（3-4-1）若#56间有连线。如下讨论，共有：24+168=192
（3-4-1-1）#56余下各1线连向#7~10中的同一点，记为#7【C(4,1)=4】。记#3连#8【C(
3,1)=3】，#4连#9【C(2,1)=2】则只能#10连#789，再#89相连，唯一解。共有：4*3*2=
24
（3-4-1-2）否则，#56的余下各1线连向的是#7~10中不同2点。如下讨论，共有：0+168
=168
若#56的余下各1线连向#7~10中的2点和#34连向#7~10中的2点相同，则余下点线为G
(4,1133)，无解：0
否则，#56余下各1线连向的和#34连向的是#7~10中的不同边。记#5连#7【C(4,1)=4
】、#6连#8【C(3,1)=3】。如下讨论，共有：4*3*(6+8)=168
若#34分别连#9#10【2!=2】，则#7~10为G(4,2)【N(4,2)=3】，共有：2*3=6
否则，因#34不能都连#78（如上，无解），所以#34中有且仅有1点连#9#10之
一。记#3【C(2,1)=2】连#9【C(2,1)=2】，则#4必连#78之一，记#4连#7【C(2,1)=2】
，则#10必连#789，再#89相连，唯一解。共有：2*2*2=8
（3-4-2）若#56间无连线，但#34连的#7~10中的2点间有连线。记#3连#7【C(4,1)=4】
、#4连#8【C(3,1)=3】，则#78相连。如下讨论，共有：4*3*(2+8+2)=144
（3-4-2-1）若#78余下各1线都连向#56：如果连向同一点，余下点线为G(3,233)，无解
；否则，则连向不同点【2!=2】，余下点线为G(4,1133)，有唯一解。共有：2
（3-4-2-2）否则，若#78余下各1线有1线连向#56，记#7【C(2,1)=2】连#5【C(2,1)=2
】，则#6余下2线只能连#9#10，#5余下1线连#9#10之一，记#5连#9【C(2,1)=2】，则#
10连#89，唯一解。共有：2*2*2=8
（3-4-2-3）否则，#78余下各1线都不连向#56，则只能连向#9#10。如下讨论，共有：0
+2=2
若#78余下各1线连向#9#10同一点，记#9【C(2,1)=2】，则#10必连#569，但此处#
56不能相连，无解。共有：0
否则，#78余下各1线连向#9#10不同点，记#7连#9【C(2,1)=2】，则#8连#10。余下
必为#56的余下各2线都连#9#10，唯一解。共有：2
（3-4-3）余下只能是：#56没有连线，且#34连的#7~10中的2点无连线。记#3连#7【C(4
,1)=4】、#4连#8【C(3,1)=3】，则#78无连线。因#9#10至少向外引出4线，所以#5678
内部至多有(8-4)/2=2线。如下讨论：4*3*(4+12+8)=288
（3-4-3-1）#56之一引出2线连#78，记#5【C(2,1)=2】，则#6连#9#10，#78分别连#9#
10【2!=2】，最后#9#10相连。共有：2*2=4
（3-4-3-2）#56各引1线分别连#78，记#5连#7【C(2,1)=2】，则#6连#8，#9#10相连后
，再各引出2线分别连#5678之一【C(4,2)=6】。共有：2*6=12
（3-4-3-3）#56与#78间只有1条连线，#5【C(2,1)=2】连#7【C(2,1)=2】，则必#6、#8
余下2线连#9#10，再#57与#9~10分别相连【2!=2】。共有：2*2*2=8
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
（4）连线数=6，把余下6点接受连线的模式用330000、321000这类数字表示：6300+
38880+18360+720+2520+1080+15=67875
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▄▄▄▄▄▄▄
（4-1）111111：只可能是一个123层分别为136点的树，记#1连#56【C(6,2)】，#2连#
78【C(4,2)】，则#3连#9#10。
#5~10点再自成一个G(6,2)【N(6,2)】。共有：C(6,2)*C(4,2)*N(6,2)=15*6*70=6300
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▄▄▄▄▄▄▄
（4-2）211110：记“2”#5【C(6,1)=6】，#2、3连向#5【C(3,1)=3】；“0”为#6【C(
5,1)=5】；#234的余下4线连到#7~10的不同4点，其中#2连#7【C(4,1)】、#3连#8【C(3
,1)】、#4连#9和#10。如下讨论，共有：6*3*5*4*3*(12+24)=1080*36=38880
【由下，N(6,132222)=12+24=36】
（4-2-1）#56相连，则#6~10余下线构成1个G(5,2)：N(5,2)=12
（4-2-2解法1）否则，#56不相连，“0”（#6）的3线必连向#7~10中三点【C(4,3)】。
由如下讨论，共有：C(4,3)*(3+3)=24
若#5连向此3点中1点【C(3,1)】，余下连法唯一，得唯一1图：C(3,1)=3
否则，#5连向非此3点的余下1点，则#7~10为G(4,1)：N(4,1)=3
（4-2-2解法2）否则，#56不相连，记#5连#7【C(4,1)】，由如下讨论：C(4,1)*(3+3)=
24
若#7余下一线连向“0”（#6点），则#6、8~10余下线构成1个G(4,2)：N(4,2)=3
否则，#7余下一线连向某“1”，记为#8【C(3,1)】，则#6必连#8~10（因为其它点
都满了），再#9#10相连：C(3,1)=3
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▄▄▄▄▄▄▄
（4-3）221100：记#2是#2~4中与2个“2”都有连线的唯一点【C(3,1)=3】，“22”是#
56【C(6,2)=15】，#3【C(2,1)=2】连#5，则#23连#5、#24连#6。记“11”是#78【C(4,
2)=6】，#3连#7、#4连#8【2!=2】，如下讨论，共有：3*15*2*6*2*(1+16)=1080*17=
18360
【由下，N(6,112233)=1+16=17】
（4-3-1）“22”（#56）间有连线，则考察任一“0”点，其3条连线只可能连向另一“
0”和“11”，唯一解：1
（4-3-2）“22”（#56）间无连线，如下讨论，共有：0+8+8=16
（4-3-2-1）“22”（#56）与“11”（#78）≥2条连线：0
（4-3-2-2）“22”（#56）与“11”（#78）有且仅有1条连线，记#5连#7【C(2,1)*C(2
,1)=4】，则#6余下1线连向2个“0”之一，记为#9【C(2,1)=2】，则#10必连#789，再#
89相连，成唯一解：4*2*1=8
（4-3-2-3）“22”（#56）与“11”（#78）无连线，则“22”（#56）的2线必连向“
00”。如下讨论，共有：2+6=8
“22”（#56）连向“00”中同一点，记为#9【C(2,1)=2】，则#10必连#789，
再#78相连，成唯一解：2*1=2
“22”（#56）连向“00”中异点，记#5连#9、#6连#10【2!】，再#7~10成一
个G(4,2)：2!*N(4,2)=2*3=6
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▄▄▄▄▄▄▄
（4-4）222000：“222”【C(6,3)】，#234与“222”连线【3!】，每个“0”与至少一
个“2”有连线，所以“000”三点与“222”三点各有一条连线【3!】，余下“000”成
一个G(3,2)【N(3,2)=1】：C(6,3)*3!*3!*1=20*6*6*1=720
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▄▄▄▄▄▄▄
（4-5解法1）311100：记“3”为#5【C(6,1)】，记“111”为#678【C(5,3)】，记#2连
#6、#3连#7、#4连#8【3!】，如下讨论，共有：C(6,1)*C(5,3)*3!*(1+6)=2520【2种解
法，100%对】
（4-5-1）若“00”间无连线，则每个“0”向“111”点团中每个“1”各伸出1线，得
唯一解：1
（4-5-2）否则“00”间有连线，则每个“0”向“111”点团各伸出2线，必有且仅有1
点（记为#6【C(3,1)】）得到2线（否则无解），每个“0”再向余下2个“1”（#78）
各伸出1线【2!】，#78相连：C(3,1)*2!=6
（4-5解法2）311100：记“3”为#5【C(6,1)】，增加1个虚拟点，与“11100”对应5点
组成6点，成G(6,3)【N(6,3)】图后，把向该虚拟点的三线引向#2~4点【3!】。共有：C
(6,1)*N(6,3)*3!=6*70*6=2520
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▄▄▄▄▄▄▄
（4-6）321000：记“3”为#5【C(6,1)】，“2”为#6【C(5,1)】，#6得#23各一线【C(
3,2)】，“1”为#7【C(4,1)】，则#4连#7，#67间不能有连线（否则#7~10余下为G(4,
1333)，无解）。记#6连#8【C(3,1)】，则#7不能连#8（否则无解），所以#7只能连#9
和#10，再#8~10间成G(3,2)【即三角形，N(3,2)=1】。共有：C(6,1)*C(5,1)*C(3,2)*C
(4,1)*C(3,1)*1=1080
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▄▄▄▄▄▄▄
（4-7）330000：“33”【C(6,2)】，“0000”构成G(4,3)（即1个4阶完全图），共有
：C(6,2)=15
【在 G**********s 的大作中提到】
: 题目：10个点（分别计为V1~V10），两两间可以有0或1条连线，每点恰有3边（即每点
: 恰与另3点各有1条连线），问这样的图的数目。
: 解：记为图G(10,3)，要求的这样的图的数目记为N(10,3)；则如果是6点、每点2边则为
: G(6,2)，其数目为N(6,2)。需求N(10,3)。
: N(3,2)=1
: N(4,2)=3
: N(5,2)=3*4=12
: N(6,2)：分2种情况：
: 情况1：两个三角形：C(6,3)/2=10
: 情况2：连通：6!/6/2=60
| s*****1
发帖数: 1 | 70 辛苦了，万分感谢！
每点
则为
50262958713792825
))
【在 G**********s 的大作中提到】
:
: ……
: 正确答案是11180820。我的解法大方向100%正确，但太多细节、至今仍有错、没能磨出
: 正确答案。前后共花了近50个小时，4/25后忙于它事就再没管了；当时的错误答案（见
: 下）是11619300。下面把这个仍有错（但大方向100%正确）的解法贴出来（也贴到我的
: 博客）。此解法能配以计算机编程解决，本来打算纯手工得到正确答案后再在重拾当初
: 的编程能力后再做，在未来几年也应没时间做了。
: 此题应该有更好的数学工具和相应的更好方法。比如，此题也是求这样的10*10矩阵的
: 数目：矩阵左上到右下对角线上全为0，其它位置非0即1，且矩阵中任一行或列求和都
: 为3。所以此题可能有线性代数相关解法。我已经近20年没有碰高数，数分线代等等全
|
|
