大连海事大学离散数学期末复习纲要总结.ppt

4. 可约的或可消去的 设X,*为代数系统，且a?X，如果对任意的x，y?X有： （a*x=a*y）∨（x*a=y*a）?x = y 则称a是可约的或可消去的。 5. 代数系统 设X是一个非空集合，?为X上的代数运算构成的非空集合，则称序偶X, ?为一个代数系统（或代数结构），其中： (1)集合X为代数系统X, ?的定义域。如果X是个有限集合，则称X, ?为有限代数系统，│X│=n为代数系统的阶；否则称X, ?为无限代数系统。 (2)?=?1，?2，…?n｝为X中的n元运算（n=1，2，3，…）构成的集合，如果?为有限集合，则可将X, ?表示为：X, ?1，?2，…?n。 6. 同态与同构的概念 设U＝X，ｏ，V＝Y，*是两个代数系统，ｏ和*是二元运算，函数f：X→Y，如果对任意的x，yX有: f(xｏy)=f(x)*f(y) (运算的像=像的运算) 则称f是代数系统U到V同态映射(简称同态)，并称代数系 统U与V同态。 (1) 如果f是满射的，则称f 是从U到V的满同态； (2) 如果f是单射的，则称f 是从U到V的单一同态； (3) 如果f是双射的，则称f 是从U到V的同构。 (4) 如果U=V，则称f是从U到U的自同构。 7. 代换性质和同余关系 代换性质：给定代数系统X，*，其中是个二元运算。设R是X中的等价关系，如果对任意的x1，x2?X和y1，y2?X有： (x1Rx2)∧(y1Ry2)?(x1*y1)R(x2*y2) 则称等价关系E对于运算具有代换性质。 同余关系：给定代数系统U=X，*，且R是集合X 中的等价关系。如果等价关系R对运算具有代换性 质，则称R是代数系统U中的同余关系。 8. 商代数与积代数 给定代数系统U=X，ｏ，其中ｏ是个二元运算，R是U中的同余关系。试构成一个新的代数系统W=X/R，?，其中 (1)X/R=｛[x]R │x?X｝； (2)对任意的x1,x2?X,有[x1]R?[x2]R=[x1ｏx2]R 则称代数系统W为U的商代数，简称商代数，并记 作U/R。 商代数与积代数（续） 设U＝X，ｏ，V＝Y，*是代数系统，试构成一个新的代数系统：U×V = X×Y，? 其中X×Y是X和Y的笛卡儿乘积，且运算?的定义为：对任意的x1，x2?X和y1，y2?Y有 x1 ,y1,x2 ,y2＝x1ｏx2，y1*y2 则称U×V是U和V的积代数，U和V是U×V的因子代数。　 9.半群和群 半群：设S,*是代数系统，*运算是S上的二元运算，若*运算是可结合的，则称S,*为一个半群。 群：（1）S，*是代数系统； （2） “*”运算满足结合律； （3）A，*中存在幺元e； （4）A，*中任意一个元素都有逆元素； 则称代数系统A，*是群。 子群 设A，*是一个群，H是A的非空子集，若H，*也是一个群，则称H，*是A，*的子群。 阿贝尔群和循环群 若群A，*对运算“*”满足交换律，则 称A，*是阿贝尔群（交换群）。 若群A，*中每个元素均是它的某个 元素a的整数幂，则称A，*是由a生成的循环群。a称为A，*的生成元素。 二、本章要点 (1)理解代数运算以及代数运算的性质（结合律、交换律、分配律、等幂律、消去律）。 (2)掌握代数系统和子代数系统的定义，理解运算的封闭性。 (3)给定集合和运算，会判别运算对该集合是否封闭。 本章要点（续） (4)给定二元运算，说明运算是否满足交换律、结合律、等幂律、分配律和消去律。 (5)掌握和理解幺元、零元、逆元的概念,给定—个集合和该集合上的二元运算，会求该运算的幺元、零元和逆元。 (6)掌握和理解同态、满同态、单一同态和同构的概念和性质,并会求解（证）相关问题。 (7)掌握半群、独异点、群、子群的概念及相关的证明。 (8)理解阿贝尔群、循环群的概念。 本章要点（续） 第七章 图论要点 1、图的基本概念： （1）无向图、有向图、简单图、子图、真子图、生成子图、完全图、正则图、零图、平凡图、加权图、补图、图同构。 （2）邻接结点、邻接边； （3）无向图：度的概念； （4）有向图：出度、入度、度； （5）奇结点、偶结点； （6）任何一个(n,m)图，其度之和等于边数的两倍； （7）任何一个图G，度为奇数的结点个数一定为偶数个。 图论要点（续） 2、路径、回路和图的连通性： （1）路径（简单路径、基本路径），回路（简单回路、基本回路）； （2）可达的概念、连通图与非连通图、分支（极大连通子图）； （3）强连通图、单向连通图和弱连通图，强分支、单向分支和弱分支。 图论要点（续） 3、图的矩阵表示： （1）掌握无向图和有向图的矩阵表示：邻接矩阵、可达性矩阵； （2）有向图