超图

超图比图更一般. 简单来讲, 图的边连接 $2$ 个顶点, 而超图的超边可以连接更多的顶点.

1定义

定义 1.1 (超图). 超图是有序对 $H = (V, E)$ , 其中

•	$V$ 是集合, 其元素叫顶点.
•	$E \subseteq P (V) \ {\emptyset}$ , 其元素叫超边, 其中 $P$ 表示幂集.

当一个超图中所有超边都具有相同数量的顶点时, 我们称这个超图是均匀的. 特别地, 当该数量为

k

时, 该超图是

k

-均匀超图.

定义 1.2 ( $k$ -均匀超图). $U = (V, E)$ 是一个 $k$ -均匀超图, 当且仅当

•	$U$ 是超图.
•	$\forall e \in E, ∣ e ∣ = k .$ 其中 $∣ e ∣$ 指 $e$ 的基数.

•	$H = ({v_{1}, v_{2}, v_{3}}, {{v_{1}}, {v_{1}, v_{2}}, {v_{1}, v_{2}, v_{3}}})$ 是超图, 它有 $3$ 个顶点和 $3$ 条超边.
•	$U = ({v_{1}, v_{2}, v_{3}, v_{4}}, {{v_{1}, v_{2}, v_{3}}, {v_{1}, v_{2}, v_{4}}, {v_{2}, v_{3}, v_{4}}})$ 是 $3$ -均匀超图, 它有 $4$ 个顶点和 $3$ 条超边, 且每条超边都连接着 $3$ 个顶点.
•	所有无向图都是 $2$ -均匀超图.
•	$K_{3}$ 是 $2$ -均匀超图.

•	单纯复形
•	Ramsey 定理

术语翻译

超图 • 英文 hypergraph