图的邻域与邻域复形 步骤1：邻域的基本定义 在图论中，给定一个图 \( G = (V, E) \) 和一个顶点 \( v \in V \)，顶点 \( v \) 的邻域（neighborhood）是指所有与 \( v \) 相邻的顶点构成的集合，记作 \( N(v) \)。形式化定义为： \[ N(v) = \{ u \in V \mid \{u, v\} \in E \}. \] 注意：邻域不包括顶点 \( v \) 自身。若需包含 \( v \)，则称为闭邻域（closed neighborhood），记作 \( N[ v ] = N(v) \cup \{v\} \)。邻域的概念是分析局部图结构的基础，例如顶点的度（degree）就是邻域的大小：\( \deg(v) = |N(v)| \)。 步骤2：邻域的性质与扩展 邻域可以推广到顶点子集。对于子集 \( S \subseteq V \)，其邻域定义为所有与 \( S \) 中至少一个顶点相邻的顶点构成的集合（不包括 \( S \) 自身）： \[ N(S) = \bigcup_ {v \in S} N(v) \setminus S. \] 邻域的性质常用于刻画图的局部特征，如正则图（每个顶点邻域大小相同）或支配集（若 \( S \) 的闭邻覆盖整个顶点集，则 \( S \) 为支配集）。邻域还关联到图的密度：例如，若每个顶点的邻域诱导一个团（完全子图），则图是弦图。 步骤3：邻域复形的引入 邻域复形（neighborhood complex）是将邻域概念提升到组合拓扑结构的工具。给定图 \( G \)，其邻域复形 \( \mathcal{N}(G) \) 是一个单纯复形（simplicial complex），其单形由顶点子集构成，这些子集有一个公共邻域顶点。具体地，\( \mathcal{N}(G) \) 的顶点集是 \( V \)，而一个子集 \( \sigma \subseteq V \) 是 \( \mathcal{N}(G) \) 的一个单形，当且仅当存在一个顶点 \( w \in V \)，使得 \( \sigma \subseteq N(w) \)（即 \( w \) 是 \( \sigma \) 中所有顶点的公共邻居）。邻域复形编码了图中顶点邻域的交集结构。 步骤4：邻域复形的性质与应用 邻域复形的拓扑性质（如连通性、同调群）与图的组合性质密切相关。例如： 若 \( G \) 是二部图，则 \( \mathcal{N}(G) \) 可能具有简单的拓扑结构（如可收缩）。 Lovász 在证明 Kneser 猜想时使用了邻域复形的同调群来估计图的色数，建立了拓扑图论中的 Lovász 定理：图的色数至少为邻域复形的连通度加一。 邻域复形还可用于研究图的均匀着色问题或检测局部稠密子结构。 步骤5：计算与复杂性 计算邻域复形需要枚举所有顶点及其邻域的交集。对于大小为 \( n \) 的图，最坏情况下复形的大小可能指数增长，但稀疏图（如平面图）的邻域复形规模可控。实际应用中，邻域复形可用于网络分析，如识别功能模块（公共邻居团）或评估网络的鲁棒性。拓扑数据分析工具（如持续同调）可提取邻域复形的拓扑特征，用于图分类或聚类。