2、图A的关联矩阵： 图B的邻接矩阵：
?2?0??0??01110?1100?? 0011??0001??0?1??0??0100000000?1?? 2??0?3、解：用标号法解题如下：
r vi 0 1 2 3 4 5 w v1 0 0 v2 3 3/ v1 3 v3 4 4 4/ v1 4 v4 ? 13 7 7 7/ v3 7 v5 ? ? 6 6/ v3 6 v6 ? ? ? 10 9 9/ v4 9 v1到v2的最短路径: v1 v2 ，对应的权为3 v1到v3的最短路径: v1 v3 ，对应的权为4 v1到v4的最短路径: v1 v3 v4 ，对应的权为7 v1到v5的最短路径: v1 v3 v5 ，对应的权为6 v1到v6的最短路径: v1 v3 v4 v6 ，对应的权为9
4、 解：将本题用带权图来描述，如下图(a)，于是求解此题便成为求带权图的最小生成树问题。按Kruskal算法，下图中(b)-(e) 就是求解最小生成树的过程。
6
装订线
总造价=3+4+7+10=24万元
四、证明题：（本大题共 4 个小题，每题 5 分，共 20 分） 得分 1、 证明：从左边开始演算:
(P?Q)?(P?R) ?(?P?Q)?(?P?R) ??P?(Q?R) ?(P?(Q?R)
2、证明：
(1)自反性：对于任意的?x,y??A?A
x?y?x?y???x,y?,?x,y???R
(2)对称性：对于任意的??x,y?,?u,v???R
?x?y?u?v?u?v?x?y???u,v?,?x,y???R
(3)传递性：对于任意的??x,y?,?u,v???R???u,v?,?r,s???R
?x?y?u?v?u?v?r?s?x?y?r?s???x,y?,?r,s???R
3、证明：1. 解：设p: 甲获胜； q：乙获胜；r：丙获胜；s：丁不败（或丁获胜）。
7
前提为：p??q；r?q；?p?s 结论为：r?s （1） r （2） r?q （3） q （4） p??q （5） ?p
（6） ?p?s （7） s
4、证明： 对于任一a∈G，e*a=a*e，群G的幺元 e ∈H, 所以H是 G 的非空
子集。
任取 a, b∈H，下面证明 a*b?1与 G 中所有的元素都可交换. ?x∈G，有
(a*b?1) *x = a*b?1*x = a*b?1* (x?1) ?1 = a* (x?1*b) ?1 = a* (b*x?1) ?1
= a* (x*b?1) = (a*x) *b?1 = (x*a) *b?1 = x* (a*b?1) 由此可知，a*b?1 ∈H
由子群判定定理可知
五、应用题：（共4分）
证明：证明：将每个人用结点表示，当两个人是朋友时，则对应两
结点连一条边，则得一无向图G??V,E?。因为每个人恰有三个朋友，所以，
得分 deg(u)?3,(?u?V)，由任意图奇数度结点一定是偶数个，可知，此图结点数一定是
偶数。
8