2013-2014二学期图论与抽象代数复习
第一部分
1.第三篇总复习题 1，2，3题 2.第四篇总复习题 1，4，6题 3.习题9 9.1题
4. *运算如下表所示，哪个能使({a,b},*)成为单元半群？（ ）
5. Q 是有理集，（Q，*）（其中*为普通乘法）不能构成（ ）。 A．群 B．单元半群 C．半群 D．交换半群 6.设Z 是整数集，＋，· 分别是普通加法和乘法，则（Z，＋，·）是（ ）。 A．域 B．整环和域 C．整环 D．含零因子环 7. 在代数系统中，整环和域的关系为（ ）。 A．整环一定是域 B．域不一定是整环 C．域一定是整环 D．域一定不是整环 8. 设D =< V,E >为有向图，V = {a, b, c, d, e, f }，E = {( a,b),( b,c),( a, d), ( d, e) ,( f, e)}是（ A．强连通图 B．单向连通图 C．弱连通图 D．不连通图 9. 在有n 个结点的连通图中，其边数（ ）。 A．最多有n?1 条 B．至少有n?1 条 C．最多有n 条 D．至少有n 条
10设G = (n,m)为无向简单图，可构成邻接矩阵的数目为（ ）。 A．n! B．m! C． D． 11. 欧拉回路是（ ）。
A．通路 B．简单回路 C．既是基本回路也是简单回路 D．既非基本回路也非简单回路 12. 哈密尔顿回路是（ ）。
A．通路 B．简单回路 C．既是基本回路也是简单回路 D．既非基本回路也非简单回路 13. 下面哪一种图不一定是树?（ ）
A．无回路的连通图 B．有 n 个结点n ?1条边的连通图 C．每对结点间都有通路的图 D．连通但删去一条边则不连通的图 下述偏序集（见下图）中能构成格的是（ ）
下述偏序集中哪一个不构成格？（ ）
。 ）
第二部分
1第三篇总复习题 11，12，13题 2.第四篇总复习题 16，21题 3.定理6.14，定理7.10推论2
4.Z是整数集，群(Z,+)是一个循环群，其生成元是______和________.
5.G是n个节点，m条边的无向图，v是次数为k的结点，则G-v(G中去掉节点的图)中有_______个结点，________条边。 6.设（G，*）是一个半群，若存在单位元且每个元素都有右逆元，则（G，*）是_____________. 7.由一个孤立结点构成的图称为________;简单图不包含___________ 第三部分
1. 设代数系统（A,*），其中A={ a ,b , c , d }，*乘法表定义如下：问*是否是可交换的；A 是否有单位元；如果有单位元，指出哪些元素是可逆的，并给出它们的逆元。
2. 第三篇总复习题 20题
3.找出 的所有子群。
3
4.有向图D 如下图所示：
(S,?)
求：(1) D 的邻接矩阵A
(2) D 中v1 到v4 长度为4 的通路数为多少？
(3) D 中长度为4 的通路总数为多少？其中有几条回路？ (4) D 中v1 到自身长度为3 的回路数为多少？
(5) D 中长度小于等于4 的通路有多少条？其中有多少条是回路？ (6) D 是哪类连通图？
5.下图给出的赋权图表示七个城市a，b，c，d，e，f，g 及架起城市间直接通信线路的预测造价，试给出一个设计方案使得各城市间能够通信且总造价最小，要求计算出最小总造价。
第四部分
1.证明：定理6.18 2.证明：定理 8.1 3.证明：定理9.1
4.第三篇总复习题 27题
5. 证明：循环群一定是可换群。
第三篇 代数系统
代数系统是建立在集合论基础上以代数运算为研究对象的学科。本篇共三章，第五章代数系统基础介绍代数系统的一般原理与性质， 第六章群论，主要介绍具有代表性的代数系统－群，最后第七章其它代数系统，介绍除群外常见的一些代数系统，如环、域、格与布尔代数等，这三章相互配合构成了代数系统的完整的整体。 第五章 代数系统基础 §5.1 代数系统一般概念
1．代数系统中的基本概念
（1）代数系统：集合上具有封闭性的运算组成代数系统（S , ）。 （2）子代数：代数系统（S, ），（S?，?）满足： ① S??S
② 如 a , b?S?，a?b = a b 则称（S?，?）为（S, ）的子代数。 §5.2 代数系统常见的一些性质 （3）代数系统常见性质 1）结合律：（a b） c＝a （b c） 2）交换律：a b＝b a
3）分配律：a （b＋c）＝（a b）＋（a c） 4）单位元：a 1＝a
5）逆元：a a－1＝1 6）零元：a 0＝0 7）生成元 §5.3 同构与同态 （4）同构：（X， ）与（Y，?）存在一一对应函数g : X?Y使得如x1 , x2?X，则有：g（x1 x2）＝g（x1）?g（x2）此时则称（X, ）与（Y，?）同构。 （5）同态：（X , ）与（Y，?）存在函数g : X?Y使得如x1 , x2?X，则有：g（x1 x2）＝g（x1）?g（x2）此时则称（X， ）与（Y，?）同态。 §5.4 常用代数系统
（6）代数系统的构成
交换律 ?可换群 生成元 （一个二元运算 ） 子集上的群 ?循环群 特殊群 结合律 半群 单位元、逆元 群 ? ? 特殊群 ?子群 交换律 单位元 ?可换半群 ?变换群 生成元 ?单元半群 ?正规子群、商群
?循环半群 （两个二元运算：?, ) 代数系统 ?可换群, 半群, 对?分配群 环 交换律 可换环 单位元, 逆元 ?域 ? ? ?单位元，无零因子
特殊子环 ?理想 特殊环 （两个二元运算：?, ) ? ?商环 ?布尔代数 ? 两个运算的单位元、逆元
两个运算有单位元 ?有界格 两个运算有逆元 ?有补格 两个运算的结合律、交换律、吸收律 格 两个运算的分配律 分配格 ?整环
第六章 群论
§6.1 一些群的定义
（7）半群——代数系统满足交换律 （8）单元半群——半群存在单位元 （9）群——半群存在单位元与逆元 （10）可换群——群满足交换律
（11）变换群——集合A上所有的变换构成的集合E（A），对于复合变换?所构成的代数系统（E（A）, ）是一个群，称变换群。 （12）循环群——群有生成元。
（13）有限群：群（S, ）中S为有限集。
（14）子群：群（G，?）上G的子集所构成的群。
（15）正规子群：（H，?）是群（G，?）的子群，如对a?G都有：aH = Ha
则称（H，?）是（G，?）的正规子群。
（16）陪集：H是G的子群，Ha＝{ha | h?H}, aH = {ah | h?H }分别称H在G中的一个右陪集或左陪集。
（17）商群：H是G的正规子群，对Ha，Hb?G/H，二元运算（Ha)?(Hb)＝Hab构成群，则称H是G的商群。 （18）单元半群性质：
? 单元半群的子系统若包含单位元也是单元半群。
? 可列个元素的单元半群的运算组合表每行（列）均不相同。 ? 循环单元半群是可换单元半群。
? 可换单元半群的所有等幂元素是一个子单元半群。 §6.2 一些群的理论与半群性质： ? 半群的子代数也是半群。 ? 循环半群是可换半群。 （19）关于群的基本理论
? 群方程可解性：a x = b（或x a = b）对x存在唯一解； ? 群的消去律：a b = a c（或b a = c a）必有b = c； ? 任一群必与变换群同构；
? 与一个群同构或满同态的代数系统必为群；
? 一个代数系统有限群满足结合律及消去律则必为群；
? 有限群必与置换群同构；
? 循环群要么与（I,＋）同构，要么与（Zm，＋m）同构；
? 一个群子集H构成群（H,o）的充分必要条件：a,b?H 则a b?H ,a?H 则a－1 ?H；
? 一个群子集H构成子群（H,o）的充分必要条件：a,b ?H 则a b－1 ?H ； ? 一个有限群的阶一定被它的子群的阶所等分（拉格朗日定理）； ? f是群（G, ）与（G?，?）的满同态，K是f的核，则必有：（G/k , ?）与（G?，?）同构；
第七章 其它代数系统
§7.1 环、理想、整环和域 （20）环：（R，＋, ），对＋的可换群，对 的半群， 对＋的分配律； （21）理想：（D，＋, ），环（R，＋, ）的子环，满足：a?R , b?D，必有：a b?D , b a?D；
（22）整环：环（R，＋, ）中，运算 有单位元，无零因子； （23）域：环（P，＋, ）中，运算 交换律，有单位元，逆元； （24）环的基本理论 环的基本运算性质： ? a 0 = 0 a = 0；
? a （－b）=（－a） b = －（a b） ? (－a) (－b)＝a b
图论与抽象代数复习
