长期多项式的可约性与图的扩展

### 长期多项式的可约性与图的扩展 #### 1. 图的收缩与非真图 在图论中，边的收缩是一个重要的操作。当收缩一条边时，只有在特定情况下才会得到非真图。具体来说，当收缩的边是连接度为三的顶点的悬挂边，或者是连接度为四的顶点的环时，收缩操作会导致得到非真图。而在其他情况下，如果原始图是真图，那么收缩后的图仍然是真图。 由此可知，一个真图不能收缩为另一个真图的情况是，它的所有边要么是连接度为二的顶点的悬挂边，要么是连接度为四的顶点的环。所有可能的这类图包括： - 三星图 \(G(3.2)\)； - 图 \(G(3.4)\)； - 数字 8 图 \(G(2.4)\)。 这些图都至少有三条边。下面用 mermaid 流程图展示边收缩与图类型的关系： ```mermaid graph TD; A[原始真图] --> B{收缩边类型}; B -->|悬挂边连度三顶点| C[非真图]; B -->|环连度四顶点| C; B -->|其他情况| D[真图]; ``` #### 2. 图的扩展定义 接下来讨论从小图到大图的扩展情况。首先给出图扩展的定义：设 \(\Gamma\) 是一个具有 \(N\) 条边和 \(M\) 个顶点的度量图，如果图 \(\Gamma'\) 是通过添加边 \(E_{N + 1}\) 得到的 \(\Gamma\) 的扩展，当且仅当 \(\Gamma' \) 是一个具有 \(N + 1\) 条边的图，且 \(\Gamma = \Gamma' \setminus E_{N + 1}\)。 图的扩展有两种实现机制： - **插入边分割顶点**：新边 \(E_{N + 1} = [x_{2N + 1}, x_{2N + 2}]\) 将某个顶点 \(m_0\) 分割成两个顶点 \(m'\) 和 \(m''\)。首先将对应的等价类进行划分，即 \(V^{m_0}(\Gamma) = (V^{m_0})' \cup (V^{m_0})''\)，且 \((V^{m_0})' \cap (V^{m_0})'' = \varnothing\)，然后分别添加端点 \(x_{2N + 1}\) 和 \(x_{2N + 2}\) 进行扩展，得到 \(V^{m'}(\Gamma') = (V^{m_0})' \cup \{x_{2N + 1}\}\) 和 \(V^{m''}(\Gamma') = (V^{m_0})'' \cup \{x_{2N + 1}\}\)。 - **添加环**：新边 \(E_{N + 1}\) 形成一个环，并连接到 \(\Gamma\) 中的某个现有顶点 \(m_0\)，使得端点 \(x_{2N + 1}\) 和 \(x_{2N + 2}\) 被添加到对应的等价类中，即 \(V^{m_0}(\Gamma') = V^{m_0}(\Gamma) \cup \{x_{2N + 1}, x_{2N + 2}\}\)。 需要注意的是，向顶点 \(V^{m'}\) 添加悬挂边可以通过形式上划分等价类 \(V^{m_0}(\Gamma) = V^{m_0}(\Gamma) \cup \varnothing\)，然后分别将端点 \(x_{2N + 1}\) 和 \(x_{2N + 2}\) 添加到 \(V^{m_0}\) 和空集中来实现。而在 \(\Gamma\) 中两个现有顶点之间添加边不属于扩展，因为收缩这条边会导致两个顶点合并。 #### 3. 图扩展的示例 以环图 \(G(1.2)\) 为例，它只有一个顶点，其扩展方式有三种： - 添加环，得到图 \(G(2.4)\)； - 添加悬挂边，得到图 \(G(2.2)\)； - 分割顶点为两个，得到图 \(G(2.3)\)。 再看图 \(G(2.2)\)，它有两个顶点，通过向每个顶点添加环或悬挂边可以得到四个扩展图：\(G(3.7)\)、\(G(3.8)\)、\(G(3.3)\) 和 \(G(3.4)\)。分割中心顶点会得到图 \(G(3.5)\) 和再次得到图 \(G(3.3)\)。另外，图 \(G(2.4)\) 和 \(G(2.3)\) 的扩展也有不同情况。 值得注意的是，图 \(G(3.1)\) 和 \(G(3.2)\) 不会在扩展 \(G(1.2)\) 时出现，原因是这两个图是树，而起始图 \(G(1.2)\) 包含一个环。从图的扩展图中可以看出，一些三条边的图可以从不同的两条边的图得到。并且，除非扩展是通过添加环实现的，否则图的环数总是保持不变。更有趣的是，如果得到的图是一个具有三条边的真度量图（不包含度为二的顶点），且不是西瓜图 \(G(3.9)\)，那么其长期多项式只包含对应于环的因子。也就是说，在两条边的非真图中可能观察到的潜在因子在扩展过程中会消失。 #### 4. 长期多项式的可约性与图的关系 图的收缩和扩展操作与长期多项式的可约性密切相关。图的收缩用于证明长期多项式的可约性，而图的扩展则用于证明大图的长期多项式的不可约性。下面通过两个引理来说明这种关系。 **引理 7.9**：任何具有两条或更多边且不包含度为二的顶点的图 \(G\) 的长期多项式，只有当对应的边属于一个简单循环（即每个顶点只经过一次的循环），或者两条边都形成环时，才能写成依赖于相同两个变量（以及任何其他变量）的两个非平凡因子的乘积。 证明过程如下： - 首先检查所有两条边的图，只需要考虑真图，即套索图 \(G(2.2)\) 和数字 8 图 \(G(2.4)\)。数字 8 图 \(G(2.4)\) 具有所需的性质，其长期多项式可以分解为依赖于两个变量 \(z_1\) 和 \(z_2\) 的因子；而套索图 \(G(2.2)\) 的长期多项式是线性因子 \((z_1 - 1)\) 和一个不可约因子的乘积，不具有所需性质。因此，该引理不仅适用于所有两条边的真图，而且可以用“当且仅当”来表述。 - 对于任意的图，不失一般性地假设所讨论的变量是 \(z_1\) 和 \(z_2\)。将原始图 \(G\) 收缩为 \(G_{1,2}\)，通过合并除 \(E_1\) 和 \(E_2\) 之外的所有边。考虑所有可能的两条边的图及其长期多项式，然后研究它们的扩展情况： - 当 \(G_{1,2} = G(2.1)\)（线段）时，其兼容扩展中可能是图 \(G_{1,2,3} = G(3.2)\) 或 \(G_{1,2,3} = G(3.4)\)，这两个图的长期多项式不能写成依赖于 \(z_1\) 和 \(z_2\) 的两个因子的乘积，所以 \(G(2.1)\) 的所有扩展都不具有所需性质。 - 当 \(G_{1,2} = G(2.2)\)（套索图）时，其长期多项式不能分解为依赖于两个变量的两个多项式的乘积，因此其所有扩展也不具有该性质。 - 当 \(G_{1,2} = G(2.3)\)（由两条边形成的环）时，边 \(E_1\) 和 \(E_2\) 属于原始图 \(G\) 中的某个循环，符合引理的结论。 - 当 \(G_{1,2} = G(2.4)\)（数字 8 图）时，需要研究不保留 \(E_1\) 和 \(E_2\) 形成的环的扩展情况。将中心顶点 \(V\) 分割有两种可能： - \(V \to \{x_1, x_4\} \cup \{x_2, x_3\}\)； - \(V \to \{x_1, x_2, x_4\} \cup \{x_3\}\)。 在情况 (a) 中，扩展后的边是平行的，这些边要么在 \(G\) 中是平行的，要么存在另一种扩展情况如 (b)。因此，只需要研究情况 (b)。假设顶点 \(V\) 分割为 \(V^1 = \{x_1, x_2, x_4\}\) 和 \(V^2 = \{x_3\}\)，在与 \(G\) 兼容的 \(G_{1,2}\) 的扩展中，有三种可能的图： - 图 \(G\) 的收缩中存在一个四条边的图，由 \(E_2\) 和 \(E_3\) 形成的环，以及在两个顶点处分别连接的悬挂边 \