【学习总结】
参考文献：
Bretto A. Hypergraph theory[J]. An introduction. Mathematical Engineering. Cham: Springer, 2013.

2.1 图与超图

2.1.1 图

（1）多重图

一个多重图，$\Gamma =(V;E)$是一个超图，使得 Γ 的秩最多为 2。超边称为（退化为）边。如果超图是简单图，没有回路，它就是一个图。因此，超图的任何定义都适用于图。给定图 Γ ，我们用 Γ (x) 表示顶点 x 的邻域，即由与 x 形成边的所有顶点形成的集合：
Γ ( x ) = { y ∈ V : { x , y } ∈ E } Γ(x) = \{y \in V:\{x,y\} \in E\} Γ(x)={y∈V:{x,y}∈E}
同理，我们定义 $A\subseteq V$ 的邻域为
$$\Gamma (A)=\bigcup _{x\in A}\Gamma (x)$$
A 的开邻域是
$${\Gamma }^o(A)=\Gamma (A)\setminus A.$$
由 $V^{\prime }\subseteq V$ 生成的导出子图由 $\Gamma (V^{\prime })$ 表示。

图 $\Gamma =(V;E)$ 是二部图，如果
$$V=V_1\cup V_2并且V_1\cap V_2=\varphi$$
并且每条边将 $V_1$ 的顶点连接到顶点 $V_2$。
众所周知，图 $\Gamma =(V;E)$ 是二部图当且仅当它不包含任何奇数环 [Wes01, Vol02]。

（2）团、弦图

如果每一对顶点都有边相连，则图是完全的。 图 $\Gamma =(V;E)$ 的团是 Γ 的完全子图。

图 Γ 的团的最大基数由 $\omega (\Gamma )$ 表示。

请记住，如果一个图的四个或更多顶点的循环中的每一个都有一个弦(chord)，即连接循环中两个不连续顶点的边，则该图是弦图(chordal)的。

2.1.2 图和超图

（1）线图（超边作为顶点、超边的相交点作为边）

令$H=(V;E=(e_i{)}_{i\in I})$是一个超图，使得$E\ne \varphi$。H 的线图（或代表图，也称相交图） line-graph(or representative graph, but also intersection graph)）是图 $L(H)=(V^{\prime };E^{\prime })$ 使得：

$V^{\prime }:=I或V^{\prime }:=E$当H没有重复超边时；
{ i , j } ∈ E ′ ( i ≠ j ) 当 且 仅 当 e i ∩ e j ≠ ϕ \{i,j\} \in E' (i \ne j)当且仅当e_{i} \cap e_{j} \ne \phi {i,j}∈E′(i​=j)当且仅当ei​∩ej​​=ϕ. 3

引理 2.1 超图 H 连通当且仅当 L(H) 连通。

命题 2.1 任何非平凡图 Γ 是线性超图的线图。

（2）2-section（超图节点是图的节点，超边内节点相互连接）

设 $H=(V;E)$ 是一个超图，H 的 第2部分（2-section）是图，用 $[H{]}_2$ 表示，其中顶点是 H 的顶点，其中两个不同的顶点形成边当且仅当它们是 在 H 的相同超边中。图 2.3 给出了一个 2-section的例子。

命题 2.2 设 H = (V ; E) 是一个超图，我们有：
$$\sum _{x\in V}d(x)=\sum _{e\in E}d(e).$$
（ps.超边度数之和等于顶点度数之和）

（3）邻域超图

详见原文。

2.2 相交族，Helly性质

2.2.1 相交族

（1）相交族（超边子集每对相交有一个交点）

设 $H=(V;E=(e_i{)}_{i\in I})$ 是一个超图。 超边 $(e_j{)}_{j\in J}$ 的一个子族，其中 $J\subseteq I$ 是一个相交族，如果每对超边都有一个非空的交点。|J|的最大基数 (H 的相交族) 用 ${\Delta }_0(H)$ 表示。
（ps.存在一个超边的子集，该子集中的每对超边都有一个非空的交点，例如 以x为中心的star结构）

2.2.2 Helly性质

（1）Helly、Strong Helly 性质

Helly 性质在超图理论中起着非常重要的作用，因为最重要的超图都具有这个性质 [BUZ02, Vol02, Vol09]。 如果每个相交族都有一个非空的交集（属于一个星形），则超图具有 Helly 性质。 很明显，如果一个超图包含一个三角形，它就没有 Helly 性质。 具有 Helly 性质的超图将称为 Hell超图 （Helly hypergraph）。
（ps. 每个【相交族】都有一个【非空的交集（属于一个star结构）】）

如果每个部分导出子超图都具有 Helly 性质，则超图具有强 Helly 性质。 图 2.9 所示的超图具有 Helly 性质，但没有强 Helly 性质。

（2）算法

对于 Helly 属性，我们有以下算法：

Strong Helly性质算法：

2.3 子树超图

（1）子树超图

让 H = (V; E) 是一个超图。 这个超图称为子树超图，如果

• 存在一个顶点集为 V 的树 Γ 使得每个超边 e ∈ E 在 Γ 中导出一个子树。

请注意，对于同一个超图，我们可能会使用上述方法生成多个树。 此外，如果 H = (V;E) 不是子树超图，则对于 V 上的任何树，至少有一个超边会导致断开子图。

反过来也可以通过子树生成超图，也叫做子树超图。同一棵树可能可以生成多个超图。

命题2.4 设Γ = (V; A) 是一棵树，H 是与Γ 相关的子树超图，H 具有Helly 性质。
命题 2.5 设 Γ = (V; A) 是一棵树，H 是一个子树超图，与 Γ 相关联，则 L(H) 是弦（chordal）。

2.4 共形图（Conformal Hypergraphs）

（1）共形图（Conformal Hypergraphs）

如果 2-section $[H{]}_2$ 的任何极大团（用于包含）是 H 的超边，则超图 H 是共形的。
图 2.11 显示了超图 H 的 2-section。可能会注意到这个超图不是共形的。

(ps. 由于x1, x3, x5也形成了一个团，红边表示的地方，但并没有超边连接他们，因此该超图不是共形图)

命题 2.6 一个超图是共形的，当且仅当它的对偶具有Helly 属性。
命题 2.7 超图 H 的线图 L(H) 是 $H^{\ast }$ 的 2-section，即
$$L(H)\simeq [H^{\ast }{]}_2$$

此外，以下两个陈述是等价的，其中 Γ 是一个图：
(i) H 验证了 Helly 属性 并且 Γ 是 H 的线图。
(ii) $H^{\ast }$ 的最大超边（用于包含）是 Γ 的最大团。

2.5 稳定（或独立）、横向和匹配Stable (or Independent), Transversal and Matching

（1）稳定 Stable (or Independent)

设 $H=(V;E=(e_i{)}_{i\in I})$ 是一个没有孤立顶点的超图。
如果 A 中不包含超边，则集合 A ⊆ V 是稳定的或独立的（或强稳定的）（对于每个 $i\in I，|A\cap V(e_i)|\le 1$）。
稳定数 $\alpha (H)$（或强稳定数 ${\alpha }^{\prime }(H)$）是一个稳定（或强稳定）的最大基数。

(ps. 稳定指A是节点V的一个子集，A中的节点与任何超边ei的集合相交最多只有一个交点。）
（ps. $\alpha (H)$ 稳定数指超图中节点不构成超边的最大节点数。)

（2）横向 Transversal

集合B ⊆ V是横向的（Transversal）如果B与每条超边相交，即
$$对于所有e\in E,B\cap V(e)\ne \varphi$$
横向的最小基数是横向数。 它由$\tau (H)$表示。

（ps. 横向指B是节点V的一个子集，B中节点与每条超边都最少有一个交点。）
（ps. $\tau (H)$指包含超图中所有超边的节点集合最少数。）

（3）匹配 Matching 和 超边覆盖

匹配(Matching)是 H 的一组成对不相交的超边集合。
H 的匹配数 ν(H) 是匹配的最大基数。超边覆盖是超边的子集：
$$(e_j{)}_{j\in J},(J\subseteq I)使得:\bigcup _{j\in J}{e}_j=V.$$
超边覆盖数 $\rho (H)$ 是超边覆盖的最小基数。

（ps. 匹配是指（超边对）的集合，例如{(e1, e3), (e2, e4), (e5, e6)}，其中e1和e3、e2和e4，e5和e6没有交点）
（ps. ν(H) 是超图中两两不相交的超边对的最大数。）

(ps. 超边覆盖是超边的子集，该子集中超边相并后得到所有的节点V。)
(ps. $\rho (H)$是能够覆盖超图中所有节点V的超边最少数。)

2.5.1 示例

（1）示例

引理 2.2 令 H = (V; E) 是一个没有孤立顶点的超图。 我们有以下属性。
(i) $\nu (H)\le \tau (H).$
(ii) $\rho (H)=\tau (H\ast ).$
(iii) ${\alpha }^{\prime }(H)=\nu (H\ast ).$
(iv) ${\alpha }^{\prime }(H)\le \rho (H).$

详见原文。

2.6 König 性质和对偶 König 性质

（1）König 性质

超图 H 具有 König 性质，如果
$$v(H)=\tau (H)$$

（2）对偶 König 性质

超图 H 具有对偶 König 性质当且仅当
$${\alpha }^{\prime }(H)=\rho (H)$$

命题 2.8 令 Γ = (V; E) 是一棵树，让 H 是与 Γ 相关的子树超图。 那么 H 具有 König 性质，即
$$v(H)=\tau (H)$$

2.7 线性空间(Linear spaces)

我们提醒读者，线性空间是一个超图，其中每对不同的顶点都包含在一条边中。 平凡线性空间是只有一个超边的超图，其中包含所有顶点。

定理 2.3 如果一个非平凡的、非空的线性空间有 n 个顶点和 m 个边，则 m ≥ n。