写在前面

这次总结一下图论距离与连通性这块的内容, 涉及到的算法不多, 但是概念还是比较多的, 分类比较一下.

主要概念

图的距离

设$u$和$v$是图$G$中给定的两个结点, 则两者之间的距离是指$G$中任意$u-v$测地线中变得数目, 记作$d(u, v)$.

满足的公理:

1. 正定
2. 对称
3. 三角不等式

定义

• 结点的偏心距: 该节点与它相距最远的结点间的距离, 记作$e(v)$, 表示为

  \[e(v)=\max_{u\in V(G)}d(u,v).\]

• $v$的偏心结点: 满足$e(v)=d(v,w)$的结点$w$. 偏心结点不一定相互.

• 互为偏心的结点: 两个结点中的任何一个都是另一个的偏心结点.

• 图的半径(radius): 所有节点中最小偏心距, 记为$\mathrm{rad}{(G)}$.

• 图的中心(center): 具有最小偏心距的结点所成集合, 记为$C(G)$.

• 图的边界(boundary): 具有最大偏心距的结点所成集合. 记为$P(G)$.

• 图的直径(diameter): 所有结点中的最大偏心距, 记为$\mathrm{diam}(G)$.

• 相对节点对(径向节点对): 满足$d(u,v)=\text{diam}(G)$的一对结点$(u,v)$. (其中一个节点为另一个的相对节点, 相对节点总是偏心的).

• 半径路: 中心节点集中的某个结点与其偏心结点间的测地线, 其长度必定为$\text{rad}(G)$.

• 直径路: 相对节点对间的测地线, 其长度为$\text{diam}(G)$.

• 连通图直径必定为非负整数, 非连通图直径规定为$\infty$.

树的距离之性质

• 树中给定的三个结点$u,v,w$, 若$u,v$邻接, 则$d(u,w)-d(v,w)=1$.
• 树的所有偏心结点都是端节点
• 树的所有相对节点都是端节点
• 树的边界都由端节点构成
• 对任意树, 每条直径路都包括其所有中心节点.
• 树的中心由一个结点或两个邻接结点组成. (通过剪枝操作得到)

自补图与距离

• 自补图:$G\cong\widetilde{G}$. 例如$C_5,P_4$.

树的重心

• 结点$v$处的分支: 以$v$为一个端节点的极大子树. 结点$v$的度等于$v$处分支的数目.
• 结点$v$处的权: $v$所有分支中含有的最大边数.
• 树的重心: 由具有最小权的结点组成的集合. (树的重心也是由一个节点或两个邻接结点组成)

图的连通性

• 割点: 若$G$是连通图, 删除其中某结点之后$G$变为非连通图, 被删除的结点即割点.(对非连通图来说, 删除某节点之后增加了连通分量数目也称为割点)
• 割边(桥): 删除某边之后连通分量数目增加, 该边为割边.
• 图的点连通度: 把图变为非连通图或者平凡图至少需要删除的结点数目, 记为$\kappa(G)$. 连通图$G$有一个割点当且仅当$\kappa(G)=1$.
• 图的点割集: 把图变成非连通图所需要删除的结点组成的集合.
• $k-$连通图: $\kappa(G)\geq k$.
• 图的边连通度: 把图$G$变成非连通图或平凡图至少要删除的边的数目, 记为$\lambda(G)$. 连通图$G$有一条割边当且仅当$\lambda(G)=1$.
• 图的边割集: 把图变为非连通图所需要删除的边组成的集合.
• 图的块: 图的极大连通子图.
• 内部不相交$u-v$路: 连接$u$与$v$的两条路, 若除$u,v$外没有其他公共结点.
• 边不相交$u-v$路: 若这两条路没有公共边. 任意内部不相交路一定是边不相交的.
• 最小割: 分离$u,v$的最小边集.

主要定理

图的距离

• 设$u,v$是一连通图的两个邻接节点, 则有$

  e(v)-e(u)

  \leq1$.

  主要采用三角不等式进行证明.

• 对任意图, 取直径路的两个端点$u,v$, 对任意结点$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),\]

  特别地, 当$w\in C(G)$时, 上述不等式变为:

  \[\text{rad}(G)\leq\text{diam}(G)\leq2\text{rad}(G).\]

• 对任意树$T$. 若$

  C(T)

  =1$, 那么$\text{diam}(T)=2\text{rad}(T)$, 若$

  C(T)

  =2$, 那么$\text{diam}(T)=2\text{rad}(T)-1$.

• $\text{diam}(G)\geq3$, 则$\text{diam}\widetilde G\leq3$.

  分类讨论, 构造三种不同距离的集合

• 自补图$G$的直径小等 3. (反证)

• 任意非平凡自补图直径为$2$或$3$.

图的连通性

• 对连通图$G$, 下述不等式成立:

  \[\kappa(G)\leq\lambda(G)\leq \delta(G).\]

• 连通图$G$的一个中心属于$G$的以一个单独的块, 包含中心节点的块称为中心块.

• Menger 定理: 设$u,v$是图$G$的两个不同的非邻接节点, 那么所有连接$u,v$的内部不相交路的数目等于分离$u,v$的最小结点集所含的节点数目.

• 至少含有两个节点的图$G$是$k-$连通的当且仅当每对节点间存在连接他们的$k$条内部不相交路.

• 设$u,v$为$G$的两个不同的非邻接节点, 那么所有连接$u,v$的边不相交路的数目等于分离$u,v$的最小边集所含的边数.

一个应用: $F-$图

定义

图$G$若满足一下两个条件, 则称这个图为$F-$图. (far)

1. $

   C(G)

   \geq2$.

2. 若$x,y\in C(G)$, 那么$d(x,y)=\text{rad}(G)$.

对每个$0\leq j\leq \text{rad}(G)$, 定义第$i$个中心距离集:

\[N_j(G)=\{x:d\big(x,C(G)\big)=j\},\]

记为$N_j$. 有$N_0(G)=C(G)$, 且若$N_k(G)\ne\varnothing$, 对$\forall j<k$, 有$N_j(G)\ne\varnothing$.

一些性质

• $G$是满足$\text{rad}(G)\geq2$的$F-$图, 若$j=\lfloor r/2\rfloor$, 那么$N_j(G)\ne \varnothing$.
• 若图$G$是半径为$r$, 直径为$d$的$F-$图, 则$G$中任何一条直径路都有一条所有结点都在中心块内, 长度至少为$d-r$的子路.
• 对任意正整数$r,k$, $(k\geq2)$, 存在半径为$r$且具有$k$个中心结点的$F-$图.