多重边图的2-洛朗多项式

doi:10.12677/PM.2020.108089

期刊菜单

多重边图的2-洛朗多项式
2-Laurent Polynomials of Multi-Edge Graphs

DOI: 10.12677/PM.2020.108089, PDF, HTML, XML, 下载: 434 浏览: 786
作者: 庚东雨：辽宁师范大学，辽宁大连
关键词: 2-洛朗多项式；不变量；多重边；2-Laurent Polynomial； Invariant； Multiple Edges

摘要: 2-洛朗多项式(2-Laurent Polynomial)是图论中重要的不变量之一。如果两个空间图的投影图是同胚的，那么这两个投影图的2-洛朗多项式是相同的，这是研究图分类问题的重要方法。而多重边图是一类既特殊又简单的图，本文研究多重边图的2-洛朗多项式并给出了其推导公式。

Abstract: 2-Laurent Polynomial is one of the important invariants in graph theory. If the projected graphs of the two spatial graphs are homeomorphic, then the 2-Laurent polynomials of the two projected graphs are the same, which is an important method to study the graph classification problem. Multi-edge graphs are a kind of special and simple graphs. In this paper, we study the 2-Laurent polynomials of multi-edge graphs and give their derivation formulas.

文章引用：庚东雨. 多重边图的2-洛朗多项式[J]. 理论数学, 2020, 10(8): 764-770. https://doi.org/10.12677/PM.2020.108089

1. 引言

图论中有许多值得我们去研究的问题，其中关于图的等价分类问题就是图理论中的重要问题之一。图的不变量是我们研究图等价分类的重要方法。其中图的多项式是常见的图不变量。图多项式在空间图理论中具有十分重要的作用和地位。许多数学家已经从很多方面对多项式及其有关的课题进行了深入研究。

本文研究一类多重边图的2-洛朗多项式。在图多项式中，Yamada多项式是重要的多项式，在学习Yamada多项式之前我们需要掌握2-洛朗多项式，这也被称为是Negami多项式 [1] 的特殊形式。

本文的创新之处在于通过对多重边图边的情况进行分类，推导出来多重边图的2-洛朗多项式的计算公式。在预备知识部分我们将回顾图理论的一些基本概念，在第二部分我们将针对多重边图的性质进行研究，第三部分通过对边的分类得到多重边图的2-洛朗多项式的计算公式，进而推导出多重边图的一种特殊情况 $θ_{n}$ 图的2-洛朗多项式。

2. 预备知识

2.1. 图的基本概念

定义2.1 [1] 图G是指一个有序三元组 $(V (G), E (G), ψ (G))$ ，其中 $V (G)$ 是图G的顶点集， $E (G)$ 是图G的边集且 $E (G) \cap V (G) = ϕ$ ， $ψ_{G}$ 是关联函数，它将G的每条边对应于G的无序顶点对(可以是相同顶点)。若边e和两个顶点u和v满足 $ψ_{G} (e) = u v$ ，则称边e联结顶点u和v，顶点u和v称为边e的端点。

注解2.1 以后为了方便，分别用V和E表示图G的边集和顶点集。

注解2.2 如果一条边连接相同的顶点，那么我们称这样的边为环边(loop)。连接两个点可以有不止一条边，这些边称为多重边。

2.2. Reidemeister Move (R变换) [2]

空间图的Reidemeister变换是由纽结投影图的经典Reidemeister变换 $R_{0}, R_{1}, R_{2}$ 和 $R_{3}$ 以及为空间图顶点邻域上的变换 $R_{4}, R_{5}, R_{6}$ 组成的。如图1所示。

Figure 1. Reidemeister move

图1. R变换

3. 2-洛朗多项式

3.1. 2-洛朗多项式的定义

定义3.1 [3] 图 $G = (V, E)$ ，V是G的顶点集，E是G的边集。 $μ (G)$ 和 $β (G)$ 分别表示图的连通分支数和一维Betti数。且 $f (G) = x^{μ (G)} y^{β (G)}$ ， $h (G)$ 是一个2-洛朗多项式：

$h (G) = h (G) (x, y) = \sum_{F \subset E} {(- x)}^{- | F |} f (G - F)$ 。

注解3.1 F是E的子集， $| F |$ 是F包含元素的数目， $G - F = (V, E - F)$ 且x和y是不定元，定义 $h (ϕ) = 1$ 。且 $G - F = (V, G - F)$ 。

命题3.1 [3] 如果e是图G的一个非环边。有 $h (G) = h (G / e) - \frac{1}{x} h (G - e)$ ，其中 $G / e$ 表示在图G中缩

边e于一点， $G - e$ 表示把边e删掉。

证明 F和 $F^{'}$ 是E的子集， $| F |$ 是F包含元素的数目，且 $| F | = | F^{'} | + 1$ 。

$\begin{matrix} h (G) = {\sum_{e \notin F \subset E} (- x)}^{- | F |} f (G - F) + {\sum_{e \in F \subset E} (- x)}^{- | F |} f (G - F) \\ = {\sum_{F \subset E - e} (- x)}^{- | F |} f (G / e - F) - 1 / x \cdot {\sum_{F^{'} \subset E - e} (- x)}^{- | F^{'} |} f (G - e - F) \\ = h (G / e) - \frac{1}{x} h (G - e) . \end{matrix}$

命题3.2 [3] 如果e是图G的一个环边。则 $h (G) = (y - \frac{1}{x}) h (G - e)$ 。

证明当e是图G的环边时，那么 $G / e = G - e$ ，则

$\begin{matrix} h (G) = {\sum_{e \notin F \subset E} (- x)}^{- | F |} f (G - F) + {\sum_{e \in F \subset E} (- x)}^{- | F |} f (G - F) \\ = y {\sum_{F \subset E - e} (- x)}^{- | F |} f (G / e - F) - 1 / x \cdot {\sum_{F^{'} \subset E - e} (- x)}^{- | F^{'} |} f (G - e - F) \\ = y h (G / e) - \frac{1}{x} h (G - e) \\ = (y - \frac{1}{x}) h (G - e) . \end{matrix}$

3.2. 2-洛朗多项式的性质

给定两个图 $G_{1}$ 和 $G_{2}$ ， $G_{1} \cup G_{2}$ 表示图 $G_{1}$ 和 $G_{2}$ 不交并， $G_{1} \lor G_{2}$ 表示图 $G_{1}$ 和 $G_{2}$ 的一点并。我们称G有一割边e，如果 $G - e$ 比G有更多的连通分支数。

性质3.1 [3] $h (G_{1} \cup G_{2}) = h (G_{1}) h (G_{2})$ 。

证明令 $F = F_{1} \cup F_{2}$ ， $E = E_{1} \cup E_{2}$ ， $F_{1} \subset E_{1} \subset G_{1}$ ， $F_{2} \subset E_{2} \subset G_{2}$ 。

因为 $μ (G_{1} \cup G_{2}) = μ (G_{1}) + μ (G_{2})$ ， $β (G_{1} \cup G_{2}) = β (G_{1}) + β (G_{2})$ 。

$\begin{matrix} h (G_{1}) h (G_{2}) = \sum_{F_{1} \subset E_{1} \subset E} {(- x)}^{- | F_{1} |} f (G_{1} - F_{1}) \cdot \sum_{F_{2} \subset E_{2} \subset E} {(- x)}^{- | F_{2} |} f (G_{2} - F_{2}) \\ = {\sum_{F_{1}, F_{2} \subset E} (- x)}^{- | F_{1} | - | F_{2} |} \cdot x^{μ (G_{1} - F_{1}) + μ (G_{2} - F_{2})} y^{β (G_{1} - F_{1}) + β (G_{2} - F_{2})} \\ = \sum_{F_{1}, F_{2} \subset E} {(- x)}^{- | F_{1} | - | F_{2} |} f (V, G_{1} - F_{1} \cup G_{2} - F_{2}) \\ = h (G_{1} \cup G_{2}) . \end{matrix}$

性质3.2 [3] $h (G_{1} \lor G_{2}) = \frac{1}{x} h (G_{1}) h (G_{2})$ 。

证明令 $F = F_{1} \cup F_{2}$ ， $E = E_{1} \cup E_{2}$ ， $F_{1} \subset E_{1} \subset G_{1}$ ， $F_{2} \subset E_{2} \subset G_{2}$ 。

$\begin{matrix} h (G_{1} \lor G_{2}) = {\sum_{F \subset E} (- x)}^{- | F |} f (G_{1} \lor G_{2} - F) \\ = {\sum_{F_{1} \subset E_{1}} (- x)}^{- | F_{1} |} \cdot {\sum_{F_{2} \subset E_{2}} (- x)}^{- | F_{2} |} \cdot \frac{1}{x} f (G_{1} - F_{1}) f (G_{2} - F_{2}) \\ = \frac{1}{x} h (G_{1}) h (G_{2}) . \end{matrix}$

性质3.3 [3] 如果G有割边，则 $h (G) = 0$ 。

证明设e是G的割边，则 $G - e = G_{1} \cup G_{2}$ ， $G / e = G_{1} \lor G_{2}$ 。由命题3.1，性质3.1和性质3.2可得

$\begin{matrix} h (G) = h (G / e) - \frac{1}{x} h (G - e) \\ = h (G_{1} \lor G_{2}) - \frac{1}{x} h (G_{1} \cup G_{2}) \\ = \frac{1}{x} h (G_{1}) h (G_{2}) - \frac{1}{x} h (G_{1}) h (G_{2}) \\ = 0. \end{matrix}$

3.3. 多重边图的2-洛朗多项式计算

命题3.3 $h (•) = x$ 。

证明由定义可得， $h (•) = {(- x)}^{0} \cdot x y^{0} = x$ 。

命题3.4 $h (• •) = x^{2}$ 。

证明由性质3.1， $h (G_{1} \cup G_{2}) = h (G_{1}) h (G_{2})$ ，可得 $h (• •) = h (•) h (•) = x \cdot x = x^{2}$ 。

定义3.2 给定两个可分的图 $G_{1}$ 和 $G_{2}$ ， $V_{1}$ 和 $V_{2}$ 分别是 $G_{1}$ 和 $G_{2}$ 的任意两个顶点，将 $V_{1}$ 和 $V_{2}$ 用n条边连接起来，记作 $G_{1} \lor_{n} G_{2}$ 。如图2所示。

注解3.2 其中 $(G_{1} \lor_{n} G_{2}) / {e_{1, \dots, n}}$ 表示图 $G_{1} \lor_{n} G_{2}$ 把边 $e_{1} \dots e_{n}$ 去掉同时将 $V_{1}$ 和 $V_{2}$ 两个顶点粘结在一起， $(G_{1} \lor_{n} G_{2}) - {e_{1, \dots, n}}$ 表示图 $G_{1} \lor_{n} G_{2}$ 中去掉边 $e_{1} \dots e_{n}$ 。

并有以下等式成立

$\begin{array}{l} ((G_{1} \lor_{n} G_{2}) - e_{1}) / {e_{2, \dots, n}} = ((G_{1} \lor_{n} G_{2}) - {e_{1, 2}}) / {e_{3, \dots, n}} \\ = \dots = ((G_{1} \lor_{n} G_{2}) - {e_{1, \dots, n - 1}}) / e_{n} = (G_{1} \lor_{n} G_{2}) / {e_{1, \dots, n}} . \end{array}$

Figure 2. $G_{1} \lor_{n} G_{2}$

图2. $G_{1} \lor_{n} G_{2}$

定理3.1

$h (G_{1} \lor_{n} G_{2}) = \sum_{i = 1}^{n} \frac{C_{n}^{n + 1 - i} \cdot y^{n - i}}{{(- x)}^{i - 1}} h [(G_{1} \lor_{n} G_{2}) / {e_{1, \dots, n}}] + \frac{1}{{(- x)}^{n}} h [(G_{1} \lor_{n} G_{2}) - {e_{1, \dots, n}}] .$

证明设F和 $F_{n}$ 是E的子集，E是 $G_{1} \lor_{n} G_{2}$ 的边集 $| F |$ 是F包含元素的数目，则 $| F | = | F_{n} | + n$ 。由2-洛朗多项式的定义 $h (G) = h (G) (x, y) = {\sum_{F \subset E} (- x)}^{- | F |} f (G - F)$ ，对F中所包含n条边 $e_{1}, e_{2}, \dots, e_{n}$ 的情况进行分类：

1) 若F中只含某一条边 $e_{i}$ ，共有 $C_{n}^{n - 1}$ 种情况，且每一种情况的计算结果是相同的，如图3所示。

Figure 3. $G_{1} \lor_{1} G_{2}$

图3. $G_{1} \lor_{1} G_{2}$

由割边的定义可知 $e_{i}$ 是图 $G_{1} \lor_{1} G_{2}$ 的割边，则 $h (G_{1} \lor_{1} G_{2}) = 0$ 。

2) 若F中只含两条边 $e_{i_{1}, i_{2}}$ ，共有 $C_{n}^{n - 2}$ 种情况，且每一种情况的计算结果是相同的，如图4所示。

Figure 4. $G_{1} \lor_{2} G_{2}$

图4. $G_{1} \lor_{2} G_{2}$

$\begin{array}{l} h (G_{1} \lor_{2} G_{2}) \\ = {\sum_{e_{i_{1}, i_{2}} \notin F \subset E} (- x)}^{- | F |} f [(G_{1} \lor_{2} G_{2}) - F] + C_{2}^{1} \cdot {\sum_{\begin{array}{l} e_{i_{1}} \notin F \subset E \\ e_{i_{2}} \in F \subset E \end{array}} (- x)}^{- | F |} f [(G_{1} \lor_{2} G_{2}) - F] \\ + \sum_{e_{i_{1}, i_{2}} \in F \subset E} {(- x)}^{- | F |} f [(G_{1} \lor_{2} G_{2}) - F] \\ = y \cdot {\sum_{F \subset E - {e_{i_{1}, i_{2}}}} (- x)}^{- | F |} f [(G_{1} \lor_{2} G_{2}) / {e_{i_{1}, i_{2}}} - F] - \frac{C_{2}^{1}}{x} \cdot {\sum_{F_{1} \subset E - {e_{1}, i_{2}}} (- x)}^{- | F_{1} |} f [((G_{1} \lor_{2} G_{2}) - e_{i_{2}}) / e_{i_{1}} - F] \\ + \frac{1}{x^{2}} \cdot \sum_{F_{2} \subset E - {e_{i_{1}, i_{2}}}} {(- x)}^{- | F_{2} |} f [(G_{1} \lor_{2} G_{2}) - {e_{i_{1}, i_{2}}} - F] \\ = y h [(G_{1} \lor_{2} G_{2}) / {e_{i_{1}, i_{2}}}] - \frac{C_{2}^{1}}{x} h [((G_{1} \lor_{2} G_{2}) - e_{i_{2}}) / e_{i_{1}}] + \frac{1}{x^{2}} h [(G_{1} \lor_{2} G_{2}) - {e_{i_{1}, i_{2}}}] \\ = (y - \frac{C_{2}^{1}}{x}) h [(G_{1} \lor_{2} G_{2}) / {e_{i_{1}, i_{2}}}] + \frac{1}{x^{2}} h [(G_{1} \lor_{2} G_{2}) - {e_{i_{1}, i_{2}}}] . \end{array}$

3) 若F中只含3条边 $e_{i_{1}, i_{2}, i_{3}}$ ，共有 $C_{n}^{n - 3}$ 种情况，且每一种情况的计算结果是相同的。

$\begin{array}{l} h (G_{1} \lor_{3} G_{2}) \\ = {\sum_{e_{i_{1}, i_{2}, i_{3}} \notin F \subset E} (- x)}^{- | F |} f [(G_{1} \lor_{3} G_{2}) - F] + C_{3}^{2} \cdot \sum_{\begin{array}{l} e_{i_{1}, i_{2}} \notin F \subset E \\ e_{i_{3}} \in F \subset E \end{array}} {(- x)}^{- | F |} f [(G_{1} \lor_{3} G_{2}) - F] \\ + C_{3}^{1} \cdot {\sum_{\begin{array}{l} e_{i_{1}} \notin F \subset E \\ e_{i_{2}, i_{3}} \in F \subset E \end{array}} (- x)}^{- | F |} f [(G_{1} \lor_{3} G_{2}) - F] + \sum_{e_{i_{1}, i_{2}, i_{3}} \in F \subset E} {(- x)}^{- | F |} f [(G_{1} \lor_{3} G_{2}) - F] \\ = y^{2} h [(G_{1} \lor_{3} G_{2}) / {e_{i_{1}, i_{2}, i_{3}}}] - \frac{C_{3}^{2} \cdot y}{x} h [((G_{1} \lor_{3} G_{2}) - e_{i_{3}}) / {e_{i_{1}, i_{2}}}] \\ + \frac{C_{3}^{1}}{x^{2}} h [((G_{1} \lor_{3} G_{2}) - {e_{i_{2}, i_{3}}}) / e_{i_{1}}] - \frac{1}{x^{3}} h [(G_{1} \lor_{3} G_{2}) - {e_{i_{1}, i_{2}, i_{3}}}] \\ = (y^{2} - \frac{C_{3}^{2} \cdot y}{x} + \frac{C_{3}^{1}}{x^{2}}) h [(G_{1} \lor_{3} G_{2}) / {e_{i_{1}, i_{2}, i_{3}}}] - \frac{1}{x^{3}} h [(G_{1} \lor_{3} G_{2}) - {e_{i_{1}, i_{2}, i_{3}}}] . \end{array}$

4) 若F中只含k条边 $e_{i_{1}, \dots, i_{k}}$ ，共有 $C_{n}^{n - k}$ 种情况，且每一种情况的计算结果是相同的。

$\begin{array}{l} h (G_{1} \lor_{k} G_{2}) \\ = {\sum_{e_{i_{1}, \dots, i_{k}} \notin F \subset E} (- x)}^{- | F |} f [(G_{1} \lor_{k} G_{2}) - F] + C_{k}^{k - 1} \cdot {\sum_{\begin{array}{l} e_{i_{2}, \dots, i_{k}} \notin F \subset E \\ e_{i_{1}} \in F \subset E \end{array}} (- x)}^{- | F |} f [(G_{1} \lor_{k} G_{2}) - F] \\ + \dots + C_{k}^{1} \cdot \sum_{\begin{array}{l} e_{i_{k}} \notin F \subset E \\ e_{i_{1}, \dots, i_{k - 1}} \in F \subset E \end{array}} {(- x)}^{- | F |} f [(G_{1} \lor_{k} G_{2}) - F] + {\sum_{e_{i_{1}, \dots, i_{k}} \in F \subset E} (- x)}^{- | F |} f [(G_{1} \lor_{k} G_{2}) - F] \\ = [y^{k - 1} + \frac{C_{k}^{k - 1} y^{k - 2}}{{(- x)}^{1}} + \frac{C_{k}^{k - 2} y^{k - 3}}{{(- x)}^{2}} + \dots + \frac{C_{k}^{1} y^{0}}{{(- x)}^{k - 1}}] h [(G_{1} \lor_{k} G_{2}) / {e_{i_{1}, \dots, i_{k}}}] \\ + \frac{1}{{(- x)}^{k}} h [(G_{1} \lor_{k} G_{2}) - {e_{i_{1}, \dots, i_{k}}}] \\ = \sum_{i = 1}^{k} \frac{C_{k}^{k + 1 - i} \cdot y^{k - i}}{{(- x)}^{i - 1}} h [(G_{1} \lor_{k} G_{2}) / {e_{i_{1}, \dots, i_{k}}}] + \frac{1}{{(- x)}^{k}} h [(G_{1} \lor_{k} G_{2}) - {e_{i_{1}, \dots, i_{k}}}] . \end{array}$

综上所述，对F中所包含n条边 $e_{1}, e_{2}, \dots, e_{n}$ 的情况进行分类，得到多重边图的2-洛朗多项式为：

定义3.3 [4] $θ_{n}$ 表示由两个顶点和n条连接这两个顶点的边组成的图，也被称为“s-theta图”，如图5所示。

Figure 5. $θ_{n}$

图5. $θ_{n}$

推论3.1 $θ_{n}$ 图的2-洛朗多项式的计算公式为：

$h (θ_{n}) = \sum_{i = 1}^{n} \frac{C_{n}^{n + 1 - i} \cdot x y^{n - i}}{{(- x)}^{i - 1}} + \frac{x^{2}}{{(- x)}^{n}} .$

证明由 $θ_{n}$ 图的定义可知， $θ_{n}$ 图是 $G_{1} \lor_{n} G_{2}$ 图的一种特殊情况，当图 $G_{1}$ 和 $G_{2}$ 分别是两个点时 $G_{1} \lor_{n} G_{2} = θ_{n}$ ，所以由定理1和命题1，命题2可得：

$\begin{matrix} h (θ_{n}) = h (G_{1} \lor_{n} G_{2}) \\ = [\sum_{i = 1}^{n} \frac{C_{n}^{n + 1 - i} \cdot y^{n - i}}{{(- x)}^{i - 1}}] \cdot h [(G_{1} \lor_{n} G_{2}) / {e_{1, \dots, n}}] \\ + \frac{1}{{(- x)}^{n}} \cdot h [(G_{1} \lor_{n} G_{n}) - {e_{1, \dots, n}}] \\ = [\sum_{i = 1}^{n} \frac{C_{n}^{n + 1 - i} \cdot y^{n - i}}{{(- x)}^{i - 1}}] \cdot h (•) + \frac{1}{{(- x)}^{n}} \cdot h (• •) \\ = \sum_{i = 1}^{n} \frac{C_{n}^{n + 1 - i} \cdot x y^{n - i}}{{(- x)}^{i - 1}} + \frac{x^{2}}{{(- x)}^{n}} . \end{matrix}$

参考文献

参考文献

[1]	Negami, S. (1987) Polynomial Invariants of Graphs. Transactions of the American Mathematical Society, 299, 601-622. https://doi.org/10.1090/S0002-9947-1987-0869224-1
[2]	姜伯驹. 绳圈的数学[M]. 大连: 大连理工大学出版社, 2011: 53-69.
[3]	Yamada, S. (1989) An Invariant of Spatial Graphs. Journal of Graph Theory, 13, 537-551. https://doi.org/10.1002/jgt.3190130503
[4]	Li, M., Lei, F., Li, F. and Vesnin, A. (2018) The Yamada Polynomial of Spatial Graphs Obtained by Edge Replacements. Journal of Knot Theory and Its Ramifications, 27, Article ID: 1842004. https://doi.org/10.1142/S021821651842004X

为你推荐

友情链接