发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

XGboost是一种梯度提升决策树（GBDT）的模型，它的思想是由决策树（CART）到Adaboost，再到GBDT发展起来的，下面开始总结一下学习XGboost原理的一些心得体会。

XGboost原理推导

首先我们来看XGboost的目标函数： \[L(\phi)=\sum_i l(\hat y_i ,y_i)+\sum_k \Omega(f_k) \qquad (1-1)\]

其中

\[\Omega (f)=\gamma T+\frac{1}{2} \lambda \parallel \omega \parallel ^2\]

这里一个个解释，目标函数中的第二项\(\displaystyle \sum_k \Omega(f_k)\)，这是正则项，也称惩罚项，它是控制模型的复杂度，也就是说这一项的目的是为了在模型复杂程度和模型效果之间取一个平衡。\(f_k\)是基分类器（XGboost中的基分类器是CART），是来自于Boosting思想中的加法模型，即 \[\hat y_i =\sum_k f_k(x_i)\]

在\(\Omega (f)\)的表达式中，\(T\)表示树中的叶子节点数，\(\omega\)是叶子节点上的值。目标函数中的第一项是损失函数（Lost function），\(\hat y_i\)是预测值，\(y_i\)是真实值，\(i\)是样本数。

根据这个目标函数，我们要求的就是\(f_k\)，即当前状态下的决策树是什么样子的。求解的方法是向前分步算法： \[L^{(t)}=\sum_i l(y_i,\hat y^{(t-1)}_i + f_t(x_i))+\Omega (f_t) \qquad (1-2)\]

也就是说，在当前状态第\(t\)轮，那么的\(t-1\)轮的结果就是已知的，所以优化上面的式子就能得到\(f_t\)。其实这个式子还有一个常数项\(\displaystyle \sum_{k=1}^{t-1}\Omega(f_k)\)，即前\(t-1\)轮的正则项，由于常数项对于优化结果是没有影响的，所以去掉了。求解式（1-2），这里用到二阶泰勒展开，先回顾一下二阶泰勒展开： > \(\displaystyle f(x)=f(x_0)+f'(x_0)(x-x_0)+\frac{1}{2}f''(x_0)(x-x_0)^2\)

换一种写法可能对这个问题更直观一点： > \(\displaystyle f(x_0+\Delta x)=f(x_0)+f'(x_0)\Delta x+\frac{1}{2}f''(x_0)(\Delta x)^2\)

下面我们将式（1-2）中的损失函数二阶展开，把\(\hat y^{(t-1)}_i\)看作是泰勒公式中的\(x_0\)，\(f_t(x_i)\)看作是\(\Delta x\)，展开得到下式： \[L^{(t)}\simeq \sum_i[l(y_i,\hat y^{(t-1)}_i)+g_i f_t(x_i)+\frac{1}{2}h_i f^2_t(x_i)]+\Omega (f_t) \qquad (1-3)\]

其中

\[g_i=\partial _{\hat y^{(t-1)}} l(y_i,\hat y^{(t-1)}) \qquad h_i=\partial ^2_{\hat y^{(t-1)}} l(y_i,\hat y^{(t-1)})\] 即\(g_i\)，\(h_i\)分别是损失函数\(l(y_i,\hat y^{(t-1)})\)对\(\hat y^{(t-1)}\)的一阶导数和二阶导数。

由于式（1-3）中的\(l(y_i,\hat y^{(t-1)})\)为已知项，即为常数项，所以去除后可以得到下式： \[L^{(t)}\simeq \sum_i[g_i f_t(x_i)+\frac{1}{2}h_i f^2_t(x_i)]+\Omega (f_t) \qquad (1-4)\]

接下来将式（1-4）中的正则项\(\Omega (f_t)\)的具体内容代入式子中，得到下式： \[L^{(t)}\simeq \sum_i[g_i f_t(x_i)+\frac{1}{2}h_i f^2_t(x_i)]+\gamma T+\frac{1}{2}\lambda \sum^T_{j=1} \omega^2_j \qquad (1-5)\]

式中的\(\omega _j\)是叶子节点\(j\)上的值。接下来需要做一个求和下标的转换，式（1-5）中的求和是对所有的样本点求和，那么我们可以这样想，因为每一个样本点最终都会落到一个叶子节点上，所以对于每一个叶子节点，至少有一个样本点。这样一来，对所有的样本点求和就可以转换成对所有的叶子节点求和，可以得到下式： \[L^{(t)}\simeq \sum^T_{j=1}[ (\sum _{i\in I_j} g_i)\omega _j +\frac{1}{2}(\sum _{i\in I_j} h_i+\lambda)\omega ^2_j]+\gamma T \qquad (1-6)\]

式（1-6）中的\(I_j\)是一个集合，表示所有落到叶子节点\(j\)的样本点。对于某棵决策树结构，式（1-6）的未知量就只有\(\omega _j\)，并且整个式子（1-6）是关于\(\omega _j\)的一元二次方程，求最值时，令\(\displaystyle \frac{\partial {L^{(t)}}}{\partial \omega _j}=0\)即可求得\(\omega ^*_j\)： \[\omega ^*_j =-\frac{\sum _{i\in I_j} g_i}{\sum _{i\in I_j} h_i+\lambda}\]

将\(\omega ^*_j\)的值代入式（1-6）得到下式： \[L^{(t)} (q)=-\frac{1}{2} \sum ^T_{j=1} \frac{(\sum _{i\in I_j} g_i)^2}{\sum _{i\in I_j} h_i+\lambda}+\gamma T\]

这里便得到了评价树结构好坏的score function，根据这个score function就可以得到划分节点的依据，即某节点分开后的score function减去这个节点未分开的score function： \[L_{split}=\frac{1}{2} [\frac{(\sum _{i\in I_L} g_i)^2}{\sum _{i\in I_L} h_i+\lambda}+\frac{(\sum _{i\in I_R} g_i)^2}{\sum _{i\in I_R} h_i+\lambda}-\frac{(\sum _{i\in I} g_i)^2}{\sum _{i\in I} h_i+\lambda}]-\gamma\]

式子中的\(I_L,I_R\)分别表示某节点分裂后落到左边节点的所有样本点和落到右边节点的所有样本点。

(未完待续)

参考文献

  1. Chen, Tianqi, and Carlos Guestrin. "Xgboost: A scalable tree boosting system." Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining. ACM, 2016.
  2. 《统计学习方法》 李航 著
  3. 深入理解网红算法XGBoost
  4. 对xgboost的理解
  5. 一文理解GBDT的原理

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

主成分分析（Principal Component Analysis，PCA）是一种常见的数据降维方法，其目的是在“信息”损失较小的前提下，将高维的数据转换到低维，从而减小计算量。

首先从一张图来直观感受下：

pca

图中蓝色的点为样本点，每个样本点有二维特征，图中展示的就是将二维特征降成一维特征。图中中心的小白点是所有样本点的中心，过这个中心点为可以画出无数条直线，样本点在这条直线上的投影就是降维后的数据。那么选择这条直线的标准是什么呢？标准就是样本点在直线上的投影要尽可能地分散，对应到数学形式上就是方差最大。下面进行数学推导。

数学推导

样本\(X=[x_1, x_2,...,x_n]\)，其中\(x_i \in R^p\)，即每个样本是\(p\)维的。现在我们进行降维操作，通过一个矩阵变换来实现： \[y_i=Wx_i \qquad其中y_i\in R^q\] 其中 \[W=\left[\begin{matrix} \omega ^T_1 \\ \vdots \\ \omega ^T_q \end{matrix}\right] \in R^{q \times q}\] 这样一来，相当于把\(x_i\)的\(p\)维数据降到\(y_i\)的\(q\)维（\(q<p\)），整个问题也变成了如何得到\(W\)。

如果将式子展开得到如下形式： \[\begin{aligned} Y &= WX\\ &= \left[ \begin{matrix} \omega ^T_1 \\ \omega ^T_2 \\ \vdots \\ \omega ^T_q \end{matrix} \right] \times \begin{matrix} [x_1 & x_2 & \cdots & x_n] \end{matrix} \\ &= \left[\begin{matrix} \omega ^T_1 x_1 & \omega ^T_1 x_2 & \cdots & \omega ^T_1 x_n \\ \omega ^T_2 x_1 & \omega ^T_2 x_2 & \cdots & \omega ^T_2 x_n \\ \vdots & \vdots & \ddots & \vdots \\ \omega ^T_q x_1 & \omega ^T_q x_2 & \cdots & \omega ^T_q x_n \end{matrix}\right] \\ &= \begin{matrix} [y_1 & y_2 & \cdots & y_n] \end{matrix} \end{aligned}\] 现在假设其中一个\(\omega _i\)为\(\omega\)，其中一个样本点\(x_i\)为\(x\)，注意\(\omega\)和\(x\)都是\(p\)维的，那么: \[ \omega ^T x = \omega \cdot x = |\omega||x|cos\theta \] 其中可以对\(\omega\)进行缩放，我们将约束其模为1，即\(|\omega|=1(\omega ^T \omega=1)\)，于是： \[ \omega ^T x = |x|cos\theta \] 即问题转化为样本点\(x\)在\(\omega\)上的投影，现在要使得这些投影点的方差最大。下面介绍一些概念，然后进行推导。

样本均值： \[ \bar{x}=\frac{1}{n}\sum ^n_i x_i\] 样本投影均值： \[ \mu=\frac{1}{n}\sum ^n_i \omega ^Tx_i\] 样本\(X\)与样本\(Y\)的协方差： \[ \begin{aligned} Cov(X,Y) &= E[(X-E(X))(Y-E(Y))] \\ &= \frac{1}{n}\sum ^n_i (x_i - \bar{x})(y_i - \bar{y}) \end{aligned}\] 样本点在\(\omega\)上投影的方差： \[ \begin{aligned} \sigma ^2 &= \frac{1}{n}\sum ^n_i (\omega^T x_i - \mu)^2\\ &= \frac{1}{n}\sum ^n_i (\omega^T x_i - \frac{1}{n}\sum ^n_i \omega ^Tx_i)^2\\ &= \frac{1}{n}\sum ^n_i(\omega^T x_i - \omega^T(\frac{1}{n}\sum ^n_i x_i))^2\\ &= \frac{1}{n}\sum ^n_i(\omega^T x_i - \omega^T\bar{x})^2\\ &= \frac{1}{n}\sum ^n_i(\omega^T(x_i - \bar{x}))^2 \qquad这里\omega^T( x_i - \bar{x})是一个数\\ &= \frac{1}{n}\sum ^n_i(\omega^T(x_i - \bar{x}))(\omega^T( x_i - \bar{x}))^T\\ &= \frac{1}{n}\sum ^n_i\omega^T(x_i - \bar{x})(x_i - \bar{x})^T\omega\\ &= \omega^T(\frac{1}{n}\sum ^n_i (x_i - \bar{x})(x_i - \bar{x})^T)\omega\\ &= \omega^T\Sigma\omega \end{aligned}\] 其中\(\Sigma\)是样本\(X\)与自身的协方差矩阵。这样一来问题就变成以下优化问题： \[ max\quad \omega^T\Sigma\omega \\ s.t.\quad \omega^T\omega=1 \] 用拉格朗日乘数法求解： \[ L(\omega,\lambda)=\omega^T\Sigma\omega-\lambda(\omega^T\omega-1)\\ \frac{\partial L(\omega,\lambda)}{\partial \omega}=2\Sigma\omega-2\lambda\omega=0\\ \Sigma\omega=\lambda\omega \] 即\(\lambda\)是\(\Sigma\)的特征值，\(\omega\)是特征值为\(\lambda\)的特征向量。由此可以推出： \[ \sigma^2=\lambda\omega^T\omega=\lambda \] 即投影后的方差就是协方差矩阵的特征值，使投影后的方差最大就是协方差矩阵的特征值最大。求解协方差矩阵\(\Sigma\)的特征值和特征向量时可以用到谱分解（又称特征分解）： \[ \Sigma=Q\Lambda Q^T \] 其中\(Q\)为正交矩阵，\(\Lambda\)为对角矩阵，对角线上的元素为矩阵\(\Sigma\)的特征值。\(Q\)的列向量\(q_i\)为\(\Lambda\)中对角元素\(\lambda_{ii}\)对应的特征向量。

PCA算法步骤如下

输入数据集\(X=[x_1, x_2,...,x_n]其中x_i\in R^n\)，需要降到\(k\)维，

  1. 去平均值(又称去中心化)，即\(x_i-\bar{x}\)，得到\(\bar{X}=[x_1-\bar{x},x_2-\bar{x},...,x_n-\bar{x}]\)
  2. 求解协方差矩阵\(\displaystyle \Sigma=\frac{1}{n}\bar{X}\bar{X}^T\)的特征值及对应的特征向量
  3. 选取前\(k\)大的特征值\((\lambda_1,\lambda_2,...,\lambda_k)\)及对应的特征向量\((\omega_1,\omega_2,...,\omega_k)\)
  4. 降维后的数据 \[Y=WX,W=\left[\begin{matrix} \omega ^T_1 \\ \vdots \\ \omega ^T_k \end{matrix}\right]\]

代码如下

1
2
3
4
5
6
7
8
9
10
11
import numpy as np
from sklearn.decomposition import PCA

# 官网 https://scikit-learn.org/stable/modules/generated/sklearn.decomposition.PCA.html
# 输入数据为(n_samples, n_features)
X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
pca = PCA(n_components=1)
pca.fit(X)

print(pca.explained_variance_ratio_) # 所保留的特征的方差百分比
print(pca.fit_transform(X)) # 返回降维后的数据(n_samples, n_components)

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

7.1 概念

  • 边着色：对\(G\)的边进行染色，若相邻边染不同颜色，则称对\(G\)进行正常边着色，如果能用\(k\)种颜色对图\(G\)进行正常边着色，称\(G\)是\(k\)边可着色的。
  • 边色数\(\chi '\)：设\(G\)是图，对\(G\)进行正常边着色需要的最少颜色数，称为\(G\)的边色数，记为\(\chi '(G)\)
  • 点着色：设\(G\)是一个图，对\(G\)的每个顶点着色，使得相邻顶点着不同颜色，称为对\(G\)的正常顶点着色。如果用\(k\)种颜色可以对\(G\)进行正常顶点着色，称\(G\)可\(k\)正常顶点着色。
  • 点色数\(\chi\)：对图\(G\)正常顶点着色需要的最少颜色数，称为图\(G\)的点色数，记为\(\chi (G)\)
  • 次大度\(\Delta _2(G)\): \[\Delta _2(G)=\underset{u\in V(G)}{max} \underset{\begin{matrix} \small v\in N(u)\\ \small d(v)\leq d(u) \end{matrix}}{max}d(v)\]

7.2 边色数

  • \(\chi '(K_{m,n})=\Delta (最大度)\)
  • （维津定理）若G是单图，则\(\chi '(G)=\Delta 或\chi '(G)=\Delta +1\)
  • 设\(G\)是单图且\(\Delta (G)>0\)，若\(G\)中只有一个最大度点或恰有两个相邻的最大度点，则\(\chi '(G)=\Delta\)
  • 设\(G\)是单图，若点数\(n=2k+1\)且边数\(m>k\Delta\)，则\(\chi '(G)=\Delta +1\)
  • 设\(G\)是奇数阶\(\Delta\)正则单图，若\(\Delta >0\)，则\(\chi '(G)=\Delta +1\)

7.3 点色数

  • 对任意的图\(G\)，有\(\chi (G)\leq \Delta (G)+1\)
  • 若\(G\)是连通的单图，并且它既不是奇圈，又不是完全图，则\(\chi (G)\leq \Delta (G)\)
  • 设\(G\)是非空简单图，则\(\chi (G)\leq \Delta _2(G)+1\)
    • 推论：设\(G\)是非空简单图，若G中最大度点互不邻接，则有\(\chi (G)\leq \Delta (G)\)
  • 五色定理：每个平面图是5可着色的

7.4 色多项式（添边和减边）

除了添边和减边，还有通过图\(G\)的补图\(\bar{G}\)来算。

  • 若图\(G\)的生成子图\(H\)的每个分支都是完全图，则称\(H\)为\(G\)的理想子图。
  • 记\(G\)的具有\(r\)个分支的理想子图的个数为\(N_r(G)\)

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

第六章 平面图

6.1 概念

  • 平面图：如果能把图\(G\)画在平面上，使得除顶点外，边与边之间没有交叉，称\(G\)可嵌入平面，或称\(G\)是可平面图。可平面图\(G\)的边不交叉的一种画法，称为\(G\)的一种平面嵌入，\(G\)的平面嵌入表示的图称为平面图
  • 面：一个平面图\(G\)把平面分成若干连通片，这些连通片称为\(G\)的区域，或\(G\)的一个面。\(G\)的面组成的集合用\(\psi\)表示；无界的区域称为外部面或无限面。
  • 次数：某面\(f\)的边界中含有的边数（割边计算2次）称为该面\(f\)的次数, 记为\(deg(f)\)

6.2 性质

  • 次数公式：设\(G=(n, m)\)是平面图，则\(\sum deg(f)=2m\)
  • 平面图Euler公式：设\(G=(n, m)\)是连通平面图，\(\phi\)是\(G\)的面数，则：\(n-m+\phi =2\)
    • 推论1 设\(G\)是具有\(\phi\)个面\(k\)个连通分支的平面图，则\(n-m+\phi =k+1\)
    • 推论2 设\(G\)是具有\(n\)个点\(m\)条边\(\phi\)个面的连通平面图，如果对\(G\)的每个面\(f\) ,有\(deg (f) ≥ l ≥3\)，则\(\displaystyle m\leq \frac{l}{l-2}(n-2)\)
      • 推论2也可以表述为设\(G=(n, m)\)是连通图，如果\(\displaystyle m> \frac{l}{l-2}(n-2)\)，则\(G\)是非可平面图
    • 推论3 设\(G\)是具有\(n\)个点\(m\)条边\(\phi\)个面的简单平面图，则\(m\leq 3n-6\)
    • 推论4 设\(G\)是具有\(n\)个点\(m\)条边的连通平面图，若\(G\)的每个圈均由长度是\(l\)的圈围成，则\(m(l-2)=l(n-2)\)
    • 推论5 \(G\)是具有\(n\)个点\(m\)条边的简单平面图，则\(\delta \leq 5\)

6.3 判定

  • 对于简单图\(G=(n, m)\)，如果\(m>3n-6\)，则\(G\)是非可平面的
  • 对于简单连通图\(G=(n, m)\)，如果每个面次数至少为\(l\geq 3\),且\(\displaystyle m>(n-2)\frac{l}{l-2}\)，则\(G\)是非可平面的
  • 库拉托斯基定理：\(G\)是可平面的当且仅当\(G\)不含有与\(K_5\)和\(K_{3,3}\)同胚的子图
  • 瓦格纳定理：\(G\)是可平面的当且仅当\(G\)不含有能够收缩成\(K_5\)和\(K_{3,3}\)的子图
  • 图\(G\)是可平面的，当且仅当它的基础简单图是可平面的
    • 给定图\(G\), 去掉\(G\)中的环，用单边代替平行边而得到的图称为\(G\)的基础简单图
  • 图\(G\)是可平面图当且仅当\(G\)的每个块是可平面图

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

第五章 匹配与因子分解

5.1 概念

  • 匹配：如果\(M\)是图\(G\)的边子集(不含环），且\(M\)中的任意两条边没有共同顶点，则称\(M\)是\(G\)的一个匹配或对集或边独立集
  • 饱和点：如果\(G\)中顶点\(v\)是\(G\)的匹配\(M\)中某条边的端点，称它为\(M\)饱和点，否则为\(M\)非饱和点
  • 最大匹配：如果\(M\)是图\(G\)的包含边数最多的匹配，称\(M\)是\(G\)的一个最大匹配
  • 完美匹配：若最大匹配饱和了\(G\)的所有顶点，称它为\(G\)的一个完美匹配
  • \(M\)交错路：如果\(M\)是图\(G\)的匹配，\(G\)中一条由\(M\)中的边和非\(M\)中的边交错形成的路，称为\(G\)中的一条\(M\)交错路
  • \(M\)可扩路：若\(M\)交错路的起点与终点是\(M\)非饱和点，称这种\(M\)交错路为\(M\)可扩路

Hall定理：

  • 设\(G=(X, Y)\)是偶图，则\(G\)存在饱和\(X\)每个顶点的匹配的充要条件是对\(\forall S\subseteq X\)，有\(|N(S)|\geq |S|\)
  • Hall定理也可表述为：设\(G=(X,Y)\)是偶图，如果存在\(X\)的一个子集\(S\),使得\(|N(S)|<|S|\)，那么\(G\)中不存在由\(X\)到\(Y\)的匹配

\(k\)正则偶图：

  • 若\(G\)是\(k(k>0)\)正则偶图，则\(G\)存在完美匹配
  • 每个\(k\)方体都是\(k\)正则偶图
  • 每个\(k\)方体都有完美匹配(\(k\geq 2\))
  • 没有割边的3正则图存在完美匹配。（有割边的3正则图不一定存在完美匹配）
  • \(K_{2n}\)的不同完美匹配个数为：\((2n-1)!!\)
  • \(K_{n,n}\)的不同完美匹配个数为：\(n!\)

5.2 因子分解

  • 所谓一个图\(G\)的因子\(G_i\)，是指至少包含\(G\)的一条边的生成子图
  • 所谓一个图\(G\)的因子分解，是指把图\(G\)分解为若干个边不重的因子之并
  • 所谓一个图\(G\)的\(n\)因子，是指图\(G\)的\(n\)度正则因子
  • 如果一个图\(G\)能够分解为若干\(n\)因子之并，称\(G\)是可\(n\)因子分解的

定理以及结论：

  1. \(K_{2n}\)可一因子分解
  2. 每个\(k(k>0)\)正则偶图G是一可因子分解的
  3. 具有\(H\)圈的3正则图可一因子分解。（可一因子分解的3正则图不一定存在\(H\)圈）
  4. 若3正则图有割边，则它不能一因子分解。（没有割边的3正则图可能也没有一因子分解，如彼得森图）
  5. \(K_{2n+1}\)可2因子分解
  6. \(K_{2n}\)可分解为一个1因子和n-1个2因子之和
  7. 每个没有割边的3正则图是一个1因子和1个2因子之和
  8. 一个连通图可2因子分解当且仅当它是偶数度正则图

5.3 匈牙利算法（在偶图中找完美匹配）

从任意匹配\(M\)开始，

  • 步骤1 若\(M\)饱和\(X\)的每个顶点，则停止。否则，任取一个\(X\)中的\(M\)非饱和顶点\(u\)，令\(S=\{u\}\)，\(T=\varnothing\)
  • 步骤2 若\(N(S)\neq T\)，任取一顶点\(y\in N(S)-T\)；若\(N(S)=T\)，则不存在完美匹配（根据Hall定理）
  • 步骤3 若\(y\)是\(M\)饱和的。设\(yz\in M\)，\(S=S\cup \{z\}\)，\(T=T\cup \{y\}\)，然后转到步骤2；若\(y\)是\(M\)非饱和的，则\(P=(u，y)\)路是\(M\)可扩的，\(M=M\bigtriangleup E(P)\)，然后转到步骤1

5.4 最优匹配算法（边赋权完全偶图找完美匹配）

注意理解匈牙利算法与库恩算法的相似与不同！

  • 可行顶点标号：设\(G=(X,Y)\)，若对任意的\(x\in X,y\in Y\)，有\(l(x)+l(y)\geq w(xy)\)，则称\(l\)是赋权完全偶图\(G\)的可行顶点标号。
    • 事实上，设： \[\begin{cases} l(x)=\underset{y\in Y}{max} \ w(xy),若x\in X,\\ l(y)=0,若y\in Y. \end{cases}\] 则\(l\)是\(G\)的一个可行顶点标号。
  • 相等子图：设\(l\)是赋权完全偶图\(G=(X, Y)\)的可行顶点标号，令\(E_l=\{ xy\in E(G)|l(x)+l(y)=w(xy)\}\)，则称\(G_l=G[E_l]\)为\(G\)的对应于\(l\)的相等子图。
  • 库恩算法（Kuhn-Munkres）: 给一初始顶点标号\(l\),在\(G_l\)中任选一个匹配\(M\)，
    • 步骤1 若\(X\)是\(M\)饱和的，则\(M\)是最优匹配。否则，令\(u\)是一个\(M\)非饱和点，置\(S=\{ u\},T=\varnothing\)
    • 步骤2 若\(T\subset N_{G_l}\)，转到步骤3。否则，计算： \[\alpha _l=\underset{x\in S,y\notin T}{min}\{ l(x)+l(y)-w(xy)\}\] \[\hat{l}=\begin{cases} l(v)-\alpha _l,v\in S\\ l(v)+\alpha _l,v\in T\\ l(v),\small 其它 \end{cases}\]     得到新的可行顶点标号，重新开始
    • 步骤3 若\(y\)是\(M\)饱和的。设\(yz\in M\)，\(S=S\cup \{z\}\)，\(T=T\cup \{y\}\)，然后转到步骤2；若\(y\)是\(M\)非饱和的，则\(P=(u，y)\)路是\(M\)可扩的，\(M=M\bigtriangleup E(P)\)，然后转到步骤1

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

第四章 Euler图与Hamilton图

4.1 Euler图

  • Euler迹：经过连通图\(G\)的每条边的迹称为Euler迹。（注意区分迹与闭迹）
  • Euler图：对于连通图\(G\)，如果\(G\)中存在经过每条边的闭迹，则称\(G\)为欧拉图，简称\(G\)为\(E\)图。欧拉闭迹又称为欧拉环游，或欧拉回路。（通俗理解为遍历边回到起点）

性质：

  • 下列陈述对于非平凡连通图\(G\)是等价的：
    • \(G\)是欧拉图；
    • \(G\)的顶点度数为偶数；
    • \(G\)的边集合能划分为圈
  • 连通图\(G\)是欧拉图当且仅当\(G\)的顶点度数为偶数
  • 连通非欧拉图G存在欧拉迹当且仅当\(G\)中只有两个顶点度数为奇数
  • Fleury(弗勒里)算法：尽量避割边行走

4.2 Hamilton图

  • Hamilton图：如果经过图\(G\)的每个顶点恰好一次后能够回到出发点，称这样的图为哈密尔顿图，简称\(H\)图。所经过的闭途径是\(G\)的一个生成圈，称为\(G\)的哈密尔顿圈。(通俗理解为遍历点回到起点)
  • Hamilton路：如果存在经过\(G\)的每个顶点恰好一次的路，称该路为\(G\)的哈密尔顿路，简称\(H\)路

性质与判定：

  • (必要条件) 若\(G\)为\(H\)图，则对\(V(G)\)的任一非空顶点子集\(S\)，有\(\omega (G-S)\leq |S|\)。（即满足不等式的图不一定是\(H\)图，不满足不等式的图一定是非\(H\)图）
  • (充分条件) 对于\(n\geq 3\)的单图\(G\)，如果G中有\(\displaystyle \delta (G)\geq \frac{n}{2}\)，那么\(G\)是\(H\)图。
  • (充分条件) 对于\(n\geq 3\)的单图\(G\)，如果\(G\)中的任意两个不相邻顶点\(u\)与\(v\)，有\(d(u)+d(v)\geq n\)，那么\(G\)是\(H\)图。
  • (邦迪-闭包)定理：图\(G\)是\(H\)图当且仅当它的闭包是\(H\)图。
    • 在\(n\)阶单图中，若对\(d(u)+d(v)\geq n\)的任意一对顶点\(u\)与\(v\)，均有\(u\ adj\ v\), 则称\(G\)是闭图。
    • 称\(\bar{G}\)是图\(G\)的闭包，如果它是包含\(G\)的极小闭图。
      • 如果\(G\)本身是闭图，则其闭包是它本身；如果\(G\)不是闭图，则由定义可以通过在度和大于等于\(n\)的不相邻顶点对间加边来构造\(G\)的闭图。
    • 图\(G\)的闭包是唯一的。
  • 度序列判定法：设\(G\)是度序列为\((d_1,d_2,...,d_n)\)的简单图，这里\(d_1\leq d_2\leq ...\leq d_n\)，并且\(n\geq 3\)。若对任何\(\displaystyle m<\frac{n}{2}\)，或有\(d_m>m\)，或有\(d_{n-m}\geq n-m\)，则\(G\)是\(H\)图

4.3 度极大非Hamilton图

  • 图\(G\)称为度极大非\(H\)图，如果它的度不弱于其它非\(H\)图
  • \(C_{m,n}\)图：对于\(\displaystyle 1\leq m<\frac{n}{2}\)，\(C_{m,n}\)图定义为\(C_{m,n}=K_m\vee （\bar{K}_m+K_{n-2m}）\)
    • 注意理解\(C_{m,n}\)的度序列为： \[(\underbrace{m,...,m,}_{m}\ \underbrace{n-m-1,...,n-m-1,}_{n-2m}\ \underbrace{n-1,...,n-1}_{m})\]
  • 对于\(\displaystyle 1\leq m<\frac{n}{2}\)，\(C_{m,n}\)图是非\(H\)图

定理1

  • 若\(G\)是\(n\geq 3\)的非\(H\)简单图，则\(G\)度弱于某个\(C_{m,n}\)图。（证明P85）
    • 定理1刻画了非\(H\)单图的特征：从度序列角度看，\(C_{m,n}\)图族中某个图是某个\(n\)阶非\(H\)单图的极图
    • 定理1的条件是充分条件而非必要条件。例如当\(n=5\)时，其度极大非\(H\)图族是：\(C_{1,5}\)与\(C_{2,5}\)，5阶圈\(C_5\)度弱于\(C_{2,5}\)，但是\(C_5\)是\(H\)图
    • 如果\(n\)阶单图\(G\)度优于所有的\(C_{m,n}\)图族，则\(G\)是\(H\)图

推论：

  • 设\(G\)是\(n\)阶单图。若\(n\geq 3\)且\(\displaystyle |E(G)|>\begin{pmatrix} n-1 \\ 2\end{pmatrix}+1\)，则\(G\)是\(H\)图。并且具有\(n\)个顶点\(\begin{pmatrix} n-1 \\ 2\end{pmatrix}+1\)条边的非\(H\)图只有\(C_{1,n}\)以及\(C_{2,5}\)
  • 证明P86，注：推论的条件是充分而非必要的

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

第三章 图的连通度

3.1 概念

  • 割边：设\(e\)是图\(G\)的一条边，若\(\omega (G-e)>\omega (G)\)，则称\(e\)为\(G\)的割边。（\(\omega\)为连通分支数）
    • 边\(e\)是图\(G\)的割边当且仅当\(e\)不在\(G\)的任何圈中
    • \(e\)为连通图\(G\)的一条边，如果\(e\)含于\(G\)的某圈中，则\(G-e\)连通
  • 割点：如果\(E(G)\)可以划分为两个非空子集\(E_1\)与\(E_2\)，使\(G[E_1]\)和\(G(E_2)\)以点\(v\)为公共顶点，称\(v\)为\(G\)的一个割点
    • \(G\)无环且非平凡，则\(v\)是\(G\)的割点，当且仅当\(\omega (G-v)>\omega (G)\)
    • 设\(v\)是树\(T\)的顶点，则\(v\)是割点，当且仅当\(v\)是树的分支点
    • 设\(v\)是无环连通图\(G\)的一个顶点，则\(v\)是\(G\)的割点，当且仅当\(V(G-v)\)可以划分为两个非空子集\(V_1\)与\(V_2\),使得对任意\(x\in V_1\), \(y\in V_2\), 点\(v\)在每一条\((x,y)\)路上
  • 块：没有割点的连通图称为块
    • 若\(|V(G)|\geq 3\),则\(G\)是块，当且仅当\(G\)无环且任意两顶点位于同一圈上（证明P48）
    • 点\(v\)是图\(G\)的割点当且仅当\(v\)至少属于\(G\)的两个不同的块（证明P49）
  • 顶点割（点割）：给定连通图\(G\)，设\(V'\subseteq V(G)\)，若\(G-V'\)不连通，称\(V'\)为\(G\)的一个点割集，含有\(k\)个顶点的点割集称为\(k\)顶点割。\(G\)中点数最少的顶点割称为最小顶点割。
  • 点连通度\(\kappa\)：在\(G\)中，若存在顶点割，称\(G\)的最小顶点割的顶点数称为\(G\)的点连通度；否则称\(n-1\)为其点连通度。\(G\)的点连通度记为\(\kappa (G)\), 简记为\(\kappa\)。若\(G\)不连通，\(\kappa (G)=0\)
  • 边连通度\(\lambda\)：在\(G\)中，最小边割集所含边数称为\(G\)的边连通度。边连通度记为\(\lambda (G)\) 。若\(G\)不连通或\(G\)是平凡图，则定义\(\lambda (G) =0\)
  • 在\(G\)中，若\(\kappa (G)≧k\), 称\(G\)是\(k\)连通的；若\(\lambda (G)≧k\)，称\(G\)是\(k\)边连通的
  • （惠特尼）定理：对任意图\(G\)，有\(\kappa (G)\leq \lambda (G)\leq \delta (G)\)
  • 设\(G\)是\((n,m)\)连通图，则\(\displaystyle \kappa (G)\leq \lfloor \frac{2m}{n}\rfloor\)
  • 敏格尔定理:
    • 设\(x\)与\(y\)是图\(G\)中的两个不相邻点，则\(G\)中分离点\(x\)与\(y\)的最小点数等于独立的\((x, y)\)路的最大数目
    • 设\(x\)与\(y\)是图\(G\)中的两个不相邻点，则\(G\)中分离点\(x\)与\(y\)的最小边数等于\(G\)中边不重的\((x, y)\)路的最大数目
    • 惠特尼
      • 一个非平凡的图\(G\)是\(k(k\geq 2)\)连通的，当且仅当\(G\)的任意两个顶点\(u\)与\(v\)间，至少存在\(k\)条内点不交的\((u ,v)\)路
      • 一个非平凡的图\(G\)是\(k(k\geq 2)\)边连通的，当且仅当\(G\)的任意两个顶点间至少存在\(k\)条边不重的\((u ,v)\)路
    • 推论 对于一个阶至少为3的无环图\(G\)，下面三个命题等价：
      • \(G\)是2连通的
      • \(G\)中任意两点位于同一个圈上
      • \(G\)无孤立点，且任意两条边在同一个圈上

证明题：

  1. 求证：无环非平凡连通图至少有两个非割点
    • 证明： 由于\(G\)是无环非平凡连通图，所以存在非平凡生成树，而非平凡生成树至少两片树叶，它不能为割点，所以，它也不能为\(G\)的割点
  2. 求证：恰有两个非割点的连通单图是一条路
    • 证明：设\(T\)是\(G\)的一棵生成树。由于\(G\)有\(n-2\)个割点，所以，\(T\)有\(n-2\)个割点，即\(T\)只有两片树叶，所以\(T\)是一条路。这说明，\(G\)的任意生成树为路。一个单图的任意生成树为路，则该图为圈或路，若为圈，则\(G\)没有割点，矛盾，所以，\(G\)为路
  3. 求证：若\(v\)是单图\(G\)的割点，则它不是\(G\)的补图的割点
    • \(v\)是单图\(G\)的割点，则\(G-v\)至少两个连通分支。现任取\(x,y\in V(\bar{G} -v)\)，如果\(x, y\)在\(G-v\)的同一分支中，令\(u\)是与\(x, y\)处于不同分支的点，那么通过\(u\)，可说明，\(x\)与\(y\)在\(G-v\)的补图中连通。若\(x, y\)在\(G-v\)的不同分支中，则它们在\(G-v\)的补图中邻接。所以，若\(v\)是\(G\)的割点，则v不是其补图的割点

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

第二章 树

2.1 概念

  • 不包含圈的图称为无圈图，连通的无圈图称为树
  • 一个无圈图称为森林，树也是森林
    • 树和森林都是简单图
    • 树和森林都是偶图
  • 平凡图称为平凡树
  • 根树：一棵非平凡的有向树\(T\)，如果恰有一个顶点的入度为0，而其余所有顶点的入度为1，这样的的有向树称为根树。其中入度为0的点称为树根，出度为0的点称为树叶，入度为1，出度大于1的点称为内点。又将内点和树根统称为分支点
  • 完全\(m\)元树：对于根树\(T\)，若每个分支点至多\(m\)个儿子，称该根树为\(m\)元根树；若每个分支点恰有\(m\)个儿子，称它为完全\(m\)元树

2.2 性质

  • 每棵非平凡树至少有两片树叶
  • 图\(G\)是树当且仅当\(G\)中任意两点都被唯一的路连接
  • 设\(T\)是\((n, m)\)树，则\(m=n-1\)
  • 具有\(k\)个分支的森林有\(n-k\)条边
  • 每个\(n\)阶连通图的边数至少为\(n-1\)
  • 任意树\(T\)的两个不邻接顶点之间添加一条边后，可以得到唯一圈
  • 设\(s=\{d_1,d_2,...,d_n \}\)是\(n\)个正整数序列，它们满足：\(d_1\geq d_2\geq ...\geq d_n,\sum d_i=2(n-1)\)，则存在一颗树\(T\)，其度序列为\(S\)

2.3 最小生成树

在连通边赋权图G中求一棵总权值最小的生成树。该生成树称为最小生成树或最小代价树

  • Kruskal算法：
    1. 选择边\(e_1\),使得其权值最小
    2. 若已经选定边\(e_1,e_2,...,e_k\)，则从\(E-\{e_1,e_2,...,e_k \}\)中选择边\(e_{k+1}\)使得：
      • \(G(e_1,e_2,...,e_{k+1})\)为无圈图
      • \(e_{k+1}\)的权值\(w(e_{k+1})\)尽可能小
    3. 当2不能进行时，停止
  • 管梅谷的破圈法

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

第一章 图的基本概念

1.1 概念

  • 平凡图：只有一个顶点并且没有边
  • 简单图：既没有环也没有重边的图
  • \(n\)阶图：顶点数为\(n\)的图
  • 顶点\(u\)与\(v\)相邻接\((adj)\)：顶点\(u\)与\(v\)有边相连接；其中\(u\)与\(v\)称为该边的两个端点。
  • 顶点\(u\)与边\(e\)相关联：顶点\(u\)是边\(e\)的端点
  • 边\(e_1\)与边\(e_2\)相邻接：边\(e_1\)与边\(e_2\)有公共端点
阅读全文 »