西交《离散数学》faq（三）

openhelp100

西交《离散数学》FAQ（三）
第二章 关系2
一、设X＝{1，2，3，4}，R是X上的二元关系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}
(1)画出R的关系图。
(2)写出R的关系矩阵。
(3)说明R是否是自反、反自反、对称、传递的。
解  (1)R的关系图如图所示：
(2) R的关系矩阵为：


(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是反自反的；由于矩阵不对称，R不是对称的；
经过计算可得

，所以R是传递的。
二、设函数f：R×R(R×R，f定义为：f(<x，y>)＝<x＋y，x－y>。
(1)证明f是单射。
(2)证明f是满射。
(3)求逆函数f－1。
(4)求复合函数f－1(f和f(f。
证明  (1)对任意的x，y，x1，y1∈R，若f(<x，y>)＝f(<x1，y1>)，则<x＋y，x－y>＝<x1＋y1，x1－y1>，x＋y＝x1＋y1，x－y＝x1－y1，从而x＝x1，y＝y1，故f是单射。
(2)对任意的<u，w>∈R×R，令x＝
，y＝
，则f(<x，y>)＝<
＋
，
－
>＝<u，w>，所以f是满射。
(3)f－1(<u，w>)＝<
，
>。
(4)f－1(f(<x，y>)＝f－1(f(<x，y>))＝f－1(<x＋y，x－y>)＝<
，
>＝<x，y>
f(f(<x，y>)＝f(f(<x，y>))＝f(<x＋y，x－y>)＝<x＋y＋x－y，x＋y－(x－y)>＝<2x，2y>。
三、给定群<G，*>，若对G中任意元a和b，有a3*b3＝(a*b)3，a4*b4＝(a*b)4，a5*b5＝(a*b)5，试证<G，*>是Abel群。
证明  对G中任意元a和b。
因为a3*b3＝(a*b)3，所以
*a3*b3*
＝
*(a*b)3*
，即得a2*b2＝(b*a)2。同理，由a4*b4＝(a*b)4可得，a3*b3＝(b*a)3。由a5*b5＝(a*b)5可得，a4*b4＝(b*a)4。
于是(a3*b3)*(b*a)＝(b*a)4＝a4*b4，即b4*a＝a*b4。同理可得，(a2*b2)*(b*a)＝(b*a)3＝a3*b3，即b3*a＝a*b3。
由于(a*b)*b3＝a*b4＝b4*a＝b*(b3*a)＝b*(a*b3)＝(b*a)*b3，故a*b＝b*a。
四、（1）证明在n个结点的连通图G中，至少有n－1条边。
证明  不妨设G是无向连通图（若G为有向图，可略去边的方向讨论对应的无向图）。
设G中结点为
、
、…、
。由连通性，必存在与
相邻的结点，不妨设它为
（否则可重新编号），连接
和
，得边
，还是由连通性，在
、
、…、
中必存在与
或
相邻的结点，不妨设为
，将其连接得边
，续行此法，
必与
、
、…、
中的某个结点相邻，得新边
，由此可见G中至少有n－1条边。
（2）试给出|V|＝n，|E|＝
(n－1)(n－2)的简单无向图G＝<V，E>是不连通的例子。
解  下图满足条件但不连通。
本内容由易百网整理发布
网址 www.openhelp100.com
QQ 515224986