一次舞会,共有n位男士和n位女士参加,已知每位男士至少认识2位女士,而每位女士最多

来源:百度知道 编辑:UC知道 时间:2024/06/16 02:59:02
一次舞会,共有n位男士和n位女士参加,已知每位男士至少认识2位女士,而每位女士最多认识2为男士,问能否把男士和女士正好分成n对,使每一对男女彼此认识

你算出来后记得告诉我啊~

…………………………什么提问都有啊………………我是来混分的……

很简单,以女士为基准,先把只认识一位男性的女士安排给他唯一认识的男士。剩下的类推,为每位女士配上一位男士即可。

我来造福后人~ 男士与女士认识的联线,构成的图为偶图,假设男士为X,女士Y,X中存在子集S,与S相连的边为E1,S的邻域为N(S),与N(S)相连的边为E2,则2|N(s)|>=E2>=E1>=2|s|,由hall定理得证
事实上,改图为2正则图 因为由图中条件得:m>=2n又m<=2n 所以m=2n,每位男士与女士都认识不同的2位异性