
离散数学中集合与图论的简单问题,帮下哈 谢谢!
1.设f=ugv,其中f,g,u,v都是从集合A到A的映射,证|f(A)|<=|g(A)|2.毕业舞会,男生和女生跳舞,已知每个男生至少与一个女生跳过舞,但未能与所有女生...
1.设f=ugv,其中f,g,u,v都是从集合A到A的映射,证|f(A)|<=|g(A)|
2.毕业舞会,男生和女生跳舞,已知每个男生至少与一个女生跳过舞,但未能与所有女生跳过舞。同样,每个女生也至少与一个男生跳过舞。证明:在所有参加舞会的女生与男生中,必可找到两个女生和男生,这两个女生中的每一个只与这两个男生中的一个跳过舞,而这两个男生中的每一个也只与这两个女生中的一个跳过舞。(用容斥原理) 展开
2.毕业舞会,男生和女生跳舞,已知每个男生至少与一个女生跳过舞,但未能与所有女生跳过舞。同样,每个女生也至少与一个男生跳过舞。证明:在所有参加舞会的女生与男生中,必可找到两个女生和男生,这两个女生中的每一个只与这两个男生中的一个跳过舞,而这两个男生中的每一个也只与这两个女生中的一个跳过舞。(用容斥原理) 展开
1个回答
展开全部
1复合映射的值域一定小于每一个映射的值域(指的是元素个数,不一定有包含关系)
2其实命题很弱。只要证明存在两个男生A、B,他们所认识的女生集合不互相为包含关系,就一定可以各选出一个A认识而B不认识的女生和B认识A不认识的女生组成满足条件的四人组。反证法,如果这个条件不成立的话,那么所有的男生所认识的女生一定是互为包含关系,则一定可以选出一个认识人最多的男生;这个男生不认识的女生就会不认识所有男生,与题中“每个女生也至少与一个男生跳过舞”矛盾。
大才女 *.*!
2其实命题很弱。只要证明存在两个男生A、B,他们所认识的女生集合不互相为包含关系,就一定可以各选出一个A认识而B不认识的女生和B认识A不认识的女生组成满足条件的四人组。反证法,如果这个条件不成立的话,那么所有的男生所认识的女生一定是互为包含关系,则一定可以选出一个认识人最多的男生;这个男生不认识的女生就会不认识所有男生,与题中“每个女生也至少与一个男生跳过舞”矛盾。
大才女 *.*!
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询