问一道题目,求解
这是上次的一道数模题,想了很久仍然无解,请各位牛人提供点思路,小弟在这里不胜感激!
- C/C++ code
题目: n个队进行单循环比赛,对于给定的正整数{z1,z2,...,zn} ,是否存在一种赛况,使得第k个队比赛过的场次是zk(k=1,...,n)。{z1,z2,...,zn}满足什么条件时赛况是唯一的?这里,赛况是指哪些队之间比赛过。对于n=6,有多少组{z1,z2,...,z6}(z1<=z2<=...z6)是存在赛况的?有多少组是存在唯一赛况的?说明:1、在n=3的情形下,z1=1,z2=1,z3=1不存在赛况,z1=1,z2=1,z3=2存在唯一的赛况,就是第三个队与第一个队、第二个队均赛过一场,而第一个队与第二个队没有赛过。2、要求首先对一般的n进行讨论,给出存在赛况的条件或是判断方法以及存在唯一赛况的条件或是判断方法。其次给出n=6的情形下的一些结果。[解决办法]
你这个问题就是
无向图由图上各顶点的度唯一确定。
它的充要条件是该无向图的任意子图也满足这一条件。
比如z1=1,z2=1,z3=1不存在赛况,那么z1=1,z2=1,z3=1,z4=3有一个子图是z1=1,z2=1,z3=1,所以也不存在赛况。
所以采用递推的思想。
[解决办法]
你这个问题就是
无向图由图上各顶点的度唯一确定。
它的充要条件是该无向图的任意子图也满足这一条件。
比如z1=1,z2=1,z3=1不存在赛况,那么z1=1,z2=1,z3=1,z4=3有一个子图是z1=1,z2=1,z3=1,所以也不存在赛况。
所以采用递推的思想。