离散数学复习ppt课件.ppt

1 大概的考试题型 选择题20填空题30计算 简答 题20证明题30 1 2 第三部分代数结构 主要内容代数系统 二元运算及其性质 代数系统和子代数半群与群 半群 独异点 群环与域 环 整环 域 2 3 第九章代数系统 主要内容二元运算及其性质一元和二元运算定义及其实例二元运算的性质代数系统代数系统定义及其实例子代数积代数代数系统的同态与同构 3 4 基本要求 判断给定集合和运算能否构成代数系统判断给定二元运算的性质求而二元运算的特异元素了解同类型和同种代数系统的概念了解子代数的基本概念计算积代数判断函数是否为同态映射和同构映射 4 5 一 二元运算及其性质 定义9 1设S为集合 函数f S S S称为S上的二元运算 简称为二元运算 S中任何两个元素都可以进行运算 且运算的结果惟一 S中任何两个元素的运算结果都属于S 即S对该运算封闭 定义9 2设S为集合 函数f S S称为S上的一元运算 简称一元运算 5 6 二元运算的性质 定义9 3设 为S上的二元运算 1 若对任意x y S有x y y x 则称运算在S上满足交换律 2 若对任意x y z S有 x y z x y z 则称运算在S上满足结合律 3 若对任意x S有x x x 则称运算在S上满足幂等律 定义9 4设 和 为S上两个不同的二元运算 1 若对任意x y z S有 x y z x z y z z x y z x z y 则称 运算对 运算满足分配律 2 若 和 都可交换 且对任意x y S有x x y x x x y x 则称 和 运算满足吸收律 6 7 特异元素 单位元 零元 定义9 5设 为S上的二元运算 1 如果存在el 或er S 使得对任意x S都有el x x 或x er x 则称el 或er 是S中关于 运算的左 或右 单位元 若e S关于 运算既是左单位元又是右单位元 则称e为S上关于 运算的单位元 单位元也叫做幺元 2 如果存在 l 或 r S 使得对任意x S都有 l x l 或x r r 则称 l 或 r 是S中关于 运算的左 或右 零元 若 S关于 运算既是左零元又是右零元 则称 为S上关于运算 的零元 7 8 可逆元素和逆元 3 设 为S上的二元运算 令e为S中关于运算 的单位元 对于x S 如果存在yl 或yr S使得yl x e 或x yr e 则称yl 或yr 是x的左逆元 或右逆元 关于 运算 若y S既是x的左逆元又是x的右逆元 则称y为x的逆元 如果x的逆元存在 就称x是可逆的 8 9 惟一性定理 定理9 1设 为S上的二元运算 el和er分别为S中关于运算的左和右单位元 则el er e为S上关于 运算的惟一的单位元 类似地可以证明关于零元的惟一性定理 注意 当 S 2 单位元与零元是不同的 当 S 1时 这个元素既是单位元也是零元 定理9 2设 为S上可结合的二元运算 e为该运算的单位元 对于x S如果存在左逆元yl和右逆元yr 则有yl yr y 且y是x的惟一的逆元 9 10 9 2代数系统 定义9 6非空集合S和S上k个一元或二元运算f1 f2 fk组成的系统称为代数系统 简称代数 记做 构成代数系统的成分 集合 也叫载体 规定了参与运算的元素 运算 这里只讨论有限个二元和一元运算 代数常数 通常是与运算相关的特异元素 如单位元等 研究代数系统时 如果把运算具有它的特异元素也作为系统的性质之一 那么这些特异元素可以作为系统的成分 叫做代数常数 10 11 子代数系统 定义9 8 设V 是代数系统 B是S的非空子集 如果B对f1 f2 fk都是封闭的 且B和S含有相同的代数常数 则称是V的子代数系统 简称子代数 有时将子代数系统简记为B 说明 子代数和原代数是同种的代数系统对于任何代数系统V 其子代数一定存在 11 12 第十章群与环 主要内容群的定义与性质子群与群的陪集分解循环群与置换群环与域 12 13 基本要求 判断或证明给定集合和运算是否构成半群 独异点和群熟悉群的基本性质能够证明G的子集构成G的子群熟悉陪集的定义和性质熟悉拉格朗日定理及其推论 学习简单应用会求循环群的生成元及其子群熟悉n元置换的表示方法 乘法以及n元置换群能判断给定代数系统是否为环和域 13 14 半群 独异点与群的定义半群 独异点 群的实例群中的术语群的基本性质 10 1群的定义与性质 14 15 半群 独异点与群的定义 定义10 1 1 设V 是代数系统 为二元运算 如果 运算是可结合的 则称V为半群 2 设V 是半群 若e S是关于 运算的单位元 则称V是含幺半群 也叫做独异点 有时也将独异点V记作V 3 设V 是独异点 e S关于 运算的单位元 若 a S a 1 S 则称V是群 通常将群记作G 15 16 有关群的术语 定义10 2 1 若群G是有穷集 则称G是有限群 否则称为无限群 群G的基数称为群G的阶 有限群G的阶记作 G 2 只含单位元的群称为平凡群 3 若群G中的二元运算是可交换的 则称G为交换群或阿贝尔 Abel 群 定义10 4设G是群 a G 使得等式ak e成立的最小正整数k称为a的阶 记作 a k 称a为k阶元 若不存在这样的正整数k 则称a为无限阶元 16 17 群的性质 幂运算规则 定理10 1设G为群 则G中的幂运算满足 1 a G a 1 1 a 2 a b G ab 1 b 1a 1 3 a G anam an m n m Z 4 a G an m anm n m Z 5 若G为交换群 则 ab n anbn 17 18 群的性质 消去律 元素的阶 定理10 3 G为群 则G中适合消去律 即对任意a b c G有 1 若ab ac 则b c 2 若ba ca 则b c 例5设G是群 a b G是有限阶元 证明 1 b 1ab a 2 ab ba 定理10 4 G为群 a G且 a r 设k是整数 则 1 ak e当且仅当r k 2 a 1 a 18 19 10 2子群与群的陪集分解 定义10 5设G是群 H是G的非空子集 1 如果H关于G中的运算构成群 则称H是G的子群 记作H G 2 若H是G的子群 且H G 则称H是G的真子群 记作H G 例如nZ n是自然数 是整数加群的子群 当n 1时 nZ是Z的真子群 对任何群G都存在子群 G和 e 都是G的子群 称为G的平凡子群 19 20 子群判定定理 定理10 5 判定定理一 设G为群 H是G的非空子集 则H是G的子群当且仅当 1 a b H有ab H 2 a H有a 1 H 定理10 6 判定定理二 设G为群 H是G的非空子集 H是G的子群当且仅当 a b H有ab 1 H 定理10 7 判定定理三 设G为群 H是G的非空有穷子集 则H是G的子群当且仅当 a b H有ab H 20 21 典型子群的实例 定义10 6设G为群 a G 令H ak k Z 则H是G的子群 称为由a生成的子群 记作 定义10 7设G为群 令C a a G x G ax xa 则C是G的子群 称为G的中心 例6设G是群 H K是G的子群 证明 1 H K也是G的子群 2 H K是G的子群当且仅当H K或K H 21 22 陪集 定义10 9设H是G的子群 a G 令 Ha ha h H 称Ha是子群H在G中的右陪集 称a为Ha的代表元素 定理10 8设H是群G的子群 则 1 He H 2 a G有a Ha 定理10 9设H是群G的子群 则 a b G有 a Hb ab 1 H Ha Hb 22 23 推论 推论设H是群G的子群 则 1 a b G Ha Hb或Ha Hb 2 Ha a G G证明 由等价类性质可得 定理10 10设H是群G的子群 在G上定义二元关系R a b G R ab 1 H则R是G上的等价关系 且 a R Ha 23 24 左陪集的定义与性质 设G是群 H是G的子群 H的左陪集 即 aH ah h H a G关于左陪集有下述性质 1 eH H 2 a G a aH 3 a b G a bH b 1a H aH bH 4 若在G上定义二元关系R a b G R b 1a H则R是G上的等价关系 且 a R aH 5 a G H aH 24 25 Lagrange定理 定理10 12 Lagrange 设G是有限群 H是G的子群 则 G H G H 其中 G H 是H在G中的不同右陪集 或左陪集 数 称为H在G中的指数 推论1设G是n阶群 则 a G a 是n的因子 且有an e 推论2对阶为素数的群G 必存在a G使得G 25 26 Lagrange定理的应用 命题 如果群G只含1阶和2阶元 则G是Abel群 例8证明6阶群中必含有3阶元 证设a为G中任意元素 有a 1 a 任取x y G 则xy xy 1 y 1x 1 yx 因此G是Abel群 证设G是6阶群 则G中元素只能是1阶 2阶 3阶或6阶 若G中含有6阶元 设为a 则a2是3阶元 若G中不含6阶元 下面证明G中必含有3阶元 如若不然 G中只含1阶和2阶元 即 a G 有a2 e 由命题知G是Abel群 取G中2阶元a和b a b 令H e a b ab 则H是G的子群 但 H 4 G 6 与拉格朗日定理矛盾 26 27 10 3循环群与置换群 定义10 10设G是群 若存在a G使得 G ak k Z 则称G是循环群 记作G 称a为G的生成元 循环群的分类 n阶循环群和无限循环群 设G 是循环群 若a是n阶元 则 G a0 e a1 a2 an 1 那么 G n 称G为n阶循环群 若a是无限阶元 则 G a0 e a 1 a 2 称G为无限循环群 27 28 循环群的生成元 定理10 13设G 是循环群 1 若G是无限循环群 则G只有两个生成元 即a和a 1 2 若G是n阶循环群 则G含有 n 个生成元 对于任何小于n且与n互质的数r 0 1 n 1 ar是G的生成元 n 成为欧拉函数 例如n 12 小于或等于12且与12互素的正整数有4个 1 5 7 11 所以 12 4 28 29 循环群的子群 定理10 14设G 是循环群 1 设G 是循环群 则G的子群仍是循环群 2 若G 是无限循环群 则G的子群除 e 以外都是无限循环群 3 若G 是n阶循环群 则对n的每个正因子d G恰好含有一个d阶子群 29 30 10 4环与域 定义10 12设是代数系统 和 是二元运算 如果满足以下条件 1 构成交换群 2 构成半群 3 运算关于 运算适合分配律则称是一个环 通常称 运算为环中的加法 运算为环中的乘法 环中加法单位元记作0 乘法单位元 如果存在 记作1 对任何元素x 称x的加法逆元为负元 记作 x 若x存在乘法逆元的话 则称之为逆元 记作x 1 30 31 定理10 16设是环 则 1 a R a0 0a 0 2 a b R a b a b ab 3 a b c R a b c ab ac b c a ba ca 4 a1 a2 an b1 b2 bm R n m 2 环的运算性质 31 32 特殊的环 定义10 13设是环 1 若环中乘法 适合交换律 则称R是交换环 2 若环中乘法 存在单位元 则称R是含幺环 3 若 a b R ab 0 a 0 b 0 则称R是无零因子环 4 若R既是交换环 含幺环 无零因子环 则称R是整环 5 设R是整环 且R中至少含有两个元素 若 a R 其中R R 0 都有a 1 R 则称R是域 32 33 第五部分图论 本部分主要内容图的基本概念欧拉图 哈密顿图树平面图支配集 覆盖集 独立集 匹配与着色 33 34 第十四章图的基本概念 主要内容图通路与回路图的连通性图的矩阵表示图的运算预备知识多重集合 元素可以重复出现的集合无序集 A B x y x A y B 34 35 基本要求 深刻理解握手定理及推论的内容并能灵活地应用它们深刻理解图同构 简单图 完全图 正则图 子图 补图 二部图的概念以及它们的性质及相互之间的关系记住通路与回路的定义 分类及表示法深刻理解与无向图连通性 连通度有关的诸多概念会判别有向图连通性的类型熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方法 会求可达矩阵 35 36 相关概念 1 图 可用G泛指图 无向的或有向的 V G E G V D E D n阶图2 有限图3 n阶零图与平凡图 1阶零图 4 空图 5 用ek表示无向边或有向边6 顶点与边的关联关系 关联 关联次数 环 孤立点7 顶点之间的相邻与邻接关系 36 37 多重图与简单图 定义14 3 1 无向图中的平行边 大于1条 及重数 2 有向图中的平行边及重数 注意方向性 3 多重图 含平行边的图 4 简单图 既不含边 也不含环的图 在定义14 3中定义的简单图是极其重要的概念 37 38 顶点的度数 定义14 4 1 设G 为无向图 v V d v v的度数 简称度 2 设D 为有向图 v V d v v的出度d v v的入度d v v的度或度数 3 G G 4 D D D D D D 5 奇顶点度与偶度顶点 38 39 定理14 1设G 为任意无向图 V v1 v2 vn E m 则 推论任何图 无向或有向 中 奇度顶点的个数是偶数 握手定理 定理14 2设D 为任意有向图 V v1 v2 vn E m 则 39 40 图的度数列 1 V v1 v2 vn 为无向图G的顶点集 称d v1 d v2 d vn 为G的度数列2 V v1 v2 vn 为有向图D的顶点集 D的度数列 d v1 d v2 d vn D的出度列 d v1 d v2 d vn D的入度列 d v1 d v2 d vn 3 非负整数列d d1 d2 dn 是可图化的 是可简单图化的 易知 2 4 6 8 10 1 3 3 3 4 是可图化的 后者又是可简单图化的 而 2 2 3 4 5 3 3 3 4 都不是可简单图化的 特别是后者也不是可图化的 40 41 n阶完全图与竞赛图 定义14 6 1 n n 1 阶无向完全图 每个顶点与其余顶点均相邻的无向简单图 记作Kn 简单性质 边数 2 n n 1 阶有向完全图 每对顶点之间均有两条方向相反的有向边的有向简单图 简单性质 3 n n 1 阶竞赛图 基图为Kn的有向简单图 简单性质 边数 41 42 子图 定义14 8G G 1 G G G 为G的子图 G为G 的母图 2 若G G且V V 则称G 为G的生成子图 3 若V V或E E 称G 为G的真子图 4 V V V且V 的导出子图 记作G V 5 E E E且E 的导出子图 记作G E 42 43 补图 定义14 9设G 为n阶无向简单图 以V为顶点集 以所有使G成为完全图Kn的添加边组成的集合为边集的图 称为G的补图 记作 若G 则称G是自补图 43 44 14 2通路与回路 定义14 11给定图G 无向或有向的 G中顶点与边的交替序列 v0e1v1e2 elvl vi 1 vi是ei的端点 1 通路与回路 为通路 若v0 vl 为回路 l为回路长度 2 简单通路与回路 所有边各异 为简单通路 又若v0 vl 为简单回路 3 初级通路 路径 与初级回路 圈 中所有顶点各异 则称 为初级通路 路径 又若除v0 vl 所有的顶点各不相同且所有的边各异 则称 为初级回路 圈 4 复杂通路与回路 有边重复出现 44 45 通路与回路的长度 定理14 5在n阶图G中 若从顶点vi到vj vi vj 存在通路 则从vi到vj存在长度小于或等于n 1的通路 推论在n阶图G中 若从顶点vi到vj vi vj 存在通路 则从vi到vj存在长度小于或等于n 1的初级通路 路径 定理14 6在一个n阶图G中 若存在vi到自身的回路 则一定存在vi到自身长度小于或等于n的回路 推论在一个n阶图G中 若存在vi到自身的简单回路 则一定存在长度小于或等于n的初级回路 45 46 14 3图的连通性 无向图的连通性 1 顶点之间的连通关系 G 为无向图 若vi与vj之间有通路 则vi vj 是V上的等价关系R u v V且u v 2 G的连通性与连通分支 若 u v V u v 则称G连通 V R V1 V2 Vk 称G V1 G V2 G Vk 为连通分支 其个数p G k k 1 k 1 G连通 46 47 无向图的连通度 1 删除顶点及删除边G v 从G中将v及关联的边去掉G V 从G中删除V 中所有的顶点G e 将e从G中去掉G E 删除E 中所有边2 点割集与边割集点割集与割点定义14 16G V VV 为点割集 p G V p G 且有极小性v为割点 v 为点割集定义14 17G E EE 是边割集 p G E p G 且有极小性e是割边 桥 e 为边割集 47 48 有向图的连通性 定义14 20D 为有向图vi vj vi可达vj vi到vj有通路vi vj vi与vj相互可达 性质 具有自反性 vi vi 传递性 具有自反性 对称性 传递性vi到vj的短程线与距离类似于无向图中 只需注意距离表示法的不同 无向图中d vi vj 有向图中d 及d无对称性 48 49 有向图的连通性及分类 定义14 22D 为有向图D弱连通 连通 基图为无向连通图D单向连通 vi vj V vi vj或vj viD强连通 vi vj V vi vj易知 强连通 单向连通 弱连通判别法定理14 8D强连通当且仅当D中存在经过每个顶点至少一次的回路定理14 9D单向连通当且仅当D中存在经过每个顶点至少一次的通路 49 50 二部图 定义14 23设G 为一个无向图 若能将V分成V1和V2 V1 V2 V V1 V2 使得G中的每条边的两个端点都是一个属于V1 另一个属于V2 则称G为二部图 或称二分图 偶图等 称V1和V2为互补顶点子集 常将二部图G记为 又若G是简单二部图 V1中每个顶点均与V2中所有的顶点相邻 则称G为完全二部图 记为Kr s 其中r V1 s V2 注意 n阶零图为二部图 50 51 有向图的邻接矩阵 无限制 定义14 26设有向图D V v1 v2 vn E e1 e2 em 令为顶点vi邻接到顶点vj边的条数 称为D的邻接矩阵 记作A D 或简记为A 性质 51 52 推论设Bl A A2 Al l 1 则Bl中元素 为D中长度为l的通路总数 定理14 11设A为有向图D的邻接矩阵 V v1 v2 vn 为顶点集 则A的l次幂Al l 1 中元素 为D中vi到vj长度为l的通路数 其中 为vi到自身长度为l的回路数 而 为D中长度小于或等于l的回路数 为D中长度小于或等于l的通路数 邻接矩阵的应用 为D中长度为l的回路总数 52 53 定义14 27设D 为有向图 V v1 v2 vn 令 有向图的可达矩阵 无限制 称 pij n n为D的可达矩阵 记作P D 简记为P 由于 vi V vi vi 所以P D 主对角线上的元素全为1 由定义不难看出 D强连通当且仅当P D 为全1矩阵 下图所示有向图D的可达矩阵为 53 54 第十五章欧拉图与哈密顿图 主要内容欧拉通路 欧拉回路 欧拉图 半欧拉图及其判别法哈密顿通路 哈密顿回路 哈密顿图 半哈密顿图带权图 货郎担问题 54 55 基本要求 基本要求深刻理解欧拉图 半欧拉图的定义及判别定理深刻理解哈密顿图 半哈密顿图的定义 会用哈密顿图的必要条件判断某些图不是哈密顿图 会用充分条件判断某些图是哈密顿图 要特别注意的是 不能将必要条件当作充分条件 也不要将充分条件当必要条件 55 56 欧拉图定义 定义15 1 1 欧拉通路 经过图中每条边一次且仅一次行遍所有顶点的通路 2 欧拉回路 经过图中每条边一次且仅一次行遍所有顶点的回路 3 欧拉图 具有欧拉回路的图 4 半欧拉图 具有欧拉通路而无欧拉回路的图 几点说明 规定平凡图为欧拉图 欧拉通路是生成的简单通路 欧拉回路是生成的简单回路 环不影响图的欧拉性 56 57 无向欧拉图的判别法 定理15 1无向图G是欧拉图当且仅当G连通且无奇度数顶点 定理15 2无向图G是半欧拉图当且仅当G连通且恰有两个奇度顶点 57 58 有向欧拉图的判别法 定理15 3有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度 定理15 4有向图D是半欧拉图当且仅当D是单向连通的 且D中恰有两个奇度顶点 其中一个的入度比出度大1 另一个的出度比入度大1 而其余顶点的入度都等于出度 定理15 5G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈之并 58 59 哈密顿图与半哈密顿图 定义15 2 1 哈密顿通路 经过图中所有顶点一次仅一次的通路 2 哈密顿回路 经过图中所有顶点一次仅一次的回路 3 哈密顿图 具有哈密顿回路的图 4 半哈密顿图 具有哈密顿通路且无哈密顿回路的图 几点说明 平凡图是哈密顿图 哈密顿通路是初级通路 哈密顿回路是初级回路 环与平行边不影响哈密顿性 哈密顿图的实质是能将图中的所有顶点排在同一个圈上 59 60 无向哈密顿图的一个必要条件 定理15 6设无向图G 是哈密顿图 对于任意V1 V且V1 均有p G V1 V1 推论设无向图G 是半哈密顿图 对于任意的V1 V且V1 均有p G V1 V1 1 60 61 无向哈密顿图的一个充分条件 定理15 7设G是n阶无向简单图 若对于任意不相邻的顶点vi vj 均有d vi d vj n 1 则G中存在哈密顿通路 推论设G为n n 3 阶无向简单图 若对于G中任意两个不相邻的顶点vi vj 均有d vi d vj n 则G中存在哈密顿回路 从而G为哈密顿图 61 62 第十六章树 主要内容无向树及其性质生成树 最小生成树 基本回路系统 基本割集系统根树及其分类 最优树 最佳前缀码 波兰符号法 逆波兰符号法 62 63 基本要求 基本要求深刻理解无向树的定义及性质熟练地求解无向树准确地求出给定带权连通图的最小生成树深刻理解基本回路 基本割集的概念 并会计算理解根树及其分类等概念会画n阶 n较小 非同构的无向树及根树 1 n 6 熟练掌握求最优树及最佳前缀码的方法掌握波兰符号法与逆波兰符号法 63 64 16 1无向树及其性质 定义16 1 1 无向树 连通无回路的无向图 2 平凡树 平凡图 3 森林 至少由两个连通分支 每个都是树 组成 4 树叶 1度顶点 5 分支点 度数 2的顶点 64 65 无向树的等价定义 定理16 1设G 是n阶m条边的无向图 则下面各命题是等价的 1 G是树 2 G中任意两个顶点之间存在惟一的路径 3 G中无回路且m n 1 4 G是连通的且m n 1 5 G是连通的且G中任何边均为桥 6 G中没有回路 但在任何两个不同的顶点之间加一条新边 在所得图中得到惟一的一个含新边的圈 定理16 2设T是n阶非平凡的无向树 则T中至少有两片树叶 65 66 不一定连通 也不一定不含回路 如图所示 定义16 2设G为无向图 1 G的树 T是G的子图并且是树 2 G的生成树 T是G的生成子图并且是树 3 生成树T的树枝 T中的边 4 生成树T的弦 不在T中的边 5 生成树T的余树 全体弦组成的集合的导出子图 16 2生成树 66 67 推论2的边数为m n 1 推论3为G的生成树T的余树 C为G中任意一个圈 则C与一定有公共边 证否则 C中的边全在T中 这与T为树矛盾 定理16 3无向图G具有生成树当且仅当G连通 生成树存在条件 推论1G为n阶m条边的无向连通图 则m n 1 证必要性显然 充分性用破圈法 注意 在圈上删除任何一条边 不破坏连通性 67 68 基本回路系统 定理16 4设T为G的生成树 e为T的任意一条弦 则T e中含一个只有一条弦其余边均为T的树枝的圈 不同的弦对应的圈也不同 定义16 3设T是n阶m条边的无向连通图G的一棵生成树 设e 1 e 2 e m n 1为T的弦 设Cr为T添加弦e r产生的只含弦e r 其余边均为树枝的圈 称Cr为G的对应树T的弦e r的基本回路或基本圈 r 1 2 m n 1 并称 C1 C2 Cm n 1 为G对应T的基本回路系统 称m n 1为G的圈秩 记作 G 68 69 基本割集的存在 定理16 5设T是连通图G的一棵生成树 e为T的树枝 则G中存在只含树枝e 其余边都是弦的割集 且不同的树枝对应的割集也不同 定义16 4设T是n阶连通图G的一棵生成树 e 1 e 2 e n 1为T的树枝 Si是G的只含树枝e i的割集 则称Si为G的对应于生成树T由树枝e i生成的基本割集 i 1 2 n 1 并称 S1 S2 Sn 1 为G对应T的基本割集系统 称n 1为G的割集秩 记作 G 69 70 最小生成树 定义16 5T是G 的生成树 1 W T T各边权之和 2 最小生成树 G的所有生成树中权最小的 求最小生成树的一个算法避圈法 Kruskal 设G 将G中非环边按权从小到大排序 e1 e2 em 1 取e1在T中 2