视频教程链接：
https://www.bilibili.com/video/BV13tHfzREnV/?p=2&spm_id_from=333.976.top_right_bar_window_history.content.click&vd_source=98031030bb7928a33e1b19aa75c4a7aa

图解法求解线性规划问题 Solving LPs with the graphical method

线性规划的基本性质

1. 若某一线性规划问题存在唯一最优解，则该最优解必在可行域的某个顶点处；
2. 若某一线性规划问题存在多个最优解，则其中至少有一个最优解在可行域的顶点处；
3. 若某一线性规划问题存在多个最优解，且已找到一个最优顶点，那么另一个最优解必为该顶点的相邻顶点，且两个最优顶点连线上的所有点均为最优解

例题

• 某工厂生产两种产品（A 和 B），单位产品的利润贡献分别为 9 英镑（产品 A）和 12 英镑（产品 B），即 \(c_1 = 9\)，\(c_2 = 12\)。
• 每种单位产品的生产均需消耗一定的机器工时和钻孔工时，具体工时消耗如下表所示：

产品	机器工时	钻孔工时
A	4	2
B	2	5

每周机器工时的最大可用量为 80 小时，钻孔工时的最大可用量为 120 小时。
决策问题：下周应生产两种产品各多少单位，才能实现利润最大化？

若有多个点的取值都为最大值，则存在多个最优解，例如：

数学规划（最优化）相关专业术语补充 terminology for mathematical programming (optimisation)

• 1. 不可行问题Infeasible problem： 不存在可行解，即约束条件之间相互矛盾。
• 2. 无界问题Unbounded problem： 目标函数在可行域内可以无限优化（最大化问题的最优值为 \(+\infty\)，最小化问题的最优值为 \(-\infty\)），即约束条件的限制作用不足。
• 3. 可解问题Solvable problem： 既非不可行问题，也非无界问题的规划问题。
• 4. 有效约束/无效约束 Active/inactive constraint： 这个约束对可行域的边界真的起作用，删掉它会改变可行域
  • 形式化定义：对于第 \(i\) 个约束 \(a_{i1}x_1 + \dots + a_{in}x_n \le b_i\)，设 \((x_1^*,\dots,x_n^*)\) 为问题的最优解。若 \[ a_{i1}x_1^* + \dots + a_{in}x_n^* = b_i \] 则该约束为**有效约束**；若 \[ a_{i1}x_1^* + \dots + a_{in}x_n^* < b_i \] 则该约束为无效约束。
• 5. 紧约束Binding constraint: 设约束是\(g(x) \le b\) 如果在某个点上刚好取等号： \(g(x) = b\) 那这个约束就叫紧约束
  • 通俗来说：这个约束在当前点“绷紧了”，没有松弛量了
  • 紧约束一定是有效约束，如果一个约束在你关心的点上已经取等号了，说明这个点正好压在它的边界上。那它显然不是完全没用的约束，至少在这个点它确实起了限制作用。
  • 多数情况下（非全部），有效约束也是紧约束，一个约束可能对整个可行域是有用的，但在你当前这个点上并没有刚好取等号

• 6. 松弛变量：把“≤”约束改写成等式时，加上的非负变量
• 7. 剩余变量：把“≥”约束改写成等式时，减去的非负变量。

第 2 讲：单纯形算法 Simplex algorithm

• 单纯形表 (simple tableau) 是为单纯形算法而设计的一种计算表，其功能类似于方程组的增广矩阵，易于进行基变换运算
• 它不是连续优化里“梯度下降/最速下降”那种概念。因为线性规划的可行域是一个多面体，单纯形法是在顶点和顶点之间跳，不是在平滑曲面上顺着梯度滑

相关定义

• 标准型（所有约束为等式、所有变量非负）：

• 标准型中：
  • 若有 n 个变量、m 个方程，且 n>m
  • 则有 n−m 个自由度
  • 可以令 n−m 个变量为 0，再解出剩下的 m 个变量。
• 非基本变量 (non-basic variables)：被设为 0 的变量
• 基本变量 (basic variables)：其他的变量（通过联立方程求出的变量）
• 基本可行解 (basic feasible solution, BFS)：求出的基本变量都满足非负

注意：

• 每个变量不是基本变量，就是非基本变量
• 基本变量个数 = 等式约束的数量

单纯形算法的几何与代数结合思路

• 单纯形算法的每一次迭代，都会得到一个基可行解
• 若模型存在可行解，单纯形算法通常以原点对应的顶点为初始迭代点，即令原决策变量为 0，松弛变量的取值等于约束条件的右端项
• 若当前基可行解并非最优解，算法会迭代至相邻顶点对应的另一个基可行解
• 迭代的本质是换基：一个非基变量转为基变量，同时一个基变量转为非基变量

初始化：初始基可行解为(0,0,80,120)，此时目标函数值Z=0。该解并非最优解，因为提高x1​或x2​的取值均可提升目标函数值。

核心要求：每个等式约束中，需有且仅有一个系数为 1 的基变量，后续所有基可行解的求解均需满足这一要求。

步骤

单纯形算法总结（一）

1. 加入松弛变量，将所有不等式约束转化为等式约束，构建初始单纯形表(基本变量个数 = 等式约束的数量)
   • 此时判断是否根据是否有 = / 大于号的约束是否使用2phase 方法
   • 否则需要先构造辅助问题，再用非人工变量替换人工变量的优化问题
2. 若目标函数行的所有系数均为正数，已得到最优解；若未满足，执行以下步骤；
3. 选取目标函数行中系数最负的变量为入基变量（若多个变量系数同为最负，任选其一即可）；
4. 将约束条件的RHS（右端项）与入基变量列对应的正系数做比值，选取比值最小的行确定主元，该行对应的基变量为出基变量。
   • 正的意思是最小比值检验只在入基列正元素中做。负的、零的都不参与。而不是算后取绝对值
5. 执行主元变换（初等行变换），使主元变为 1，且主元列的其余元素均为 0；
6. 除目标函数行外，其余每一行需有且仅有一个系数为 1 的基变量；
7. 目标函数行中，所有基变量的系数均为 0；
8. 重复上述迭代步骤，直至满足最优性检验条件：目标函数行的所有系数（除RHS）均 ≥0。
9. 结果：基变量的值即为RHS对应的值，非基变量的值为0，最有值为Z对应的RHS

• 选入变量时，表里选“最负的”的原理：本质上等价于原目标函数里选“正系数最大的”。

比例检验原理

谁最先被压到 0，谁就成为“卡住你”的那个约束，那个变量就必须出基。

示例1:

• 示例2

第三讲：单纯形法的特殊情况 special cases

退化现象 degenerate

• 两个（或以上）非基变量在最终行中拥有相同的最小负系数Two (or more) non-basic variables have the same “most negative” coefficient in the last row
  • 可任选其中一个作为进基变量，最终仍能求得最优解
• 确定进基变量后，进行最小比值检验时，两个（或以上）基变量得出相同的最小比值
  • 理论上可任选其一，但可能引发一些问题：退化现象（但一般不需要考虑）

原理解释

把单纯形法想成：你在一个房间的角点之间移动，每走一步都想让目标函数更优

• 进基变量：表示你准备沿着某个方向往前走
• 出基变量：表示谁先“顶到墙”，所以你最多只能走这么远
• 正常情况：只有一个变量先顶到墙。那你走了一步，到了一个新角点，事情很清楚
• 平局情况：有两个变量同时顶到墙。这说明你走到的位置，正好卡在一个“更尖的角”上，多个约束同时紧绷。这时如果你随便挑一个出基，数学上可以继续，但可能出现：基变了，但是你的人其实没挪地方，于是这一轮枢轴变换之后，目标函数值可能一点没改善，陷入死循环

无界问题

确定进基变量后，进行出基变量的最小比值检验时，进基变量所在列的所有系数均≤0

多重最优解

判定：最终行中有一个（或以上）非基变量的系数为 0

• 增大该非基变量的取值并将其选为进基变量时，目标函数值不会发生变化。
• 对该非基变量执行一次迭代操作，可得到另一个基本可行最优解。
• 若一个线性规划问题存在多重最优解，则至少存在两个基本可行最优解，其余所有最优解均可表示为这两个基本可行最优解的凸组合。

• 为什么 λ 必须在 [0, 1]? 因为这是 凸组合的定义。 对于两个点 \(A\) 和 \(B\)，凸组合是： \[ \lambda A + (1-\lambda) B \] 其中必须满足： \[ 0 \le \lambda \le 1 \] 这样生成的点才在 \(A\) 和 \(B\) 之间的线段上。

Simplex Two-Phase method

定义：两相法是在没有明显的初始基本可行解（BFS）时解决线性规划问题的系统技术

判断方法：出现 = 或 \ge 约束，通常就要考虑 two-phase

• 约束与≥不平等（没有自然松弛变量）
• 平等约束（完全没有松弛变量）
• 负右侧值
• 混合约束类型使初始化变得复杂

步骤：

Phase I（找初始 BFS）：

• 目的：不优化原目标函数，先判断原问题是否存在可行解。
• 方法：引入人工变量 w1​,w2​,…,wm​（注意不是松弛/剩余变量)
  构造辅助问题：minW=w1​+w2​+⋯+wm​

• 结果判断：
  • 若 Wmin​=0：所有人造变量可消为 0，原问题存在可行解。
  • 若 Wmin​>0：至少一个人造变量无法消去，原问题无可行解。

Phase II：

• 步骤：删除人工变量，恢复原目标函数，继续用单纯形法求解。
• 目的：在已找到的可行起点上，优化原问题

• 例1：

同理第二题：

第3讲 – Optimisation modelling – QP and IP

• 到目前为止，我们只处理过线性规划模型(LP)。这类模型通常是利润最大化或成本最小化问题
• 它们是最容易求解的优化模型
• 单纯形法是首个被提出的优化模型求解方法 ——仅适用于线性规划 Simplex algorithm was the first proposed method for solving optimisation models – applicable only to LP’s
• 它并非线性规划的唯一求解方法；后续发展的内点法在软件包中同样（甚至更）常用
  It is not the only solution method for LP’s; the Interior Point Method, developed later on, is also (or more!) popular / implemented in software packages

Beyond LP’s 超越线性规划

• 凸优化问题可被标准求解器精确且较快求解。
• 凸优化问题：最小化目标为凸函数，可行域为凸集；此时局部最小值即为全局最小值（最优解）A convex optimization problem is one in which the objective function (to minimise) is a convex function of decision variables and the set of feasible solutions is convex That makes any local mimimum to be also a global minimum(and hence, an optimal solution)

重要的非线性优化模型类别

本节课聚焦优化建模（而非求解方法），重点讲解：

• 二次规划（QP）Quadratic Programming
  • 主要应用于金融领域；多数求解器可精确求解大规模 QP 问题。
• 整数规划（IP）Integer Programming
  • 主要用于逻辑约束建模；计算难度高，大规模模型需启发式算法。

二次规划（QP）

二次目标函数 + 线性约束 The objective function is quadratic of decision
variables; linear constraints

General form: Min \( x^T \cdot Q \cdot x + x^T \cdot c \)
subject to:
\( Ax = b \)
\( x \ge 0 \)

其中：

• \( x^T = (x_1, \dots, x_n) \)：决策变量向量
• \( Q \)：\( n \times n \) 对称矩阵
• \( c \)：\( n \) 维列向量
• \( A \)：\( m \times n \) 矩阵
• \( b \)：\( m \) 维列向量

• 未来股价 / 收益未知，属于随机变量。投资组合收益为随机变量，围绕期望值的波动被视为风险
• 常用方法：通过优化找到收益方差 / 风险最小的组合
• 目标函数（最小化）代表方差，约束包含可行性要求。将方差表示为组合权重的函数，需估计参数：
  • 各股票收益的方差
  • 每对股票收益间的协方差

整数规划（IP）

• 许多应用中，（部分）决策变量被约束为整数。
  • 全变量为整数：整数规划（IP）
  • 部分变量为整数：混合整数规划（MIP）
• 整数约束会极大增加求解难度。仅适用于中小规模（常近似求解）
• 优化软件（含 Excel 规划求解）可求解 IP/MIP，但仅适用于小规模问题
• 二进制变量Binary Variable，取值仅为 0 或 1，用于建模逻辑约束，代表 “是 / 否” 决策
  本节以金融资本预算为例

• 资本预算问题（IP）

可投资金：19000 英镑，共 4 个投资项目，全投或不投。
项目成本与净现值（NPV）如下：

	项目 1	项目 2	项目 3	项目 4
成本	6700	10000	5500	3400
NPV	8000	11000	6000	4000

目标：最大化净现值

二进制变量建模逻辑约束

• 恰好投资 2 个项目？
• 至多投资 2 个项目？
• 投资项目 2 则必须投资项目 4？
• 项目 2 和 4 至多投一个？
• 项目 2 和 4 至少投一个？
• 项目 2、3、4 中至多投 2 个？

阈值与基数约束（MIP）

某工厂可生产 3 种新型洗涤剂 A、B、C：

• 单位利润（英镑 / 千克）：13、10、15
• 单位成本（英镑 / 千克）：5、4、6
• 总预算：10000 英镑

另有生产线启动固定成本，要求：

• A：产量≥80kg，否则不生产
• B：产量≥70kg，否则不生产
• C：产量≥75kg，否则不生产

目标：最大化利润。

• 设x1​,x2​,x3​为 A、B、C 产量（千克），阈值约束：
• x1​≥80 或 x1​=0
• x2​≥70 或 x2​=0
• x3​≥75 或 x3​=0

建模方法：为每个连续变量添加二进制变量dj​

• dj​=1：生产产品j（xj​>0）
• dj​=0：不生产（xj​=0）

模型含 3 个连续变量 + 3 个整数 / 二进制变量，为混合整数规划（MIP）
阈值约束建模：

模型： 最大化：\( 13x_1 + 10x_2 + 15x_3 \)
约束：
\( 5x_1 + 4x_2 + 6x_3 \leq 10000 \)
\( 80d_1 \leq x_1 \leq 2000d_1 \)
\( 70d_2 \leq x_2 \leq 2500d_2 \)
\( 75d_3 \leq x_3 \leq 1668d_3 \)
\( d_1, d_2, d_3 \) 为二进制变量

• 练习册习题：

QP+MIP 组合阈值约束

最低风险投资组合（QP）中，常加入阈值约束：

第4讲 – Duality Theory 对偶理论

• 对偶理论的基础在于每一个线性规划问题（原问题）都可以关联一个对偶问题，这两个问题的最优解之间存在紧密的联系。
• 对于最小化问题，我们先不急着直接求最优解，而是先从另一个角度构造一些“肯定不超过最优值”的数；这些数都是下界，而对偶问题就是在这些下界里找最大的那个。

对带约束的最优化问题，每个约束都引入一个乘子 \( y_i \)，称为Lagrange multipliers or dual variables
构造拉格朗日函数

• 如果 \( x^* \) 是原问题最优解，那么通常存在某个 \( y^* \)，使得 \( (x^*, y^*) \) 是拉格朗日函数的驻点（驻点stationary point即所有一阶偏导数均为 0 的点）。这给后面对偶变量的解释打了基础。
• 这只是最优性的必要条件（非充分条件）—— 但在部分情形下，该条件可直接确定最优解，如下例所示：

线性规划（LP）情形

理论证明

• 同理可推得一般约束与变量的对偶规则：

对偶模型构造规则

• 原问题的每个约束对应对偶问题的一个变量
• 原问题的每个变量对应对偶问题的一个约束
• 若原问题为最大化，则对偶问题为最小化
• 对偶问题目标函数系数 = 原问题约束右端项（RHS）
• 对偶问题约束右端项（RHS） = 原问题目标函数系数
• 约束系数矩阵转置（如对偶第一个约束系数 = 原问题x1​的系数）

写对偶问题的步骤：

• 对偶问题
  • min – max对换
  • 变量的个数 – 原约束的个数
  • 变量的系数 – 原问题的RHS
• 对偶变量的正负性 – 原约束条件的正负性（正）
• 约束条件
  • 约束条件的个数 = 原变量数量
  • 约束条件的符号 – 原文题变量X的正负性（反）
    • Xi大于0 – 第i个约束条件是小于
    • Xi小于0 – 第i个约束条件是大于
    • Xi没有约束（没写或者说明是free） – 第i个约束条件是等于
  • 约束条件的系数
    • LHS – 原约束条件的系数矩阵的列
    • RHS – 原问题的各变量的系数
• 从原问题最优解得到对偶问题最优解：

定理（只是记录）

弱对偶性Weak duality 证明

互补松弛性 Complementary Slackness

• 直观含义：最优解处，约束的松弛 / 剩余变量与对应对偶变量的乘积为 0
• 由强对偶性可进一步得出：对偶变量的最优值就是原问题对应约束的影子价格

核心结论汇总

1. 若原问题有最优解，则对偶问题也有最优解，且两者最优目标值相等；对偶变量最优值 = 原问题对应约束的影子价格。
2. 最优解处，约束松弛 / 剩余与对应对偶变量乘积为 0（互补松弛）。
3. 若原问题无界，则对偶问题不可行。
4. 若原问题不可行(infeasible)，则对偶问题无界(unbounded)

例题

例1:

原问题无解，对偶问题无界

例2:

第五讲 – Branch-and-Bound (B&B) Algorithm 分支定界（B&B）算法

总结：Branch and Bound 的核心是：先解 LP relaxation 得到 bound；如果解不是整数，就对非整数变量分支；不断排除不可能更优、不可行、或已经整数的子问题，直到所有节点都被 fathomed，最后留下的最好整数解就是最优解。

• Q1. What is Branch and Bound used for?
  • 用于求解整数规划问题，尤其是 ILP / MILP
• Q2. What is LP relaxation?
  • 把整数限制去掉，把：\(x_j \in \mathbb{Z}\) 暂时放宽为：\(x_j \ge 0\)或连续变量。这样得到一个普通 LP，更容易解。
• Q3. Why do we branch?

• Q4. What is a branching variable?

• Q5. What does fathomed mean?
  • 一个节点 / 子问题已经不需要继续分支。
  • 常见原因：
  • LP 解已经是整数解；
  • LP 解不可行；
  • LP relaxation 的 bound 已经不可能比当前最好整数解更好
• Q6. What are upper bound and lower bound in maximization B&B?

• Q8. When does the algorithm stop?
  • 当所有子问题都被 fathomed，也就是没有任何还需要继续检查的节点时，算法停止。
  • 此时当前最好的整数可行解就是最优整数解。

第六讲 – Sensitivity Analysis 敏感性分析

Shadow prices and reduced costs 影子价格与简约成本

约束的影子价格shadow price

• 每个约束都有影子价格，它等于对应松弛变量的简约成本
• 影子价格反映：约束右端项（RHS）变动对最优目标值的影响，其值是RHS增加1最优值的变化量

变量的简约成本reduced cost

• 每个变量都有简约成本，可在满足最优性条件的最终单纯形表最后一行中读出。
• 目标函数系数变动对最优目标值的影响。

下面说明如何用影子价格做敏感性分析：

影子价格和简约成本都是灵敏度分析中的重要内容。影子价格分析约束右端项变化对最优目标值的影响，简约成本分析目标函数系数变化对变量是否进入最优解的影响。

下面说明如何用影子价格做敏感性分析

simulation 仿真

必须区分预测forcasting与仿真：

• 预测：给出最可能的单一结果
• 仿真：生成大量可能结果 / 情景（也叫情景生成）

生成随机数

从正态分布生成样本

• 从正态分布中获取样本有多种方法。一种常见方法是：对一个随机均匀数应用累积分布函数的反函数（这正是NORM.INV 函数的做法）。我们之后会进一步学习这种方法，它适用于很大一类分布。
• 现在我们介绍另一种同样广泛接受的方法：它基于中心极限定理，并且只需要一个随机数发生器。

中心极限定理

• 回顾中心极限定理的一个表述：当大量相互独立且同分布（iid）的随机变量相加时，其和近似服从正态分布。

n 个随机变量的‘标准化’和（即先减去期望，再除以标准差）近似服从 N(0,1)：

连续型随机变量的逆变换法 inverse transformation method.

运用接受 – 拒绝法从指定分布中生成样本Simulation – Acceptance-Rejection method

例1、2

解读Gams的输出文件（考试不考怎么写，但是考怎么看输出文件）

• Maximum achievable profit = 2500

• 决策变量 Decision Variables
  • 生产50个product 1
  • 不要生产产品2
• Reduced Cost: 简约价格
  • 𝑥2 = 0and reduced cost = -10
  • 产品 2 的利润必须增加 10 个单位，生产该产品才会变得有利可图
    Needs +10 increase in profit coefficient . Only then enters solution

• 第一行 Labor：
  • LHS（level） = RHS（Upper） → Binding constraint
  • Shadow price（Marginal）：Increasing labor by 1 unit increases profit by 25
• 第二行 Machine：
  • LHS < RHS → Non-binding constraint
    Slack exists:Slack = 200 − 50 = 150
  • Shadow Price = 0：Increasing machine capacity does not increase profit.

• ✔ Binding constraint → non-zero shadow price
• ✔ Non-binding constraint → zero shadow price

总结：

Markov Models and Hidden Markov Models

Graph Theory

Notation

• n 表示顶点数
• e 表示边数
  • 图 G，我们可以使用 \(n(G)\) 或 \(n_G\)，以及 \(e(G)\) 或 \(e_G\)

• Loop：环 —— 连接同一个顶点自身的边（长度为 1 的圈）
• Connected graph：连通图 —— 任意两顶点之间都有路径可达
• Disconnected graph：非连通图 —— 包含多个互不连通的连通分支 (Connected component)
• Isomorphic graph：同构图 —— 结构完全一致、仅画法 / 顶点编号不同的图
• Subgraph：子图；Spanning subgraph：生成子图；Induced subgraph：导出子图
• Degree：顶点度数；Regular graph：正则图（所有顶点度数相等）
• Adjacency matrix：邻接矩阵 —— 图的矩阵表示形式
• Labelled graph：标号图；Unlabelled graph：无标号图Simple graph：简单图 —— 无环、无重边的无向图

简单图Simple graph 和 有向图Digraph

本课程主要研究 简单图Graph ，是指：

1. 边没有方向（与之相对的是有向图 digraph）
2. 没有自环 – 顶点不能和自己相连
3. 没有重边 – 两个顶点之间最多只有一条边。

本课程不会研究以下几类图：

• 有向图 digraph
• 自环与伪图 pseudograph
  • 允许存在环的图
• 重边与多重图 multigraph
  • 允许两点之间存在多条边的图

1.1 一些重要的图

• 一些小型图同时属于不同的图族，因此可以用多种方式表示。例如：
  • 单个顶点可以表示为 \(N_1\)、\(K_1\)、\(P_1\)
  • 单条边可以表示为 \(K_2\)、\(P_2\) 或 \(K_{1,1}\)
  • \(K_3\) 与 \(C_3\) 是同一个图
  • \(P_3\) 也就是 \(K_{1,2}\)
  • \(C_4\) 也就是 \(K_{2,2}\)

图类型	符号	顶点数	边数
完全图	Kn​	n	2n(n−1)​
完全二部图	Kn,m​	n+m	nm
路径图	Pn​	n	n−1
环图	Cn​	n	n
空图	Nn​	n	0
星图	K1,n​	n+1	n
Petersen 图	—	10	15

• 用度数公式求边数（任意图的边数e = 度数和 / 2 ）

1.2 连通图与非连通图 Connected and Disconnected graphs

• 连通图是由一个整体组成的图
  非连通图 是由多个分离部分组成的图。
• 非连通图中的每一个连通部分叫一个连通分量 connected component
• 连通图最基本的性质是：从任意一个顶点出发，都可以沿着边走到任意另一个顶点

1.3 Isomorphism of graphs 图的同构

1.4 Subraphs子图 spanning subgraph生成子图 induced subgraph诱导子图

• 子图：子图可以删点，也可以删边
• 生成子图：保留所有顶点，删除部分边
• 诱导子图 ：通过删除顶点得到，同时删除与这些顶点相关的边

1.5 度与度序列 Degrees and Degree Sequence

图 G 中，与顶点 v 相连的边的数量，叫作顶点 v 的度，记作：\(\deg v\)

• 如果要强调是在哪个图中的度，可以写作：\(\deg_G v\)

一个图中所有顶点的度组成的列表，叫作度序列

• 度序列本质上是一个集合，顺序不重要，
  不过在实际应用中，我们通常会把度序列按照某种顺序排列，例如从大到小排列

正则图 Regular graph（r）

如果一个图中所有顶点的度都相等，那么这个图叫正则图

如果所有顶点的度都等于r，那么这个图叫：r-regular graph，也就是r- 正则图

1.6 邻接矩阵 Adjacency Matrix

邻接矩阵有几个重要性质

• 邻接矩阵是对称矩阵 \(a_{ij} = a_{ji}\)
  • 因为本课程研究的是无向图，边 \((i,j)\) 和 \((j,i)\) 是同一条边
• 对角线元素为 0 \(a_{ii} = 0\)
  • 因为简单图没有自环
• 每一行或每一列的和等于对应顶点的度

• 顶点编号会影响邻接矩阵

1.7 有标号图与无标号图 Labelled vs Unlabelled Graphs

一个顶点被编号的图，叫作有标号图。除了数字以外，也可以使用任意 n 个不同符号作为顶点标号

标号同构：两个有标号图在相同编号的顶点对应之后完全重合

• 两个图有标号同构，当且仅当它们的邻接矩阵相等 labelled isomorphic⟺A(G)=A(H)
• 注意这里强调的是有标号同构，不是普通同构
  • 普通同构允许重新对应顶点；有标号同构要求相同标号的顶点直接对应

1.8 度序列的基本性质

1.9 图的补图 Complement of a graph

1.10 自补图 Self-complementary graphs

1.11 m-dimensional cube Qm m 维立方体 Q_m

1.12 Some Ramsey theory（如果考再看）

粗略地说，Ramsey 理论说明：在任何足够大的、随机的或混乱的结构中，一定存在某个非常规则、组织良好的部分。

1.13 相似顶点与相似边 Similar vertices and edges

Examples. All vertices and edges in Kn, Cn,Qm and the

Petersen graph are similar.

The vertices and edges of Pn at staying at the same dis

tance from the end-vertices are similar.

All vertices besides the central one, and all edges of a

star K1,n are similar.

Hakimi – Havel Algorithm

根据握手定理，一个图中奇数度顶点的个数必须是偶数，所以这个序列不可能是某个图的度序列

例子：

1. 删除第一个 5，让后面 5 个数减 1：4\ 2\ 2\ 1\ 1\ 2
   • 这是 modified sequence，记作 m
2. 重新排序：4\ 2\ 2\ 2\ 1\ 1
   • 这是 reordered sequence，记作 r。
3. 继续处理 4：删除 4，让后面 4 个数减 1：1\ 1\ 1\ 0\ 1
4. 重新排序…

• 既然这个序列是 graphical，我们就可以构造出一个具有该度序列的图。构造时可以从最后一行对应的图开始，沿着表格倒着往回走，把之前删除的顶点一个一个加回来。

Walks and Cycles

Connectivity 连通性

定义：
图G的边连通度，记作：\(\lambda(G)\)
是为了让图断开，最少需要删除的边数

m-edge-connected

Cutset 割边集

Vertex connectivity 点连通度

Cut vertex 割点

点连通度、边连通度、度之间的定理

树、最小权树、Kruskal 算法、Prim 算法与生成树计数

• 树是一种连通图，并且不包含任何环。

• 对于一棵有 n 个顶点的树，|E|=n-1，有 n-1 条边。

生成树 Spanning Trees

一个连通图 G 的生成树是一个子图，它满足：

1. 包含 G 的所有顶点；
2. 是连通的；
3. 不包含环。

同样对于n个顶点有n-1个边

最小权生成树 Minimum Weight Spanning Trees，MST

假设每条边都有一个权重，也可以理解为成本。

一棵最小生成树是指：

在所有生成树中，总权重最小的生成树。

Kruskal 算法

思想：从权重最小的边开始加入。，但是不能形成环

• 第 1 步
• 按照权重从小到大排序所有边。
• 第 2 步
• 选择最小的边。
• 第 3 步
• 继续加入当前可选的最小边。
• 第 4 步
• 如果某条边会形成环，就跳过它。
• 第 5 步
• 当已经选择了n-1条边时停止

Prim 算法

思想：从一棵树开始逐渐扩展。每次都加入一条连接当前树和新顶点的最小权边

• 第 1 步
• 任意选择一个起始顶点。
• 第 2 步
• 找到从当前树出发的最小权边。
• 第 3 步
• 加入新的顶点。
• 第 4 步
• 重复，直到包含所有顶点。

特征	Kruskal 算法	Prim 算法
策略	基于边	基于顶点
是否需要起始顶点	不需要	需要
是否需要检查环	需要	不需要
适合的图	稀疏图	稠密图
时间复杂度	O(E\log E)	O(E\log V)

生成树计数 Counting Spanning Trees

一个图有多少棵生成树？

图着色 Colouring

色数

图着色的规则是：相邻的两个顶点不能用同一种颜色

如果一个图可以用 不超过 k 种颜色 完成合法着色，那么称这个图是 k-可着色的 k – colorable
例如一个图可以用 3 种颜色染好，那它也是：4- colourable 5-colourable

团 Clique

独立集 Independent Set

唯一可着色 Uniquely Colourable

如果一个图在不考虑颜色名称置换的情况下，只有一种 \chi-着色，那么称这个图是唯一可着色的。

也就是说，允许把颜色 1、2、3 重新命名，但本质上的着色方式只有一种

边着色 Edge Colouring

图 G 与它的补图 \(\overline{G}\) 之间的一些重要关系。

平面性 Planarity

围长 girth

图中最短环的长度

1.1 欧拉公式 Euler’s Formula

二部平面图

1.2 外平面图 Outerplanar Graphs

1.3 Kuratowski 定理

欧拉图、Fleury 算法、中国邮递员问题、用迹覆盖边、最短路径算法、哈密顿图、Ore 定理与旅行商问题

欧拉迹与欧拉回路

欧拉迹 Euler Trail：是指一条迹，它经过图中的每一条边，并且每条边恰好经过一次。

欧拉回路 Euler Circuit：起点和终点相同的欧拉迹。

Euler 定理

握手定理 Handshaking Theorem

Fleury 算法

Fleury 算法提供了一种构造欧拉迹或欧拉回路的方法。

桥 Bridge

中国邮递员问题 Chinese Postman Problem

用迹覆盖边 Covering Edges by Trails

用最少数量的迹覆盖图中的所有边

最短路径算法 Shortest Path Algorithms

给定一个带权图，要求确定两个顶点之间总权重最小的路径。

Dijkstra 算法 – 用于所有边权都非负的情况。

Floyd-Warshall 算法

哈密顿图 Hamiltonian Graphs

Eulerian 欧拉	Hamiltonian 哈密顿
每条边访问一次	每个顶点访问一次
存在度数条件	没有简单的完整刻画
基于边	基于顶点

Ore 定理

旅行商问题 Travelling Salesman Problem，TSP