都是群G1★到G2的同态映射，证明C★是G1★的一个子群。其中CxxG1且fxgx３、GVE8分
Vv，Ee是每一个面至少由k（k3）条边围成的连通平面
图，则
e
kv2k2，由此证明彼得森图（Peterso
）图是非平面图。（11分）
四、逻辑推演16
用CP规则证明下题（每小题8分）1、ABCDDEFAF2、xPxQxxPxxQx
五、计算18
1、设集合Aa，b，c，d上的关系Rabbabccd用矩阵运算求出R的传递闭包tR。（9分）
2、如下图所示的赋权图表示某七个城市v1v2v7及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。（９分）
试卷一答案：一、填空20（每小题2分）1、0，1，2，3，4，6；2、BCA；3、1；4、PSRPSR；5、1；6、11132224；7、abacadbdcdIA；8、
9、a；abcd；adcd；10、c
f二、选择20（每小题2分）题目答案1CD2B、C3C4A5D6C7A8D9B10A
三、证明261、证：“”
abcX
若abacR由
R
对称性知
bacaR，由R传递性得bcR
“”若abR，acR有
bcR
任意
abX，因
aaR若abRbaR所以R是对称的。
若abR，bcR即R是传递的。2、证则baRbcRacR
abC
，
有
fagafbgb
，
又
fb1f1bgb1g1bfb1f1bg1bgb1
fa★b1faf1bgagb1ga★b1
a★b1C
3、证：
C★是G1★的子群。
①设G有r个面，则
2edFirk
i1
r
，即
r
2ek。而ver2故
2verve
2ek即得
e
kv2k2。（8分）ekv2k2不成立，
②彼得森图为k5e15v10，这样
所以彼得森图非平面图。（3分）
一、逻辑推演161、证明：
f①A②AB③ABCD④CD⑤D⑥DE⑦DEF⑧F⑨AF2、证明①xPx②Pc③xPxQx④PcQc⑤Qc⑥xQx⑦xPxxQx
P（附加前提）T①IPT②③IT④IT⑤IPT⑥⑦ICP
P（附加前提）US①PUS③T②④IUG⑤CP
二、计算181、解：
0r