图的多重图与超图 首先，我们从 多重图 （Multigraph）开始。在基础图论中，一个简单图（Simple Graph）的每对顶点之间至多有一条边，且没有自环。而 多重图 扩展了这个定义：允许同一对顶点之间存在 多条平行边 （也称为多重边），同时也可能允许 自环 （即一个顶点到自身的边）。 形式化定义：多重图 \( G = (V, E) \) 由顶点集 \( V \) 和边集 \( E \) 组成，但边不再只是顶点对，而是有序对（有向多重图）或无向对（无向多重图），且允许重复的边实例。通常用关联函数将每条边与一个顶点对（允许相同顶点）关联。 例子：城市之间的多条直达航班、通信网络中的冗余链路都可以用多重图建模。 注意：在多重图中，顶点的“度”定义为关联到该顶点的边数（自环通常计为2度）。许多图论概念（如路径、连通性）可以直接推广到多重图，但有些定义（如图的邻接矩阵）需要调整（例如用边数代替0/1）。 接下来，我们引入 超图 （Hypergraph）。在普通图（包括多重图）中，每条边恰好连接两个顶点（二元关系）。而 超图 进一步扩展：每条边可以连接 任意数量的顶点 （包括0个或1个，但通常至少2个）。 形式化定义：超图 \( H = (V, E) \) 由顶点集 \( V \) 和超边集 \( E \) 组成，其中每条超边 \( e \in E \) 是 \( V \) 的一个非空子集（如果允许空边则单独说明）。 例子：合作网络（一篇论文有多个作者可视为一条超边）、物品组合购买记录、集合覆盖问题等。 超图分类：若所有超边大小相同（设为 \( k \)），称为** \( k\)-一致超图** （当 \( k=2 \) 时退化为普通图）。 然后，讨论超图的 表示与基本概念 。 关联矩阵 ：一个 \( |V| \times |E| \) 的矩阵，其中元素 \( h(v, e) = 1 \) 当且仅当顶点 \( v \) 属于超边 \( e \)。 对偶超图 ：将顶点与超边交换角色得到的新超图。 超图的图模型 ： 星图表示 ：每条超边用一个新顶点代表，并与该超边中所有原始顶点相连，得到一个二分图。 团扩展 ：将每条超边替换为一个完全子图（即超边中所有顶点两两相连），从而将超图转化为普通图，但会丢失超边结构信息。 进一步，我们探讨超图的 着色与覆盖问题 。 超图着色 ：给每个顶点分配颜色，使得每条超边（大小至少2）不单色（即至少有两个顶点颜色不同）。最小的颜色数称为 超图的色数 。注意这等价于其团扩展图的正常顶点着色，但定义可调整（如“强着色”要求超边内所有顶点颜色互异）。 覆盖与横贯 ：一个 横贯 （Transversal）是顶点子集，与每条超边相交。最小横贯的大小称为 横贯数 。对偶地，一个 匹配 是一组不相交的超边，最大匹配的大小称为 匹配数 。这些是组合优化中的核心问题。 最后，我们简要介绍 超图与多重图的关系 。 多重图可以看作边带有重数的图，也可视为2一致超图（每条边仍连接两个顶点，但允许重复）。 超图可以通过“细分”或“转化为二分图”来利用图论工具研究，但许多普通图的定理在超图上不再平凡（例如超图的拉普拉斯矩阵、谱理论需要更复杂的定义）。 应用领域包括数据库关系模型、电路设计、社交网络中的团体分析等。