离散数学2013年4月考试真题(02324)

已知a，b，c，d，e，f，g共7个人中，a会讲英语;b会讲英语和汉语;c会讲英语、意大利语和俄语;d会讲汉语和日语;e会讲意大利语和德语;f会讲俄语、日语和法语;g会讲德语和法语。若将他们的座位安排在圆桌旁，要使得每个人都能与他身边的人交谈，应如何安排座位，说明理由并画出座位安排图。

设G =< V，E >是连通图，且e∈E，证明：当且仅当e是G的割边时，e才在G的每棵生成树中。

设S={1，2，3，4}，并设A=SxS，在A上定义关系R为： R< c，d >当且仅当a+b=c+d，证明R是等价关系。

构造下面的推理证明：任何自然数都是整数，存在着自然数，所以存在着整数(设个体域为实数集合R)。

?有向图D=如图30图，请完成下列问题：

(1)给出D的邻接矩阵及4次以下的幂;

(2)判定D中长度为2的路径有几条?从v₁到v₄长度为3的路径有几条?

(3)求D的可达性矩阵P。

设< A，* >为群，任意a，b，c∈A，证明：若a*b=a*c，则b=c。

设A={1，2，3，4，5，8，12，24}，R为A上整除关系，试画出的哈斯图，并求出A中最大元，最小元，极大元，极小元。

设有向图D=的邻接矩阵A=，那么|E|=_______，|V|=_______。