习题一
1. 一个工厂为一结点；若两个工厂之间有业务联系，则此两点之间用边相联；这样就得到一个无向图。若每点的度数为3，则总度数为27，与图的总度数总是偶数的性质矛盾。若仅有四个点的度数为偶数，则其余五个点度数均为奇数，从而总度数为奇数，仍与图的总度数总是偶数的性质矛盾。（或者利用度数为奇数的点的个数必须为偶数个）
2.
若存在孤立点，则m 不超过K n-1的边数, 故
m <= (n-1)(n-2)/2, 与题设矛盾。
3.
4. 用向量(a 1,a 2,a 3)表示三个量杯中水的量, 其中a i 为第i 杯中水的量, i = 1,2,3. 以满足a 1+a 2+a 3 = 8 (a 1,a 2,a 3为非负整数)的所有向量作为各结点, 如果(a 1,a 2,a 3)中某杯的水倒满另一杯得到 ( a ’1, a ’2, a ’3 ) , 则由结点到结点画一条有向边。这样可得一个有向图。
本题即为在此图中找一条由( 8, 0, 0 )到( 4, 4, 0 )的一条有向路，以下即是这样的一条：
5. 可以。
6 若9个人中没有4个人相互认识，构造图G ，每个点代表一个点，两个人相互认识则对应的两个点之间有边。
1） 若可以找到点v ，d(v)>5，则与v 相连的6个点中，要么有3个相互认识，要么有3个
相互不认识（作K 6并给边涂色:红=认识，蓝=不认识，只要证图中必有同色三角形。v 1有5条边，由抽屉原则必有三边同色(设为红)，这三边的另一顶点设为v 2, v 3, v 4。若 △v 2v 3v 4有一边为红，则与v 1构成红色△，若△v 2v 3v 4的三边无红色，则构成蓝色△）。若有3个人相互认识，则这3个人与v 相互认识，这与假设没有4个人相互认识矛盾，所以这6个人中一定有3个人相互不认识
∑
∑∑∑∑
∑∑==+====-=++=-==---=--=n
i i n i i n i n i n i n
i i i n i i n i i i i a a n n a a a n n n a n a v v 12 12 1211
2
212 12 i i 2/)1(C )1(2)1(])1[(a a 。
， 所以 因为 ，＋ 的负度数，则为结点的正度数，为结点记－－－－－
( 8, 0, 0 ) ( 5, 3, 0 ) ( 5, 0, 3 ) ( 2, 3, 3 ) ( 2, 5, 1 )
(7, 0, 1 ) ( 7, 1, 0 ) ( 4, 4, 0 )
( 4, 1, 3 )
2） 若可以找到点v ，d(v)<5，不与v 相连的点至少有4个，由于没有4个人相互认识，所
以这4个人中至少有2个人相互不认识，这两个人与v 共3个人相互不认识 3） 若每个点的度数都为5，则有奇数个度数为奇数的点，不可能。
7. 同构。同构的双射如下：
8. 记e 1= (v 1,v 2), e 2= ( v 1,v 4), e 3= (v 3,v 1), e 4= (v 2,v 5), e 5= (v 6,v 3), e 6= (v 6,v 4), e 7= (v 5,v 3), e 8= (v 3,v 4), e 9 = (v 6,v 1), 则
邻接矩阵为： 关联矩阵为：
边列表为：A= (1,1,3,2,6,6,5,3,6), B= (2,4,1,5,3,4,3,4,1). 正向表为：A= (1,3,4,6,6,7,10), B= (2,4,5,1,4,3,3,4,1).
?
??????????????
??
??
?---------100110000001001000010100010011010100000001001100000111
, 001101000100000000001001010000001010????????????????????
习题二
1.用数学归纳法。k=1时，由定理知结论成立。设对于k命题成立。
对于k+1情形，设前k个连通支的结点总个数为n1, 则由归纳假设，前k个连通支的总边数m1<= ( n1－k+1)( n1－k)/2。最后一个连通支的结点个数为n－n1, 其边数
m2<= ( n－n1)( n－n1－1)/2，
所以，G的总边数
m= m1+ m2<= ( n1－k+1)( n1－k)/2 + ( n－n1)( n－n1－1)/2 n1=n－1时，m<= ( (n-1)－k+1)( (n-1)－k)/2 +0= ( (n－k)( (n－k－1)/2, 命题成立。
n1＜= n－2时，由于 n1<=k, 故
m<= ( (n－2)－k+1)( n1－k)/2 + ( n－n1)( n－k－1)/2＝( n－k)( n－k－1)/2 ,
命题成立。
2．若G连通，则命题已成立；否则， G至少有两个连通支。
任取结点v1, v2，若G的补图中边(v1, v2)不存在，则(v1, v2)是G中边，v1, v2在G 的同一个连通支（假设为G1）中。设G2是G的另一连通支，取v3G2, 则v1 v3v2 是补图中v1到v2的一条道路，即结点v1, v2在补图中有路相通。
由v1, v2的任意性，知补图连通。
3．设L1,L2是连通图G的两条最长路，且L1,L2无公共结点。设L1,L2的长度(边数)为p.
由于G是连通的，故L1上必有一结点v1与L2上一结点v2有道路L’相通。
结点v1将L1分为两部分，其中一部分的长度p/2 , 记此部分道路为L3。同样，结点v2将L2分为两部分，其中一部分L4的长度 p/2 。
这样，L3＋L’＋L4就是G的一条新的道路，且其长度大于p, 这与G的最长路(L1)的长度是p的假设矛盾。
4. 对结点数n作归纳法。
（1）n= 4时m≥5. 若有结点的度≤1, 则剩下的三结点的度数之和≥4，不可能。于是每个结点的度≥2，从而存在一个回路。
若此回路为一个三角形，则还有此回路外的一结点，它与此回路中的结点至少有二条边，从而构成一个新的含全部四个结点的回路，原来三角形中的一边（不在新回路中）即是新回路的一条弦。
若此回路为含全部四个结点的初等回路，则至少还有一边不在回路上，此边就是该回路的一条弦。
（2）设n-1情形命题已成立。对于n情形：
若有结点的度≤1, 则去掉此结点及关联边后，依归纳假设命题成立。
若有结点v的度=2, 设v关联的两结点为s,t，则去掉结点v及关联边、将s,t合并为一个结点后，依归纳假设命题成立。
若每个结点的度≥3，由书上例2.1.3的结果知命题成立。
5 a)对于任意边(u,v),由于不存在三角形，所以d(u)+d(v)<=n，对所有m条边求和，不等
式左边每个d(v)被计算了d(v)次
b) 对n归纳，设小于n时不等式成立，当|V|=n时，删去边(u,v)及点u，v以及相关的边得到G'，由归纳假设，G'最多(n-2)2/4条边，由于(u,v)与G'不构成三角形，因此由G'变回G时最多增加(n-2)+1条边，所以G的边最多(n-2)2/4+(n-2)+1=n2/4
注：此题与三角形的存在性无关
设最大度数为k，且d(v)=k，令E0={与v相连的边}，E1={不与v相连的边}，则|E0|=k，|E1|<=(n-k-1)*k，其中n-k-1表示去除了v及其邻点，这些点的度数都小于等于k
m=|E0|+|E1|<=nk-k2<= n2/4
6．问题可化为求下列红线表示的图是否存在一条欧拉道路的问题：存在欧拉道路！
7 设C是H道路，当S中顶点在C上不相邻时，C-S最多被分成|S|+1段，而当S中顶点有相邻时段数将更少，而C是G的生成子图，所以t<=|S|+1
8．由推论2.4.1, 只需验证G的任意一对结点的度数之和大于或等于n即可。
若存在结点v1, v2满足deg(v1)+deg(v2) G－{v1, v2} 的边数<= K n-2的边数= (n-2)(n-3)/2 . 另一方面，由题设知 G－{ v1, v2} 的边数＝m－（deg(v1)+deg(v2)）＞[(n-1)(n-2)/2+2]－n= (n-2)(n-3)/2 , 与上式矛盾。 9 对n进行数学归纳法，设n小于等于k时命题成立，则当n=k+1时 对任意顶点v，G-v得到的G'仍是有向完全图，由归纳假设存在H道路v1v2…v k 若G中存在边(v,v1)或(v k,v)则命题成立 否则G中存在边(v1,v)和(v,v k)，这也意味着可以找到i，1<=i 10 对于任意的点u,v，若u与v认识，则d(u)+d(v)=(n-2)+2=n 若u不认识v，则从V-{u,v}中让取一点w，w认识u和v 否则若w不认识u，则v和w都不认识u，v和w合起来只能最多认识n-3个人，矛盾。 由w的任意性，d(u)+d(v)>=2(n-2)，当n>=4时，2(n-2)>=n 所以对任意两个点度数和大于等于n 11 对于这q条边，每条边的两个端点压缩合并为一个点，并去掉重边得到G' G'各点度数均大于等于n/2，所以存在H回路，该回路中q个新点恢复成原2q个点，则所代表的q条边仍在此H回路中 注：q不能超过n/2 12 构造图G，每个小立方体对应一个点，两个立方体之间有公共面则对应顶点间有边 设最左上角点为黑色，依据相邻点不同色的原则给所有点着色，则黑色点有14个，白色点有13个，若所要求路径存在，则意味着从黑色点开始遍历这27个点到达白色点，这不可能 13．1）将边按权值由小到大排序： 边： a23 a35 a15 a13 a34 a45 a24 a12 a25 a14 权： 26 27 29 33 34 35 38 42 49 52 2) 分支定界： S1: a23 a35 a15 a13 a34 , 非H回路,d (S1)=149; 将a34置换为其后的a45, a24，a12，a25，a14，也全都是非H回路； S2: a23 a35 a15 a34 a45, 非H回路,d(S2)=151; 将a45置换为其后的a24，a12，a25，a14，也全都是非H回路； S3: a23 a35 a15 a45 a24 , 非H回路,d (S8)=155; 将a24置换为其后的a12，a25，a14，也全都是非H回路； S4: a23 a35 a15 a24 a12 , 非H回路,d (S4)=162; S5: a23 a35 a15 a24 a25 , 非H回路,d (S5)=169; S6: a23 a35 a15 a24 a14 , H回路,d0:=172; S7: a23 a35 a15 a12 a25 , 非H回路,d (S7)=173; S8: a23 a35 a13 a34 a45 , 非H回路,d (S8)=155; 将a34 , a45置换为其后的数，也全都是非H回路； S9: a23 a35 a34 a45 a24 , 非H回路,d (S9)=160; 将a45 , a24置换为其后的数，也全都是非H回路； S10: a23 a35 a45 a24 a12 , 非H回路,d (S10)=168; 将a12置换为其后的a25 , a14，也全都是非H回路； S11: a23 a35 a45 a12 a25 , 非H回路,d (S11)=179; 将a12 ,a25置换为其后的数，其路长差于d0，故不必考虑； S12: a23 a35 a24 a12 a25, 非H回路,d (S12)=182; 将a24，a12，a25,置换为其后的数，其总长差于d0，故不必考虑； 继续下去所得组长度会比S6差，故可终止计算。 所以，H 回路为S6, 路长为172。 14. 这是一个旅行商问题(具体计算略)： 15. 这是一个最短路问题(具体计算略)： 16. (0,0) (2,5) (6,6) 7 V 1 V 2 V 3 V 6 V 3 23. V3V2 习题三 1． 因为n 个结点的树的边有n-1条，故其总度数为 2 (n-1)，故度为1的结点个数为 2 (n-1)－2n 2－3n 3－……－kn k . 2. 设L 是树T 的一条最长路，L 中的结点依次为 v 1, v 2 , …, v k 。因为L 中各结点都有边相连，所以它们的度数均大于或等于1。 若deg (v 1)>1, 则除了边(v 1, v 2)外，还存在边(v 1, v’) 。因为树中不存在回路，故v’{ v 1, v 2 , …, v k }，于是，(v’,v 1, v 2 , …, v k )是T 的一条新的路，其长度比L 更长。这与L 是T 的最长路矛盾。 所以deg (v 1)＝1，类似可证deg (v k )＝1。 4．(a) 直接根据图确定B 5B 5T 可得树的棵数： .1014 20124100 1411013)det(55=--------= T B B (b) 去掉边(v 1, v 5)，则直接根据图确定B 5B 5T 可得不含边(v 1, v 5)的树的棵数： ,754 2 1 241001411012 )det(55=--------= T B B 于是，含边(v 1, v 5)的树的棵数为：101－75＝26。 (c) 去掉边(v 4, v 5)，则直接根据图确定B 5B 5T 可得不含边(v 1, v 5)的树的棵数： . 60 3 2 1 241001411013 )det(55=--------= T B B 5. (a) 因为 , ????? ???????----------=????? ???????----------=000001001010010001000110001000000010000 1,110011001010110001000111001000000011100 1*11B B (b) 去掉边(v 1, v 5)后，有 , ????? ???? ???---------=????????? ???---------=00 1 100100010011000100000010001,11001 1000101100010011100 1000000 11101*11B B (c) 去掉到v 3的其它全部边(v 4, v 3)、(v 5, v 3)后，有 ,0001 1 110001000000100000100001,10110010110001000100100000 1 11001* 11? ? ??? ???? ???--------=? ? ??? ? ??? ???--------=B B . . 242001 131011311002 1=-------= )B det(B T 1*1为根的根树的个数为 因此以v . .810011 31011311002),(1=-------=)B det(B T 1 *151的根树的个数为为根且不含边因此以v v v . .92 1 13100 01 11002 ),(321=-----= )B det(B T 1*1的根树的个数为 为根且含边因此以v v v 10. (1) 余树为｛e 1, e 2, e 5, e 8｝, 重排B 5的各列得 . 1 000 01000010 001 C I C e e e e e e e e , C 3.4.4,, 01-0 0 0001 1-010 11-00B , 1-000 1-010 01-01 0011-B , ) B B ( 01-0 0 0001 1-010 11-00 1- 000 1-010 01-01 0011- e e e e e e e e f12f 7 643851 f12121112117 643851????? ? ???? ?? ------==????? ???????------=???? ????????---????????????-----=-=????? ???????=????????????=????? ???????=-100 1 001011001111 )(10 1 001011001111 10011000 10110100 1000 10100101 001121121152基本回路矩阵为由定理则 ＝T T B B B (2) 由定理3.4.8, 基本割集矩阵为 . 10 010********* 10 1 1 -0011-0101 1-001 I C - I S S e e e e e e e e T f12f11f 7643851?? ??? ? ??????===)()(2 14．(a) 这是一个求最优二叉树的问题。 各字符出现次数为： s t a e c 空格 3 4 5 1 1 4 余树 树T 所以最优二进制编码为： e: 1100 c: 1101 s: 111 t: 00 空格：01 a: 10 此时字符串的二进制编码总长度为43 . (b) 去掉空格，类似(a)计算。 15. 将图中各边进行编号得右图。 取参考支撑树 t 0={ e 1, e 2, e 3, e 5} . (1) 因为S e1(t 0)={ e 1, e 4, e 6 }, S e2(t 0)={ e 2, e 4, e 6 }, S e3(t 0)={ e 3, e 6 }, S e5(t 0)={ e 5, e 6 }, 所以 T e1 ={{ e 4, e 2, e 3, e 5}, {e 6, e 2, e 3, e 5}}={ t , t 2}, T e2 ={{ e 1, e 4, e 3, e 5}, {e 1, e 6, e 3, e 5}}={ t , t 4}, T e3 ={{ e 1, e 2, e 6, e 5}}={ t 5}, T e5 ={{ e 1, e 2, e 3, e 6}}={ t 6}, 从而 T 1 ＝{ t 1, t 2, t 3, t 4, t 5, t 6} . (2) 因为S e2(t 1)={ e 2, e 1 }, S e3(t 1)={ e 3, e 6 }, S e5(t 1)={ e 5, e 6 }, S e2(t 2)={ e 2, e 1 }, S e3(t 2)={ e 3, e 1, e 4 }, S e5(t 2)={ e 1, e 4, e 5 }, S e3(t 3)={ e 3, e 6 }, S e5(t 3)={ e 6, e 5 }, S e3(t 4)={ e 3, e 2, e 4 }, S e5(t 4)={ e 2, e 4, e 5 }, S e5(t 5)={ e 5, e 3 }, 所以 S e2(t 0) S e2(t 1)＝{ e 2} , S e2(t 0) S e2(t 2)＝{ e 2} , 从而 T e1 e2 ＝； S e3(t 0) S e3(t 1)＝{ e 3, e 6 } , S e3(t 0) S e3(t 2)＝{ e 3} , 从而 T e1 e3 ＝{{ e 4, e 2, e 6, e 5}}={ t 7}； S e5(t 0) S e5(t 1)＝{ e 5, e 6 } , S e5(t 0) S e5(t 2)＝{ e 5 } , 从而 T e1 e5 ＝{{ e 4, e 2, e 3, e 6}}={ t 8}； S e3(t 0) S e3(t 3)＝{ e 3, e 6 } , S e3(t 0) S e3(t 4)＝{ e 3 } , 从而 T e2 e3 ＝{{ e 1, e 4, e 6, e 5}}={ t 9}； S e5(t 0) S e5(t 3)＝{ e 5, e 6 } , S e5(t 0) S e5(t 4)＝{ e 5 } , 从而 T e2 e5 ＝{{ e 1, e 4, e 3, e 6}}={ t 10}； S e5(t 0) S e5(t 5)＝{ e 5} , 从而 T e3 e5 ＝； 于是 T 2 ={ t 7 , t 8, t 9, t 10} . (3) 可以验证 T e1 e2 e3＝T e1 e3 e5＝T e2 e3 e5＝, 所以T 3 = . 4 4 8 1 1 2 3 5 5 10 1 1 2 3 5 5 10 4 4 8 18 0 1 0 0 0 0 1 1 1 1 e 4 e e 5 e e 2 e 1 最后，由以上计算可知，全部生成树为{ t 0 , t 1, t 2, t 3, t 4, t 5, t 6, t 7 , t 8, t 9, t 10 }. 16. 用Kruskal 算法。先将权排序，而后按权由小到大选边8-1条(构成回路时所 选边不放入)，可得一棵最小生成树（总权为22）： （注：可编辑下载，若有不当之处，请指正，谢谢!） v v 6 https://www.doczj.com/doc/8618276231.html,/blog/static/6742112520081231911205/ R^n至少有两种重要的结构：拓扑结构和代数结构（线性空间结构）。 函数连续性只涉及第一种，而可微性则涉及两种（？拓扑—>微分拓扑，拓扑群—>李群）因为微分Df(x)=A的定义牵涉到线性运算和极限概念：f(x+h)-f(x)-Ah=o(||h||) 可微性的概念可以推广到有拓扑结构和线性代数结构这两种结构的其他空间。 现代微分概念源于非线性问题的局部线性化。 半球面是可以摊成平面区域的 要把地球表面画成地图，就非得把球面“撕破”不可 https://www.doczj.com/doc/8618276231.html,/lunwen/2008/200810/266972_5.shtml https://www.doczj.com/doc/8618276231.html,/f?kz=113722720 同伦等价(homotopy equivalent)是拓扑学中所关心的另外一种等价关系，它的 要求比同胚更宽松。取一个拓扑空间，对它进行某些特定的连续形变，所得到的空 间与原来的空间是同伦等价的。举个例子：初始空间是一个实心球，我们可以把它 压缩成一张没有体积的圆盘，再搓成一条没有面积的线段，甚至挤成一个连长度都 没有的点，得到的这些空间都跟原来的同伦等价；我们也可以从原来的实心球里“长”出半个圆盘来作为“耳朵”(半圆盘的直径还贴在实心球表面上)，甚至再 “长”出几条线段来作为“触角”(线段的一端在实心球表面上)，所得到的空间还 是跟原来的同伦等价。“终结者2”里面那个给人深刻印象的液体机器人，它在身体 没有撕裂开的情况下的各种形态就是同伦等价的。 研究拓扑的一种方法是把拓扑问题转化为代数问题。最常见的例子是计算一个拓 扑空间各个维数的同调群(homology group)和同伦群(homotopy group)，然后根据这 南 京 航 空 航 天 大 学 第1页 （共6页） 二○ ～ 二○ 学年 第二学期《 》考试试题 考试日期： 年 月 日 试卷类型： 试卷代号： 班号 学号 姓名 题号 一 二 三 四 五 六 七 八 九 十 总分得分 一、（1）证明：无向图中的奇度点的数目一定是偶数。 （2）分别判断下面数列是否可以图化？是否可以简单图化？如果可以，分别画出一个相应的图。写出求解过程。 ① (3,3,3,1) ②(4,3,3,3,3,3,3) 本题分数 10分 得 分 二、T 是简单无向图，请由定义直接证明：T 连通无回路 当 且仅当 T 中任意两点之间有唯一的初级通路（即基本通路）。 三、求K 7和K 2,3的点色数、边色数和面色数（请写出求解过程）。 本题分数 10分得 分 本题分数 10分 得 分 四、无向简单平面图G 中最小度δ>4，证明：G 中至少有30条边。 五、设i 是虚数单位，Z 是整数集，+是普通加法， G={a+bi | a,b ∈Z}，证明： 六、 八、f 是群G 到群H 的满同态，R 是G 上的一个二元关系， R={ 第四章代数结构（作业） 作业：P86：4、7、9 4、 （1）若a和b是整数，则a+b+ab也是整数，故a*b也是整数，所以运算*是封闭的。（2）任选整数集合中的三个元素x,y和z。则有： (x*y)*z = (x+y+xy)*z = (x+y+xy)+z+(x+y+xy)×z = x+y+z+xy+xz+yz+xyz x*(y*z) = x*(y+z+yz) = x+(y+z+yz)+x×(y+z+yz) = x+y+z+yz+xy+xz+xyz = (x*y)*z 因此，*运算满足结合律。 （3）假设e为（Z,*）的幺元，则有： 任选整数集中的一个元素x，都有 0*x = 0+x+0×x=x且 x*0 = x+0+x×0=x 故0是(Z,*)的幺元。 7、N+上的所有元素都是（N+ ,*）等幂元； （N+ ,*）无幺元； （N+ ,*）的零元为1。 9、（A,*）中的等幂元：a、b、c、d； （A,*）中的幺元：b； （A,*）中的零元：c； a-1 = d，b-1 = b，c-1 不存在，d-1 = a， 作业：P87：12、13、18 12、（A，*）到（N4,⊕4）的同构映射f为： f(a)=0, f(b)=1, f(c)=2, f(d)=3; 或者： f(a)=0, f(b)=3, f(c)=2, f(d)=1; 13、同构映射f为： f(0)=?, f(1)={a}, f(2)={b}, f(3)={a,b}; 或者： f(0)=?, f(1)={b}, f(2)={a}, f(3)={a,b}; 18、任选a ∈N +,b ∈N +, 只需证明f(a+b)=f(a)+f(b) 由f 的定义可知：f(a+b)=2a+2b=f(a)+f(b)，故f 是（N +,+）到(E +,+)的同态映射。 作业：P96：3，P97：7 3、(1)显然，*运算对Z 是封闭的。 (2) (a*b)*c = (3(a+b+2)+ab)*c = 3((3(a+b+2)+ab)+c+2)+(3(a+b+2)+ab)×c = 3(3a+3b+c+ab+8+ac+bc+2c)+abc = 3(3a+3b+3c+ab+ac+bc+8)+abc a*(b*c) = a*(3(b+c+2)+bc) = 3(a+(3(b+c+2)+bc)+2)+a(3(b+c+2)+bc) = 3(a+3b+3c+bc+8+ab+ac+2a)+abc = 3(3a+3b+3c+ab+ac+bc+8)+abc = (a*b)*c 故*运算满足结合律。 （3）任选a ∈Z ，(-2)*a=a 且a*(-2)=a ，所以-2是(Z,*)的幺元。 所以（Z,*）是独异点。 7、因为1为(A,*)运算的幺元，而且对任意A 的子集A ’,*在A ’上都是封闭和可结合的运算，因此，（A,*）的所有子独异点为(A ’,*)，其中A ’必须包含1。即：(A,*)的所有子独异点为： ({1},*),({1,2},*),({1,3},*),({1,4},*),({1,2,3},*),({1,2,4},*),({1,3,4},*),({1,2,3,4},*) P105：3、4、13 3、??????1100b a ×??????220 0b a ＝??? ?? ?212100b b a a ,a 1,a 2∈{1,-1}, 所以a 1×a 2∈{1,-1}，b 1×b 2∈{1,-1}。 故（G,×）是封闭的。 而 (??????1100b a ×??????2200b a )×??????3300b a =??????212 100b b a a ×????? ?3300b a =??????3213 2100b b b a a a ??????1100b a ×(????? ?22 00b a ×??????3300b a )=??????1100b a ×??????323 200b b a a =??????3213210 0b b b a a a 故（G,×）是可结合的。（也可以说因为矩阵乘法是可结合的。） 授课时间十一周第 2 次课 更广泛的同态映射定义 定义设V1= 1. 给出代数系统中6大律 4大特殊元的定义。 2. 什么是群？什么是环？什么是整环？什么是域？什么是格？什么是布尔代数？ 3. 对以下定义的集合和运算判别它们能否构成代数系统？如果能，请说明是构成哪一种代数系统， 并简要说明理由。 （1）}3,3/1,2,2/1,1{1 =S ，*为普通乘法。 （2）{}+=,1,02 S 为普通乘法。 （3）n n S },1,1,0{3 -= 为任意给定的正整数且,*2≥n 为模n 乘法， 为模n 加法。 （4）≤=},3,2,1,0{4 S 为小于等于关系。 （5）},6,3,2,1{5 =S ﹡和+分别表示最小公倍数和最大公约数。 4. 设A ={2，4，6，8}，A 上的二元运算*定义为：a *b =min {a ，b }，则在独异点中，单位元是 ， 零元是 。 5. 关于群的说法正确的是 （A ）群都有子群 (B)群的陪集也是群（C ）群的并是群 （D ）有限群只有2个生成元 6. 关于无零因子环，正确的是 （A ）没有零元 （B ）xy=0，则x 和y 中必有一个是0 （C ）没有零因子 (D)零元不唯一 7. 关于单位元，正确的说法是 （A ）单位元就是1 （B ）单位元就是0 （C ）有单位元，说明有左右单位元（D ）单位元不唯一 8. Z 8的全部生成元是 ，它有 个子群。 9. ???? ??=13424321σ， ???? ??=12344321τ σ-1= ，τσ= . 10. 证明实数域关于加法和乘法是域. 11. 设G 的运算表如下表所示，问G 是否为循环群？如果是，求出它所有的生成元和子群； 12. n=5时，所有不同构的格有哪些？请做出他们的哈斯图，并判断他们是不是分配格，有补格，以及布 尔代数？ 13. 除逻辑代数以外请举出2个布尔代数的实例。 计算机科学各主领域及其基本问题 本节综合CC2013和CC2001报告，给出计算机科学各领域的简介，以及计算机科学中各领域的基本问题。以下学科领域按字母先后顺序排列，不分轻重。 1.算法与复杂性（Algorithms and Complexity，AL） 算法是计算机科学和软件工程的基础。现实世界中任何软件系统的性能仅依赖于两个方面：一方面是所选择的算法；另一方面是在各不同层次实现的效率。 对所有软件系统的性能而言，好的算法设计都是至关重要的。此外，算法研究能够深刻理解问题的本质和可能的求解技术，而不依赖于具体的程序设计语言、程序设计模式、计算机硬件或其他任何与实现有关的内容。 计算的一个重要内容就是根据特定目的选择适当的算法并加以运用，同时认识到可能存在不合适的算法。这依赖于对那些具有良好定义的重要问题求解算法的理解，以及认识到这些算法的优缺点和它们在特定环境中的适宜性。效率是贯穿该领域的一个核心概念。 下面，给出算法与复杂性领域的基本问题。 （1）对于给定的问题类，最好的算法是什么？要求的存储空间和计算时间有多少？空间和时间如何折中？ （2）访问数据的最好方法是什么？ （3）算法最好和最坏的情况是什么？ （4）算法的平均性能如何？ （5）算法的通用性如何？ 2．体系结构（Architecture and Organization，AR） 计算机在计算技术中处于核心地位。如果没有计算机，计算学科将只是理论数学的一个分支。 作为计算专业的学生，都应该对计算机系统的功能部件、功能特点、性能和相互作用有一定的理解，而不应该只将计算机看作是一个执行程序的黑盒子。 了解计算机体系结构和组织还有一定的实际意义。为了构造程序，需要理解计算机体系结构，从而使该程序在一台真正的机器上能更有效地运行。在选择用于应用的系统时，应该理解各种部件之间的折中，如CPU、时钟频率与内存大小的折中。 下面，给出体系结构领域的基本问题。 （1）实现处理器、内存和机内通信的方法是什么？ （2）如何设计和控制大型计算系统，而且使其令人相信，尽管存在错误和失败，但它仍然是按照我们的意图工作的？ （3）哪种类型的体系结构能有效地包含许多在一个计算中能并行工作的处理元素？ （4）如何度量性能？ 3．计算科学（Computational Science，CN） 从该学科诞生之日起，科学计算的数值方法和技术就构成了计算机科学研究的一个主要领域。随着计算机问题求解能力的增强，该领域（正如该学科一样）已经在广度和深度两方面得到了发展。现在，科学计算本身就代表了一个学科，一个与计算机科学密切相关的学科。为此，CC2001任务组只是将它划为计算机科学的一个主领域，但不确定任何核心知识单元，也就是说，尽管它是计算机科学的一个组成部分，但不要求每个教学大纲都必须包含这些内容。 问答题： 1： 第三篇代数结构 Algebraic Structures 引言： 1）代数结构也称为代数系统，是抽象代数的主要研究对象。 2）抽象代数是数学的一个分支，它用代数的方法从不同的研究对象中概括出一般的数学模型并研究其规律、性质和结构。 3）抽象代数学的研究对象是抽象的，它不是以某一具体对象为研究对象，而是以一大类具有某种共同性质的对象为研究对象，因此其研究成果适用于这一类对象中的每个对象，从而达到了事半功倍的效果。 抽象代数学的主要内容： 1）研究各种各样的代数系统，它是在较高的观点上，把一些形式上很不相同的代数系统，撇开其个性，抽出其共性，用统一的方法描述、研 究和推理，从而得到一些反映事物本质的结论，再把它们应用到那些 系统中去，高度的抽象产生了广泛的应用。 构成一个抽象代数系统有三方面的要素：集合、集合上的运算以及说明运算性质或运算之间关系的公理。 整数集合Z和普通加法＋构成了代数系统〈Z,＋〉，n阶实矩阵的集合Mn(R)与矩阵加法＋构成代数系统〈Mn(R),＋〉。幂集P(B)与集合的对称差运算⊕也构成了代数系统 考察他们的共性，不难发现他们都含有一个集合，一个二元运算，并且这些运算都具有交换性和结合性等性质。为了概括这类代数系统的共性，我们可以定义一个抽象的代数系统 为了研究抽象的代数系统，我们需要先定义一元和二元代数运算以及二元运算的性质，并通过选择不同的运算性质来规定各种抽象代数系统的定义。在此基础上再深入研究这些抽象代数系统的内在特性和应用。 信息科学技术学院2003-2004学年第二学期 本科生期末考试试卷 一、（每小题3分,共18分）判断以下命题的真假.如果为真在后面括弧内打 √，否则打?. 1．A ={x |x ∈N 且(x ,5)=1}，则构成代数系统，+为普通加法 （ ） 2．?x , y ∈R ，x o y =|x -y |，则0为 习题一 1. 一个工厂为一结点；若两个工厂之间有业务联系，则此两点之间用边相联；这样就得到一个无向图。若每点的度数为3，则总度数为27，与图的总度数总是偶数的性质矛盾。若仅有四个点的度数为偶数，则其余五个点度数均为奇数，从而总度数为奇数，仍与图的总度数总是偶数的性质矛盾。（或者利用度数为奇数的点的个数必须为偶数个） 2. 若存在孤立点，则m 不超过K n-1的边数, 故 m <= (n-1)(n-2)/2, 与题设矛盾。 3. 4. 用向量(a 1,a 2,a 3)表示三个量杯中水的量, 其中a i 为第i 杯中水的量, i = 1,2,3. 以满足a 1+a 2+a 3 = 8 (a 1,a 2,a 3为非负整数)的所有向量作为各结点, 如果(a 1,a 2,a 3)中某杯的水倒满另一杯得到 ( a ’1, a ’2, a ’3 ) , 则由结点到结点画一条有向边。这样可得一个有向图。 本题即为在此图中找一条由( 8, 0, 0 )到( 4, 4, 0 )的一条有向路，以下即是这样的一条： 5. 可以。 6 若9个人中没有4个人相互认识，构造图G ，每个点代表一个点，两个人相互认识则对应的两个点之间有边。 1） 若可以找到点v ，d(v)>5，则与v 相连的6个点中，要么有3个相互认识，要么有3个 相互不认识（作K 6并给边涂色:红=认识，蓝=不认识，只要证图中必有同色三角形。v 1有5条边，由抽屉原则必有三边同色(设为红)，这三边的另一顶点设为v 2, v 3, v 4。若 △v 2v 3v 4有一边为红，则与v 1构成红色△，若△v 2v 3v 4的三边无红色，则构成蓝色△）。若有3个人相互认识，则这3个人与v 相互认识，这与假设没有4个人相互认识矛盾，所以这6个人中一定有3个人相互不认识 2） 若可以找到点v ，d(v)<5，不与v 相连的点至少有4个，由于没有4个人相互认识，所 以这4个人中至少有2个人相互不认识，这两个人与v 共3个人相互不认识 ∑ ∑∑∑∑ ∑∑==+====-=++=-==---=--=n i i n i i n i n i n i n i i i n i i n i i i i a a n n a a a n n n a n a v v 12 12 1211 2 212 12 i i 2/)1(C )1(2)1(])1[(a a 。 ， 所以 因为 ，＋ 的负度数，则为结点的正度数，为结点记－－－－－ ( 8, 0, 0 ) ( 5, 3, 0 ) ( 5, 0, 3 ) ( 2, 3, 3 ) ( 2, 5, 1 ) (7, 0, 1 ) ( 7, 1, 0 ) ( 4, 4, 0 ) ( 4, 1, 3 ) 集合论与代数结构 课程名称：集合论与代数结构 课号：00830690 任课老师：于江生（副教授） 开课时间：每学年的下学期 学时：4学时/周 学分：4 授课对象：北大本科生（公共辅修课） 课程概要： 1.介绍Cantor的朴素集合论（包括基数理论和序数理论）和集合论ZF公理体系、GB公 理体系。回顾20世纪初数学基础之争和为解决Russell悖论所作的努力，科普G?del 不完全性定理、连续统假设及其意义。 2.介绍格论（Lattice Theory）及其应用，介绍抽象代数（Abstract Algebra）的基本概念（群、 环、域）。着重讲授群论及其应用（详细内容见《群论的应用_学生作业》）。课程的最后部分介绍域的扩张和Galois理论，并证明三等分角和倍立方体的尺规作图问题不可能。 课程目标：培养学生的数学美感，锻炼其逻辑思维能力和想象力，并使之了解近代集合论和代数学的发展。鼓励学生运用数学知识解决各自学科的实际问题，培养他们的独立科研的能力和理论联系实践的能力。 参考书及课外读物： [1]H. B. Enderton (1977), Elements of Set Theory, Academic Press, Inc. [2]L. C. Grove (1983), Algebra, Academic Press, Inc. [3]T. W. Hungerford (1980), Algebra, GTM series, Springer-Verlag [4]Jacobson, Lectures in Abstract Algebra (Vol 1, 2, 3), GTM series (No. 30, 31, 32), Springer-Verlag [5]Takeuti and Zaring, Introduction to Axiomatic Set Theory, GTM series (No. 1), Springer-Verlag [6]Takeuti and Zaring, Axiomatic Set Theory, GTM series (No. 8), Springer-Verlag [7] B. L. van der Waerden (1955), Algebra, Springer-Verlag [8]耿素云、屈婉玲、王捍贫（2002），《离散数学教程》，北京大学出版社 [9]耿素云（1998），《集合论与图论》，北京大学出版社 [10]屈婉玲（1998），《代数结构与组合数学》，北京大学出版社 第八章几个典型的代数结构 本章我们将介绍具有一个二元运算的代数结构半群与群，以及具有两个运算的代数结构环和域。半群与群在形式语言、快速加法器设计、纠错码制定和自动机理论中都有卓有成效的应用。 §8.1 半群与独异点 半群是最简单的一类代数结构，其运算个数少，且运算的性质也少。半群在时序机理论、形式语言、语法分析等方面有着广泛的应用。 一. 半群、独异点和它们的子代数 定义1 给定代数，其中*是二元运算，若*满足结合律，则称代数为半群。 定义2 给定代数，如果二元运算*满足结合律且有么元，则称为独异点。 可以看出，独异点是含有么元的半群。因此有些人将独异点称为含么半群。 例1（1）代数和都是半群，因为运算＋和×都满足结合律；而且还是独异点，因为0是＋的么元，1是×的么元。 （2）代数和不是半群，因为减法和除法不满足结合律。 定义3 如果是半群，且关于运算*封闭，则是的子代数，称为的子半群。 显然子半群是半群。 定义4 如果是独异点，且关于运算*封闭，，则是的子代数，称为的子独异点。 显然子独异点是独异点。 例2（1）代数和分别是独异点和的子独异点。 （2）如果∑是非空有限字母表，那么<∑＋,连结>是半群，<∑*,连结,Λ>是独异点。如果，则连结>是<∑＋,连结>的子半群，连结,Λ>是<∑*,连结,Λ>的子独异点。 定义5 在半群（独异点）中，若运算是可交换的。则称此半群（独异点）为可交换半群（可交换独异点）。 定理8.1.1 在任何可交换独异点中，S的幂等元组成的集合T可构成其子独异点。 证明：，是幂等元，所以。对任意的， 。所以，故是子独异点。 本定理对可交换半群也成立。 下面我们定义独异点中任意元素的幂。用归纳定义： （1）（基础）。 （2）（归纳）。 由于独异点中，运算*是可结合的，容易证明如此定义的的幂满足以下指数定律： （a） （b） 定义6 设是独异点，若存在元素，，都，使得。则称元素为的生成元，也称元素生成独异点，并称此独异点为循环独异点。 定理8.1.2 每个循环独异点是可交换的。 证明：设是循环独异点，且其生成元为。则，存在，使得，，。于是 故：是可交换的。 类似地，可定义半群的任意元素的幂、循环半群、生成元等概念，也可得出循环半群是可交 2013年秋季《集合论与代数系统》复习大纲 一、集合论 1. 掌握元素与集合、集合与集合之间的关系（∈，?） 2. 掌握集合的基本运算?、?、~，⊕，-、P(A)、笛卡尔积及其性质 二、二元关系 1. 掌握二元关系的5种性质，并能准确判断：自反性、反自反性、对称性、反对称性、传递性。 2. 熟练掌握等价关系的定义，并能判定；给定等价关系，熟练求出A/R；掌握自然映射的含义；划分和等价关系的一一对应，即给定集合划分能求出等价关系，给出等价关系能求出对应的映射。模n同余关系。 3. 偏序关系的定义、哈斯图、求给定子集的最大元、最小元、极大元、极小元、上界，上确界，下界，下确界。 4. 给定集合上二元关系的计数、等价关系的计数。 5.给定关系R和T，熟练求出domR,ranR, R?{b,c}, R[{a}],R°T, r(R), s(R), t(R) 三、函数和集合基数 1. 掌握函数的三种性质，并能证明和判定：单射函数、满射函数和双射函数 2. 给定集合A和B，从A到B上函数的计数问题 3. 理解并牢记典型集合的基数：N,R,P(N),2N,Q,N?N等。 4. 可数集和不可数集的判定，集合基数从小到大排序，最小无穷集合基数； 5.康托定理及其含义（cardP(A)>cardA，不存在最大集合） 重点复习ppt上的若干重要结论 四、代数结构 1. 代数结构的构成成分，掌握交换律、结合律、幂等律、吸收律、分配律和消去律 2. 能求出代数结构中的零元、单位元和可逆元素的逆元。熟练求出两个代数的积代数及其单位元和积代数中元素之间的运算 3. 掌握同态映射的定义，同态映射的种类：单同态、满同态和同构；能求解同态像，同态核 4. 群的定义，并能做出判断和证明 5. 循环群的定义，求出循环群中全部生成元和生成子群;可交换群的判定 6.子群的判定方法，熟练求出给定子群的所有陪集 熟练掌握ppt中的例题和重要结论代数结构与拓扑结构Cartan
图论与代数-test
离散数学代数结构作业部分答案
5.3 代数系统的同态与同构
代数系统期中复习
计算机科学各主领域和其基本问题
代数系统证明题
代数结构简介
北大代数结构与组合数学期中试题_计算机基础数学
图论与代数结构第一二三章习题解答
集合论与代数结构
代数结构
2013年秋季《集合论与代数系统》复习大纲
相关主题
文本预览