AliveRiver

外观

离散2知识点总结

约 5871 字大约 20 分钟

2026-05-12

本word文档是个人根据大连理工大学离散数学的PPT和课本进行的知识点总结，仅限参考，如有造成知识点空缺，本人概不负责。

该word文档的所有解释权归本人所有。

该word文档拒绝以盈利性质分享。

该word文档已经不再更新，如有错误请自觉改写。

第六章 代数系统

6.1 代数系统

6.1.1 二元运算

{width="5.768055555555556in" height="1.7229166666666667in"}

值得注意的是：n元运算是封闭的，即经运算后产生的象（即运算结果）仍在同一个集合中。

此外，有些运算 存在幺元或零元，它在运算中起着特殊的作用， 称它为S中的特异元或代数常数。

{width="5.768055555555556in" height="0.6305555555555555in"}

（一个显而易见且不怎么常用的定理）

{width="5.768055555555556in" height="3.4444444444444446in"}

（一定要学会读运算表）

6.1.2 代数系统

{width="5.768055555555556in" height="1.3458333333333334in"}

集合S的基数即 | S | 定义代数系统的基数，也称作代数系统的阶。 如果S是有限集合，则说代数结构是有限代数系统；否则便说是无穷代数系统。

S被称为代数系统的载体，S和运算叫做代数系统的成分

{width="5.873096019247594in" height="0.7702996500437446in"}

（同类型只考察代数系统的运算和代数常数）

{width="5.768055555555556in" height="1.6645833333333333in"}

{width="6.473767497812774in" height="1.314747375328084in"}

值得一提的是，一个子代数可以又平凡又真，以下举例：

S={1,2,3} V=<S,*,1> (*为正常意义下的乘法，1为该代数系统的代数常数)

T=<{1},*,1>

T为V的平凡子代数（只包含V中的代数常数），又是真子代数（T的集合被S真包含）

6.2 代数系统的基本性质

{width="5.768055555555556in" height="1.3569444444444445in"}

{width="5.768055555555556in" height="1.1534722222222222in"}

如果某一运算满足交换律，则该运算的运算表关于主对角线对称

{width="5.768055555555556in" height="3.1284722222222223in"}

{width="5.768055555555556in" height="3.1173611111111112in"}

{width="5.768055555555556in" height="2.0256944444444445in"}

{width="5.768055555555556in" height="1.070138888888889in"}

（一个显而易见的定理）

{width="5.768055555555556in" height="3.9972222222222222in"}

{width="5.768055555555556in" height="2.892361111111111in"}

{width="5.768055555555556in" height="0.6701388888888888in"}

如果某一运算是等幂的，则该运算的运算表的主对角线上的每个元素都与所在行（列）的头元素相等

{width="5.768055555555556in" height="2.703472222222222in"}

{width="5.768055555555556in" height="0.6722222222222223in"}

幺元唯一性

幺元==单位元

{width="5.768055555555556in" height="1.917361111111111in"}

上边这个根据运算表判断幺元挺有用的

{width="5.768055555555556in" height="2.061111111111111in"}{width="5.768055555555556in" height="0.7006944444444444in"}

零元唯一性

{width="5.768055555555556in" height="1.6097222222222223in"}

上边这个根据运算表判断零元挺有用的

{width="5.768055555555556in" height="0.6361111111111111in"}

幺元零元大部分情况下不相等

{width="5.768055555555556in" height="3.501388888888889in"}

{width="5.768055555555556in" height="2.0104166666666665in"}

逆元不一定唯一

{width="5.768055555555556in" height="1.7777777777777777in"}

逆元唯一的条件

{width="5.768055555555556in" height="1.9590277777777778in"}

可以尝试理解记忆

{width="5.768055555555556in" height="3.4256944444444444in"}

{width="5.768055555555556in" height="2.8777777777777778in"}

{width="5.768055555555556in" height="0.7513888888888889in"}

（显而易见）

6.3 同态与同构

6.3.1 同态

此处给出书上和PPT上的两种表述方式，可以自行斟酌理解

{width="6.420684601924759in" height="1.335774278215223in"}

运算的像等于像的运算

{width="5.768055555555556in" height="2.0208333333333335in"}

{width="5.768055555555556in" height="0.475in"}

{width="5.768055555555556in" height="3.459722222222222in"}

（对于多个运算的代数系统的同态定义）

{width="6.834588801399825in" height="1.4584394138232721in"}

（自同态的定义，其实就是存在一个由自身映射到自身的函数）

以下是书中的两个同态的性质

{width="6.103392388451444in" height="0.5806867891513561in"}

同态的一个特别重要的属性是幺元保持性，即如果幺元存在，则它也会通过同态映射为另一个代数系统中的幺元（两个幺元不一定相等）

{width="5.768055555555556in" height="0.6805555555555556in"}

（ R(f)为f的值域，显而易见的定理 ）

同态的分类

{width="6.609798775153106in" height="1.3377909011373579in"}

注意同态像的定义

满同态的性质

{width="5.768055555555556in" height="3.7118055555555554in"}

{width="5.768055555555556in" height="3.7083333333333335in"}

6.3.2 同构

{width="5.768055555555556in" height="2.3027777777777776in"}

大白话：同态映射为双射的同态即为同构

满足同构的两个代数系统，一个系统的运算性质与规律可以完全迁移到另一个代数系统中。

在他们的运算表中，除了元素和运算的标记不同外，其他全部相同。

{width="6.516118766404199in" height="0.4456003937007874in"}

等价关系：关系满足自反 对称 可传递

{width="5.768055555555556in" height="1.7569444444444444in"}

6.4 同余关系

此处先普及一下取模运算的一些性质：

{width="5.5389523184601925in" height="4.38376968503937in"}

此处链接

{width="5.768055555555556in" height="2.3430555555555554in"}

大白话理解代换性质：从两类中分别任意取出一个元素进行运算，运算结果一定都属于同一类

如果一个代数结构中有多个运算，则需要考察等价关系对于所有这些运算是否都有代换性质

{width="5.768055555555556in" height="2.5861111111111112in"}

证明如下（课堂笔记有些粗糙，见谅）：

{width="4.685631014873141in" height="6.082403762029746in"}

6.5 商代数

{width="5.768055555555556in" height="2.4451388888888888in"}

如果你不知道商集是什么（取自离散1中的ppt）：

{width="5.768055555555556in" height="2.729617235345582in"}

此处还有ChatGPT3.5版本：

{width="5.768055555555556in" height="2.942361111111111in"}

这是我自己找的例子：

{width="5.768055555555556in" height="2.401388888888889in"}

{width="5.768055555555556in" height="2.8506944444444446in"}

不要问笔者自然同态映射到底是什么，我也不知道

{width="5.768055555555556in" height="3.6381944444444443in"}

一个神奇的定理

6.6 积代数

{width="5.768055555555556in" height="2.790277777777778in"}

两个代数结构的积代数，与两个因子代数是同一类型的

是用因子代数中的相应运算定义了积代数中的运算

积代数的性质：

{width="6.674689413823272in" height="2.134358048993876in"}

6.7 课件中的总结：

{width="5.768055555555556in" height="3.6in"}

{width="5.768055555555556in" height="3.553472222222222in"}

{width="5.768055555555556in" height="3.3381944444444445in"}

{width="5.768055555555556in" height="2.5708333333333333in"}

{width="5.768055555555556in" height="2.7305555555555556in"}

{width="5.768055555555556in" height="3.2625in"}

{width="5.768055555555556in" height="3.845138888888889in"}

{width="5.768055555555556in" height="1.4305555555555556in"}

{width="5.768055555555556in" height="3.5701388888888888in"}{width="5.768055555555556in" height="1.4729166666666667in"}

{width="5.768055555555556in" height="1.0in"}

{width="5.768055555555556in" height="3.2006944444444443in"}

{width="5.768055555555556in" height="2.5506944444444444in"}

{width="5.768055555555556in" height="1.78125in"}

{width="5.768055555555556in" height="3.8472222222222223in"}

第七章 群与环

7.1 半群

7.1.1 半群

{width="5.768055555555556in" height="0.7784722222222222in"}

{width="5.768055555555556in" height="1.082638888888889in"}

独异点也叫拟群或者含幺半群

{width="5.768055555555556in" height="1.2083333333333333in"}

大白话：具有结合律的代数系统为半群 具有幺元的半群为独异点

好像没什么用的定理）

{width="5.768055555555556in" height="1.1111111111111112in"}

{width="5.768055555555556in" height="2.897222222222222in"}

{width="5.768055555555556in" height="0.8097222222222222in"}

注意区分生成集和生成半群 （不过好像还没见过题）

{width="5.768055555555556in" height="2.53125in"}

（可以类比代数系统，值得注意的是子半群也满足结合律）

{width="5.768055555555556in" height="2.3965277777777776in"}

{width="5.768055555555556in" height="0.7597222222222222in"}

{width="6.760833333333333in" height="1.1721161417322834in"}

{width="6.408173665791776in" height="4.210137795275591in"}

以下是独异点的一些特性：

{width="5.768055555555556in" height="0.6104166666666667in"}

{width="5.768055555555556in" height="1.5368055555555555in"}

7.1.2 半群和独异点的同态与同构（此部分书中没有，是课件上的）

{width="5.768055555555556in" height="2.8041666666666667in"}

{width="5.768055555555556in" height="2.803472222222222in"}

{width="5.768055555555556in" height="1.3444444444444446in"}

（完全等价于代数系统）

{width="5.768055555555556in" height="1.5416666666666667in"}

{width="5.768055555555556in" height="2.984722222222222in"}

（可传递性？？？）

最抽象的一集（感觉不是很会考）

{width="5.768055555555556in" height="1.1083333333333334in"}

{width="5.768055555555556in" height="3.78125in"}

知识点补充：

恒等映射是一个返回相同值的函数，该值用作其参数。也称为恒等关系或恒等转换。如果f是一个函数，则对于x的所有值，参数x的恒等关系表示为f（x）= x

网页链接

入射也就是单射，f:A->B，在f的作用下A中每一个元素在B中存在唯一一个元素和它对应。

{width="5.768055555555556in" height="3.317361111111111in"}

{width="5.768055555555556in" height="1.5277777777777777in"}

7.2 群

7.2.1 群的概念

{width="4.903029308836396in" height="1.4861876640419946in"}

{width="4.43078302712161in" height="0.8333759842519685in"}

{width="5.111373578302712in" height="2.465404636920385in"}

{width="5.243324584426946in" height="3.2640562117235348in"}

7.2.2 群的性质

{width="4.771078302712161in" height="2.8751476377952754in"}

判断是否是群，优先判断这四点

{width="5.069704724409449in" height="3.3960083114610673in"}

{width="4.710820209973753in" height="2.1983836395450567in"}

{width="6.102156605424322in" height="1.359034339457568in"}

{width="5.9456627296587925in" height="1.9568000874890639in"}

{width="4.903029308836396in" height="3.743248031496063in"}

{width="6.237864173228346in" height="1.20461832895888in"}

|为整除符号，r|k即为r可以整除k

{width="6.558767497812774in" height="2.0312248468941383in"}

{width="6.4783103674540685in" height="1.4908245844269465in"}

{width="6.684914698162729in" height="1.3612248468941381in"}

7.3 子群与群的陪集分解

7.3.1 子群

{width="4.9655325896762905in" height="1.854261811023622in"}

群与子群具有相同的幺元（这里和代数系统不一样）

{width="6.70832239720035in" height="0.8104669728783902in"}

注意平凡子群的定义

7.3.2 子群的判定

{width="6.388935914260718in" height="1.5808639545056868in"}

{width="6.495360892388452in" height="1.256266404199475in"}

{width="6.443417541557305in" height="1.0137653105861768in"}

（注意判定定理三中H为有穷子集）

7.3.3 子群的性质

{width="5.229435695538058in" height="0.6458661417322835in"}

{width="5.166932414698163in" height="0.826431539807524in"}

{width="5.4030555555555555in" height="0.5694739720034996in"}

{width="5.501980533683289in" height="1.0710290901137358in"}

{width="4.826095800524935in" height="3.5982556867891513in"}

{width="3.554374453193351in" height="2.212657480314961in"}

7.3.4 子群的陪集分解

{width="5.768055555555556in" height="2.683333333333333in"}

最最抽象的一集：

{width="5.444668635170603in" height="2.0032392825896763in"}

再强调一遍------等价关系=自反 对称 可传递

{width="5.262106299212598in" height="2.8192115048118986in"}

我觉得我们需要一个例题来缓解一下，为什么可以划分成等价类：

{width="5.768055555555556in" height="3.328472222222222in"}

{width="5.768055555555556in" height="1.6291666666666667in"}

{width="5.7909361329833775in" height="0.99624343832021in"}

{width="5.780060148731408in" height="1.1408311461067366in"}

{width="5.768055555555556in" height="1.288888888888889in"}

{width="5.778840769903762in" height="0.9325087489063867in"}

（等势即集合中元素个数（集合的基）相同）

一个总结：

{width="5.768055555555556in" height="3.832638888888889in"}

7.3.5 拉格朗日定理

H的左陪集的数目称为H在G内的"指数"，并标记为【G:H】

{width="5.768055555555556in" height="1.4340277777777777in"}

群的阶即群中元素的个数

以下是拉格朗日定理的推论：

{width="5.768055555555556in" height="0.5979166666666667in"}

{width="5.768055555555556in" height="0.8645833333333334in"}

7.4 循环群与置换群

7.4.0 置换 对称 变换

{width="5.768055555555556in" height="2.863888888888889in"}

集合到自身的映射称为变换

（即满足成群的条件------封闭 结合 幺元 逆元）

{width="5.768055555555556in" height="2.8131944444444446in"}

{width="5.768055555555556in" height="1.3055555555555556in"}

7.4.1 循环群

{width="5.768055555555556in" height="1.0375in"}

{width="5.768055555555556in" height="0.7645833333333333in"}

{width="5.768055555555556in" height="2.8465277777777778in"}

知识点回顾，元素的阶

{width="5.768055555555556in" height="1.3708333333333333in"}

{width="5.768055555555556in" height="1.2833333333333334in"}

知识点回顾：欧拉函数（φ函数）与互素（互质）

{width="5.768055555555556in" height="1.4569444444444444in"}

互质是公约数只有1的两个整数，叫做互质整数

{width="5.768055555555556in" height="1.7402777777777778in"}

对于定理7.21中性质（3）的一个例子

{width="5.768055555555556in" height="3.525in"}

7.4.2 置换群

{width="5.768055555555556in" height="2.982638888888889in"}

{width="5.768055555555556in" height="2.525in"}

一一变换即满足双射的变换（也叫置换）

7.5 群的同态与同构

{width="5.768055555555556in" height="1.8909722222222223in"}

{width="5.768055555555556in" height="1.5173611111111112in"}

{width="5.768055555555556in" height="0.5381944444444444in"}

等价于代数系统的同态

一个性质

{width="5.768055555555556in" height="0.6388888888888888in"}

7.6 群与环

7.6.1 环的概念与性质

{width="5.768055555555556in" height="1.88125in"}

{width="5.768055555555556in" height="1.0444444444444445in"}

{width="5.768055555555556in" height="2.1798611111111112in"}

对于有零因子环的定义：

存在a,b∈R，ab=0→a≠0∧b≠0

对于无零因子环的一个解释：群中的0没有因数，即没有两个非零数相乘等于零

{width="5.768055555555556in" height="3.14375in"}

{width="5.768055555555556in" height="2.576388888888889in"}

7.6.2 域的概念

{width="5.768055555555556in" height="1.3111111111111111in"}

即在可交换环的基础上，满足乘法群除零元外都有逆元

包含有限个元素的域被称为有限域

{width="5.768055555555556in" height="0.5604166666666667in"}

{width="5.768055555555556in" height="0.9722222222222222in"}

7.7 应用自行了解，此处不赘述

第八章 格与布尔代数

知识回顾

{width="5.222490157480315in" height="2.368176946631671in"}

{width="5.486393263342082in" height="3.3821183289588803in"}

{width="5.625288713910761in" height="1.3195122484689414in"}

{width="5.4169455380577425in" height="2.1181649168853895in"}

{width="5.694737532808399in" height="4.132156605424322in"}{width="5.7086264216972875in" height="4.264107611548557in"}{width="5.5558409886264215in" height="1.9306550743657043in"}{width="5.528062117235345in" height="2.451514654418198in"}

也称为上确界与下确界

{width="4.826095800524935in" height="3.5982556867891513in"}

8.1 格的定义与性质

{width="5.768055555555556in" height="0.5881944444444445in"}

{width="5.768055555555556in" height="2.321527777777778in"}

{width="5.222490157480315in" height="0.5069706911636046in"}

（等价于模电与命题）

{width="5.768055555555556in" height="3.0805555555555557in"}

{width="5.768055555555556in" height="1.2159722222222222in"}

（等幂律可以由吸收律推出）

{width="5.768055555555556in" height="1.9902777777777778in"}

{width="5.430834426946632in" height="0.7430938320209973in"}

{width="5.768055555555556in" height="0.6909722222222222in"}

{width="5.768055555555556in" height="3.095833333333333in"}

{width="4.986367016622922in" height="0.7778182414698163in"}

（分配律不一定满足）

8.2 分配格 有补格与布尔代数

{width="5.768055555555556in" height="1.9840277777777777in"}

（满足分配律的格，两个式子证一个就行，可以互推）

{width="5.768055555555556in" height="3.020138888888889in"}

{width="5.768055555555556in" height="3.401388888888889in"}

一道小小的例题，来进行加固

{width="5.768055555555556in" height="3.0347222222222223in"}

8.3 应用自行了解，此处不赘述

第九章 图的基本概念及其矩阵表示

9.1 图的基本概念

9.1.1 图的定义及相关概念

{width="5.768055555555556in" height="4.095833333333333in"}

{width="5.768055555555556in" height="3.964583333333333in"}

{width="5.768055555555556in" height="3.3270833333333334in"}

{width="5.768055555555556in" height="3.797222222222222in"}

{width="5.768055555555556in" height="4.616666666666666in"}

{width="5.768055555555556in" height="3.951388888888889in"}

{width="5.768055555555556in" height="3.3493055555555555in"}

9.1.2 结点的度

{width="5.768055555555556in" height="3.845138888888889in"}

握手定理：

{width="5.768055555555556in" height="0.6152777777777778in"}

{width="5.768055555555556in" height="1.0180555555555555in"}

{width="5.768055555555556in" height="1.2180555555555554in"}

{width="5.768055555555556in" height="0.8805555555555555in"}

{width="5.768055555555556in" height="0.5993055555555555in"}{width="5.4030555555555555in" height="0.6180872703412074in"}

{width="5.768055555555556in" height="2.1756944444444444in"}

{width="5.768055555555556in" height="2.89375in"}

{width="5.768055555555556in" height="3.7131944444444445in"}

{width="5.768055555555556in" height="1.2194444444444446in"}

{width="5.768055555555556in" height="1.4527777777777777in"}

{width="5.768055555555556in" height="0.7368055555555556in"}

N个结点的完全有向图的边数为Cn2的2倍

{width="5.768055555555556in" height="3.490972222222222in"}

9.2 子图和图的运算

9.2.1 子图和补图

{width="5.768055555555556in" height="3.7180555555555554in"}

{width="5.768055555555556in" height="3.390277777777778in"}

导出子图也叫做诱导子图

{width="5.768055555555556in" height="1.6993055555555556in"}

{width="5.768055555555556in" height="2.411111111111111in"}

9.2.2 图的运算

{width="5.768055555555556in" height="2.9027777777777777in"}

{width="5.768055555555556in" height="2.803472222222222in"}

知识回顾（对称差）：

{width="5.768055555555556in" height="1.2513888888888889in"}

{width="5.768055555555556in" height="1.3395833333333333in"}

{width="5.768055555555556in" height="3.1055555555555556in"}

9.3 路径、回路和连通性

9.3.1 路径与回路

{width="5.768055555555556in" height="2.592361111111111in"}

{width="5.768055555555556in" height="3.3444444444444446in"}

圈也叫基本回路

{width="5.768055555555556in" height="2.0444444444444443in"}

{width="5.768055555555556in" height="0.5909722222222222in"}

{width="5.768055555555556in" height="0.38263888888888886in"}

{width="5.768055555555556in" height="2.3291666666666666in"}

如何快速判断有无有向回路

{width="5.768055555555556in" height="1.3680555555555556in"}

{width="5.768055555555556in" height="2.84375in"}

9.3.2 图的连通性

{width="5.768055555555556in" height="1.9243055555555555in"}

{width="5.768055555555556in" height="0.6680555555555555in"}

{width="5.768055555555556in" height="2.761111111111111in"}

{width="5.305827865266842in" height="1.8334273840769904in"}

{width="5.768055555555556in" height="1.6833333333333333in"}

{width="5.768055555555556in" height="1.0263888888888888in"}

平凡图：一阶零图

{width="5.768055555555556in" height="2.4006944444444445in"}

简单来说，连通分支就是把可以互相到达的点与它们的边放在一起形成一个新的子图

{width="5.768055555555556in" height="2.6395833333333334in"}

b是a的基础图

{width="5.768055555555556in" height="3.834722222222222in"}

a是强连通 b是单向连通 c是弱连通

{width="5.768055555555556in" height="3.0236111111111112in"}

简单来说，具有某种性质的最大的子图称为极大子图，根据具有的性质进行命名

{width="5.768055555555556in" height="2.2680555555555557in"}

{width="5.768055555555556in" height="2.8041666666666667in"}

简单有向图：没有平行边和自回路的有向图

{width="5.768055555555556in" height="1.788888888888889in"}

删去后使图不再连通的点叫割点，删去后使图不再连通的边叫割边（桥）在第十章会很有用（大概）

9.3.3 ppt总结版

{width="5.768055555555556in" height="4.0375in"} {width="5.768055555555556in" height="3.4270833333333335in"} {width="5.768055555555556in" height="3.78125in"} {width="5.768055555555556in" height="4.279166666666667in"} {width="5.768055555555556in" height="3.435416666666667in"} {width="5.768055555555556in" height="2.272222222222222in"}

9.4 图的矩阵表示

9.4.1 邻接矩阵

{width="5.768055555555556in" height="3.5840277777777776in"}

简单说，我们把邻接矩阵当做一个二维数组，a[i][j]只有0和1两种值，a[i][j]==1则说明i和j之间有一条边，相应的，如果为0则i和j之间没有边

在有向图的邻接矩阵中，主对角线上的元素为1则说明该点有自回路，如果关于主对角线对称的两个位置均为1则说明这两个点之间互相有边

{width="5.768055555555556in" height="3.395138888888889in"}

{width="4.93080927384077in" height="0.5069706911636046in"} {width="5.768055555555556in" height="1.667361111111111in"}

{width="5.768055555555556in" height="0.7375in"}

{width="5.768055555555556in" height="2.01875in"}

{width="5.768055555555556in" height="1.8055555555555556in"} {width="5.768055555555556in" height="0.9118055555555555in"}

{width="5.768055555555556in" height="0.7958333333333333in"}

{width="5.768055555555556in" height="1.9868055555555555in"} {width="5.768055555555556in" height="1.1263888888888889in"}

{width="5.768055555555556in" height="1.7180555555555554in"} {width="5.768055555555556in" height="0.3736111111111111in"}

{width="5.768055555555556in" height="0.9541666666666667in"}

{width="5.768055555555556in" height="0.6479166666666667in"}

{width="5.768055555555556in" height="1.1534722222222222in"}

总结一下：

A为邻接矩阵，Aij仅代表i和j之间是否有一条边（1为有，0为无）

AT为邻接矩阵的转置，也是补图的邻接矩阵，ATij表示原图中j和i之间是否有边

AATij表示从i和j两点出发，能各自只经过一条边到达的同一个结点个数。也就是i和j两点所共同链接的结点个数

ATAij表示能只经过一条边就到达i和j的结点的个数。也就是能同时链接i和j的结点的个数

Am是邻接矩阵的m次幂，Amij表示从i到j之间距离为m的路径的个数

9.4.2 可达性矩阵

{width="5.768055555555556in" height="1.7416666666666667in"}

{width="5.768055555555556in" height="1.4583333333333333in"}

{width="5.768055555555556in" height="2.1506944444444445in"}

{width="5.768055555555556in" height="1.6875in"}

路径矩阵P的求解需要B(k-1）具体操作为：如果B(k-1）ij不为零则Pij为1，相反如果B(k-1）ij为零则Pij为0

{width="5.768055555555556in" height="2.7805555555555554in"}

矩阵的布尔运算

{width="5.768055555555556in" height="3.2618055555555556in"}

{width="5.768055555555556in" height="4.084722222222222in"}

{width="5.768055555555556in" height="2.7159722222222222in"}

关联矩阵用的很少

{width="5.768055555555556in" height="3.813888888888889in"}

{width="5.768055555555556in" height="4.129166666666666in"}

设G是n阶连通无环的有向图，其关联矩阵是M，M的秩是n-1

第十章 几种特殊图

10.1 欧拉图

相关定义

{width="6.606375765529309in" height="1.0801181102362205in"}

知识点回顾：平凡图------一阶零图（一个孤立的点）

{width="6.710237314085739in" height="1.1568821084864391in"}

闭路径又称回路

也就是说，有欧拉回路的图才是欧拉图

相关定理

{width="5.768055555555556in" height="0.6006944444444444in"}

{width="5.768055555555556in" height="1.4090277777777778in"}

判断欧拉回路

{width="5.768055555555556in" height="0.9159722222222222in"}

无向图的欧拉路径

{width="5.768055555555556in" height="1.3319444444444444in"}

有向图的欧拉路径

{width="5.768055555555556in" height="0.6756944444444445in"}

如何寻找无向图中的欧拉回路：

{width="5.083594706911636in" height="3.6251859142607175in"}

相关问题

一笔画问题（如何不重复的情况下一笔画完图形）
中国邮路问题（没讲，在书上10.6节，有兴趣自行了解）

10.2 哈密尔顿图

相关定义

{width="5.034981408573929in" height="1.4167399387576554in"}

知识点回顾------完全图：n阶完全图中每个节点的度均为n-1（有向图中每个节点的出度为n-1）即任意两个顶点之间都有边

有哈密尔顿回路的图才是哈密尔顿图

哈密尔顿图的充要条件还未找到，也就是说目前没有有效解决哈密尔顿图的算法

与欧拉图类比：

欧拉图是边不重复

哈密尔顿图是点不重复（点都不重复了，边更不可能重复了）

相关定理

{width="5.768055555555556in" height="0.7194444444444444in"}

知识点回顾------分支数ω：也称连通分支数，即相互连通的点归到一个点集，点集的数量就是分支数

知识点回顾------G-S：即图G中抛去点集S中的点以及它们所连接的边后所剩下的子图

这是哈密尔顿图的必要条件，可以用来判断某些图是不是哈密尔顿图（满足了也未必是哈密尔顿图）

{width="5.768055555555556in" height="2.1in"}

{width="5.768055555555556in" height="1.1604166666666667in"}

{width="5.768055555555556in" height="0.9673611111111111in"}

（书上的表述其实和ppt上的大差不差）

这是哈密尔顿图的充分条件，也就是说可以用它来判断是不是哈密尔顿图（n较大时不好用&&不满足也可能是哈密尔顿图）

10.3 二部图

相关定义

{width="5.201655730533683in" height="1.2639534120734908in"}

二部图（二分图）的定义------可以看成两个点集与它们之间的边，同一点集内不含边

{width="4.937753718285214in" height="0.8681003937007874in"}{width="4.889140419947506in" height="0.5208595800524934in"}

完全二部图的定义

{width="5.104429133858268in" height="3.312670603674541in"}

{width="5.09053915135608in" height="0.9583825459317585in"}

对于二部图来说，匹配就是两个点集中各自任选一个点进行连线，且这两个点不能再有其他连线了

对于二部图G(n,m) n<m 来说，最大匹配就是让n中的每个点都尽可能被m中的一个点连接

对于二部图G(n,m) n<m 来说，完美匹配就是让n中的每个点都被m中的一个点连接

相关定理

{width="2.3473425196850393in" height="1.8959306649168854in"}

{width="5.000256999125109in" height="0.6250317147856518in"}

如何判断二部图

{width="5.201655730533683in" height="1.1042235345581801in"}

结点数较大时不好用

{width="4.986367016622922in" height="1.1111679790026248in"}

芝士充分条件

相关问题

排课问题

分配名额

等等...

10.4 平面图

相关定义

{width="5.768055555555556in" height="0.9930555555555556in"}

非常玄学的定义（小声bb）

{width="5.768055555555556in" height="4.006944444444445in"}

特殊的同构

{width="5.768055555555556in" height="3.1194444444444445in"}

非常抽象的定义。但可以通过观察法发现它是多边形图------如果一个图最外边是一个基本回路，其他的边都在这个大回路中且不想交，则它是多边形图

{width="5.768055555555556in" height="3.4208333333333334in"}

{width="5.768055555555556in" height="4.20625in"}

{width="5.750295275590551in" height="0.7569838145231846in"}

{width="5.618344269466316in" height="0.7639282589676291in"}

{width="5.768055555555556in" height="1.2090277777777778in"}

其实就是把原图中的面替换成点，面与面之间的相邻关系用点与点之间的边来代替

{width="5.768055555555556in" height="1.9861111111111112in"}

{width="5.768055555555556in" height="2.272222222222222in"}

着色问题的定义

{width="5.768055555555556in" height="0.6875in"}

相关定理

{width="5.768055555555556in" height="2.609027777777778in"}

（其实是如何判断平面图）

{width="5.768055555555556in" height="3.2152777777777777in"}

a是K3,3（两子集为3,3的完全二部图） B是K5（五阶完全图）

相应的大于a和b的图（点多 边多）也不是平面图

{width="5.768055555555556in" height="0.96875in"}

平面图中非常重要的公式

{width="5.083594706911636in" height="0.6597561242344707in"}

{width="5.768055555555556in" height="2.8652777777777776in"}

{width="5.768055555555556in" height="3.723611111111111in"}

相关问题

平面图的着色和它的应用

{width="5.768055555555556in" height="2.4930555555555554in"}{width="5.768055555555556in" height="3.48125in"}

第十一章 树

11.1 树

相关定义

{width="5.768055555555556in" height="3.265277777777778in"}

{width="5.768055555555556in" height="1.2493055555555554in"}

{width="5.768055555555556in" height="0.6034722222222222in"}

{width="5.768055555555556in" height="4.017361111111111in"}

高度也称为深度（才不是为了对应深搜）

{width="5.768055555555556in" height="0.7631944444444444in"}

{width="5.768055555555556in" height="0.6923611111111111in"}

相关定理

{width="6.387740594925634in" height="2.2133300524934385in"}

{width="5.768055555555556in" height="1.054861111111111in"}

{width="5.768055555555556in" height="0.6472222222222223in"}

11.2 生成树

相关定义

{width="6.654856736657917in" height="0.8800503062117235in"}

即在原图G中删掉一些边，使其变成树，则该树为生成树

{width="5.768055555555556in" height="2.4854166666666666in"}

相关定理

{width="5.768055555555556in" height="3.814583333333333in"}

{width="5.215545713035871in" height="1.854261811023622in"}

如何求最小生成树

11.3 m叉树

相关定义

{width="5.768055555555556in" height="2.2020833333333334in"}

{width="3.743248031496063in" height="0.48613626421697287in"}

{width="5.768055555555556in" height="1.863888888888889in"}

{width="5.768055555555556in" height="1.5333333333333334in"}

相关定理

{width="5.768055555555556in" height="0.8347222222222223in"}

哈哈！就一条！

相关问题

{width="5.768055555555556in" height="1.1458333333333333in"}

{width="5.768055555555556in" height="3.5479166666666666in"}

{width="5.768055555555556in" height="0.73125in"}

{width="5.768055555555556in" height="4.363888888888889in"}

{width="5.768055555555556in" height="4.0625in"}

11.4 有序树

相关定义

{width="5.768055555555556in" height="2.798611111111111in"}

{width="5.768055555555556in" height="0.7256944444444444in"}

{width="5.768055555555556in" height="3.167361111111111in"}

前缀编码的定义

{width="5.768055555555556in" height="3.884027777777778in"}

其实就是二叉树

相关问题

{width="5.768055555555556in" height="3.692361111111111in"}

Python里的运算图）

{width="5.768055555555556in" height="4.166666666666667in"}

11.5 二叉树的遍历

相关定义

{width="4.125212160979878in" height="4.423838582677165in"}

周游也就是遍历

给个例子

{width="5.768055555555556in" height="3.240972222222222in"}

相关问题

{width="5.768055555555556in" height="4.0368055555555555in"}

{width="5.768055555555556in" height="4.188194444444444in"}

11.6 搜索树

{width="5.768055555555556in" height="4.019444444444445in"}

{width="5.768055555555556in" height="3.7756944444444445in"}

这里讲的搜索树其实就是树的搜索

最最最常用的搜索------深度优先搜索（DFS）

{width="5.768055555555556in" height="3.451388888888889in"}

举例

{width="5.768055555555556in" height="4.154861111111111in"}

{width="5.768055555555556in" height="3.509027777777778in"}