第十一课：序关系、函数、图论¶
Page 2-11 — 序关系复习¶
（与第十课后半部分内容重叠）
哈斯图例子： - ⟨{2,3,6,12,24,36}, |⟩：整除关系的哈斯图 - ⟨𝜌{a,b,c}, ⊆⟩：幂集上的包含关系的哈斯图
有序集元素排序总结： - 最小元/最大元：存在则唯一 - 极小元/极大元：有限集恒存在，未必唯一 - 链：任意两元素可比；反链：任意两元素不可比 - 半序关系 = 反自反+反对称+传递（严格序）
Page 12-14 — 函数的定义¶
- 函数f:X→Y ⊆ X×Y，满足： 1. 定义域全覆盖：dom(f)=X（每个x都有对应y） 2. 单值性：⟨x,y⟩∈f且⟨x,y'⟩∈f ⇒ y=y'
- 函数也叫映射或变换
- 函数是特殊的关系
例子： - 恒等函数Iₐ：相等关系Eₐ - f:N→N, y=2x：函数 - 整除关系不是函数（2|4,2|8，不满足单值性） - 空关系∅：X≠∅时不是函数，X=∅时是空函数 - ADD:N×N→N, y=x₁+x₂：二元函数
Page 14 — 函数的表示方法¶
- 列表法：列出所有序偶
- 图表法：平面直角坐标系
- 解析法：算术表达式
- 递归定义：用自身定义（如阶乘）
Page 17-18 — 函数的类型 ⭐¶
满射（surjection）¶
- ran(f)=Y（值域=陪域）
- 每个y∈Y都有至少一个x使f(x)=y
- "全覆盖"
单射（injection）¶
- x₁≠x₂ ⇒ f(x₁)≠f(x₂)
- 不同的x对应不同的y
- "一对一"
双射（bijection）¶
- 既单射又满射
- "一一对应"
💡 人话： - 满射：每一个y都能被某个x映射到，没有"漏"的元素 - 单射：不同的x不会映射到同一个y，没有"撞车" - 双射：完美的配对，不多不少刚刚好
Page 19-20 — 函数合成¶
- (g∘f)(x) = g(f(x))
- 合成保持单射和满射：
- 若f,g都单射，则g∘f也单射
- 若f,g都满射，则g∘f也满射
- g∘f单射 ⇒ f单射（g不一定单射）
- g∘f满射 ⇒ g满射（f不一定满射）
Page 24-25 — 逆函数¶
- 作为关系，函数可以求逆R⁻¹
- 但只有双射函数才有逆函数
- 非单射：f⁻¹不满足单值性
- 非满射：dom(f⁻¹)≠Y
- 双射函数f的逆f⁻¹也是双射函数
Page 26-27 — 逆函数性质与左右逆¶
- (f⁻¹)⁻¹ = f
- f⁻¹∘f = Eₓ, f∘f⁻¹ = Eʏ
- (g∘f)⁻¹ = f⁻¹∘g⁻¹
- 左逆：g∘f=Eₓ ⟺ f是单射
- 右逆：f∘g=Eʏ ⟺ f是满射
- f可逆 ⟺ 既有左逆又有右逆且相等 ⟺ f是双射
💡 人话：单射可以找到左逆（从像还原到源），满射可以找到右逆（对每个y选一个x）。双射就是两个方向都能还原。
Page 28-33 — 图的基本概念¶
- 图 G=⟨V,E⟩：结点集V + 边集E（E是多重集合）
- 1736年欧拉：柯尼斯堡七桥问题 → 图论创立
边的类型： - 有向边：有序对⟨起点,终点⟩ - 无向边：两元素多重集{端点1,端点2} - 无向边可以有环（loop）
图的分类： | 类型 | 特征 | |------|------| | 简单图 | 无环、无重边的无向图 | | 完全图Kₙ | 任意两不同结点间都有边 | | 重图 | 有平行边（重数>1） | | 零图 | 仅有孤立结点（E=∅） | | 赋权图 | 边或结点有权重 |
Page 34-36 — 赋权图¶
- 普通图研究拓扑关系（邻接、连通、通路）
- 赋权图附加数量关系（距离、成本、代价）
- GIS应用的基础
Page 37-39 — 结点的度 ⭐¶
- 度d(v)：关联v的边的数目
- 有向图：出度d⁺(v) + 入度d⁻(v)
- 握手定理：所有顶点的度之和 = 2×边数（必为偶数！）
- 有向图中出度之和 = 入度之和
- 奇数度顶点必为偶数个
- 正则图：所有顶点度数相同，k-正则图
- Kₙ是(n-1)-正则图