哪位强人帮个忙?有道图论题,有些挑战,我不会做……

来源:百度知道 编辑:UC知道 时间:2024/06/19 01:51:21
我在学校参加数模,下面是学校出的数模题中的第一题。虽然这题对于数模来讲关系不大,但还是很想做出来,只是,本人比较菜,做不出来- -!,还请哪位高手指教。

题目是这样的:

有n个评委,m组面试的学生。要求:
1,每组学生恰有3位评委去面试。
2,任意两组的评委中,最多有1位评委重复。

问:给定任意的n,求能满足上面条件的m的最大值,。

已知结论:
n=3,m最大为1
n=4,m最大为1
n=5,m最大为2
n=6,m最大为4
n=7,m最大为7

n=10,答案我不知道,但m至少为12

另,n=7,15,31,63……2n+1时,是完全图

并且,允许使用计算机编程!不过请贴出源码
如果编程,我自己有一个要求:对于n=15,程序至多运行5秒钟就可得出答案

期待哪位牛人,解出来这道题。我一定对他崇拜万分,感激不尽!
回xtimz:
这的确是我们竞赛题,不过我们这比赛早比完了,5.1三天比的。所以我现在拿出来提问也没有任何不妥。
你的链接中,有2人是在比赛期间提问的,并期望在比赛结束前得到答案。
我现在拿出来问,显然对于比赛成绩没有任何影响了,我只希望得到解法,学习学习。

回钟云浩:
解释一下你的原则(1),在n为任何情况下,是否都是2?
可以告诉你,在n=7时,每个点都使用了3次。
并且部分的告诉你,你的方法不可行,得不到最优解。

另:谁线性代数好的么?貌似这题可以尝试一下矩阵。我线代太烂了- -!

设评委n人,给每个评委编号:1,2,3,...n
可以按下列原则和步骤:
(1)每次取出一组可行的编号后,统计所有编号对应的与它们不排斥的编号(就是能共同使用的编号),如某编号对应的与它不排斥的编号小于两个,则这个编号不能再用了.
(2)剔除已不能用的编号---具体做法看例子 (用(1)来判断编号是否还能用)
(3)标注其它排斥---具体做法看例子

例如
n=6
第一步:取一组可行的编号(1,2,3)
编号:1,2,3,...6对应的与它们不排斥的编号分别为
((4,5,6),(4,5,6),(4,5,6),(1,2,3,5,6),(1,2,3,4,6),(1,2,3,4,5))

标注其它排斥
((4,5,6),(4,5,6),(4,5,6),(1,2,3,5,6)--其中1,2,3排斥,(1,2,3,4,6)--其中1,2,3排斥,(1,2,3,4,5)--其中1,2,3排斥)

第二步:取一组可行的编号(1,4,5)
编号:1,2,3,...6对应的与它们不排斥的编号分别为
((6),(4,5,6),(4,5,6),(2,3,6)--其中2,3排斥,(2,3,6)--其中2,3排斥,(1,2,3,4,5)--其中1,2,3排斥)

剔除已不能用的编号
((6),(4,5,6),(4,5,6),(2,3,6)--其中2,3排斥,(2,3,6)--其中2,3排斥,(2,3,4,5)--其中2,3排斥)

标注其它排斥
((6),(4,5,6) --其中4,5排斥,(4,5,6) --其中4,5排斥,(2,3,6)--其中2,3排斥,(2,3,6)--其中2,3排斥,(2,3,4,5)--其中2,3排斥,4,5排斥)

第三步:取一组可行的编号(2,4,6)
编号:1,2,3,...6对应的与它们不排斥的编号分别为
((6),(5),(4,5,6) --其中4,5排斥,(3),(2,3,6)--其中2,3排斥,(3,5))

剔除已不能用的编号