《超图及其应用》笔记(1)-基本概念

定义

超图是图的推广, 我们仍记顶点集为$V=\{x_1,\cdots,x_n\},$ 将边集记为$E=(E_1,\cdots,E_m),$ $E_i$中的点视为连接在一起. 我们要求$E$满足:

1. $E_i\neq \varnothing$,

2. $\bigcup_{i=1}^mE_i=V.$

将超图记为$H=(V,E).$ 由于第二个条件, 有时也直接隐去$V$, 直接记$H=E$为超图.

类似于简单图, 也有简单超图的概念: $\,\forall\,E_i\subset E_j,$ $i=j.$ 即超边间没有包含关系. 因此简单超图里也是没有重边的. 我们同样有关联矩阵$A=(a_{ij})_{n\times m},$ $a_{ij}=1$当且仅当$x_i\in E_j$, 否则取零.

称$H’=(V’,E’=(e_j))$为超图$H$的子超图, 若$V’\subset V,$ $E’\subset E,$ 且$e_j\subset V’.$ 称$H’=(E_j|j\in J)$为由$J$导出的边导出子图, 对于$A\subset X,$ 称$H’=(E_j\cap A|E_j\cap A\neq \varnothing)$为由$A$导出的点导出子图. 一个特别的导出子图是$H(x)=\{E_j|x\in E_j\}$, 称其为星.

类似于对偶图, 我们也有对偶超图. 称$H^\ast =(X_1,\cdots,X_n)$为$H=(E_1,\cdots,E_m)$的对偶超图, 点集$e_1,\cdots,e_m$对应于$H$中的边, 而超边$X_i=\{e_j|x_i\in E_j\}.$ 注意到利用星的定义, 我们有:

$$H^\ast =(V^\ast =E,E^\ast =(H(x))_{x\in V}).$$

对偶超图有好的性质, 如它的关联矩阵$A^\ast $就是原超图关联矩阵$A$的转置, 此时便能直观地发现$(H^\ast )^\ast =H.$

记$n(H)=|V|$为超图$H$的阶, $m(H)=|E|$为超图的边数, $r(H)=\max_j|E_j|$为超图的秩, $s(H)=\min_j|E_j|$为反秩(anti-rank), 也称为余秩(co-rank). 若$r(H)=s(H)$, 称$H$为一致超图, 此时所有超边元素个数相等. 一个秩$r$简单一致超图也称为$r$一致的.

度

记$x$的度为$d_H(x)=m(H(x)),$ 图的最大度记为$\Delta(x)=\max d_H(x).$ 若每个点具有相同的度$k$, 称超图$H$是$k$正则的, 此时每个点总在$k$个超边内. 注意到正则与一致的概念构成对偶, $H$是$k$正则的当且仅当$H^\ast $是$k$一致的. 同时也有:

$$\Delta(H)=r(H^\ast ),\quad r(H)=\Delta(H^\ast ).$$

命题 1. 一个$n$元组$d_1\ge \cdots\ge d_n$为一个阶为$n$秩为$r$的一致超图的度序列, 当且仅当$\sum_{i=1}^nd_i\ge d_1r$为$r$的倍数, 且$d_n\ge 1.$

必要性显然, 对于秩$r$的一致超图$H$, 每个边含$r$个点. 每个点统计度时, 每个超边被统计了$r$次, 因此$\sum_{i=1}^nd_i=m(H)r,$ 同时显然有$m(H)\ge d_1.$ $d_n\ge 1$也是自然的条件.

对于充分性, 只需给定算法构造合适的超图. 事实上用贪心算法就够了, 每次取度最高的$r$个点放到一条超边里即可, 然后重新排列度序列使得其递减. 我们需要验证算法是可执行到最后的, 即不会出现非零度点小于$r$的情况.

在一次操作时, 若最高度对应点全部被选中, 则$\sum_{i=1}^n d_i-r\ge (d_1-1)r,$ 操作后度序列条件仍然满足. 若最高点对应度未全部被选中, 则原先至少有$r+1$个点具相同的最高度, $\sum_{i=1}^n d_i\ge d_1(r+1).$ 若$d_1\ge r,$ 则

$$\sum_{i=1}^n d_i-r\ge d_1r;\eqno{(\ast )}$$

若$d_1<r,$ 则由于$\sum_{i=1}^n d_i$为$r$的倍数, 它大于等于$d_1r+r,$ 因此同样有不等式$(\ast ).$ 综上, 经过一次操作后, 新的度序列仍然满足全部条件(除去零度点).

接下来利用反证法, 假设操作到某时刻后非零度点不够$r$个, 那么$\sum_{i=1}^n d_i\le (r-1)d_1<d_1r,$ 不满足条件, 产生矛盾. 因此该算法总能操作到$d_1=0$的情况, 也即超图构建完毕.

定理 2. 给定整数列$r_1,\cdots,r_m,$ $d_1\ge \cdots \ge d_n,$ 存在超图$H=(E_1,\cdots,E_m),$ $X=\{x_1,\cdots,x_n\},$ 使得$d_H(x_i)=d_i,$ $|E_j|=r_j,$ 当且仅当$\sum_{j=1}^mr_j=\sum_{i=1}^nd_i,$ 且$\sum_{j=1}^m\min\{r_j,k\}\ge \sum_{i=1}^k d_i,$ $\,\forall\,k\le n.$

首先说明充分性, 我们尝试利用网络流来构造一个超图. 取源$a$汇$z.$ 记每个超边为$j,$ 每个点为$x_i.$ 以容量$r_j$连接$(a,j),$ 以容量$d_i$连接$(x_i,z),$ 以容量$1$连接$(j,x_i).$ 对于整数流, 若$(j,x_i)$有流, 则在超图中令$x_i\in E_j.$ 若整数流流量为$\sum_{i=1}^nd_i=\sum_{j=1}^mr_j,$ 则每个$E_j$中恰有$r_j$个点, 而每个点$x_i$又恰在$d_i$个超边中, 超图构建完毕.

由最大流最小割定理, 我们只需说明$\sum_{i=1}^nd_i$就是一个最小割, 从而最大流可选取为整数流, 流量满足前面的条件. 假设已经割掉$\{d_i|i\notin I\},$ $I\subset \{1,\cdots,n\}.$ 那么只需说明在进一步的割法中, $\sum_{i\in I}d_i$达到最小. 其它的割法需要阻断$(a,x_i)_{i\in I},$ 为此对于每个$j,$ 要么直接割掉前面的$r_j,$ 要么割掉$k$个$(j,x_i)_{i\in I}.$ 从而$j$贡献的最小费用是$\min\{r_j,k\},$ 对$j$求和发现条件恰好说明了这样的费用不比割$\{d_i\}_{i\in I}$低. 这就说明了结论.

对于必要性, $\sum_{i=1}^nd_i$将每个超边统计了$r_j$遍, 这就是$\sum_{j=1}^mr_j.$ 对于另一个条件, 我们仍来利用网络流. 超图的存在性直接说明了最大流的存在性, 从而最小割就是$\sum_{i=1}^nd_i.$ 因此前述其他的割法不比直接割汇低, 这就表述了欲证的条件.

其它性质

对于$1\le r\le n,$ 定义阶为$n$的$r$一致完全超图$K_n^r$为由基数为$n$的$r$子集全体作为超边的超图.

定理 3. 每个$n$阶简单超图都满足$\sum_{E\in H}\binom{n}{|E|}^{-1}\le 1,$ 进一步$m(H)\le \binom{n}{[\frac{n}{2}]}.$ 后式取等当且仅当$H=K^{[\frac{n}{2}]}_n,$ 当$n$为奇数时也可以是$K^{\frac{n+1}{2} }_n.$

可以通过哈斯图来辅助分析. 从$\varnothing$到$X$的经过结点$E$的道路共有$|E|!(n-|E|)!$条. 对$E’\neq E,$ 道路间没有重复, 因为它们不具有包含关系. 因此总道路满足$n!\ge \sum_{E\in H}|E|!(n-|E|)!.$ 这就是第一个不等式. 对于第二个不等式, 由$\binom{n}{|E|}\le \binom{n}{[\frac{n}{2}]}$立即可得.

对于取等的情况, 若$n$为偶数, $|E|=\frac{n}{2},$ 是一致超图, 进而可得到完全性; 若$n$为奇数, $|E|=\frac{n-1}{2}$或$\frac{n+1}{2}.$ 只需说明不一致时边数一定不够即可.

称超图$H$是可分离的, 若$\bigcap_{E\in H(x)}E=\{x\}.$ 注意到图$H$是可分的当且仅当$H^\ast $是简单超图. 从而由前面的定理, 可以得到可分离超图的度序列$d_1\ge \cdots\ge d_n$满足

$$\sum_{i=1}^n\binom{m}{d_i}^{-1}\le 1.$$

称超图$H$是线性的, 若$|E_i\cap E_j|\le 1,$ $\,\forall\,i\neq j$. 利用反证法简单讨论即有:

命题 4. $H$线性当且仅当对偶图$H^\ast $线性.

定理 5. 对每个$n$阶线性超图, 有$\sum_{E\in H}\binom{|E|}{2}\le \binom{n}{2}.$ 若进一步$H$是$r$一致的, 则边数满足$m(H)\le\frac{n(n-1)}{r(r-1)}.$ 取等当且仅当$H$是Steiner系统$S(2,r,n).$ Steiner系统是完全超图$K^r_n$的边导出子图, 要求每对点恰在一个超边中.

超图之间存在同构关系. 称超图$H\cong H’,$ 若存在双射$f:V\rightarrow V’,$ 使得$e=\{x_1,\cdots,x_k\}\in E$ $\Leftrightarrow$ $f(e)=\{f(x_1),\cdots,f(x_k)\}\in E’.$

命题 6. $H\cong H’\Leftrightarrow H^\ast \cong {H’}^\ast $

利用关联矩阵判断即可.

文章最后更新于 2022-09-19 19:43:37