离散数学中的超图及其表示

超图可以描述为一种图，其中超图不是连接两个顶点/节点，而是连接顶点/节点的一个子集。边也可以称为超边，用于包含任意非空顶点集。这些类型的超边由k超图包含，该超图精确地连接k个顶点。如果存在一个普通图，它将被视为2超图，因为在普通图中，一条边连接两个顶点。

超图的表示

无向超图H可以表示为一对H = (V, E)，其中V用于表示一组项目，这些项目称为顶点或节点，E用于表示V的一组非空子集，这些子集也称为边或超边。

这里 E 可以定义为 P(X) 的子集，其中 P(X) 用于表示 X 的幂集。

借助于闭合曲线，每个超边将被表示。这些超边的成员被此闭合曲线包含，以便它可以创建超图。

例如

超图的阶和大小

超图的阶和大小可以通过以下公式确定

超图的阶 = 顶点集的大小，以及

超图的大小 = 边集的大小

因此，在上述超图中，共有5个顶点，名为A、B、C、D、E，边的数量为3条，名为：e1、e2、e3。我们知道，超图的阶 = 顶点数量，超图的大小 = 边数量。因此，借助这些值，上述超图的阶和大小描述如下：

超图到二分图

借助于二分图，我们总是能够表示一个超图，但是借助于二分图表示超图并不总是方便的。在此过程中，超图很少被利用。在二分图中，顶点集被分成两个子集，名为P和Q。这里每条边都与P中的一个顶点和Q中的一个顶点连接。H的顶点可以很容易地表示为Q中的顶点。H的超边可以很容易地表示为P中的顶点。如果s是H中超边t的一个成员，那么我们将插入一条边(p, q)。

上述超图以两种方式表示。左侧，5条边连接3条超边。右侧，相同的5个顶点连接到新的顶点（三个），用于通过普通边显示超边。

超图的性质

超图包含多种类型的性质，描述如下：

空超图

空超图不包含任何类型的边，但它可以包含顶点。

示例：在以下图中，我们可以看到没有边，但它包含五个顶点，名为：A、B、C、D和E。

d-正则

在此超图中，每个顶点的度数都为d。此语句意味着它精确地包含在d条超边中。

示例：在下面的超图中，所有顶点（A、B和C）都包含度数2。这就是为什么这个超图是2-正则超图。

2-可着色

2-可着色图的顶点被分为P和Q两类。借助于这些类，每个基数至少为2的超边都包含来自每个类的至少1个顶点。

非简单

非简单超图将包含循环（可以定义为具有单个顶点的超边）或重复边（可以定义为包含相同顶点集的两条或更多边）。

示例：在以下图中，我们可以看到有2个循环，名为：e1和e2。因此，这个超图是一个非简单超图。

简单

简单超图不包含任何循环或重复边。

K一致

在此，每个超边将由恰好k个顶点创建。

示例：在下面的超图中，我们可以看到有4条超边：e1、e2、e3和e4，每条超边都有2个顶点。所以我们可以说这个超图是一个2-一致超图。

K分

在此超图中，每个超边都包含每种类型的一个顶点，并且此超图中的顶点被分为k个部分。

示例：在下面的超图中，我们可以看到顶点被分为3个部分，即(A, D)、(B, E)和(D, F)。在此图像中，每个超边对于每个分区只包含1个顶点。