tags: Combinatorics GT
写在前面
这次总结一下图论距离与连通性这块的内容, 涉及到的算法不多, 但是概念还是比较多的, 分类比较一下.
主要概念
图的距离
设uuu和vvv是图GGG中给定的两个结点, 则两者之间的距离是指GGG中任意u−vu-vu−v测地线中变得数目, 记作d(u,v)d(u, v)d(u,v).
满足的公理:
正定对称三角不等式
定义
结点的偏心距: 该节点与它相距最远的结点间的距离, 记作e(v)e(v)e(v), 表示为
e(v)=maxu∈V(G)d(u,v).
e(v)=\max_{u\in V(G)}d(u,v).
e(v)=u∈V(G)maxd(u,v).
vvv的偏心结点: 满足e(v)=d(v,w)e(v)=d(v,w)e(v)=d(v,w)的结点www. 偏心结点不一定相互.
互为偏心的结点: 两个结点中的任何一个都是另一个的偏心结点.
图的半径(radius): 所有节点中最小偏心距, 记为rad(G)\mathrm{rad}{(G)}rad(G).
图的中心(center): 具有最小偏心距的结点所成集合, 记为C(G)C(G)C(G).
图的边界(boundary): 具有最大偏心距的结点所成集合. 记为P(G)P(G)P(G).
图的直径(diameter): 所有结点中的最大偏心距, 记为diam(G)\mathrm{diam}(G)diam(G).
相对节点对(径向节点对): 满足d(u,v)=diam(G)d(u,v)=\text{diam}(G)d(u,v)=diam(G)的一对结点(u,v)(u,v)(u,v). (其中一个节点为另一个的相对节点, 相对节点总是偏心的).
半径路: 中心节点集中的某个结点与其偏心结点间的测地线, 其长度必定为rad(G)\text{rad}(G)rad(G).
直径路: 相对节点对间的测地线, 其长度为diam(G)\text{diam}(G)diam(G).
连通图直径必定为非负整数, 非连通图直径规定为∞\infty∞.
树的距离之性质
树中给定的三个结点u,v,wu,v,wu,v,w, 若u,vu,vu,v邻接, 则d(u,w)−d(v,w)=1d(u,w)-d(v,w)=1d(u,w)−d(v,w)=1.树的所有偏心结点都是端节点树的所有相对节点都是端节点树的边界都由端节点构成对任意树, 每条直径路都包括其所有中心节点.树的中心由一个结点或两个邻接结点组成. (通过剪枝操作得到)
自补图与距离
自补图:G≅G~G\cong\widetilde{G}G≅G. 例如C5,P4C_5,P_4C5,P4.
树的重心
结点vvv处的分支: 以vvv为一个端节点的极大子树. 结点vvv的度等于vvv处分支的数目.结点vvv处的权: vvv所有分支中含有的最大边数.树的重心: 由具有最小权的结点组成的集合. (树的重心也是由一个节点或两个邻接结点组成)
图的连通性
割点: 若GGG是连通图, 删除其中某结点之后GGG变为非连通图, 被删除的结点即割点.(对非连通图来说, 删除某节点之后增加了连通分量数目也称为割点)割边(桥): 删除某边之后连通分量数目增加, 该边为割边.图的点连通度: 把图变为非连通图或者平凡图至少需要删除的结点数目, 记为κ(G)\kappa(G)κ(G). 连通图GGG有一个割点当且仅当κ(G)=1\kappa(G)=1κ(G)=1.图的点割集: 把图变成非连通图所需要删除的结点组成的集合.k−k-k−连通图: κ(G)≥k\kappa(G)\geq kκ(G)≥k.图的边连通度: 把图GGG变成非连通图或平凡图至少要删除的边的数目, 记为λ(G)\lambda(G)λ(G). 连通图GGG有一条割边当且仅当λ(G)=1\lambda(G)=1λ(G)=1.图的边割集: 把图变为非连通图所需要删除的边组成的集合.图的块: 图的极大连通子图.内部不相交u−vu-vu−v路: 连接uuu与vvv的两条路, 若除u,vu,vu,v外没有其他公共结点.边不相交u−vu-vu−v路: 若这两条路没有公共边. 任意内部不相交路一定是边不相交的.最小割: 分离u,vu,vu,v的最小边集.
主要定理
图的距离
设u,vu,vu,v是一连通图的两个邻接节点, 则有∣e(v)−e(u)∣≤1|e(v)-e(u)|\leq1∣e(v)−e(u)∣≤1.
主要采用三角不等式进行证明.
对任意图, 取直径路的两个端点u,vu,vu,v, 对任意结点www都有:
rad(G)≤diam(G)=d(u,v)≤d(u,w)+d(v,w)≤2maxi∈(u,v)d(i,w)≤2e(w),
\text{rad}(G)\leq \text{diam}(G)=d(u,v)\leq d(u,w)+d(v,w)\leq2\max_{i\in(u,v)}d(i,w)\leq2e(w),
rad(G)≤diam(G)=d(u,v)≤d(u,w)+d(v,w)≤2i∈(u,v)maxd(i,w)≤2e(w),
特别地, 当w∈C(G)w\in C(G)w∈C(G)时, 上述不等式变为:
rad(G)≤diam(G)≤2rad(G).
\text{rad}(G)\leq\text{diam}(G)\leq2\text{rad}(G).
rad(G)≤diam(G)≤2rad(G).
对任意树TTT. 若∣C(T)∣=1|C(T)|=1∣C(T)∣=1, 那么diam(T)=2rad(T)\text{diam}(T)=2\text{rad}(T)diam(T)=2rad(T), 若∣C(T)∣=2|C(T)|=2∣C(T)∣=2, 那么diam(T)=2rad(T)−1\text{diam}(T)=2\text{rad}(T)-1diam(T)=2rad(T)−1.
diam(G)≥3\text{diam}(G)\geq3diam(G)≥3, 则diamG~≤3\text{diam}\widetilde G\leq3diamG≤3.
分类讨论, 构造三种不同距离的集合
自补图GGG的直径小等3. (反证)
任意非平凡自补图直径为222或333.
图的连通性
对连通图GGG, 下述不等式成立:
κ(G)≤λ(G)≤δ(G).
\kappa(G)\leq\lambda(G)\leq \delta(G).
κ(G)≤λ(G)≤δ(G).
连通图GGG的一个中心属于GGG的以一个单独的块, 包含中心节点的块称为中心块.
Menger定理: 设u,vu,vu,v是图GGG的两个不同的非邻接节点, 那么所有连接u,vu,vu,v的内部不相交路的数目等于分离u,vu,vu,v的最小结点集所含的节点数目.
至少含有两个节点的图GGG是k−k-k−连通的当且仅当每对节点间存在连接他们的kkk条内部不相交路.
设u,vu,vu,v为GGG的两个不同的非邻接节点, 那么所有连接u,vu,vu,v的边不相交路的数目等于分离u,vu,vu,v的最小边集所含的边数.
一个应用: F−F-F−图
定义
图GGG若满足一下两个条件, 则称这个图为F−F-F−图. (far)
∣C(G)∣≥2|C(G)|\geq2∣C(G)∣≥2.若x,y∈C(G)x,y\in C(G)x,y∈C(G), 那么d(x,y)=rad(G)d(x,y)=\text{rad}(G)d(x,y)=rad(G).
对每个0≤j≤rad(G)0\leq j\leq \text{rad}(G)0≤j≤rad(G), 定义第iii个中心距离集:
Nj(G)={x:d(x,C(G))=j},
N_j(G)=\{x:d\big(x,C(G)\big)=j\},
Nj(G)={x:d(x,C(G))=j},
记为NjN_jNj. 有N0(G)=C(G)N_0(G)=C(G)N0(G)=C(G), 且若Nk(G)≠∅N_k(G)\ne\varnothingNk(G)=∅, 对∀j 一些性质 GGG是满足rad(G)≥2\text{rad}(G)\geq2rad(G)≥2的F−F-F−图, 若j=⌊r/2⌋j=\lfloor r/2\rfloorj=⌊r/2⌋, 那么Nj(G)≠∅N_j(G)\ne \varnothingNj(G)=∅.若图GGG是半径为rrr, 直径为ddd的F−F-F−图, 则GGG中任何一条直径路都有一条所有结点都在中心块内, 长度至少为d−rd-rd−r的子路.对任意正整数r,kr,kr,k, (k≥2)(k\geq2)(k≥2), 存在半径为rrr且具有kkk个中心结点的F−F-F−图.