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.

Keywords:2-Laurent Polynomial, Invariant, Multiple Edges

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

庚东雨

辽宁师范大学，辽宁 大连

收稿日期：2020年7月31日；录用日期：2020年8月18日；发布日期：2020年8月26日

摘 要

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

关键词 :2-洛朗多项式，不变量，多重边

Copyright © 2020 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

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

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

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

2. 预备知识

2.1. 图的基本概念

定义2.1 [1] 图G是指一个有序三元组 $\left(V\left(G\right),E\left(G\right),\psi \left(G\right)\right)$，其中 $V\left(G\right)$ 是图G的顶点集， $E\left(G\right)$ 是图G的边集且 $E\left(G\right)\cap V\left(G\right)=\varphi$，${\psi }_G$ 是关联函数，它将G的每条边对应于G的无序顶点对(可以是相同顶点)。若边e和两个顶点u和v满足 ${\psi }_G\left(e\right)=uv$，则称边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所示。

图1. R变换

3. 2-洛朗多项式

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

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

$h\left(G\right)=h\left(G\right)\left(x,y\right)={\displaystyle \underset{F\subset E}{\sum }{\left(-x\right)}^{-\left|F\right|}f}\left(G-F\right)$。

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

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

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

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

$\begin{array}{c}h\left(G\right)={{\displaystyle \underset{e\notin F\subset E}{\sum }\left(-x\right)}}^{-\left|F\right|}f\left(G-F\right)+{{\displaystyle \underset{e\in F\subset E}{\sum }\left(-x\right)}}^{-\left|F\right|}f\left(G-F\right)\\ ={{\displaystyle \underset{F\subset E-e}{\sum }\left(-x\right)}}^{-\left|F\right|}f\left(G/e-F\right)-1/x\cdot {{\displaystyle \underset{F^{\prime }\subset E-e}{\sum }\left(-x\right)}}^{-\left|F^{\prime }\right|}f\left(G-e-F\right)\\ =h\left(G/e\right)-\frac{1}{x}h\left(G-e\right).\end{array}$

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

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

$\begin{array}{c}h\left(G\right)={{\displaystyle \underset{e\notin F\subset E}{\sum }\left(-x\right)}}^{-\left|F\right|}f\left(G-F\right)+{{\displaystyle \underset{e\in F\subset E}{\sum }\left(-x\right)}}^{-\left|F\right|}f\left(G-F\right)\\ =y{{\displaystyle \underset{F\subset E-e}{\sum }\left(-x\right)}}^{-\left|F\right|}f\left(G/e-F\right)-1/x\cdot {{\displaystyle \underset{F^{\prime }\subset E-e}{\sum }\left(-x\right)}}^{-\left|F^{\prime }\right|}f\left(G-e-F\right)\\ =yh\left(G/e\right)-\frac{1}{x}h\left(G-e\right)\\ =\left(y-\frac{1}{x}\right)h\left(G-e\right).\end{array}$

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

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

性质3.1 [3] $h\left(G_1\cup G_2\right)=h\left(G_1\right)h\left(G_2\right)$。

证明 令 $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$。

因为 $\mu \left(G_1\cup G_2\right)=\mu \left(G_1\right)+\mu \left(G_2\right)$，$\beta \left(G_1\cup G_2\right)=\beta \left(G_1\right)+\beta \left(G_2\right)$。

$\begin{array}{c}h\left(G_1\right)h\left(G_2\right)={\displaystyle \underset{F_1\subset E_1\subset E}{\sum }{\left(-x\right)}^{-\left|F_1\right|}}f\left(G_1-F_1\right)\cdot {\displaystyle \underset{F_2\subset E_2\subset E}{\sum }{\left(-x\right)}^{-\left|F_2\right|}}f\left(G_2-F_2\right)\\ ={{\displaystyle \underset{F_1,F_2\subset E}{\sum }\left(-x\right)}}^{-\left|F_1\right|-\left|F_2\right|}\cdot x^{\mu \left(G_1-F_1\right)+\mu \left(G_2-F_2\right)}{y}^{\beta \left(G_1-F_1\right)+\beta \left(G_2-F_2\right)}\\ ={\displaystyle \underset{F_1,F_2\subset E}{\sum }{\left(-x\right)}^{-\left|F_1\right|-\left|F_2\right|}f\left(V,G_1-F_1\cup G_2-F_2\right)}\\ =h\left(G_1\cup G_2\right).\end{array}$

性质3.2 [3] $h\left(G_1\vee G_2\right)=\frac{1}{x}h\left(G_1\right)h\left(G_2\right)$。

证明 令 $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{array}{c}h\left(G_1\vee G_2\right)={{\displaystyle \underset{F\subset E}{\sum }\left(-x\right)}}^{-\left|F\right|}f\left(G_1\vee G_2-F\right)\\ ={{\displaystyle \underset{F_1\subset E_1}{\sum }\left(-x\right)}}^{-\left|F_1\right|}\cdot {{\displaystyle \underset{F_2\subset E_2}{\sum }\left(-x\right)}}^{-\left|F_2\right|}\cdot \frac{1}{x}f\left(G_1-F_1\right)f\left(G_2-F_2\right)\\ =\frac{1}{x}h\left(G_1\right)h\left(G_2\right).\end{array}$

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

证明 设e是G的割边，则 $G-e=G_1\cup G_2$，$G/e=G_1\vee G_2$。由命题3.1，性质3.1和性质3.2可得

$\begin{array}{c}h\left(G\right)=h\left(G/e\right)-\frac{1}{x}h\left(G-e\right)\\ =h\left(G_1\vee G_2\right)-\frac{1}{x}h\left(G_1\cup G_2\right)\\ =\frac{1}{x}h\left(G_1\right)h\left(G_2\right)-\frac{1}{x}h\left(G_1\right)h\left(G_2\right)\\ =0.\end{array}$

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

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

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

命题3.4 $h\left(••\right)=x^2$。

证明 由性质3.1， $h\left(G_1\cup G_2\right)=h\left(G_1\right)h\left(G_2\right)$，可得 $h\left(••\right)=h(•)h(•)=x\cdot x=x^2$。

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

注解3.2 其中 $\left(G_1{\vee }_n{G}_2\right)/\left\{e_{\text{1,}\cdots ,n}\right\}$ 表示图 $G_1{\vee }_n{G}_2$ 把边 $e_1\cdots e_n$ 去掉同时将 $V_1$ 和 $V_{\text{2}}$ 两个顶点粘结在一起， $\left(G_1{\vee }_n{G}_2\right)-\left\{e_{\text{1,}\cdots ,n}\right\}$ 表示图 $G_1{\vee }_n{G}_2$ 中去掉边 $e_1\cdots e_n$。

并有以下等式成立

$\begin{array}{l}\left(\left(G_1{\vee }_n{G}_2\right)-e_1\right)/\left\{e_{\text{2,}\cdots ,n}\right\}=\left(\left(G_1{\vee }_n{G}_2\right)-\left\{e_{1,2}\right\}\right)/\left\{e_{3,\cdots ,n}\right\}\\ =\cdots =\left(\left(G_1{\vee }_n{G}_2\right)-\left\{e_{1,\cdots ,n-1}\right\}\right)/e_n=\left(G_1{\vee }_n{G}_2\right)/\left\{e_{1,\cdots ,n}\right\}.\end{array}$

图2. $G_1{\vee }_n{G}_2$

定理3.1

$h\left(G_1{\vee }_n{G}_2\right)={\displaystyle \underset{i=1}{\overset{n}{\sum }}\frac{C_n^{n+1-i}\cdot y^{n-i}}{{\left(-x\right)}^{i-1}}}h\left[\left(G_1{\vee }_n{G}_2\right)/\left\{e_{\text{1,}\cdots ,n}\right\}\right]+\frac{1}{{\left(-x\right)}^n}h\left[\left(G_1{\vee }_n{G}_2\right)-\left\{e_{\text{1,}\cdots ,n}\right\}\right].$

证明 设F和 $F_n$ 是E的子集，E是 $G_1{\vee }_n{G}_2$ 的边集 $\left|F\right|$ 是F包含元素的数目，则 $\left|F\right|=\left|F_n\right|+n$。由2-洛朗多项式的定义 $h\left(G\right)=h\left(G\right)\left(x,y\right)={{\displaystyle \underset{F\subset E}{\sum }\left(-x\right)}}^{-\left|F\right|}f\left(G-F\right)$，对F中所包含n条边 $e_1,e_2,\cdots ,e_n$ 的情况进行分类：

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

图3. $G_1{\vee }_{\text{1}}{G}_2$

由割边的定义可知 $e_i$ 是图 $G_{\text{1}}{\vee }_1{G}_2$ 的割边，则 $h\left(G_1{\vee }_1{G}_2\right)=\text{0}$。

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

图4. $G_1{\vee }_{\text{2}}{G}_2$

$\begin{array}{l}h\left(G_1{\vee }_2{G}_2\right)\\ ={{\displaystyle \underset{e_{i_1,i_2}\notin F\subset E}{\sum }\left(-x\right)}}^{-\left|F\right|}f\left[\left(G_1{\vee }_2{G}_2\right)-F\right]+C_2^1\cdot {{\displaystyle \underset{\begin{array}{l}{e}_{i_1}\notin F\subset E\\ e_{i_2}\in F\subset E\end{array}}{\sum }\left(-x\right)}}^{-\left|F\right|}f\left[\left(G_1{\vee }_2{G}_2\right)-F\right]\\ +{\displaystyle \underset{e_{i_1,i_2}\in F\subset E}{\sum }{\left(-x\right)}^{-\left|F\right|}}f\left[\left(G_1{\vee }_2{G}_2\right)-F\right]\\ =y\cdot {{\displaystyle \underset{F\subset E-\left\{e_{i_1,i_2}\right\}}{\sum }\left(-x\right)}}^{-\left|F\right|}f\left[\left(G_1{\vee }_2{G}_2\right)/\left\{e_{i_1,i_2}\right\}-F\right]-\frac{C_2^1}{x}\cdot {{\displaystyle \underset{F_1\subset E-\left\{e_1,i_2\right\}}{\sum }\left(-x\right)}}^{-\left|F_1\right|}f\left[\left(\left(G_1{\vee }_2{G}_2\right)-e_{i_2}\right)/e_{i_1}-F\right]\\ +\frac{1}{x^2}\cdot {\displaystyle \underset{F_2\subset E-\left\{e_{i_1,i_2}\right\}}{\sum }{\left(-x\right)}^{-\left|F_2\right|}}f\left[\left(G_1{\vee }_2{G}_2\right)-\left\{e_{i_1,i_2}\right\}-F\right]\\ =yh\left[\left(G_1{\vee }_2{G}_2\right)/\left\{e_{i_1,i_2}\right\}\right]-\frac{C_2^1}{x}h\left[\left(\left(G_1{\vee }_2{G}_2\right)-e_{i_2}\right)/e_{i_1}\right]+\frac{1}{x^2}h\left[\left(G_1{\vee }_2{G}_2\right)-\left\{e_{i_1,i_2}\right\}\right]\\ =\left(y-\frac{C_2^1}{x}\right)h\left[\left(G_1{\vee }_2{G}_2\right)/\left\{e_{i_1,i_2}\right\}\right]+\frac{1}{x^2}h\left[\left(G_1{\vee }_2{G}_2\right)-\left\{e_{i_1,i_2}\right\}\right].\end{array}$

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

$\begin{array}{l}h\left(G_1{\vee }_3{G}_2\right)\\ ={{\displaystyle \underset{e_{i_1,i_2,i_3}\notin F\subset E}{\sum }\left(-x\right)}}^{-\left|F\right|}f\left[\left(G_1{\vee }_3{G}_2\right)-F\right]+C_3^2\cdot {\displaystyle \underset{\begin{array}{l}{e}_{i_1,i_2}\notin F\subset E\\ e_{i_3}\in F\subset E\end{array}}{\sum }{\left(-x\right)}^{-\left|F\right|}}f\left[\left(G_1{\vee }_3{G}_2\right)-F\right]\\ +C_3^1\cdot {{\displaystyle \underset{\begin{array}{l}{e}_{i_1}\notin F\subset E\\ e_{i_2,i_3}\in F\subset E\end{array}}{\sum }\left(-x\right)}}^{-\left|F\right|}f\left[\left(G_1{\vee }_3{G}_2\right)-F\right]+{\displaystyle \underset{e_{i_1,i_2,i_3}\in F\subset E}{\sum }{\left(-x\right)}^{-\left|F\right|}}f\left[\left(G_1{\vee }_3{G}_2\right)-F\right]\\ =y^{2}h\left[\left(G_1{\vee }_3{G}_2\right)/\left\{e_{i_1,i_2,i_3}\right\}\right]-\frac{C_3^2\cdot y}{x}h\left[\left(\left(G_1{\vee }_3{G}_2\right)-e_{i_3}\right)/\left\{e_{i_1,i_2}\right\}\right]\\ +\frac{C_3^1}{x^2}h\left[\left(\left(G_1{\vee }_3{G}_2\right)-\left\{e_{i_2,i_3}\right\}\right)/e_{i_1}\right]-\frac{1}{x^3}h\left[\left(G_1{\vee }_3{G}_2\right)-\left\{e_{i_1,i_2,i_3}\right\}\right]\\ =\left(y^2-\frac{C_3^2\cdot y}{x}+\frac{C_3^1}{x^2}\right)h\left[\left(G_1{\vee }_3{G}_2\right)/\left\{e_{i_1,i_2,i_3}\right\}\right]-\frac{1}{x^3}h\left[\left(G_1{\vee }_3{G}_2\right)-\left\{e_{i_1,i_2,i_3}\right\}\right].\end{array}$

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

$\begin{array}{l}h\left(G_1{\vee }_k{G}_2\right)\\ ={{\displaystyle \underset{e_{i_1,\cdots ,i_k}\notin F\subset E}{\sum }\left(-x\right)}}^{-\left|F\right|}f\left[\left(G_1{\vee }_k{G}_2\right)-F\right]+C_k^{k-1}\cdot {{\displaystyle \underset{\begin{array}{l}{e}_{i_2,\cdots ,i_k}\notin F\subset E\\ e_{i_1}\in F\subset E\end{array}}{\sum }\left(-x\right)}}^{-\left|F\right|}f\left[\left(G_1{\vee }_k{G}_2\right)-F\right]\\ +\cdots +C_k^1\cdot {\displaystyle \underset{\begin{array}{l}{e}_{i_k}\notin F\subset E\\ e_{i_1,\cdots ,i_{k-1}}\in F\subset E\end{array}}{\sum }{\left(-x\right)}^{-\left|F\right|}}f\left[\left(G_1{\vee }_k{G}_2\right)-F\right]+{{\displaystyle \underset{e_{i_1,\cdots ,i_k}\in F\subset E}{\sum }\left(-x\right)}}^{-\left|F\right|}f\left[\left(G_1{\vee }_k{G}_2\right)-F\right]\\ =\left[y^{k-1}+\frac{C_k^{k-1}{y}^{k-2}}{{\left(-x\right)}^1}+\frac{C_k^{k-2}{y}^{k-3}}{{\left(-x\right)}^2}+\cdots +\frac{C_k^1{y}^0}{{\left(-x\right)}^{k-1}}\right]h\left[\left(G_1{\vee }_k{G}_2\right)/\left\{e_{i_1,\cdots ,i_k}\right\}\right]\\ +\frac{1}{{\left(-x\right)}^k}h\left[\left(G_1{\vee }_k{G}_2\right)-\left\{e_{i_1,\cdots ,i_k}\right\}\right]\\ ={\displaystyle \underset{i=1}{\overset{k}{\sum }}\frac{C_k^{k+1-i}\cdot y^{k-i}}{{\left(-x\right)}^{i-1}}h}\left[\left(G_1{\vee }_k{G}_2\right)/\left\{e_{i_1,\cdots ,i_k}\right\}\right]+\frac{1}{{\left(-x\right)}^k}h\left[\left(G_1{\vee }_k{G}_2\right)-\left\{e_{i_1,\cdots ,i_k}\right\}\right].\end{array}$

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

$h\left(G_1{\vee }_n{G}_2\right)={\displaystyle \underset{i=1}{\overset{n}{\sum }}\frac{C_n^{n+1-i}\cdot y^{n-i}}{{\left(-x\right)}^{i-1}}h}\left[\left(G_1{\vee }_n{G}_2\right)/\left\{e_{1,\cdots ,n}\right\}\right]+\frac{1}{{\left(-x\right)}^n}h\left[\left(G_1{\vee }_n{G}_2\right)-\left\{e_{1,\cdots ,n}\right\}\right].$

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

图5. ${\theta }_n$

推论3.1 ${\theta }_n$ 图的2-洛朗多项式的计算公式为：

$h\left({\theta }_n\right)={\displaystyle \underset{i=1}{\overset{n}{\sum }}\frac{C_n^{n+1-i}\cdot x{y}^{n-i}}{{\left(-x\right)}^{i-1}}}+\frac{x^2}{{\left(-x\right)}^n}.$

证明 由 ${\theta }_n$ 图的定义可知， ${\theta }_n$ 图是 $G_1{\vee }_n{G}_2$ 图的一种特殊情况，当图 $G_1$ 和 $G_2$ 分别是两个点时 $G_1{\vee }_n{G}_2={\theta }_n$，所以由定理1和命题1，命题2可得：

$\begin{array}{c}h\left({\theta }_n\right)=h\left(G_1{\vee }_n{G}_2\right)\\ =\left[{\displaystyle \underset{i=1}{\overset{n}{\sum }}\frac{C_n^{n+1-i}\cdot y^{n-i}}{{\left(-x\right)}^{i-1}}}\right]\cdot h\left[\left(G_1{\vee }_n{G}_2\right)/\left\{e_{1,\cdots ,n}\right\}\right]\\ +\frac{1}{{\left(-x\right)}^n}\cdot h\left[\left(G_1{\vee }_n{G}_n\right)-\left\{e_{1,\cdots ,n}\right\}\right]\\ =\left[{\displaystyle \underset{i=1}{\overset{n}{\sum }}\frac{C_n^{n+1-i}\cdot y^{n-i}}{{\left(-x\right)}^{i-1}}}\right]\cdot h(•)+\frac{\text{1}}{{\left(-x\right)}^n}\cdot h\left(••\right)\\ ={\displaystyle \underset{i=1}{\overset{n}{\sum }}\frac{C_n^{n+1-i}\cdot x{y}^{n-i}}{{\left(-x\right)}^{i-1}}}+\frac{x^2}{{\left(-x\right)}^n}.\end{array}$

文章引用

庚东雨. 多重边图的2-洛朗多项式
2-Laurent Polynomials of Multi-Edge Graphs[J]. 理论数学, 2020, 10(08): 764-770. https://doi.org/10.12677/PM.2020.108089

参考文献