图论部分整理
注：本部分源自ytr和hw的整理，我就加了一点
图的基本定理
一、引言
图与图模型
- 图(graph)G是由有限非空集合V及其二元子集E构成,其中V中元素称为顶点(vertex), E中元素称为边(edge)；集合V和E分别称为G的顶点集(vertex set)和边集(edge set)。
- 如果uv是图G的边, 那么就称u和v在G中是邻接的(adjacent). G中的顶点数和边数分别称为该图的阶(order)和边数(size) .
连通图
- 诱导子图(induced subgraph):设图F是图G的一个子图． 对于F中的任意顶点u和v, 只要uv是G 中的边, 则uv一定是F中的边,
- 链(walk):G中一条u-v链(walk) W 即为G 的一个顶点序列,满足:从u出发,到v结束,且图的顶点是邻接的．换句话说,可以把W表述成:
- 链的长度(length): 一条链所经过的边的总数(包括边重复出现的次数)
- 平凡链(trivial walk):长度为0;
- 迹(trail): 边没有被多次经过的u－v链．
- 路(path):链中没有重复的顶点,显然每条路都是迹。
定理1.6:
若因G包含一条长为$l$的$u-v$链, 则G包含一条长至多为$l$的
$u - v$ 路．(反证法证明)回路(circuit):长至少为3的闭迹.(顶点可以重复)
- 圈(cycle):没有顶点重复的回路
- (边)连通(connected):如果G 包含一条u-v路, 那么就称u 和ν 是连通的
(connected)。(注意是path,不是walk;但是有walk可以用定理1.6推出有path) - (图)连通(connected):如果对于G中每对不同顶点u,υ,G 都包含一条u-υ 路, 那么G称为是连通的(connected) .
- 不连通的(disconnected):一个不是连通的图G 称为不连通的(disconnected) .
- 连通分支(component): 若G的一个连通子图不是G的其他任何连通子图的真子图, 则称它为G的一个连通分支(component).(图G是连通的当且仅当G恰好有1个连通分支)
- 定理1.8:
设G是一个阶至少为3的图若G包含两个不同的顶点u和v,使得G-u与G-v是连通的, 则G是连通的．(设x,y 是G的两个顶点．分情形讨论:$1.\{x,y\}\neq \{u,v\}~2.\{x,y\}=\{u,v\}$) - 距离(distance): G 为n阶连通图, u和v为G 的两个顶点. u和v之间的距寓(distance)定义为G中包u-v路的最小长度,记为$d_{G}(u,v)$或$d(u,v)$
- 测地线(geodesic):长为$d(u,v)$的u－v路称为u-v测地线(geodesic)
- 直径(diameter) :连通图G 的所有顶点之间的最大距离称为G 的直径(diameter),记为diam(G).
- 定理1.9:
若G是一个阶至少为3的连通图, 则G包含两个不同的顶点u和v,使得G-u和G-v是连通的．(反证:考虑d(u,v)=diam(G), G-v假设不连通,然后找x,y$\in G-v$,假设x-u测地线,u-y测地线找矛盾) - 定理1.10:
设G是一个阶至少为3的图则G是连通的当且仅当G包含两个不同的顶点u和v,使得G-u和G-v都是连通的．(1.9+1.8得)
若干常见的图类
- 完全的(complete):如果图G的任何两个不同顶点都是邻接的,则称G是完全的,记为$K_{n}$,边数为$C_{n}^{2}$
- 补图(complement)$\bar{G}$:$\bar{G}$的顶点集为V($G$), 且对于$G$的每对顶点u,v, uv是$G$的边当且仅当uv不是$G$的边．
- 定理1.11:
若$G$是一个不连通图,则$\bar{G}$是连通的.(直接证明) - 二部图(bipartite graph): 若V(G)能够被划分为两个子集U和W(称为部集(partite set)) , 使得G的每条边必然连接U中一个顶点和W中一个顶点.
- 定理1.12:
非平凡图G是二部的当且仅当G不含奇圈．(等价于逆否命题:设G是一个不含奇圈的非平凡图, 则G是二部的．,反证之,挺麻烦的放了) - 完全二部图:二部图和完全图合体啦！|U|=s和|W|=t的完全二部图记做$K_{s,t}$或者$K_{t,s}$,当其中有一个是1的时候称为星(star)图
- 多部图,完全多部图和二部图完全二部图相似,e.g.$k_{1,1,1}$
- 联(join) $G+H$:由$G\cup U$通过连接G的每一个顶点与H的每一个顶点而获得
- 笛卡儿乘积(Cartesian product) $G\times H$:$V(G\times H)=V(G)\times V(H)$,$G\times H$的每一个顶点都是有序对$(u,v),u\in V(G),V\in V(H)$(不难发现总点数是两个图order的乘积)
- n方体(n-cube):$Q_{N}=Q_{N-1}\times K_{2},N\geq 2$; $Q_{1}=K_{2}$
多重图与有向图
- 环(loop):在多重图中, 允许连接顶点到其自身的边, 这样的边称为环(loop)
- 平行边(parallel edge):若两条或两条以上的边连接同一对(不同的) 顶点。
二、度
顶点的度
- 度(degree):顶点u 相关联的边的总数称为是u 的度(degree)记做$deg_{G}v$
- 度为0位孤立顶点,度为1为端点(end-vertex)
- G的最小度记做$\delta (G)$,最大度记做$Δ(G)$,若G为n阶图,有
- 定理2.1(图论第一定理):
若图G的边数为m, 则 - 推论2.3:
每一个图都有偶数个奇点。 - 定理2.4:
设G为n阶图,若对于G中任意两个不邻接的顶点u和v, 都满足:则G是连通的且diam(G)$\leq$2 - 推论2.5:
设G是阶为n的图,若$δ(G)≥ (n-1)/2$,则$G$是连通的(根据2.4找两个点直接证明) - 有向图中:
出度(outdegree) : od v 定义为D 中以v为起点的有向边个数,
入度(indegree) : id v 则定义为D中以v为终点的有向边个数．
正则图
- 正则的(regular):若G的顶点有相同的度即$δ(G)=Δ(G)$,称G是正则的；r-正则(r-regular)指:G中的每一个点的度为r。3-正则图被称为立方图(cubic graph)
- 定理2.6
设r和n为满足$0\leq r \leq n-1$的整数． 则存在n阶的r正则图当且仅当r和n 中至少有一个为偶数． - 定理2.7
对于任意图G和任意整数$r\geq\Delta(G)$, 都存在r正则图H, 它包含G作为诱导子图．(构造法证明,对于G,找G’,连接不是最大度的边构成G1,对于G1,找G1’…..一直构造直到$\Delta(G)=\delta (G)$;也可以另外加点,同理构造,(e.g.2.8))
度序列
- 度序列(degree sequence):若把图G所有顶点的度排成一个序列s,则s称为G 的度序列(degree sequence).
- 可图的(graphical): 一个由非负整数组成的有限序列称为是可图的(graphical) , 如果它是某个图的度序列.
- **定理2.10:
由非负整数构成的非增序列$s:d_1,d_2…d_n$是可图的当且仅当序列 是可图的.(就是对非增序列删除首项,假设为a,然后对后面的a项每项减一判断可不可图,如果判断不出来,继续……)**
三、同构
同构的定义
- 同构的(isomorphic):如果存在一个从V$(G_1)$到V($G_{2}$)的一一对应$ϕ$,使得:$u_1v_1∈E(G_1)$当且仅当$\phi(u_1)\phi(v_1)\in E(G_2)$,此时$ϕ$称为从$G_1$到$G_2$的一个同构(isomorphism).
- 定理3.1:
两个图$G_1$和$G_2$是同构的当且仅当它们的补图$\bar{G_1}$和$\bar{G_{2}}$是同构的． - 自补的(selιcomplementary):当$G≅ \bar{G} $,称G是自补的。
- 定理3.2:
如果G和H是同构图,则它们对应的顶点有相同的度． - 因此判断同构可以先看看有没有一样的度序列;然后看看里面的结构关系,比如度3的点连了啥,G中所有的结构性质它的同构图H也都应该有
- 定理3.5:
设G和H为同构图,则:
(a) G是二部的当且仅当H是二部的,
(b) G是连通的当且仅当H是连通的．
同构关系
- 定理3.6:
在图的集合中,同构是一种等价关系．
四、树
割边
割边：连通图G的一条边e=uv称为割边(bridge)，如果G−e是不连通的。
定理4.1：图G的边e是割边当且仅当e不在G的任一个圈上。
树
- 树：树(tree)是无圈的连通图。
- 双星：恰好包含两个非端点的树称为双星，这里两个点必然是邻接的。
- 有根树： 在有些情形下，选择树T的一个顶点，并指令它为T的根，此时T就成为一个有根树。
- 森林：无圈图称为森林。
- 定理4.2：图G是树当且仅当G的任何两个顶点都被唯一的路连接。
- 定理4.3：每个非平凡树至少有两个端点。
- 定理4.4：每个n阶树的边数是n−1。
- 推论4.5：阶位n且有k个连通分支的每个森林有n−k条边。
- 定理4.7：每个n阶连通图的边数至少为n−1。
- 定理4.8：设G是阶为n且边数为m的图，若G满足如下性质中的任意两个:
(1)G是连通的，(2)G是无圈的，(3)m=n−1，则G是树。 - 定理4.9：设T为k阶树，若图G满足δ(G)≥k−1，则T同构于G的某个子图。
最小生成树算法
- 定理4.10：每个连通图都含有一个生成树。
- 见算法导论整理
生成树的个数
- 定理4.15：(Gayley公式)具有指定顶点集的$n$阶不同树的个数是$n^{n-2}$
- 矩阵树定理：设$G$是顶点集为$V(G)=\{v_1, v_2, …, v_n\}$的图，设$A$=[$a_{ij}$]是G的邻接矩阵，$C$=[$c_{ij}$]为 $n\times n$ 矩阵，其中则$G$的生成树的个数为$C$的任一余子式的值。
五、图的连通度
割点
- 割点的定义：去掉这个点后，原图不再连通
- 定理5.1：设$v$是图$G$中与一条割边相关联的顶点，则$v$是$G$的割点当且仅当$deg v\geq 2$ 。
- 推论5.2：设$G$是一个阶至少为3的连通图。若$G$包含一条割边，则$G$一定包含一个割点。
- 定理5.3：设$v$是连通图$G$的一个割点，$u$和$w$是$G-v$不同连通分支中的两个顶点，则$v$位于$G$的任意一条$u-w$路上。
- 推论5.4：顶点$v$是连通图$G$的一个割点当且仅当存在与$v$不同的两个顶点$u$和$w$，使得$v$位于$G$的任意一条$u-w$路上。
- 定理5.5：设$G$是非平凡的连通图，$u\in V(G)$。若$v$是$G$中距离$u$最远的顶点，则$v$不是$G$的割点。
- 推论5.6：任意非平凡的连通图至少包含两个非割点的顶点。
块
- 不含割点的非平凡连通图称为是不可分图。
- 定理5.7：阶至少为3的图是不可分的当且仅当任意两个顶点都位于某个圈上。
- 若图$G$的一个不可分子图不是其他任一不可分子图的真子图，则称该子图是$G$的一个块。
- 定理5.8：设$R$是定义在非平凡连通图$G$的边集上的如下关系：对于$e,f\in E(G)$，若$e=f$或$e,f$位于$G$的同一个圈上，则$e,f$有关系$R$，记为$e\;R\;f$。则$R$是等价关系。
- 推论5.9：非平凡连通图$G$的任意两个不同的块$B_1$和$B_2$具有下面性质：
- $B_1$和$B_2$是边不相交；
- $B_1$和$B_2$至多有一个公共顶点；
- 若$B_1$和$B_2$有一个公共顶点$v$，则$v$是$G$的割点。
连通度
- 对于完全图$G$，$G$的最小顶点割的基数称为是$G$的点连通度，简称为$G$的连通度，用$\kappa(G)$表示。
- $\kappa(K_n)=n-1$
- 定理5.11：对于任意图$G$，点连通度$\le$边连通度$\le$最小度，
- 定理5.12：若$G$是一个立方图，则$\kappa(G)=\lambda(G)$.
- 定理5.13：若$G$是一个阶为$n$且边数为$m(m\geq n-1)$的图，则
$\kappa(G)\leq\lfloor\frac{2m}{n}\rfloor$ - 定理5.14：对于任意两个整数$r$和$n(2\leq r < n)$,
其中H(r, n)表示每个点度都为r的n阶连通图。
Menger定理
- 设$S$是图$G$的顶点集的一个子集，$u$和$v$是$G$的两个顶点，若$G-S$是不连通的，且$u$和$v$属于$G-S$的不同连通分支，则称$S$分离$u$和$v$。
- 定理5.16：设$u$和$v$是图$G$的不邻接的两个顶点，则$u-v$分离集中顶点的最小个数等于$G$中不相交的$u-v$路的最大个数。
- 定理5.17：一个非平凡图$G$是$k$联通的$(k\geq2)$当且仅当对于$G$的任意顶点$u,v$，$G$至少有$k$条内部不相交的$u-v$路。
- 推论5.18：设$G$为$k$连通图，$S$是由$G$中任意$k$个顶点构成的集合。若图$H$是由$G$通过添加一个新的顶点$w$以及连接$w$到$S$中所有顶点所得，则$H$也是$k$联通的。
- 推论5.19：若$G$为$k$连通图，$u,v_1,v_2,…,v_k$为$G$中$k+1$个不同顶点，则$G$有内部不相交的$u-v_i$路$(1\leq i\leq k)$.
- 定理5.20：若$G$为$k$连通图$(k\geq 2)$，则$G$中任意$k$个顶点均位于某个圈上。
- 定理5.21：对于图$G$的两个不同的顶点$u$和$v$,$G$中分离$u,v$的边的最小个数等于$G$中边不相交$u-v$路的最大个数。
- 定理5.22：一个非凡图$G$是$k$边连通的当且仅当对于$G$中任意两个不同的顶点$u,v$,$G$包含$k$条边不相交的$u-v$路。
六、旅行问题（可遍历性）
Euler图
- 迹：无重边
- 图$G$的一条回路称为是Euler回路,如果$C$包含$G$的每一条边.
- 含有Euler回路的图成为是Euler图.
- 对于一个连通图$G$,含有$G$的每一条边的开迹称为是$Euler$迹.
- 定理6.1:一个非平凡图$G$是$Euler$的当且仅当$G$的每个顶点的度都为偶数.
- 推论6.2:一个连通图$G$含有一条$Euler$迹当且仅当$G$且有两个度为奇数的定点.而且,$G$的每一条$Euler$迹始于一个度为技术的顶点而终止于另一个度为奇数的顶点.
- 设$G$和$H$是两个非平凡图.则$G\times H$是Euler的当且仅当$G$和$H$都是$Euler$的或者$G$和$H$的每个顶点度均为奇数.
Hamilton图
- 一个含图$G$每个定点的圈称为是$G$的一个Hamilton圈.
- 一个含有Hamilton圈的图称为是一个Hamilton图.
- 定理6.4: $Petersen$图不是$Hamilton$图.
- 定理6.5: 如果$G$ 是一个$Hamilton$图,则对$G$顶点的任一个非空子集$S$,都有
$k(G-S)\leq|S|$. - 设$G$为一个图,如果对$V(G)$的某个非空真子集$S$,有$k(G-S)>|S|$,则$G$不是$Hamilton$的. 此处k(G)表示G的连通分量的个数。
- 如果$G$含有一个割点,则$G$不是$Hamilton$的.
- 定理6.6:(Ore 定理)设$G$为一个$n(\geq 3)$阶的图,如果对于$G$的每对不邻接的顶点$u,v$,有
$degu+degv\geq n$,则$G$是$Hamilton$的. - 推论6.7:设$G$为一个$n\geq 3$阶的图,如果对于$G$中的每个顶点$v$,均有$degv\geq n/2$,则$G$是$Hamilton$的.
- 定理6.8: 设$u$和$v$是一个$n$阶图$G$的两个不邻接的顶点,并且$degv+degu\geq n$,则$G+uv$是$Hamilton$的当且仅当$G$是$Hamilton$的.
- 定理6.9:一个图是$Hamilton$的当且仅当它的闭包是$Hamilton$的.
- 推论6.10:如果$G$是一个阶至少为3的图,且它的闭包$C(G)$是一个完全图,则$G$是一个$Hamilton$图.
- 定理6.11:设$G$是一个$n\geq 3$阶的图,如果对于每个整数$j(1\leq j< n/2)$,$G$中度至少为$j$的顶点数小于$j$,则$G$是$Hamilton$的.
- 设G是一个 $n(n \ge 3)$阶的图。如果对于每个整数 j ($1\le j < n/2$)，G中度至多为j的顶点数小于j，则G是Hamilton的。
Hamilton链与Hamilton数
八、图中的匹配与分解
- 独立的: 图中边的集合称为是独立的,如该集合中任意两条边不邻接.
- 图$G$中边的一个独立集合成为是$G$的一个匹配.
- 邻域:设$G$为二部图,其部集为$U$和$W$,且$|U|\leq|W|$.对于$U$的非空子集$X$,$X$的邻域$N(X)$是指$X$中所有顶点邻域的并.
- 部集$U$称为是友好的,若对于$U$的任意非空子集$X$,均有$|N(X)|\geq X$.$(Hall’s condition)$
- 定理8.3: 设$G$为二部图,其部集为$U$和$W$,且$r=|U|\leq|W|$,则$G$包含一个基数为$r$的匹配当且仅当$U$是友好的.
- 定理8.4: 非空有限集族${S_1,S_2,…,S_n}$有一个互异代表元系当且仅当对于任一整数$k(1\leq k\leq n)$,集族中任意$k$个集合的并至少包含$k$个元素.
- 婚姻定理: 在一个由$r$个女人和$s$个男人构成的人群中,$1\leq r\leq s$.在熟识的男女之间可能出现$r$对婚姻当且仅当对每个整数$k(1\leq k\leq r)$,任意$k$个女人共认识至少$k$个男人.
- 最大基数的匹配为最大匹配.
- 若阶为$2k$的图$G$存在一个基数为$k$的匹配$M$,则称该匹配$M$为完美匹配.
定理8.6: 任意$r$正则二部图$(r\geq1)$均有一个完美匹配.
接下来都是按照英文书的定义
- 定理8.7: 对于n阶无孤立点图 $G$，$\alpha’(G)+\beta’(G)=n$
- 定理8.8: 对于n阶无孤立点图 $G$， $\alpha(G)+\beta(G)=n$
- $\alpha(G)$ 点独立数
- $\beta(G)$ 点覆盖数
- $\alpha’(G)$ 边独立数
- $\beta’(G)$ 边覆盖数
因子分解
- 图G的1正则生成子图成为G的1因子。1因子的边集为完美匹配。
- 定理8.10（Tutte定理）: 图G包含1因子当且仅当对于V(G)的任意真子集S，$k_0(G-S) \le |S|$. 其中$k_0$表示奇连通分支的数量。
- 定理8.11(Petersen’s 定理): 每个3正则无割边图包含1因子。
- 定理8.12: 任一至多含有两条割边的3正则图包含1因子。
- 称图G是可1因子分解的，若图G有1因子$F_1,F_2,…,F_r$ of $G$ 使得$\{E(F_1),E(F_2),…,E(F_r)\}$是 $E(G)$的一个划分.此时我们成$G$被因子分解为1因子$F_1,F_2,…,F_r$，这些因子构成了$G$的1因子分解。
- 定理8.13: Petersen不可1因子分解。
- 定理8.14: 对于任意整数$k$, $K_{2k}$可1因子分解.
- 定理8.17: 对于任意整数可 Hamiltonian因子分解. Hamiltonian因子分解指满足所有2因子都是哈密顿圈的一个2因子分解。
- 定理8.18: $K_9$可 $3K_3$因子分解.
- 定理8.19: $n\geq3$ 阶的Kirkman三元系存在当且仅当$n\equiv3(mod\,6)$
- 定理8.20: 对于所有整数$k\geq1$, $K_{2k}$可因子分解为k-1个哈密顿圈和一个1因子。