东大20春学期《离散数学X》在线平时作业3参考资料

东大20春学期《离散数学X》在线平时作业3参考资料引言这份参考资料旨在为同学们完成《离散数学X》在线平时作业3提供一些学习上的指引与思路。离散数学的学习，关键在于对基本概念的深刻理解和对常用方法的熟练掌握。本次作业所涉及的内容，主要集中在图论的核心部分以及代数系统的初步知识。希望同学们在参考本文档时，能够结合课堂所学和教材内容，独立思考，真正理解每一个知识点，而不是简单地照搬答案。一、图论基础（重点回顾）本次作业中，图论部分依然是考察的重点。同学们需要熟练掌握以下几个方面：1.1图的基本概念与术语*顶点与边：无向图、有向图、简单图、多重图、完全图、子图、生成子图等概念的准确理解。在判断或构造特定类型的图时，这些基本定义是出发点。*度与握手定理：无向图中所有顶点的度数之和等于边数的两倍。有向图中则有出度与入度之分，所有顶点的出度之和等于入度之和等于边数。握手定理是解决许多图论计数问题的基础，务必牢记并能灵活应用。*图的连通性：无向图的连通分量、点连通度、边连通度；有向图的强连通、弱连通、单向连通的概念及判断方法。BFS（广度优先搜索）和DFS（深度优先搜索）不仅是遍历图的方法，也是判断连通性、寻找最短路径（在无权图中）的有效工具。1.2路径、回路与图的遍历*路径与回路：简单路径、简单回路、初级路径、初级回路的定义。理解它们的区别与联系，对于后续学习欧拉图、哈密顿图至关重要。*欧拉图与哈密顿图：*欧拉图：重点掌握欧拉通路和欧拉回路的判定定理。对于无向图，欧拉回路存在当且仅当图是连通的且所有顶点度数均为偶数；欧拉通路存在当且仅当图是连通的且恰好有两个奇度顶点（这两个顶点分别为通路的起点和终点）。有向图的情况类似，但需考虑出度与入度的平衡。*哈密顿图：相对复杂，目前没有像欧拉图那样简单实用的充要条件。作业中可能会涉及到一些充分条件（如Dirac定理、Ore定理）的应用，或者通过观察、尝试来判断和构造哈密顿路径或回路。*最短路径问题：虽然作业可能不直接考察复杂算法的编程实现，但Dijkstra算法的基本思想（按路径长度递增的次序产生最短路径）和Floyd-Warshall算法的动态规划思想值得理解，这对于解决一些简单的最短路径问题有帮助。1.3树及其性质*树的定义与基本性质：树是无回路的连通无向图。n个顶点的树有且仅有n-1条边；树中任意两个顶点之间有且仅有一条简单路径；在树中添加一条边会形成唯一的回路。这些性质是判断一个图是否为树以及解决树的相关问题的基础。*生成树与最小生成树：*生成树：连通图的生成树是包含图中所有顶点的极小连通子图。一个连通图可能有多个生成树。*最小生成树：在带权连通图中，权值之和最小的生成树。Kruskal算法（避圈法，按边权递增顺序选择不构成回路的边）和Prim算法（加点法，从某一顶点开始，逐步添加权值最小的边将新顶点纳入树中）是构造最小生成树的经典算法，需要理解其步骤和原理，并能手动模拟求解。二、代数系统初步（核心概念）代数系统部分，本次作业可能会涉及到群、环、域的基本概念，重点是群的定义和性质。2.1代数系统的基本概念*运算：二元运算的定义（封闭性是关键），运算的性质如交换律、结合律、分配律、吸收律、幂等律等。*特殊元素：幺元（单位元）、零元、逆元的定义和性质。对于给定的集合和运算，要能判断这些特殊元素是否存在，并求出它们（如果存在）。2.2群的定义与性质*半群与独异点：半群是对运算封闭且满足结合律的代数系统；独异点是含有幺元的半群。*群的定义：群是每个元素都有逆元的独异点。即，一个代数系统<G,*>如果满足：1.运算*在G上封闭；2.运算*满足结合律；3.存在幺元e∈G；4.对每个元素a∈G，都存在逆元a⁻¹∈G。则称<G,*>为一个群。*群的基本性质：*群中的幺元是唯一的。*群中每个元素的逆元是唯一的。*消去律成立：若a*b=a*c，则b=c；若b*a=c*a，则b=c。*子群：子群的定义，以及判断一个非空子集是否构成子群的条件（如：对运算封闭、对逆元封闭；或a*b⁻¹∈H等）。*阿贝尔群：运算满足交换律的群称为阿贝尔群（交换群）。2.3环与域的基本概念（可能涉及）*环：环是具有两个二元运算（通常称为“加法”和“乘法”）的代数系统，其中关于加法构成阿贝尔群，关于乘法构成半群，并且乘法对加法满足分配律。*域：域是一种特殊的环，其中非零元素关于乘法构成阿贝尔群。有理数集、实数集、复数集关于普通加法和乘法都构成域。三、解题思路与常见题型提示1.基本概念判断题：这类题目主要考察对定义的准确记忆和理解。例如，判断一个图是否为欧拉图、是否为树，判断一个代数系统是否为群等。解题时务必对照定义的各个条件，逐条检查。2.计算题：如图的顶点度数计算、握手定理的应用、求生成树的个数（简单情况）、求最小生成树的权值和、求群中元素的逆元等。需要细心，确保计算准确。3.构造题：如构造满足特定条件的图（如指定度数序列的图、具有某种性质的子图）、构造最小生成树等。这类题目需要结合相关定理和算法，逐步构建。4.证明题：这是离散数学的难点。例如，证明一个图是哈密顿图（可能用到充分条件），证明一个代数系统是群或子群。证明时要逻辑清晰，论据充分，善于利用已知定义、定理和性质。四、学习建议*回归教材：所有知识点都源于教材，仔细阅读教材相关章节，确保对基本概念和定理的理解没有偏差。*多做练习：离散数学的学习离不开练习。通过做题可以检验对知识的掌握程度，熟悉解题技巧。*注重理解：不要死记硬背公式和定理，要理解其背后的思想和推导过程。只有理解了，才能灵活运用。*善用工具：对于图论问题，可以尝试画图帮助理解；对于代数系