图论及其应用 学习笔记（一）图的基本概念「建议收藏」

记录一下这门课程的知识点和个人理解，参考资料为这门课老师的讲解、电子科大杨春老师的PPT，以及《图论与网络最优化算法》这本书

图的定义与图论模型

图的定义

一个图是一个序偶<V,E>，记为G=(V,E),其中：

1. V是一个有限的非空集合，称为顶点集合,其元素称为顶点或点。用|V|表示顶点数；
2. E是由V中的点组成的无序对构成的集合，称为边集，其元素称为边，且同一点对在E中可以重复出现多次。用|E|表示边数。

图可以用图形表示：V中的元素用平面上一个黑点（小圆圈）表示，E中的元素用一条连接V中相应点对的任意形状的线表示。

图的相关概念

• 有限图：顶点集和边集都有限的图称为有限图；
• 平凡图：只有一个顶点的图称为平凡图；
• 空图：边集为空的图称为空图；
• n阶图：顶点数为n的图称为n阶图；
• (n, m) 图：顶点数为n,边数为m的图称为(n, m) 图；
• 边的重数：连接两个相同顶点的边的条数称为边的重数；重数大于1的边称为重边；
• 环：端点重合为一点的边称为环；
• 简单图：无环无重边的图称为简单图；其余的图称为复合图；
• 顶点u与v相邻接：顶点u与v间有边相连接；其中u与v称为该边的两个端点；
• 顶点u与边e相关联：顶点u是边e的端点；
• 边e1与边e2相邻接：边e1与边e2有公共端点；

图论模型

为了抽象和简化现实世界，常建立数学模型。图是关系的数学表示，为了深刻理解事物之间的联系，图是常用的数学模型。

• 一般步骤：
  1. 定义顶点和边的规则
  2. 绘图
  3. 用图论的方法解决问题
• 经典问题：
  • 旅行商问题
    一电脑代理商要从她所在城市出发，乘飞机去六个城市，
    然后回到出发点，如果要求每个城市只经历一次，能否办
    到？给出行走方案
  • 最小路径问题

图的同构

• 定义：设有两个图$G1=(V1,E1)$和$G2=(V2,E2)$,若在其顶点集合间存在双射，使得边之间存在如下关系：设
  $$u_1\leftrightarrow u_2;v_1\leftrightarrow v_2;u_1,v_1\in V1;u2,v2\in V2;u_1{v}_1\in E1$$

  当且仅当$u_2{v}_2\in E_2$,且$u1v1$与$u_2{v}_2$的重数相同。称$G1$与$G2$同构，记为：
  $$G1\cong G2$$

完全图、偶图与补图

• 完全图：每两个不同的顶点之间都有一条边相连的简单图称为完全图。有：

$$m(K_n)=\frac{1}{2}n(n-1)$$

• 偶图：也称二部图。是指一个图，它的点集可以分解为两个(非空)子集X和Y，使得每条边的一个
  端点在X中，另一个端点在Y中。
  

• 完全偶图：完全偶图是指具有二分类$（X,Y）$的简单偶图，其中X的每个顶点与Y的每个顶点相连，若|X|=m，|Y|=n，则这样的偶图记为$K_{m,n}$，下图为$K_{2,3}$:
  

• 补图：
  对于一个简单图$G=(V,E)$，令集合
  E 1 = { u v ∣ u ≠ v , u , v ∈ V } E_1 = \{uv\vert u \neq v,u,v \in V\} E1​={
  uv∣u=v,u,v∈V}
  则称图$H=(V,E_1-E)$为G的补图，记为$H=\bar{G}$
  注：某些教材会将$E_1-E$表示为$E_1\backslash E$

• 自补图：如果图G与其补图同构，则称G为自补图
  注：如果两个数a、b满足$amodp=bmodp$，则称他们模p相等，记做$a\equiv b(modp)$
  有：
  $$n=0,1(mod4)也即n对4取余的结果为0或1$$

子图的相关概念

简单的说，图G的任意一部分（包括本身）都称为是图G的一个子图

• 定义：如果 $V(H)\subseteq V(G),E(H)\subseteq E(G)$ 且 $H$ 中边的重数不超过 $G$ 中对应边的条数, 则称 $H$ 为 G的子图, 记为 $H\subseteq G$当 $H\subseteq G,H\ne G$ 时, 称 $\mathrm{H}$ 是 $G$ 的真子图, 记为 $H\subset G$
• 顶点导出子图：如果 $V^{\prime }\subseteq V(G)$, 则以 $V^{\prime }$ 为顶点集，以两个端点均在 $V^{\prime }$ 中的边集组成的图, 称头 图G的点导出子图。记为: $G\left[V^{\prime }\right]$ 。
• 边导出子图：如果 $E^{\prime }\subseteq E(G)$, 则以 $E^{\prime }$ 为边集, 以 $E^{\prime }$ 中边的所有端点为顶点集组成的图, 称为 图G的边导出子图。记为: $G\left[E^{\prime }\right]$
• 图的生成子图：如果一个子图包含G的所有顶点，称该子图为G的一个生成子图

图运算

在图论中，将两个或更多的图按照某种方式合并，或者对一个图作某种形式的操作，可以得到很有意义的新图。将图合并或对一个图进行操作，称为图运算。图运算形式很多。

• 删点：设 $V^{\prime }\subseteq V(G)$, 在 $\mathbf{G}$ 中删去 $V^{\prime }$ 中的顶点和 $\mathbf{G}$ 中与之关 联的所有边的操作, 称为删点运算。记为 $G-V^{\prime }$ 特别地, 如果只删去一个点 $\mathbf{v}$, 则记为 G-v。
• 删边：设 $E^{\prime }\subseteq E(G)$, 在 $G$ 中删去 $E^{\prime }$ 中的所有边的操作, 称为删边运算。记为 $G-E^{\prime }$。特别地, 如果只删去一条边e, 则记为G-e。
  注: 删点、删边后得到的图是原图的子图。
• 图的并运算 ：设$G_1,G_2$是$G$的两个子图，$G_1$与$G_2$并是指由$V(G_1)\cup V(G_2)$为顶点集, 以 $E\left(G_1\right)\cup E\left(G_2\right)$ 为边集组成的子图。记为:$G_1\cup G_2$。特别是, 如果 ${\mathbf{G}}_1,{\mathbf{G}}_2$ 不相交(没有公共顶点), 称它们的并为直接并, 可以记为: $G_1+G_2$
• 图的交运算：设 ${\mathbf{G}}_1,{\mathbf{G}}_2$ 是 $\mathbf{G}$ 的两个子图, ${\mathbf{G}}_1$ 与 ${\mathbf{G}}_2$ 交是指由 $V\left(G_1\right)\cap V\left(G_2\right)$ 为 顶点集, 以 $E\left(G_1\right)\cap E\left(G_2\right)$ 为边集组成的子图。记为: $G_1\cap G_2$
• 图的差运算：设 $G_1,G_2$ 是两个图, $G_1$ 与 $G_2$ 的差是指从 $G_1$ 中删去 $G_2$ 中的边得到的 新图。记为 $G_1-G_2=G\left[E\left(G_1\right)\backslash E\left(G_2\right)\right]$ 注意是边导出子图
• 图的对称差运算（或称环和运算）：设 $G_1,G_2$ 是两个图, $G_1$ 与 $G_2$ 的对称差定义为:
  $$G_1\Delta G_2=\left(G_1\cup G_2\right)-\left(G_1\cap G_2\right)$$

顶点的度

顶点的度及其性质

• 定义：$G$ 的顶点 $v$ 的度 $d(v)$ 是指 $G$ 中与 $v$ 关联的边的数目, 每个环计算两次。分别用 $\delta (\mathrm{G})$ 和 $\Delta (\mathrm{G})$ 表示图G的最小与最大度。
• 奇点与偶点：奇数度的顶点称为奇点，偶数度的顶点称为偶点。
• k-正则图：设$G=(V,E)$为简单图，如果对所有$v\in V$,有$d(v)=k$，称图G为k-正则图。
• 定理（图论第一定理，又称握手定理）：定理: 图 $G=(V,E)$ 中所有顶点的度的和等于边数 $m$ 的 2 倍, 即:
  $$\sum _{v\in V(G)}d(v)=2m$$
• 推论1：在任何图中，奇点个数为偶数。
• 推论2：正则图的阶数和度数不同时为奇数。
  证明 : 设 $G$ 是 $k$-正则图, 若 $k$ 为奇数, 则由推论 1 知 正则图 $G$ 的度数必为偶数

图的度序列及其性质

一个图 $G$的各个点的度 $d_1,d_2,\dots ,d_n$构成的非负整数组 $\left(d_1,d_2,\dots ,d_n\right)$ 称为 $G$的度序列 。任意一个图 $G$ 对应唯一一个度序列, 图的度序列是 刻画图的特征的重要“拓扑不变量”。

• 拓扑不变量：图 G 的“拓扑不变量” 是指与图G有关的一个数或数组（向量）。它对于与图G同构的所有图来说不会发生改变。一个图G可以对应很多拓扑不变量。如果某组不变量可完全决定一个图, 称它为不变量的完全集。
• 定理: 非负整数组 $({\mathrm{d}}_1,{\mathrm{d}}_2,\dots ,{\mathrm{d}}_{\mathrm{n}})$是图的度序列的 充分必要条件是: ${\sum }_{i=1}^n{d}_i$ 为偶数。

证明：必要性由握手定理立即得到。如果 ${\sum }_{i=1}^n{d}_i$ 为偶数, 则数组中为奇数的数字个数必为偶数。按照如下方式作图 G :
若 ${\mathrm{d}}_1$ 为偶数, 则在 与之对应的点作 ${\mathrm{d}}_{\mathrm{i}}/2$ 个环; 对于剩下的偶数个奇数,两两配对后分别在每配对点间先连一条边，然后在每个顶点画$(d_j-1)/2$个环。该图的度序列就是已知数组。

关于图序列，主要研究3个问题：

1. 存在问题：什么样的整数组是图序列？
2. 计数问题：一个图序列对应多少不同构的图？
3. 构造问题：如何画出图序列对应的所有不同构图？
   研究现状: (1)彻底解决了，(2)解决得不好，(3)没有解决。

• 定理: 非负整数组$\pi =\left(d_1,d_2,\cdots ,d_n\right),d_1\ge d_2\ge \cdots \ge d_n,{\sum }_{i=1}^n{d}_i=2m$是图序列的充分必要条件是:${\pi }_1=\left(d_2-1,d_3-1,\cdots ,d_{d_1+1}-1,d_{d_1+2},\cdots ,d_n\right)$是图序列。
  例 $\pi =(6,5,4,3,2,2,2)$是否为图序列？如果是，作出对应的一个简单图。
  解：
  $$\begin{array}{rl}{\pi }_1& =(4,3,2,1,1,1)\\ {\pi }_2& =(2,1,0,0,1)\end{array}$$
  由于是图序列，所以原序列是图序列。
  

• 定理: (厄多斯1960)非负整数组
  $$\pi =\left(d_1,d_2,\cdots ,d_n\right),d_1\ge d_2\ge \cdots \ge d_n,\sum _{i=1}^n{d}_i=2m$$
  是图序列的充分必要条件是:
  ∑ i = 1 r d i ≤ r ( r − 1 ) + ∑ i = r + 1 n min ⁡ { r , d i } , 1 ≤ r ≤ n − 1 \sum_{i = 1}^{r} d_{i} \leq r(r-1)+\sum_{i = r+1}^{n} \min \left\{r, d_{i}\right\}, 1 \leq r \leq n-1 i=1∑r​di​≤r(r−1)+i=r+1∑n​min{
  r,di​},1≤r≤n−1

该定理证明很难!
上世纪60年代以来, 人们又研究所谓的唯一图序列问题

• 定理: 一个满足 ${\mathbf{d}}_2={\mathbf{d}}_{\mathbf{n}-1}$ 的图序列 $\pi =\left(d_1,d_2,\cdots ,d_n\right)$ 是唯一图序列的充分必要条件是下列条件之一满足:
  ( 1 ) d 1 = d n , d n ∈ { 1 , n − 1 , n − 2 } ( 2 ) d 1 = d n = 2 , n = 5 ( 3 ) d 1 > d 2 = d n = 1 ( 4 ) d 1 > d 2 = d n = 2 , d 1 ∈ { n − 1 , n − 2 } ( 5 ) n − 2 = d 1 = d n − 1 > d n ( 6 ) n − 3 = d 1 = d n − 1 > d n = 1 ( 7 ) n − 1 = d 1 > d 2 = d n = 3 , n = 6 \begin{align} &(1) d_{1}=d_{n}, d_{n} \in\{1, n-1, n-2\} \\ &(2) d_{1}=d_{n}=2, n=5 \\ &(3) d_{1}>d_{2}=d_{n}=1 \\ &(4) d_{1}>d_{2}=d_{n}=2, d_{1} \in\{n-1, n-2\} \\ &(5) n-2=d_{1}=d_{n-1}>d_{n}\\ &(6) n-3=d_{1}=d_{n-1}>d_{n}=1\\ &(7) n-1=d_{1}>d_{2}=d_{n}=3, n=6\\ \end{align} ​(1)d1​=dn​,dn​∈{
  1,n−1,n−2}(2)d1​=dn​=2,n=5(3)d1​>d2​=dn​=1(4)d1​>d2​=dn​=2,d1​∈{
  n−1,n−2}(5)n−2=d1​=dn−1​>dn​(6)n−3=d1​=dn−1​>dn​=1(7)n−1=d1​>d2​=dn​=3,n=6​​

图的频序列及其性质

• 定理：一个简单图$G$的$n$个点的度不能互不相同

证明：因为图G为简单图，所以：
$$△(G)\le n-1$$
情形1：若 $\mathrm{G}$ 没有孤立点，则 $1\le d(v)\le n-1,\forall v\in V(G)$
由鸽笼原理：必有两顶点度数相同;
情形 2: 若 $\mathrm{G}$ 只有一个孤立点, 设 $G1$ 表示 $\mathrm{G}$ 去掉孤
立点后的部分, 则: $1\le d(v)\le n-2,\forall v\in V\left(G_1\right)$
由鸽笼原理：在 ${\mathrm{G}}_1$ 里必有两顶点度数相同;
情形 3: 若 $\mathrm{G}$ 只有两个以上的孤立点, 则定理显然 成立。

• 定义: 设$n$阶图$G$的各点的度取$s$个不同的非负整数 $d_1,d_2,\dots ,d_s$ 又设度为 $d_i$ 的点有 $b_i$ 个 $(i=1,2,\dots ,s)$ , 则 $$\sum _{i=1}^s{b}_i=n$$故非整数组 $\left(b_1,b_2,\dots ,b_s\right)$ 是 $n$ 的一个划分，称为 $G$ 的频 序列。
• 定理：一个$n$ 阶图 $G$ 和它的补图有相同的频序列。

今天的文章图论及其应用 学习笔记（一）图的基本概念「建议收藏」分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。