Machine-translated from Chinese.
定义
超图是图的推广, 我们仍记顶点集为$V=\{x_1,\cdots,x_n\},$
将边集记为$E=(E_1,\cdots,E_m),$ $E_i$中的点视为连接在一起.
我们要求$E$满足:
$E_i\neq \varnothing$,
$\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;\tag*{(\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
definition
Hypergraph is a generalization of graph, we still remember the vertex set as $V=\{x_1,\cdots,x_n\},$
The points in the edge set $E=(E_1,\cdots,E_m),$ $E_i$ are considered to be connected together.
We require $E$ to satisfy:
$E_i\neq \varnothing$,
$\bigcup_{i=1}^mE_i=V.$
Mark the hypergraph as $H=(V,E).$. Due to the second condition, sometimes $V$ is also hidden directly.
Directly record $H=E$ as hypergraph.
Similar to simple graphs, there are also simple hypergraph Concept: $\,\forall\,E_i\subset E_j,$
$i=j.$ That is, there is no inclusion relationship between hyperedges. Therefore, there are no duplicate edges in simple hypergraphs.
We also have correlation matrix $A=(a_{ij})_{n\times m},$
$a_{ij}=1$ if and only if $x_i\in E_j$, otherwise it is zero.
Call $H'=(V',E'=(e_j))$ a hypergraph $H$ sub-hypergraph, if$V'\subset V,$
$E'\subset E,$ and $e_j\subset V'.$
Call $H'=(E_j|j\in J)$ derived from $J$ Edge derived subgraph, for $A\subset X,$
Call $H'=(E_j\cap A|E_j\cap A\neq \varnothing)$ derived from $A$ Click to export subgraph.
A special derived subgraph is $H(x)=\{E_j|x\in E_j\}$, call it star.
Similar to dual graphs, we also have dual hypergraphs.
Call $H^\ast =(X_1,\cdots,X_n)$ $H=(E_1,\cdots,E_m)$ Dual hypergraph,
The point set $e_1,\cdots,e_m$ corresponds to the edge in $H$, and the hyperedge $X_i=\{e_j|x_i\in E_j\}.$
Note that using the definition of star, we have:
$$
H^\ast =(V^\ast =E,E^\ast =(H(x))_{x\in V}).
$$
The dual hypergraph has good properties. For example, its correlation matrix $A^\ast $ is the transpose of the correlation matrix $A$ of the original hypergraph.
At this point you can intuitively discover $(H^\ast )^\ast =H.$
Let $n(H)=|V|$ be the hypergraph $H$ level, $m(H)=|E|$ is a hypergraph Number of sides,
$r(H)=\max_j|E_j|$ is a hypergraph rank,
$s(H)=\min_j|E_j|$ is anti-rank, also known as co-rank.
If $r(H)=s(H)$, call $H$ consistent hypergraph, at this time the number of all hyperedge elements is equal.
A simple consistent hypergraph of rank $r$ is also called $r$ consistent.
Degree
Record the degree of $x$ as $d_H(x)=m(H(x)),$ and record the maximum degree of the graph as $\Delta(x)=\max d_H(x).$
If each point has the same degree $k$, the hypergraph $H$ is said to be $k$ regular,
At this time, each point is always within $k$ hyperedges. Note that the concepts of regularity and consistency form a dual,
$H$ is regular to $k$ if and only if $H^\ast $ is consistent with $k$.
Also available:
$$
\Delta(H)=r(H^\ast ),\quad r(H)=\Delta(H^\ast ).
$$
Proposition 1. An $n$ tuple $d_1\ge \cdots\ge d_n$ is the degree sequence of a consistent hypergraph with order $n$ and rank $r$, if and only if $\sum_{i=1}^nd_i\ge d_1r$ is a multiple of $r$, and $d_n\ge 1.$
The necessity is obvious. For a consistent hypergraph $H$ of rank $r$, each edge contains $r$ points. When each point counts,
Each hyperedge is counted $r$ times, so $\sum_{i=1}^nd_i=m(H)r,$
At the same time, it is obvious that $m(H)\ge d_1.$ $d_n\ge 1$ is also a natural condition.
For sufficiency, it is only necessary to construct a suitable hypergraph given the algorithm. In fact, a greedy algorithm is enough,
Just take the $r$ points with the highest degree each time and put them into a hyperedge, and then rearrange the degree sequence to make it decrease.
We need to verify that the algorithm is executable to the end, that is, there will be no non-zero degree points smaller than $r$.
In one operation, if all corresponding points with the highest height are selected,
Then the sequence condition is still satisfied after $\sum_{i=1}^n d_i-r\ge (d_1-1)r,$ operation.
If the highest point correspondences are not all selected, there are at least $r+1$ points with the same highest height.
$\sum_{i=1}^n d_i\ge d_1(r+1).$ if $d_1\ge r,$ then
$$
\sum_{i=1}^n d_i-r\ge d_1r;\tag*{(\ast )}
$$
If $d_1<r,$
Then since $\sum_{i=1}^n d_i$ is a multiple of $r$, it is greater than or equal to $d_1r+r,$
Therefore, there is also the inequality $(\ast ).$. In summary, after one operation,
The new degree sequence still satisfies all conditions (except for the zero degree point).
Next, use proof by contradiction, assuming that after the operation reaches a certain moment, there are not enough $r$ non-zero degree points,
Then $\sum_{i=1}^n d_i\le (r-1)d_1<d_1r,$ does not meet the conditions, resulting in a contradiction.
Therefore, this algorithm can always operate to the situation $d_1=0$, that is, the hypergraph is constructed.
Theorem 2. Given an integer sequence $r_1,\cdots,r_m,$ $d_1\ge \cdots \ge d_n,$, there exists a hypergraph $H=(E_1,\cdots,E_m),$ $X=\{x_1,\cdots,x_n\},$ such that $d_H(x_i)=d_i,$ $|E_j|=r_j,$ if and only if $\sum_{j=1}^mr_j=\sum_{i=1}^nd_i,$ and $\sum_{j=1}^m\min\{r_j,k\}\ge \sum_{i=1}^k d_i,$ $\,\forall\,k\le n.$
First to illustrate the sufficiency, we try to use network flow to construct a hypergraph. Take source $a$ sink $z.$
Denote each hyperedge as $j,$ and each point as $x_i.$ and connect $(a,j),$ with capacity $r_j$.
Join $(x_i,z),$ with capacity $d_i$ Join $(j,x_i).$ with capacity $1$ For integer streams,
If $(j,x_i)$ has a flow, then let $x_i\in E_j.$ in the hypergraph
If the integer flow rate is $\sum_{i=1}^nd_i=\sum_{j=1}^mr_j,$
Then there are exactly $r_j$ points in each $E_j$, and each point $x_i$ is in exactly $d_i$ hyperedges.
The hypergraph is constructed.
According to the maximum flow minimum cut theorem, we only need to explain that $\sum_{i=1}^nd_i$ is a minimum cut,
Therefore, the maximum flow can be selected as an integer flow, and the flow satisfies the previous conditions.
Assume that $\{d_i|i\notin I\},$ $I\subset \{1,\cdots,n\}.$ has been cut off
Then it only needs to be stated that in further cuts, $\sum_{i\in I}d_i$ reaches the minimum.
Other cuts require blocking $(a,x_i)_{i\in I},$ for each $j,$
Either cut off the front $r_j,$ directly or cut off the $k$ $(j,x_i)_{i\in I}.$
Therefore, the minimum cost contributed by $j$ is $\min\{r_j,k\},$
The sum discovery condition for $j$ just shows that the cost is not lower than that of cutting $\{d_i\}_{i\in I}$.
This illustrates the conclusion.
For necessity, $\sum_{i=1}^nd_i$ counts each hyperedge $r_j$ times,
This is $\sum_{j=1}^mr_j.$ For another condition, we still use network flow.
The existence of the hypergraph directly illustrates the existence of the maximum flow, so the minimum cut is $\sum_{i=1}^nd_i.$
Therefore, the other cutting methods mentioned above are no lower than the direct cutting of foreign exchange, which expresses the conditions to be proved.
Other properties
For $1\le r\le n,$
Define the $r$ uniform complete hypergraph $K_n^r$ with order $n$ as a hypergraph in which all subsets $r$ with cardinality $n$ serve as hyperedges.
Theorem 3. Every simple hypergraph of order $n$ satisfies $\sum_{E\in H}\binom{n}{|E|}^{-1}\le 1,$ and further $m(H)\le \binom{n}{[\frac{n}{2}]}.$. The latter expression is equivalent if and only if $H=K^{[\frac{n}{2}]}_n,$. When $n$ is an odd number, it can also be $K^{\frac{n+1}{2} }_n.$.
Haas diagram can be used to assist analysis.
There are $|E|!(n-|E|)!$ roads from $\varnothing$ to $X$ passing through node $E$.
For $E'\neq E,$ there are no duplications between roads because they do not have an inclusive relationship.
Therefore, the total road satisfies $n!\ge \sum_{E\in H}|E|!(n-|E|)!.$, which is the first inequality.
For the second inequality,
Available immediately from $\binom{n}{|E|}\le \binom{n}{[\frac{n}{2}]}$.
For the case of equality, if $n$ is an even number, $|E|=\frac{n}{2},$ is a consistent hypergraph,
Then completeness can be obtained; if $n$ is an odd number, $|E|=\frac{n-1}{2}$ or $\frac{n+1}{2}.$
It only needs to be stated that the number of sides must not be enough when they are inconsistent.
Hypergraph $H$ is called detachable, if$\bigcap_{E\in H(x)}E=\{x\}.$
Note that the graph $H$ is separable if and only if $H^\ast $ is a simple hypergraph. Therefore, from the previous theorem,
The degree sequence $d_1\ge \cdots\ge d_n$ of the separable hypergraph can be obtained satisfying
$$
\sum_{i=1}^n\binom{m}{d_i}^{-1}\le 1.
$$
A hypergraph $H$ is said to be linear if $|E_i\cap E_j|\le 1,$ $\,\forall\,i\neq j$.
A simple discussion using proof by contradiction:
Proposition 4. $H$ is linear if and only if the dual graph $H^\ast $ is linear.
Theorem 5. For each linear hypergraph of order $n$, there is $\sum_{E\in H}\binom{|E|}{2}\le \binom{n}{2}.$. If further $H$ is consistent with $r$, then the number of edges satisfies $m(H)\le\frac{n(n-1)}{r(r-1)}.$ and is equal if and only if $H$ is a Steiner system $S(2,r,n).$. The Steiner system is an edge-derived subgraph of the complete hypergraph $K^r_n$, requiring each pair of points to be in exactly one hyperedge.
exist between hypergraphs isomorphism Relation. Called hypergraph$H\cong H',$
If there is a bijection $f:V\rightarrow V',$ such that $e=\{x_1,\cdots,x_k\}\in E$
$\Leftrightarrow$ $f(e)=\{f(x_1),\cdots,f(x_k)\}\in E'.$
Proposition 6. $H\cong H'\Leftrightarrow H^\ast \cong {H'}^\ast $
Just use the correlation matrix to judge.
The article was last updated on 2022-09-19 19:43:37
