《代数图论》第一章-基本概念

图

图$X$由顶点集$V(X),$ 边集$E(X)$组成. 每个(无向)边是一个无序对$\{x,y\},$ 常用$xy$来简化表示. 若$xy\in E,$ 则称$x,y$点相邻, 记为$x\sim y.$ 若存在双射$\varphi: V(X)\rightarrow V(Y),$ 使得$V(X)$中$x\sim y$当且仅当$V(Y)$中$\varphi(x)\sim\varphi(y),$ 则称图$X$与$Y$同构. 画图表示时, 常用数字对顶点标号.

称图是完全(complete)的, 若其两两顶点均相邻. 记有$n$个顶点的完全图为$K_n.$ 称图是空(empty)的, 若边集为空集且至少有一个顶点; 称图是无效(null)的, 若边集和点集都是空集. 这两个概念均是为叙述上的方便提出的.

前面的图均为简单图. 有时将边集$E(X)$替换为有向边集$A(X),$ 称为有向图. 此时边是有序对, 在图示中用箭头表示, 称为弧(arc). 有时也将无向图视为每个无向边均是两个有向边的有向图. 一般默认均考虑简单图. 顶点集事实上可以有无穷多个元素, 但本书默认考虑有限图.

子图

若图$Y$满足$V(X)\subset V(Y),$ $E(X)\subset E(Y),$ 则称$Y$为$X$的子图. 若还满足$V(Y)=V(X),$ 则称$Y$为$X$的生成子图. 若子图$Y$中顶点相邻当且仅当它们在$X$中相邻, 则称$Y$为$X$的诱导子图. 可以看出, 生成子图是通过删边得到的, 而诱导子图是通过删点及其邻边得到的.

有几类与子图相关的重要概念: 若子图为完全图, 则称其为团(clique). 若某顶点集的诱导子图是空的, 则称其为独立集. 图$X$最大团的大小记为$\omega(X),$ 最大独立集大小记为$\alpha(X).$ 这是图的很重要的两个属性.

图上由顶点$x$到$y$长度为$r$的道路, 指一个由$r+1$个不同顶点构成的序列, 以$x$为首, $y$为尾, 且序列中相邻的顶点在图中也相邻. 若图上任意两点有以其为首尾的道路, 则称图是连通的, 否则即为不连通的.

图是不连通的等价于我们可以将图$X$顶点集分为两个集合$R,S,$ 使得$R$中顶点与$S$中顶点均不相邻. 这时我们可以说图$X$是顶点集$R$和$S$诱导子图的无交并. 极大的连通诱导子图, 称为图$X$的连通分支, 简记为分支.

一个环(cycle)指一个连通图, 每个顶点恰有两个邻点; 图中的环即指作为子图的环. 容易证明若图中每个点都至少有两个邻点, 那么图必定包含一个环. 连通的无环图称为树, 而无环图可以拆分为若干极大连通无环图的无交并, 因此称为森林. 若某生成子图为树, 则称其为生成树. 易见图有生成树当且仅当它是连通的. 极大生成森林即指由每个分支的生成树组成的生成子图.

自同构

图$X$到自身的同构即为自同构. 容易证明自同构全体构成一个群, 记为$\operatorname{Aut}(X).$ 显然$\operatorname{Aut}(X)\subset \operatorname{Sym}(V(X)).$ 后者指对称群, 即集合$V(X)$的所有置换. 一个基本的例子是$\operatorname{Aut}(K_n)\cong \operatorname{Sym}(V(K_n))=S_n.$ 一般来说, 判断两个图是否同构, 以及某个图是否有非平凡自同构并不容易.

$v$在置换$g$下的像记为$v^g.$ 当$g\in \operatorname{Aut}(X)$时, 对子图$Y\subset X,$ 可以保边地定义子图$Y^g\subset X.$ $Y$与$Y^g$自然是同构的.

顶点$x$的度/价(valency), 指$x$的邻点个数. 图$X$的最大(最小)度, 即指所有顶点度的最大(最小)值. 若图的每个顶点度均为$k,$ 则称其为$k-$正则图.

引理 1.1. 若$x\in X,$ $g\in \operatorname{Aut}(X),$ 则$x$与$x^g$度相同.

证: 只需利用$x$及其全部邻点的诱导子图$N(x)$满足$N(x)\cong N(x)^g=N(x^g)$即可.

图$X$中两顶点$x,y$的距离$d_X(x,y),$ 指连接$x,y$最短路的长度. 若$X$明了, 可简记距离为$d(x,y).$ 一个简单的引理如下:

引理 1.2. $\,\forall\,x,y\in X,$ $g\in \operatorname{Aut}(X),$ $d(x,y)=d(x^g,y^g).$

图$X$的补图$\overline X$是这样一个图: 它满足$V(X)=V(\overline X),$ 但两顶点在$\overline X$中相邻当且仅当它们在$X$中不相邻.

容易证明如下引理:

引理 1.3. $\operatorname{Aut}(X)\cong \operatorname{Aut}(\overline X).$

若$X$是有向图, 那么对于同构, 我们要求它是保方向的.

同态

给两个图$X,Y,$ 映射$f:V(X)\rightarrow V(Y)$称为同态, 若$x\sim y\in X\Rightarrow f(x)\sim f(y)\in Y.$ 前面的同构当然也是同态. 图$X$为二分图, 若$V(X)$可划分为$V_1,V_2,$ 使得每个边的端点分别在这两个集合中. 一个同态的例子是$V(X)\rightarrow V(K_2),$ 将$V_i$映到顶点$i$.

这一例子引申出图的染色问题. 一个图的正常染色(proper colouring), 指从$V(X)$到某有限(颜色)集的映射, 使得相邻的点映至不同的颜色. 如果$X$可由$k$种颜色正常染色, 称其可被$k-$染色. 称最小的$k$为图$X$的着色数(chromatic number), 记为$\chi(X).$ 染上某种颜色的全体点构成独立集, 称为一个颜色类(colour class). 对于至少有一条边的二分图, 它的着色数即为$2.$

引理 1.4. $X$的着色数是最小的$r,$ 使得存在$X\rightarrow K_r$的同态.

证: 对同态$f:X\rightarrow Y,$ 易见对$y\in Y,$ $f^{-1}(y):=\{x\in V(X): f(x)=y\}$为独立集. 因此若有$X$到$K_r$的同态, 以$K_r$顶点为$r$个不同颜色, 对$X$中顶点按其像上色即可, 从而$\chi(X)\le r.$

若$\chi(X)$可被$r-$染色, 记颜色集为$\{1,\cdots,r\},$ 将每个颜色类映到$K_r$中相应顶点即可. 因为$X$中相邻的点颜色不同, 而不同颜色在$K_r$中彼此相邻.

图$X$到其子图$Y$的同态$f$称为收缩, 若$f|_Y$为恒等映射. 此时称$Y$为$X$的收缩核. 如对如下的图, 按红色箭头所示构造同态, 则内侧的五边形成为原图的收缩核.

对有向图的同态, 只需将保相邻改为保有序对即可. 需要注意的是, 以上讨论均默认图中无环. 边称为圈(loop), 若其两端点是同一个点. 允许圈存在的图的同态的性质将大有不同. 一个例子是将任意顶点集映到有圈的点的映射都是同态.

图$X$到自身的同态称为自同态, 自同态全体构成幺半群. 自同构群包含在其中.

循环图

接下来介绍很重要的一类图, 称为循环图(circulant graph): 它是一个有向图$X=X(\mathbb{Z}_n,C),$ 集合$C\subset \mathbb{Z}_n\setminus\{0\}.$ 其顶点为$\mathbb{Z}_n$中元素, $(i,j)$为$X$中的弧当且仅当$j-i\in C.$ $X(\mathbb{Z}_n,C)$称为$n$阶循环图, 以$C$为连接集.

若$\,\forall\,c\in C,$ $-c\in C,$ 那么$(i,j)$为弧当且仅当$(j,i)$为弧, 从而$X$可以视为无向图. 易见前面提到的环即为$X(\mathbb{Z}_n,\{\pm 1\}),$ 是循环图的一种, 记为$C_n$.

Johnson图

对正整数$v\ge k\ge i,$ 图$J(v,k,i)$是这样一个无向图: 设有含$v$个元素的集合$\Omega,$ 图以$\Omega$中含$k$个元素的全体子集为顶点, 两点连边当且仅当其对应子集之交含$i$个元素. 因此它含$\binom{v}{k}$个顶点, 为正则图, 每点以$\binom{k}{i}\binom{v-k}{k-i}$为度.

引理 1.5. $J(v,k,i)\cong J(v,v-k,v-2k+i).$

证: 将每个含$k$元素子集映到它在$\Omega$中的补集即可. 易见两补集交集含$v-2k+i$个元素当且仅当原来的两集合含$i$个元素. 因此这样的映射是同构.

由该引理, 我们总是可默认$v\ge 2k.$ 这时称$J(v,k,k-1)$为Johnson图, $J(v,k,0)$为Kneser图. 由于$\Omega$中元素的置换诱导子集间的置换, 我们有如下引理:

引理 1.6. $S_v\subset \operatorname{Aut}(J(v,k,i)).$

边图

图$X$的边图(line graph)$L(X)$是这样一个图: 它以$X$的边为顶点, 两顶点连边当且仅当它们在$X$中对应的边有公共顶点.

星形图$K_{1,n}$为由$1$个顶点与其$n$个邻点构成的图. 它的边图即为完全图$K_n.$ 对于环$C_n,$ 它与其边图同构.

对每个边考虑其两个顶点, 有如下引理:

引理 1.7. 若$X$是$k-$正则图, 那么$L(X)$是$2k-2$正则的.

$X$中每个度为$k$的顶点都决定了$L(X)$中大小为$k$的团. 若$X$含$n$个顶点, 则$L(X)$中有对应的$n$个团, 使得$L(X)$的每个顶点最多在其中的两个团中, 每条边恰在其中一个团里. 事实上通过构造的方法, 有如下的逆命题:

定理 1.8 (Krausz). 非空图是某个图的边图当且仅当它的边集可以划分为若干个团, 使得每个顶点最多在其中两个团中.

若$X$不含三角形(大小为$3$的团), 则当$L(X)$中某个点有两邻点, 两邻点都在前面所述的某个团中时, 这个点也在该团中. 不然它们对应的边在$X$即构成三角形. 因此由$X$顶点决定的$L(X)$中的团都是极大的.

显然$X\cong Y\Rightarrow L(X)\cong L(Y),$ 但反过来不见得对, 比如$L(K_{1,3})\cong L(K_3).$ 不过Whitney证明了事实上这是唯一一个连通情况下的反例. 我们来证明下面弱一点的命题.

引理 1.9. 若$X,Y$最小度大于$3,$ 则$X\cong Y\Leftrightarrow L(X)\cong L(Y).$

证: 只需注意到在边图中, 含三个点以下的团不见得还原为以某顶点出发星形图, 但三个点以上的团还原时必然还原为星形图. 只需说明四个边两两有公共顶点时, 一定是$K_{1,4}$的形状. 不然其中三个边还原时一定还原为三角形, 而这时无法再添加第四条边使得两两边有公共顶点.

从而在每个顶点度均大于$3$的情况下, $n$个顶点对应的$n$个极大团大小大于$3,$ 且反过来每个大小大于$3$的极大团都对应一个顶点. 从而顶点集到大小大于$3$的极大团全体间有一个双射, 且满足顶点相邻当且仅当对应的极大团有公共点. 因此图的属性与其边图属性互相决定, 故$X\cong Y\Leftrightarrow L(X)\cong L(Y).$

另一个关于边图的有趣描述是:

定理 1.10 (Beineke). 图是边图当且仅当它的每个最多含六个点的诱导子图是边图.

我们称二分图是半正则的, 若它有$2$-染色使得颜色相同的点度相同. 最简单的例子是完全二分图$K_{m,n},$ 由两个含$m$个点与$n$个点的独立集构成, 其间两两连接.

引理 1.11. 若连通图$X$的边图$L(X)$为正则图, 则$X$是正则的, 或是半正则的二分图.

证: 设$L(X)$是$k-$正则的, 那么$X$中每对邻点的度之和恒为$k+2.$ 因此连通的$X$中所有点的度最多只有两种取值. 若只有一种取值, 那么就是正则图; 如果有两种不同取值, 那么按这两种取值染色即可. 这样只有相异颜色的点度之和满足要求, 因此相同颜色的点必不相邻. 且这样染色后, 颜色相同的点度相同, 是半正则的.

可平面图

我们已经看到, 用图示来表示图很方便. 若图可被无交线地绘制出来, 则称其为可平面图(planar graph). 更精确地, 我们考虑将图映到平面上. 将顶点映至点, 边映至连接两点的连续无自交的曲线, 称这样的映射为平面嵌入, 若无公共点的边对应曲线不相交, 有公共顶点的边对应的曲线仅在平面上对应点相交. 图称为可平面的当且仅当存在这样一个平面嵌入.

平面图(plane graph)为取好平面嵌入的可平面图. 平面图的边将平面划分为若干区域, 称为平面图的面. 除了一个区域外, 其它区域都是有界的, 称这个无界的区域为无穷面或外面(external face). 面的长度指框住它边的个数.

著名的欧拉公式给出平面图点线面的关系:

定理 1.12 (Euler). 若连通平面图有$n$个顶点, $e$条边与$f$个面, 那么$n-e+f=2.$

可平面图称为极大可平面图, 如果再添加一条边就不再是可平面的了. 如果可平面图的平面嵌入有长度大于$3$的面, 那么一定可以再添一条边. 因此极大可平面图的平面嵌入所有面长度均为$3$. 若每个点度至少是$2$, 则每条边恰在两个面中, 我们有$2e=3f,$ 从而$e=3n-6.$ 事实上若含$n$个点的可平面图有$3n-6$条边, 它一定是极大的. 这样的图称为平面三角剖分.

一个图的平面嵌入有很多种, 这会导致平面图的面有所不同, 如下图所示. 一个很重要的拓扑结论是, $3-$连通的图本质上只有唯一一种嵌入方式.

给定平面图$X,$ 我们可以生成对偶图(dual graph)$X^\ast,$ 以$X$的面为$X^\ast$顶点, 对每条$X$中两面的公共边, 绘制一条(跨公共边的)$X^\ast$中的边连接两面对应的顶点. 注意$X^\ast$中可能有重边(multiple edge), 即两个点间连接多个边. 除了特殊说明, 我们默认不考虑图中出现重边的情况.

若图与其对偶图同构, 则称其自对偶(self-dual), 如完全图$K_4.$ 对连通的图$X,$ 可以说明$X\cong (X^\ast)^\ast.$ 嵌入的概念可以从平面推广到任意曲面上, 对偶也类似. 一个例子是非可平面图的完全图$K_6$可以嵌入到射影平面上, 是射影平面的一个三角剖分.

另一个例子是完全图$K_7$不是可平面图, 也不能嵌入到射影平面上, 但是可以嵌入到环面上.

文章最后更新于 2021-09-16 14:51:40