写在前面
最近开始更新图论笔记系列, 没办法做到面面俱到了, 就把自己觉得重要的内容放上来, 有任何问题欢迎大家指正.
主要概念
- 图(graph): 关系的数学表达, 由两个集合: 非空结点集$V$和有限的边集$E$组成.
- 图的阶(order): 集合$V(G)$的基数(势)$n$.
- 图的规模(size): 集合$E(G)$的基数$m$.
- 邻接(adjacent): 指两个节点之间有边连接.
- 关联(incident): 边与左右两个节点关联.
- 结点的度(degree): 与结点相邻接的结点数.
- 孤立点: 度为$0$的结点.
- 最小度: 图中所有结点的最小度数, 记为$\delta(G)$.
- 最大度: 图中所有结点的最大度数, 记为$\Delta(G)$.
- 正则图(regular graph): 若图中所有结点有相同的度数, 则$\delta(G)=\Delta(G)$.
- $r-$正则图: 图中所有结点度都为$r$.
- $u-v$通道(途径, walk): 指从结点$u$出发, 经过一个交互的结点和边的序列, 最后回到结点$v$的路径, 其中连续的结点和边是相关联的.
- 通道的长度: 经过边的数量, 结点和边可以重复.
- 迹(trail): 没有重复边的通道, 结点可以重复.
- 路(路径, path): 结点都不相同的迹.
- 回路(圈, cycle): 即封闭的路径(闭路, closed path), 由于结点不同则边一定不同, 所以回路也可以称为闭迹(closed trail).
- $u-v$路: 将$u$和$v$连接起来的路.
- 连通图(connected graph): 图中任意两个结点之间都存在路.
- 测地线路(测地线, 最短路): 长度最短的$u-v$路.
- 子图: $H$结点集与边集都为$G$的结点集和边集的子集, 且对$H$中任意一条边, 其两个节点都在结点集$V(H)$中. $G$称为$H$的超图.
- 连通分量(connected component): 极大连通子图.
- 生成子图(spanning subgraph): $V(H)=V(G)$.
- 导出子图(induced subgraph): 子图边集中包含了原图$G$中连接子图点集的所有边.
- 完全图(complete graph): 所有结点对都邻接. 具有$n$个结点的完全图记为$K_n$.
- 平凡图(trivial graph): $K_1$.
- 圈(circle): 含有$n$个结点的圈记为$C_n$.
- 路(path): 含有$n$个结点的路记为$P_n$, 并且满足$P_i=K_1, P_2=K_2$.
- 完全二分图(complete bipartite graph): 记为$K_{m,n}$, 是指图的结点集可以分成两个非空集合$A,B$, 分别含有$m,n$个结点, $A$中每个结点均要与$B$中每个结点相关联,且都只与$B$中结点相关联.
- 星: 只有一个结点度为$n$, 其余$n$个结点度为$1$的完全二分图, 记为$K_{1,n}$.
- 轮(wheel): $W_{1,n}=K_1+C_n$. 利用两个图的和操作得到.
图同构
- 图同构: 图$G$中结点$uv$邻接当前节点它们在图$H$中相应的结点也邻接, 记为$G\cong H$. 图同构则节点的度一定相同.
- 度序列: 含有$n$个结点图$G$的度序列指按照结点度数排列的$n-$元非递增序列. 有相同度序列的两图不一定同构.
- 可绘图序列: 可以表示某个图的非负整数的非递增序列.
- 可绘图序列的必要条件: 度数之和为偶数.
可绘图序列的判定算法
- 序列$S$中删除第 1 个数$k$.
- 如果$S$的第一个数后的$k$个数都大等 1, 则将这$k$个数分别都减去 1 得到新序列$S’$; 否则停止, 得出原序列不绘图. 若$S’$全是$0$, 停止, 得到原序列可绘图.
- 将 2 得到的序列$S’$重新排列, 得到非增序列$S^*$.
- 令$S=S^*$,转步骤 1.
例子:判断序列$[3,3,2,1,1,1]$是否可绘图.
直接根据上述算法进行判断, 下面给出 Python 以及 C++代码:
S1 = [3, 2, 2, 1, 1, 1]
S2 = [5, 4, 4, 3, 3, 3, 3, 2, 2, 1]
S3 = [7, 7, 4, 3, 3, 3, 2, 1]
S4 = [6, 5, 4, 3, 3, 3, 2, 0]
def isGraphic(S):
if len(S) == 0 or sum(S) % 2 == 1:
return False
# 只要不是全0序列, 就进入循环
while S.count(0) != len(S):
k = S.pop(0)
if k <= len(S):
for i in range(k):
if S[i] >= 1:
S[i] -= 1
else:
return False
S.sort(reverse=True)
else:
return False
return True
print(isGraphic(S1))
print(isGraphic(S2))
print(isGraphic(S3))
print(isGraphic(S4))
"""
True
True
False
True
"""
对于 python 代码, 用到了一些列表操作的内置函数, 进一步优化可以得到下面的代码:
def isGraphic(S):
if len(S) == 0 or sum(S) % 2 == 1:
return False
# 只要不是全0序列, 就进入循环
while S[0] != 0:
k = S.pop(0)
if k <= len(S):
for i in range(k):
if S[i] >= 1:
S[i] -= 1
else:
return False
S.sort(reverse=True)
return True
// C++代码实现
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
bool isGraphic(vector<int> &S) {
if (S.size() == 0 || accumulate(S.begin(), S.end(), 0) % 2 == 1)
{
return false;
}
while(S[0] != 0) {
int k = S[0];
S.erase(S.begin());
if (k <= S.size())
for (int i=0;i<k;i++) {
if (S[i] >= 1)
S[i]--;
else
return false;
}
sort(S.rbegin(), S.rend());
}
return true;
}
int main(int argc, char const *argv[])
{
vector<int> S1 = {3, 2, 2, 1, 1, 1},
S2 = {5, 4, 4, 3, 3, 3, 3, 2, 2, 1},
S3 = {7, 7, 4, 3, 3, 3, 2, 1},
S4 = {6, 5, 4, 3, 3, 3, 2, 0};
cout<<isGraphic(S1)<<endl;
cout<<isGraphic(S2)<<endl;
cout<<isGraphic(S3)<<endl;
cout<<isGraphic(S4)<<endl;
return 0;
}
图的基本操作
并与和
两个图的并必须是不相交的, 对于图$G$和$H$, 有
\[G\cup H:\begin{cases} V(G\cup H)=V(G)\cup V(H)\\[5pt] E(G\cup H)=E(G)\cup E(H)\\ \end{cases}\]两个不相交图的和$G+H$是指在$G\cup H$的基础上, 增加$G$的每个结点与图$H$的每个结点相连接得到的边.
边与结点的删除
- 设$v$是$G$ 的结点, 则$G-v$是指从图$G$ 中删除结点$v$, 并将所有与结点$v$相关联的边删除.
- 设$e$是图$G$ 的一条边, 那么$G-e$是指从图$G$ 中删除边$e$.
补图
类比集合的补运算, 图$G$的补图$\overline{G}$满足$V(\overline G)=V(G)$, 并且当且仅当$uv\notin E(G)$时, $uv\in E(\overline G)$.
- 自补图: 图$G$与其补图同构. 自补图$G$满足阶$n$可以表示成$4k$或者$4k+1$的形式, $k$为非负整数, 并且图$G$有$n(n-1)/4$条边.
笛卡尔积
又称叉乘, 指两个图的结点之间进行笛卡尔积. 满足结合律.
利用笛卡尔积可以定义如下的几种图.
超立方体
递归定义, 可由定义式扩展到高维空间.
\[Q_1=K_2,Q_n=K_2\times Q_{n-1}.\]网格
\[M(m,n)=P_m\times P_n,\\ M(p,q,r)=P_p\times P_q\times P_r.\]线图
线图$L(G)$的结点集由原图$G$边构成, 将原图$G$结点进行标记之后容易得到线图.
边收缩
设$uv$是$G$的一条边, 将节点$u,v$和与这两个结点相关联的边都去掉, 并添加一个结点$uv^$, 使得$uv^$与原结点$u,v$相邻接的结点邻接, 记为$G/uv$.