Graph Theory and Network Algorithm 0 图的基本概念

发表于 2020-11-22 更新于 2022-04-08 分类于 UCAS ， Courses 阅读次数：

图论与网络算法 (070105M04003H)，图的基本概念。

图的基本概念

概念

图（graph）：一集元素及它们之间的某种关系；$（V,E）$，$V={v_1,v_2,...,v_n}$为顶点集，$E={(v_1,v_2),(v_2,v_3),...,(v_{n-1},v_n})$为$V$中元素组成的某些无序对的集合，称之边集。$|V|=\upsilon$称之阶，$|E|=\epsilon$称之边数。
空图（empty graph）：$\{G|E(G)=\varnothing\}$。
零图（null graph）：$\{G|V(G)=\varnothing\}$。（顶点集为空则边集自然为空）
顶点度（degree）：图$G$中顶点$v$所关联的边的数目，记为$d_G(v)$。
最大度：$\Delta(G)=\max \{d_G(v)|v\in V(G)\}$。
最小度：$\delta(G)=\min \{d_G(v)|v\in V(G)\}$。
补图（complement）：$\bar G: V(\bar G)=V(G), E(\bar G)=\{(x,y)|(x,y)\notin E(G\}$。

子图（subgraph）：$H:V(G)\subseteq V(G),E(G)\subseteq E(G)$，记为$H\subseteq G$。
生成子图（spanning subgraph）：$H:H\subseteq G,V(H)=V(G)$。

顶点集是架子，生成子图就像衣服架子一样把图支撑了起来，所以又称为支撑子图。

点导出子图（induced subgraph）：给定$V'\subseteq V(G)$，以G中两端点均属于$V'$的边作为边集形成的子图，记为$G[V']$。
边导出子图（edge-induced subgraph)：给定$E'\subseteq E(G)$，以$E'$中所有边的端点作为顶点集形成的子图，记为$G[E']$。

边导出子图没有孤立的顶点。

设$V'\subseteq V(G)$，记$G-V'$为从图$G$中删除顶点子集$V'$（连同它们关联的边一起删去）所获得的子图。

$G-V'$当$V'$不为空时不是生成子图；可看作$G$由$V-V'$导出的点导出子图。

设$E'\subseteq E(G)$，记$G-E'$为从图$G$中删除边子集$E'$（但不删除它们的端点）所获得的子图。
简记$G-\{v\}$为$G-v$，$G-\{e\}$为$G-e$。

设$G_1=(V_1,E_1)$，$G_2=V_2,E_2$。

并(Union)：$(V_1 \cup V_2,E_1 \cup E_2)$，记为$G_1\cup G_2$。若$V_1\cup V_2=\varnothing$，可记为$G_1+G_2$，称之和（addition）或不交并（disjoint union）。
联/连接（join）：无公共顶点集的两图不交并，再在边集上添加$\{xy|x\in V(G_1),y\in V(G_2\}$后形成的图，记为$G_1\vee G_2$。
对称差（symmetric difference）：$(V,E_1\bigoplus E_2)$，记为$G_1\bigoplus G_2$。

$A\bigoplus B=(A\cup B)-(A\cap B)=(A-B)\cup (B-A).$

途径（walk）：点边交替序列。
迹（trail）：边不重复的途径。闭迹也称为回路（circuit）。
路（path）：顶点不重复的途径。
圈（cycle）：中途点不重复的笔迹。
距离（distance）：$\forall u,v\in V(G)$，从$u$到$v$的最短路，记为$d_G(u,v)$。

连通分支（connected branch，component）：$G[V_i],i=1,2,...,w$，其中$V_i$为$V(G)$的一个划分。
图$G$连通$\Longleftrightarrow$$w=1$。

生成树（spanning tree）：设树$T:T\subseteq G,V(T)=V(G)$，称之$G$的一个生成树。（即G的一个支撑子图，且为树）

关联矩阵

\[ M(G)=\left[\begin{array}{ccc} m_{11} & m_{12} & \cdots & m_{1\epsilon} \\ m_{21} & m_{22} & \cdots & m_{2\epsilon} \\ \vdots & \vdots & \ddots & \vdots \\ m_{\upsilon1} & m_{\upsilon2} & \cdots & m_{\upsilon\epsilon} &\end{array}\right] \]

其中$m_{ij}$表示顶点$v_i$与边$e_j$关联的次数。

邻接矩阵

\[ A(G)=\left[\begin{array}{ccc} a_{11} & a_{12} & \cdots & a_{1\upsilon} \\ a_{21} & a_{22} & \cdots & a_{2\upsilon} \\ \vdots & \vdots & \ddots & \vdots \\ a_{\upsilon1} & a_{\upsilon2} & \cdots & a_{\upsilon\upsilon} &\end{array}\right] \]

其中$a_{ij}$表示顶点$v_i$与边$v_j$关联的次数。

离心率：$e(u)=\max\limits_{v\in V(G)}d(u,v)$。
半径：$rad\ G=\min\limits_{v\in V(G)}e(u)$。
直径：$diam\ G=\max\limits_{v\in V(G)}e(u)=\max\limits_{uv\in E(G)}d(u,v)$。

定理

Theorem 1.1.1

$\sum\limits_{v\in V(G)}d(v)=2\epsilon.$

奇度顶点的个数为偶数。

若仅有两个奇度顶点，则此两点必连通。（否则该两点所在连通分支的奇度顶点数为1）

简单图$G$，$\delta(G)\ge2\Longrightarrow G$含圈。

简单图$G$，$\delta(G)\ge3\Longrightarrow G$含偶圈，且$G$中各个圈长的最大公因数是1或2。

取最长路证明。

Theorem 1.1.2

二部图$\Longleftrightarrow$不含奇圈的图。

$\Longrightarrow$ 叙述证明；

$\Longleftarrow$ 构造性证明，$\forall u\in V(G)$，设$X/Y = \{v\in V(G)| u,v间距离为奇/偶数\}$ ，欲证$\forall e=v_1v_2:v_1,v_2$分别属于$X,Y$。

Theorem 1.1.3

连通图$\Longrightarrow\epsilon\ge \upsilon-1$。

对$\upsilon$做数学归纳法，
$\upsilon=k+1$时考虑$G-v,、\forall v\in V(G)$。

$v=2n,\delta\ge n\Longrightarrow$连通图。

反证，至少$\exists G[V_i]:|V_i|\le n$。

Theorem 1.3.1

树的等价定义：

$G$是树，即$G$为连通且不含圈；
$G$中无环边（loop）且任两顶点之间有且仅有一条路；
$G$中无圈且$\epsilon=\upsilon-1$；
$G$连通且$\epsilon=\upsilon-1$；
$G$连通且$\forall e\in E(G):G-e$不连通；
$G$无圈且$\forall e\in E(\bar{G}),G+e$恰有一个圈。

$1\Longrightarrow2$ 仅需证唯一性，反证，若不唯一必有圈；

$2\Longrightarrow3$ 对$\upsilon$做数学归纳法，$\upsilon=k+1$时考虑$G-uv,、\forall uv\in E(G)$；

$3\Longrightarrow4$ 反证；

$4\Longrightarrow5$ 保证图的连通性至少需要$v-1$条边（Theorem 1.1.3）；

$5\Longrightarrow6$ 先证$G$无圈，得$G$是树，再由（2）得$G+e$有圈；反证，若该圈不唯一则与树的定义矛盾；

$6\Longrightarrow1$ 即证$G$连通，$\forall u,v\in V(G)$，分$u,v$是否相邻两种情况讨论。

非平凡树至少含有两个一度顶点（叶子）。

平凡树：只有一个顶点的树。

反证，考虑Theorem 1.1.1（度边关系）。

Theorem 1.4.1

每个连通图都有生成树。

考虑$G$的连通的生成子图中边数最少的一个，反证其无圈（若有圈则去除圈上任意边，仍为连通的生成子图，与其取法矛盾）。

算法

最短路问题

Dijkstra算法（[/ˈdaɪkstrə/]）
- 思想：标号法，$\forall v\in \bar{S},l(v):=\min\{l(v),l(v_i+w(v_iv)\}$。
- 时间复杂度：$O(v^2)$

最小生成树问题

Kruskal算法
- 思想：逐次选取不与已选取边构成圈的权值最小的边。
- 时间复杂度：$O(v_2\log_2 v)$

练习

$\epsilon = \upsilon +1\Longrightarrow\exists v\in V(G):\ d(v)\ge3$

反证，由Theorem 1.1.1（度边关系）得出矛盾。

$\forall u,v\in V(G)$，若$uv\in E(G)$，则$!\exists w\in V(G)-\{u,v\}:uw,vw\in E(G)$；若$uv\notin E(G)$，则$|\{w|uw,vw\in E(G)\}|=2$，求证$G$为正则图。（$G$无三角形，且任意两个不相邻顶点恰有两个共同邻点，求证$G$为正则图。）

$\forall u,v\in V (G)$，设$d(u)=k$，若$u,v$相邻，可知$d(v)\ge d(u)$，由对称性可知$d(v)=d(u)$；若否，$\forall u'\in N(u),\ d(u)=d(u')=d(v)$。

二部图$G=(X,Y)$，$n>2$，$\forall x \in X:d(x)<|Y|-1,\ \forall y\in Y:d(y)>0$，求证$\exists x_1,y_1,x_2,y_2: x_1y_1,x_2y_2\in E(G),\ x_1y_2,x_2y_1\notin E(G)$。

取$X$中度最大的点$x_1$（取法可以从$X$中没有度为$|Y|-1$的点联想到），则$\exists y_2\in Y: x_1y_2\notin E(G)$。而由已知$d(y)>0$，故$\exists x_2\in X: x_2y_2\in E(G)$，且有$d(x_2)\le d(x1)$，故$|N(x_2)|\le |N(x_1)|$。$\because y_2\in N(x_2),\ y_2\notin N(x_1),\ \therefore \exists y_1:y_1\notin N(x_2),y_1\in N(X_1)$（这是因为$N(x_2)$与$N(x_1)$没有包含关系，所有一定有错开的元素）。

连通图$G:\upsilon(G)\ge2,\epsilon(G)<\upsilon(G)\Longrightarrow G$至少有$2$个一度顶点。

由连通图性质得$\epsilon\ge\upsilon-1$，得$\epsilon=\upsilon-1$，故$G$是非平凡树，得证。

连通图中两条最长路必有公共顶点。

反证，说明形如“工”的图中可以取出一条更长的路。

简单图$G:\delta(G)\ge\frac{\upsilon(G)-1}{2}\Longrightarrow G$连通。

反证，若$G$不连通，必有一个连通分支的顶点数$\le \frac{\upsilon}{2}$，与最小度矛盾。

树$T:\Delta(T)\ge k\Longrightarrow T$至少有$k$个$1$度顶点。

设有$x$个一度顶点，则$2(\upsilon-1)=2\epsilon=\sum\limits_{v\in V(G)}d(v)\ge k+x+2(\upsilon-1-x)$，推出$x\ge k$。

证明：含$\epsilon$边的$\upsilon$阶图至少有$\epsilon-\upsilon+1$个圈。

考虑其生成树有$\upsilon-1$条边，
每多一边则形成一个不同的圈。

1. 设$T,T'$为$G$的两颗生成树，$\forall e\in E(T)-E(T')$，证明$\exists e'\in E(T')-E(T):T'+e-e'$和$T-e+e'$都是$G$的生成树。
2. 设$G$是各边权不等的赋权连通图，不使用Kruskal算法证明：$G$只有一颗权值最小的生成树。

考虑$k=\min\{i|e_i\in\{e_1,e_2,...,e_{\upsilon-1}\},e_i\notin T\}$，
即$e_k$是第一条属于$T$但不属于$T'$的边，则$T'+e_k$有一圈，此圈上$\exists e':e'\in T',e'\notin T$（否则$T$有圈），这样取出来的$e=e_k,e'$满足条件；

反证。

修改Kruskal算法用以：
1. 求赋权连通图的最大权生成树；
2. 求不连通赋权图中的最小权生成森林。

只需把最大权改为最小权；

修改结束条件为$i+1=\upsilon(G)-1$。

总结

证明$\epsilon$和$\upsilon$的关系时，可以考虑对$\upsilon$做数学归纳法。